Sets, Relations & Functions
Logic and Truth Tables
Grade 11
Question:
<p>Determine which of the following is NOT a tautology:</p><p>(a) <strong>(p ∨ q) ∨ (p ∨ (¬q))</strong></p><p>(b) <strong>(p ∧ q) ∨ (p ∧ (¬q))</strong></p><p>(c) <strong>(p ∨ q) ∧ (p ∨ (¬q))</strong></p><p>(d) <strong>(p ∨ q) ∧ ((¬p) ∨ (¬q))</strong></p>
<p>(A) (p ∨ q) ∨ (p ∨ (¬q)) is a tautology</p>
<p>(B) (p ∧ q) ∨ (p ∧ (¬q)) is not a tautology</p>
<p>(C) (p ∨ q) ∧ (p ∨ (¬q)) is not a tautology</p>
<p>(D) (p ∨ q) ∧ ((¬p) ∨ (¬q)) is not a tautology</p>
Step-by-Step Solution
Key Concept: Use logical laws to simplify: a disjunction with T is T; a conjunction with F is F. Identify which statement depends on variable values.
<p><strong>Step 1:</strong> Check option (a): <strong>(p ∨ q) ∨ (p ∨ (¬q)) ≡ p ∨ (q ∨ (¬q)) ≡ p ∨ T ≡ T</strong> ✓ Tautology</p><p><strong>Step 2:</strong> Check option (b): <strong>(p ∧ q) ∨ (p ∧ (¬q)) ≡ p ∧ (q ∨ (¬q)) ≡ p ∧ T ≡ p</strong> ✗ Not a tautology (depends on p)</p><p><strong>Step 3:</strong> Check option (c): <strong>(p ∨ q) ∧ (p ∨ (¬q)) ≡ p ∨ (q ∧ (¬q)) ≡ p ∨ F ≡ p</strong> ✗ Not a tautology (depends on p)</p><p><strong>Step 4:</strong> Check option (d): <strong>(p ∨ q) ∧ ((¬p) ∨ (¬q)) ≡ (p ∨ q) ∧ (¬(p ∧ q))</strong> ✗ Not a tautology (false when both p and q are true)</p><p>∴ Options (b), (c), and (d) are not tautologies. The answer depends on which one is being asked for.</p>
Correct Answer: D