GATE 2014 CS (CS2) – Question 63

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · Multiple choice

Which Boolean expression is NOT a tautology?

$((a\to b)\land(b\to c))\to(a\to c)$
$(a\leftrightarrow c)\to(\neg b\to(a\land c))$
$(a\land b\land c)\to(c\lor a)$
$a\to(b\to a)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $(a\leftrightarrow c)\to(\neg b\to(a\land c))$

Explanation

For optionB set a=false,c=false,b=false. Then a↔c is true and¬b is true, but a∧c is false, so the nested implication and therefore the whole formula are false. Hence **B** is not a tautology. One counterexample suffices; the other formulas express valid implication principles.