GATE CS 1991 Q03 — Propositional and First Order Logic

We are given that both of the following propositional formulae are tautologies:

1. $F_1 \land F_2 \rightarrow F_3$
2. $F_1 \land F_2 \rightarrow \sim F_3$

Let $P = F_1 \land F_2$. The given conditions can be written as:

$$P \rightarrow F_3 \equiv \text{True}$$

$$P \rightarrow \sim F_3 \equiv \text{True}$$

Using the implication equivalence $A \rightarrow B \equiv \sim A \lor B$, we get:

$$\sim P \lor F_3 \equiv \text{True} \quad \text{--- (1)}$$

$$\sim P \lor \sim F_3 \equiv \text{True} \quad \text{--- (2)}$$

Taking the logical conjunction of equations (1) and (2):

$$(\sim P \lor F_3) \land (\sim P \lor \sim F_3) \equiv \text{True}$$

Applying the distributive law:

$$\sim P \lor (F_3 \land \sim F_3) \equiv \text{True}$$

Since $F_3 \land \sim F_3 \equiv \text{False}$ (a contradiction), this simplifies to:

$$\sim P \lor \text{False} \equiv \text{True}$$

$$\sim P \equiv \text{True} \implies P \equiv \text{False}$$

Substituting $P = F_1 \land F_2$ back, we get:

$$F_1 \land F_2 \equiv \text{False}$$

Since the conjunction $F_1 \land F_2$ is always false (a contradiction), it is not satisfiable.

Therefore, Option B is the correct statement.