Unit 1 · Discrete Structures and Optimisation Paper 2 CS · September 2022

Consider α, β, γ as logical variables. Which of the following are correct logical equivalences?
(A) α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ)
(B) α ∨ β ≡ ¬α ∨ β
(C) (α ⇒ β) ≡ (¬β ⇒ ¬α)
(D) ¬(α ∨ β) ≡ (¬α ⇒ ¬β)
Choose the correct answer from the options given below:

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

Show answer & explanation

Correct answer: C. (A) and (C) only

Explanation

(A) is distributivity and (C) is the contrapositive. (B) fails at α = T, β = F. (D): ¬α ⇒ ¬β ≡ α ∨ ¬β, which is not ¬α ∧ ¬β.