Let p, q and r be propositions and the expression (p -> q) -> r be a contradiction. Then, the expression (r -> p) -> q is A. a tautology B. a contradiction C. always TRUE when p is FALSE D. always TRUE when q is TRUE

GATE 2017 · Discrete Mathematics · Propositional Logic · medium

Answer: The expression (r -> p) -> q reduces to q, so it is always TRUE when q is TRUE (option D).

1. Extract r = false from the contradiction: (p -> q) -> r being a contradiction means it is false in every world. An implication is false only when its antecedent is true and its consequent false, so for ALL worlds we must have (p -> q) = true and r = false. In particular r is false.
2. Substitute r = false into the target: With r = false, the inner implication r -> p = false -> p = true (vacuously). So (r -> p) -> q = true -> q.
3. Reduce true -> q to q: true -> q simplifies to q. Hence (r -> p) -> q equals q under the hypothesis. So the expression is neither a tautology nor a contradiction; it is true exactly when q is true and false when q is false. That is option D.