GATE CS 2004 Q70 — Propositional and First Order Logic

To determine the nature of the propositional statement, let us analyze the formula:

Let $A = P \implies (Q \vee R)$ and $B = (P \wedge Q) \implies R$. The formula is of the form $A \implies B$.

1. Testing for Validity (Can $F$ be False?)

An implication $A \implies B$ is false if and only if $A$ is True and $B$ is False.

• For $B = (P \wedge Q) \implies R$ to be False:
  • $P \wedge Q$ must be True $\implies P = \text{True}$ and $Q = \text{True}$.
  • $R$ must be False $\implies R = \text{False}$.
• Now, let us substitute these values into $A$: $$A = P \implies (Q \vee R)$$ $$A = \text{True} \implies (\text{True} \vee \text{False}) = \text{True} \implies \text{True} = \text{True}$$

Since we found an assignment ($P = \text{True}$, $Q = \text{True}$, $R = \text{False}$) where $A$ is True and $B$ is False, the entire statement $F$ evaluates to False. Therefore, the statement is not valid.

2. Testing for Satisfiability (Can $F$ be True?)

Let us choose an assignment, say $P = \text{False}$:

• $A = \text{False} \implies (Q \vee R) = \text{True}$
• $B = (\text{False} \wedge Q) \implies R = \text{False} \implies R = \text{True}$
• $F = A \implies B = \text{True} \implies \text{True} = \text{True}$

Since there exists at least one truth assignment that makes the statement True, the statement is satisfiable.

Since the statement is satisfiable but not valid, the correct option is A.