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 108 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.