Let P, Q and R be three atomic propositional assertions. Let X denote (P ∨ Q)…

2005

Let P, Q and R be three atomic propositional assertions. Let X denote (P ∨ Q) → R and Y denote (P → R) ∨ (Q → R). Which one of the following is a tautology?

  1. A.

    X ≡ Y

  2. B.

    X → Y

  3. C.

    Y → X

  4. D.

    ¬Y → X

Attempted by 12 students.

Show answer & explanation

Correct answer: B

To determine which expression is a tautology, we first simplify the given assertions X and Y using logical equivalences. (X = (P ∨ Q) → R) is equivalent to (¬(P ∨ Q) ∨ R), which simplifies via De Morgan's Law to (¬ P ∧ ¬ Q) ∨ R). Similarly, (Y = (P → R) ∨ (Q → R)) simplifies to

(¬P ∨ R) ∨ (¬Q ∨ R), which reduces to (¬P ∨ ¬Q ∨ R) .Comparing the simplified forms, X requires both P and Q to be false for R not to imply truth, whereas Y is true if either P or Q is false. Thus, whenever X is true (meaning (¬P ∧ ¬Q) or R is true, Y must also be true because

(¬P ∨ ¬Q) is implied by (¬P ∧ ¬ Q). Therefore, X → Y is always true. However, the reverse (Y → X) fails when P is false but Q is true; Y becomes true while X remains false. Hence, only X → Y is a tautology.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir