Quiz. Normal Forms & DPLL - Equivalence [000d]

  • November 22, 2025
Which of the following equivalences hold?
  1. \(\bot \equiv \bot \)
  2. \(\top \equiv \top \)
  3. \(\neg \top \equiv \neg \bot \)
  4. \(\neg (p \land q) \equiv \neg p \lor \neg q\)
  5. \(p \equiv p \lor q\)
  6. \(\neg \neg p \equiv p\)

Solution. 

  • November 22, 2025
  1. True. Both sides are always false.
  2. True. Both sides are always true.
  3. False. Left side is always false, right side is always true.
  4. True. This is De Morgan's law. Good to remember \[ \neg (p \land q) \equiv \neg p \lor \neg q \]
  5. False. Left side is true when p is true, right side is true when either p or q is true.
  6. True. Double negation elimination.