Sets, Relations & Functions
Mathematical Reasoning / Tautology
Grade None
Question:
<p>Which of the following is NOT a tautology?</p>
<p>\(p \rightarrow (p \vee q)\)</p>
<p>\(p \wedge q \rightarrow p\)</p>
<p>\((p \vee q) \rightarrow (p \wedge (\sim q))\)</p>
<p>\((p \wedge q) \rightarrow p\)</p>
Step-by-Step Solution
Key Concept: A tautology is a logical statement that is true for ALL possible truth value assignments. You must check each option by constructing truth tables or using logical equivalences to find which statement can be false for some assignment.
<p><strong>Step 1:</strong> Recall that a tautology is a formula that evaluates to TRUE for every possible assignment of truth values to its variables.</p><p><strong>Step 2:</strong> For each option, construct a truth table or test with specific truth assignments:</p><p>• <strong>Option A:</strong> p ∨ ¬p (Law of Excluded Middle) → Always TRUE (tautology)</p><p>• <strong>Option B:</strong> (p → q) ≡ (¬p ∨ q) → Always TRUE (tautology by definition of implication)</p><p>• <strong>Option C:</strong> p ∧ q → p ∧ q ∧ r → When p=T, q=T, r=F: LHS is TRUE but RHS is FALSE → NOT a tautology</p><p>• <strong>Option D:</strong> p → (p ∨ q) → Always TRUE (tautology, since p true makes disjunction true)</p><p><strong>Step 3:</strong> Option C fails the truth table test with the assignment p=T, q=T, r=F, making it NOT a tautology.</p><p>∴ Answer: C</p>
Correct Answer: C