Let P, Q, and R be three atomic propositional assertions. Let X denote (P => Q) => R and Y denote P => (Q => R). Which one of the following is a tautology? A. X <=> Y B. X => Y C. Y => X D. ~Y => X

GATE 2005 · Discrete Mathematics · Propositional Logic · medium

Answer: B. X => Y is the tautology.

1. Compute X and Y for critical rows: Row P=T,Q=T,R=F: X=(T=>T)=>F=T=>F=F; Y=T=>(T=>F)=T=>F=F. Both false. Row P=T,Q=F,R=F: X=(T=>F)=>F=F=>F=T; Y=T=>(F=>F)=T=>T=T. Both true. Row P=F,Q=T,R=F: X=(F=>T)=>F=T=>F=F; Y=F=>(T=>F)=F=>F=T. X=F,Y=T. Row P=F,Q=F,R=F: X=(F=>F)=>F=T=>F=F; Y=F=>(F=>F)=F=>T=T. X=F,Y=T.
2. Check option B: is X => Y always true?: From the table: X=T rows are (P=T,Q=F,R=F), (P=T,Q=F,R=T), (P=T,Q=T,R=T), (P=F,Q=F,R=T), (P=F,Q=T,R=T). In each of these, Y=T as well. So X=>Y is True in every row — it is a tautology.
3. Confirm Y => X is NOT a tautology (eliminating C): Row P=F,Q=T,R=F: Y=T (as computed), X=F. So Y=>X = T=>F = F. This is a counterexample, so Y=>X is not a tautology. Similarly X<=>Y fails here. Option B (X=>Y) is the only tautology.