Consider the following propositional statements: P1 : ((A ∧ B) → C)) ≡ ((A →…
2006
Consider the following propositional statements: P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C)) P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C)) Which one of the following is true?
- A.
P1 is a tautology, but not P2
- B.
P2 is a tautology, but not P1
- C.
P1 and P2 are both tautologies
- D.
Both P1 and P2 are not tautologies
Attempted by 81 students.
Show answer & explanation
Correct answer: D
Answer: Both P1 and P2 are not tautologies.
Explanation for the first equivalence:
Rewrite the left side: ((A ∧ B) → C) is equivalent to ¬(A ∧ B) ∨ C, i.e. ¬A ∨ ¬B ∨ C.
Rewrite the right side: (A → C) ∧ (B → C) is (¬A ∨ C) ∧ (¬B ∨ C), which simplifies to (¬A ∧ ¬B) ∨ C.
These two formulas differ: ¬A ∨ ¬B ∨ C versus (¬A ∧ ¬B) ∨ C. Concrete counterexample: A = true, B = false, C = false gives the left formula true and the right formula false, so the equivalence fails.
Explanation for the second equivalence:
Rewrite the left side: ((A ∨ B) → C) is ¬(A ∨ B) ∨ C, i.e. (¬A ∧ ¬B) ∨ C.
Rewrite the right side: (A → C) ∨ (B → C) is (¬A ∨ C) ∨ (¬B ∨ C), which simplifies to ¬A ∨ ¬B ∨ C.
These two formulas differ: (¬A ∧ ¬B) ∨ C versus ¬A ∨ ¬B ∨ C. The same counterexample A = true, B = false, C = false makes the left false and the right true, so the equivalence fails.
Conclusion: Neither equivalence holds for all truth assignments, so both P1 and P2 are not tautologies.
A video solution is available for this question — log in and enroll to watch it.