Let x and y be two propositions. Which of the following statements is a tautology / are tautologies? A. (not x and y) => (y => x) B. (x and not y) => (not x => y) C. (not x and y) => (not x => y) D. (x and not y) => (y => x)

GATE 2024 · Discrete Mathematics · Propositional Logic · medium

Answer: B, C and D are tautologies; A is falsified at x=False, y=True, so the answer is B, C, D.

1. Option A fails on its forcing row: not x and y is True only at x=False, y=True. There the consequent y => x = True => False = False, so A = True => False = False. A is not a tautology.
2. Option B is a tautology: x and not y is True only at x=True, y=False. There not x => y = False => False = True, so the consequent holds; on all other rows the antecedent is False (vacuously True). B is a tautology.
3. Option C is a tautology: not x and y is True only at x=False, y=True. There not x => y = True => True = True, so the consequent holds; all other rows are vacuously True. C is a tautology.
4. Option D is a tautology: x and not y is True only at x=True, y=False. There y => x = False => True = True, so the consequent holds; all other rows are vacuously True. D is a tautology.