The first order logic (FOL) statement ((𝑅 ∨ 𝑄) ∧ (𝑃 ∨ ¬𝑄)) is equivalent…
2017
The first order logic (FOL) statement ((𝑅 ∨ 𝑄) ∧ (𝑃 ∨ ¬𝑄)) is equivalent to which of the following?
- A.
\(((R\vee \neg Q)\wedge(P\vee \neg Q)\wedge (R\vee P))\) - B.
\(((R\vee Q)\wedge(P\vee \neg Q)\wedge (R\vee P))\) - C.
\(((R\vee Q)\wedge(P\vee \neg Q)\wedge(R\vee \neg P))\) - D.
\(((R\vee Q)\wedge(P\vee \neg Q)\wedge (\neg R\vee P))\)
Attempted by 76 students.
Show answer & explanation
Correct answer: B
Key idea: use resolution to derive any clause entailed by the conjunction.
Start with the original formula: (R ∨ Q) ∧ (P ∨ ¬Q).
Resolve the two clauses on Q: from (R ∨ Q) and (P ∨ ¬Q) we obtain (R ∨ P).
Because (R ∨ P) is logically entailed by (R ∨ Q) ∧ (P ∨ ¬Q), conjoining (R ∨ P) does not change the set of models.
Therefore the formula is equivalent to (R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P).
Why the other candidate formulas fail:
A formula that replaces (R ∨ Q) with (R ∨ ¬Q) changes the meaning. For example, R = false, Q = true, P = true makes the original true but the modified clause false.
A formula that adds (R ∨ ¬P) is not equivalent because (R ∨ ¬P) is not entailed. For instance, R = false, Q = true, P = true satisfies the original but falsifies (R ∨ ¬P).
A formula that adds (¬R ∨ P) is not equivalent either; e.g. R = true, Q = false, P = false makes the original true while (¬R ∨ P) is false.
A video solution is available for this question — log in and enroll to watch it.