The Binary BrothersTwo Mentors, One Mission – Your Selection
All mock tests are FREE till 31 December — register to save your progress
Unit 8 · Theory of Computation and Compilers

Match List – I with List – II.
List – I (Propositions)
(A) P ∧ (P → Q)
(B) ¬(P ∨ Q) → (P ∧ Q)
(C) P → Q
(D) P ∨ (Q ∧ R)
List – II (Disjunctive Normal Form)
(I) P ∨ Q
(II) (P ∧ ¬P) ∨ (P ∧ Q)
(III) (¬P) ∨ Q
(IV) (P ∧ P) ∨ (P ∧ Q) ∨ (P ∧ R) ∨ (Q ∧ R)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. (A)-(II), (B)-(I), (C)-(III), (D)-(IV)

Explanation

Replace every implication by X → Y ≡ ¬X ∨ Y and distribute. (A) P ∧ (P → Q) = P ∧ (¬P ∨ Q) = (P ∧ ¬P) ∨ (P ∧ Q), which is (II). (B) ¬(P ∨ Q) → (P ∧ Q) = ¬(¬P ∧ ¬Q) ∨ (P ∧ Q) = (P ∨ Q) ∨ (P ∧ Q) = P ∨ Q by absorption, which is (I). (C) P → Q is directly ¬P ∨ Q, i.e. (III), and (D) P ∨ (Q ∧ R) equals (IV) because (P ∧ P) ∨ (P ∧ Q) ∨ (P ∧ R) ∨ (Q ∧ R) = P ∨ (Q ∧ R) after absorption. So the match is (A)-(II), (B)-(I), (C)-(III), (D)-(IV).

More Theory of Computation and Compilers questions