Unit 1 · Discrete Structures and Optimisation Paper 2 CS · June 2024 Re-Exam

Consider the following, where p and q are two statements.
(A) ~(p ∧ q) ≡ ~p ∨ ~q
(B) ~(p ∨ q) ≡ ~p ∧ ~q
(C) p ∧ ~p ≡ T
(D) ~(p ⇒ q) ≡ p ∧ ~q
(E) p ∨ q ≡ ~p ∨ ~q
Which of these equivalences are correct?

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

Show answer & explanation

Correct answer: A. (A), (B) and (D) only

Explanation

A and B are De Morgan's laws, and D holds because p ⇒ q ≡ ~p ∨ q. p ∧ ~p is a contradiction (F), not T, and E is false (take p = q = T).