GATE CS 1996 Q2.3 — Propositional and First Order Logic

To find which of the given propositional formulas is NOT True (i.e., not a tautology), we can analyze each option using standard logical equivalences.

Option A: $((x \rightarrow y) \wedge x) \rightarrow y$

• Recall that $x \rightarrow y \equiv \neg x \vee y$.
• The antecedent is: $(( \neg x \vee y) \wedge x) \equiv (\neg x \wedge x) \vee (y \wedge x) \equiv \text{False} \vee (x \wedge y) \equiv x \wedge y$.
• The entire formula becomes: $(x \wedge y) \rightarrow y \equiv \neg(x \wedge y) \vee y \equiv \neg x \vee \neg y \vee y \equiv \text{True}$.
• Thus, Option A is a tautology (always True).

Option B: $((\neg x \rightarrow y) \wedge (\neg x \rightarrow \neg y)) \rightarrow x$

• Using the distributive law: $(\neg x \rightarrow y) \wedge (\neg x \rightarrow \neg y) \equiv \neg x \rightarrow (y \wedge \neg y) \equiv \neg x \rightarrow \text{False}$.
• Since $\neg x \rightarrow \text{False} \equiv \neg(\neg x) \vee \text{False} \equiv x$.
• The entire formula simplifies to $x \rightarrow x$, which is always $\text{True}$.
• Thus, Option B is a tautology (always True).

Option C: $x \rightarrow (x \vee y)$

• Using implication equivalence: $\neg x \vee (x \vee y) \equiv (\neg x \vee x) \vee y \equiv \text{True} \vee y \equiv \text{True}$.
• Thus, Option C is a tautology (always True).

Option D: $((x \vee y) \leftrightarrow (\neg x \rightarrow \neg y))$

• Let us simplify the right-hand side (RHS): $\neg x \rightarrow \neg y \equiv \neg(\neg x) \vee \neg y \equiv x \vee \neg y$.
• The equivalence is: $(x \vee y) \leftrightarrow (x \vee \neg y)$.
• If we set $x = \text{False}$ and $y = \text{True}$:
  • LHS: $\text{False} \vee \text{True} = \text{True}$
  • RHS: $\text{False} \vee \neg\text{True} = \text{False}$
• Since $\text{True} \leftrightarrow \text{False}$ is $\text{False}$, the formula is not a tautology.
• Thus, Option D is NOT True.