GATE CS 2006 Q27 — Propositional and First Order Logic

To determine if the statements $P_1$ and $P_2$ are tautologies, we can simplify both sides of the equivalence using standard logical identities.

Analysis of Statement $P_1$

Let us simplify the Left-Hand Side (LHS) and Right-Hand Side (RHS) of $P_1$:

• LHS: $$(A \land B) \to C \equiv \neg(A \land B) \lor C \equiv \neg A \lor \neg B \lor C$$
• RHS: $$(A \to C) \land (B \to C) \equiv (\neg A \lor C) \land (\neg B \lor C)$$ Applying the distributive law (factoring out $\lor C$): $$(\neg A \lor C) \land (\neg B \lor C) \equiv (\neg A \land \neg B) \lor C$$

Since $\neg A \lor \neg B \lor C$ is not logically equivalent to $( eg A \land \neg B) \lor C$, statement $P_1$ is not a tautology.

Analysis of Statement $P_2$

Let us simplify the LHS and RHS of $P_2$:

• LHS: $$(A \lor B) \to C \equiv \neg(A \lor B) \lor C \equiv (\neg A \land \neg B) \lor C$$
• RHS: $$(A \to C) \lor (B \to C) \equiv (\neg A \lor C) \lor (\neg B \lor C) \equiv \neg A \lor \neg B \lor C$$

Since $( eg A \land \neg B) \lor C$ is not logically equivalent to $\neg A \lor \neg B \lor C$, statement $P_2$ is not a tautology.

Standard Logical Equivalences

For reference, the correct distribution rules for implication are:

1. $((A \lor B) \to C) \equiv ((A \to C) \land (B \to C))$
2. $((A \land B) \to C) \equiv ((A \to C) \lor (B \to C))$

Since the operators on the right-hand side are swapped in the given statements, both $P_1$ and $P_2$ are incorrect equivalences.

Thus, both $P_1$ and $P_2$ are not tautologies.