GATE CS 2009 Q24 — Propositional and First Order Logic

To find which expression is equivalent to $P \vee Q$, let us first express the binary operation $\Box$ in terms of standard logical connectives.

From the given truth table for $P \Box Q$:

• $T \Box T = T$
• $T \Box F = T$
• $F \Box T = F$
• $F \Box F = T$

Observe that $P \Box Q$ is false only when $P$ is False and $Q$ is True. This is the exact definition of the implication $Q \rightarrow P$ (or equivalently, $P \vee \neg Q$).

Thus, we can write the operation as: $$\mathbf{A \Box B \equiv B \rightarrow A \equiv A \vee \neg B}$$

Now, let us evaluate the given options using this equivalence:

1. Option A: $\neg Q \Box \neg P$ $$\neg Q \Box \neg P \equiv \neg P \rightarrow \neg Q \equiv Q \rightarrow P \equiv P \vee \neg Q$$
2. Option B: $P \Box \neg Q$ $$P \Box \neg Q \equiv \neg Q \rightarrow P \equiv Q \vee P \equiv P \vee Q$$ This matches the target expression $P \vee Q$.
3. Option C: $\neg P \Box Q$ $$\neg P \Box Q \equiv Q \rightarrow \neg P \equiv \neg Q \vee \neg P$$
4. Option D: $\neg P \Box \neg Q$ $$\neg P \Box \neg Q \equiv \neg Q \rightarrow \neg P \equiv P \rightarrow Q \equiv \neg P \vee Q$$

Therefore, Option B is the correct equivalent expression.