Which one of the following Boolean expressions is NOT a tautology?
2014
Which one of the following Boolean expressions is NOT a tautology?
- A.
\(((\,a\,\to\,b\,)\,\wedge\,(\,b\,\to\,c))\,\to\,(\,a\,\to\,c)\) - B.
\((\,a\,\to\,c\,)\,\to\,(\,\sim b\,\to\,(a\,\wedge\,c))\) - C.
\((\,a\,\wedge\,b\,\wedge\,c)\,\to\,(\,c\vee\,a)\) - D.
\(a\,\to\,(b\,\to\,a)\)
Attempted by 143 students.
Show answer & explanation
Correct answer: B
Answer: (a -> c) -> (~b -> (a ∧ c)) is not a tautology.
Counterexample showing it is not always true:
Choose a = false, b = false, c = false.
Evaluate the antecedent (a -> c): false -> false is true.
Evaluate the consequent (~b -> (a ∧ c)): ~b is true, a ∧ c is false, so true -> false is false.
Thus the overall implication true -> false is false, so the formula is not a tautology.
Brief justification that the other three expressions are tautologies:
((a -> b) ∧ (b -> c)) -> (a -> c): If a is true then a -> b gives b true and b -> c gives c true, so a -> c holds; if a is false then a -> c is true. Therefore always true.
(a ∧ b ∧ c) -> (c ∨ a): The antecedent makes both a and c true, so the disjunction c ∨ a is true; if antecedent is false the implication is true. Hence always true.
a -> (b -> a): If a is true then b -> a is true no matter b; if a is false the outer implication is true. So it holds for all valuations.
A video solution is available for this question — log in and enroll to watch it.