GATE CS 2016 Set 1 Q1 — Propositional and First Order Logic

To find the integer $x \geq 2$ that satisfies the given proposition, we can simplify the logical expression using the laws of propositional logic.

Let the given expression be:

Using De Morgan's laws, we can distribute the negation:

Recall that the negation of an implication is $\neg(p \Rightarrow q) \equiv p \wedge \neg q$. Applying this and De Morgan's law to the second term:

Step 1: Analyze the term $(r \wedge s)$

• $r: x$ is a perfect square.
• $s: x$ is a prime number.

For any integer $x \geq 2$, a number cannot be both a perfect square and a prime number. Thus, $r \wedge s$ is always False.

Step 2: Analyze the term $(p \wedge \neg q)$

Since $(r \wedge s)$ is False, the expression simplifies to:

Now we evaluate $p \wedge \neg q$:

• $p: x \in \{8, 9, 10, 11, 12\}$
• $\neg q: x$ is not a composite number. Since $x \geq 2$, this means $x$ must be a prime number.

Therefore, $x$ must belong to the set $\{8, 9, 10, 11, 12\}$ and must be a prime number.

The only prime number in this set is $11$.

Conclusion

The only integer $x \geq 2$ that satisfies the given proposition is 11.