GATE CS 2016 Set 2 Q01 — Propositional and First Order Logic

An expression $X$ is logically implied by a premise $A$ (written as $A \models X$) if and only if the conditional statement $A \Rightarrow X$ is a tautology. This means whenever $A$ is true, $X$ must also be true.

First, let us simplify the given premise:

Thus, the premise $A$ is true if and only if both $P$ and $Q$ are true (i.e., $P = \text{true}$ and $Q = \text{true}$). To check which of the given expressions are logically implied by $A$, we evaluate each expression under this truth assignment:

1. $\text{false}$:
   Evaluates to $\text{false}$. Since $A \Rightarrow \text{false}$ is $\text{true} \Rightarrow \text{false} \equiv \text{false}$, it is not implied.
2. $Q$:
   Evaluates to $\text{true}$. Since $A \Rightarrow Q$ is $\text{true} \Rightarrow \text{true} \equiv \text{true}$, it is implied.
3. $\text{true}$:
   Evaluates to $\text{true}$. Since $A \Rightarrow \text{true}$ is always $\text{true}$, it is implied.
4. $P \vee Q$:
   Evaluates to $\text{true} \vee \text{true} \equiv \text{true}$. Thus, it is implied.
5. $\neg Q \vee P$:
   Evaluates to $\neg \text{true} \vee \text{true} \equiv \text{false} \vee \text{true} \equiv \text{true}$. Thus, it is implied.

The expressions logically implied by the premise are (ii), (iii), (iv), and (v).

Therefore, the number of logically implied expressions is 4.