P and Q are two propositions. Which of the following logical expressions are equivalent? I. P <-> ~Q II. ~P <-> Q III. ~(P <-> Q) IV. ~(P v Q) A. Only I and II B. Only I, II and III C. Only I, II and IV D. All of I, II, III and IV

GATE 2008 · Discrete Mathematics · Propositional Logic · medium

Answer: B. Only I, II and III are logically equivalent (they all express P XOR Q).

1. Build the truth table for all four expressions: P=T,Q=T: I=T<->F=F; II=F<->T=F; III=~T=F; IV=~T=F. P=T,Q=F: I=T<->T=T; II=F<->F=T; III=~F=T; IV=~T=F. P=F,Q=T: I=F<->F=T; II=T<->T=T; III=~F=T; IV=~T=F. P=F,Q=F: I=F<->T=F; II=T<->F=F; III=~T=F; IV=~F=T.
2. Compare columns: Columns for I, II, and III are all (F,T,T,F) — they are identical, so I, II, III are mutually equivalent. Column for IV is (F,F,F,T) — different from the others, so IV is NOT equivalent to I, II, or III.