Which of the following is principal conjunctive normal form for \([(𝑝∨𝑞)∧…
2019
Which of the following is principal conjunctive normal form for \([(𝑝∨𝑞)∧ ¬𝑝→¬𝑞] \) ?
- A.
(𝑝 ∨¬𝑞) - B.
(𝑝∨𝑞) - C.
(¬𝑝∨𝑞) - D.
(¬𝑝 ∨¬𝑞)
Attempted by 111 students.
Show answer & explanation
Correct answer: A
Find the CNF of the formula ((p ∨ q) ∧ ¬p) → ¬q. Key steps:
Rewrite the implication as a disjunction: ¬((p ∨ q) ∧ ¬p) ∨ ¬q
Apply De Morgan to ¬((p ∨ q) ∧ ¬p) to get ¬(p ∨ q) ∨ p, so the whole formula becomes ¬(p ∨ q) ∨ p ∨ ¬q
Replace ¬(p ∨ q) by (¬p ∧ ¬q) and simplify: (¬p ∧ ¬q) ∨ p ∨ ¬q. Since ¬q is present, the expression simplifies to p ∨ ¬q.
Conclusion: the formula is equivalent to the single disjunctive clause p ∨ ¬q, which as a CNF is the single clause (p ∨ ¬q).
Optional quick check: with p = false, q = true the original formula is false and p ∨ ¬q is also false, confirming the equivalence in a representative case.