GATE CS 2001 Q1.3 — Propositional and First Order Logic

To determine the nature of the two formulas, let us simplify them using standard propositional logic equivalences.

1. Analysis of $F_1: P \Rightarrow \neg P$

Using the implication identity $A \Rightarrow B \equiv \neg A \lor B$:

• If $P$ is False, then $F_1$ is True.
• If $P$ is True, then $F_1$ is False.

Since there is at least one truth assignment (when $P$ is False) that makes $F_1$ True, $F_1$ is satisfiable (but not valid).

2. Analysis of $F_2: (P \Rightarrow \neg P) \lor (\neg P \Rightarrow P)$

Using the implication identity on both parts:

• $P \Rightarrow \neg P \equiv \neg P$
• $\neg P \Rightarrow P \equiv \neg(\neg P) \lor P \equiv P \lor P \equiv P$

Substituting these back into $F_2$:

Since $\neg P \lor P$ is always True regardless of the truth value of $P$, $F_2$ is a tautology. Therefore, $F_2$ is valid.

Thus, $F_1$ is satisfiable and $F_2$ is valid, which matches Option A.