Which of the following is NOT True? (Read ^ as AND, v as OR, ~ as NOT, -> as one way implication and <-> as two way implication) A. ((x -> y) ^ z) -> y B. ((x -> y) ^ (~x -> y)) -> y C. (x v y) -> (~x -> y) D. ((x v y) <-> (~x -> ~y))

GATE 1996 · Discrete Mathematics · Propositional Logic · medium

Answer: D. ((x v y) <-> (~x -> ~y)) is NOT True — it fails at x=False, y=False

1. Test options A, B, C to confirm they are tautologies: A: ((x->y)^z)->y. If z=T and x->y=T, then y must be T; if z=F the antecedent is F so result is T. Verify: z=T, x=T, y=F makes (F^T)=F->F=T. All rows T — A is a tautology. B: ((x->y)^(~x->y))->y. x->y and ~x->y both true means y=T (by cases). Result T — B is a tautology. C: (x v y)->(~x->y). ~x->y is False only when ~x=T and y=F, i.e. x=F, y=F. But then x v y = F making antecedent F, so implication T. — C is tautology.
2. Find a counterexample for option D: Try x=F, y=F: x v y = F v F = F. ~x -> ~y = T -> T = T. D becomes F <-> T = False.