GATE CS 2014 Set 2 Q53 — Propositional and First Order Logic

To determine which expression is NOT a tautology, we can look for a truth assignment to the variables that makes the expression evaluate to False.

1. $((a \to b) \wedge (b \to c)) \to (a \to c)$: This is the standard transitive property of implication (hypothetical syllogism), which is always a tautology.
2. $(a \to c) \to (\sim b \to (a \wedge c))$: An implication $P \to Q$ is False only when $P$ is True and $Q$ is False.
   • To make $Q = (\sim b \to (a \wedge c))$ False, we need $\sim b$ to be True (i.e., $b = \text{False}$) and $(a \wedge c)$ to be False.
   • To make $P = (a \to c)$ True, we can set $a = \text{False}$ and $c = \text{True}$.
   Letting $a = \text{False}$, $b = \text{False}$, and $c = \text{True}$:
   • $P = \text{False} \to \text{True} = \text{True}$
   • $Q = \text{True} \to (\text{False} \wedge \text{True}) = \text{True} \to \text{False} = \text{False}$
   Thus, the entire expression evaluates to $\text{True} \to \text{False} = \text{False}$. Since it can be False, it is not a tautology.
3. $(a \wedge b \wedge c) \to (c \vee a)$: If the antecedent $(a \wedge b \wedge c)$ is True, then both $a$ and $c$ are True, which makes the consequent $(c \vee a)$ True. Thus, it is a tautology.
4. $a \to (b \to a)$: This is equivalent to $\sim a \vee (\sim b \vee a) \equiv (\sim a \vee a) \vee \sim b \equiv \text{True} \vee \sim b \equiv \text{True}$, which is a tautology.