Which one of the following Boolean expressions is NOT a tautology? A. ((a -> b) ^ (b -> c)) -> (a -> c) B. (a -> c) -> (~b -> c) C. (a ^ b ^ c) -> (c v a) D. a -> (b -> a)

GATE 2014 · Discrete Mathematics · Propositional Logic · medium

Answer: Option B: (a -> c) -> (~b -> c) is NOT a tautology, since a=F, b=F, c=F makes it false.

1. Verify options A, C, D are tautologies: Option A is hypothetical syllogism — a classical tautology. Option C: (a^b^c)->(c v a); if the conjunction is true then a is true, so (c v a) is true; if conjunction is false, implication is vacuously true. Tautology. Option D: a->(b->a). If a=T then b->T=T; if a=F then F->anything=T. Tautology.
2. Find a falsifying assignment for option B: Option B: (a->c)->(~b->c). Set a=F, b=F, c=F. Antecedent: (F->F)=T. Consequent: (~F->F)=(T->F)=F. So the formula becomes T->F=F. This assignment makes option B false, so it is NOT a tautology.