Indicate which of the following well-formed formulae are valid: A. (P => Q) and (Q => R) => (P => R) B. (P => Q) => (not P => not Q) C. (P and (not P or not Q)) => Q D. (P => R) or (Q => R) => ((P or Q) => R)

GATE 1990 · Discrete Mathematics · Propositional Logic · medium

Answer: Only A is valid; B, C and D each have a falsifying assignment, so the answer is A.

1. A is the hypothetical-syllogism tautology: Suppose the antecedent (P=>Q) and (Q=>R) holds and P is True. Then Q is True (from P=>Q), then R is True (from Q=>R), so P=>R holds. The implication can never have a True antecedent with a False consequent, so A is valid.
2. B confuses contrapositive with inverse: Take P=False, Q=True. Then P=>Q is True, but not P => not Q is True => False = False. So the whole formula is True => False = False. B is not valid.
3. C simplifies and fails: Since P and not P = False, P and (not P or not Q) = P and not Q. Take P=True, Q=False: antecedent P and not Q = True, consequent Q = False, so the implication is True => False = False. C is not valid.
4. D fails with a single-implier assignment: Take P=True, Q=False, R=False. Then P=>R = False but Q=>R = True, so the antecedent (P=>R) or (Q=>R) = True. The consequent (P or Q)=>R = True => False = False. So D = True => False = False. D is not valid.