Question

Let \(P(x)\) be a predicate.

Which of the following statements is/are NOT valid in first-order logic?

• A. \(\forall x\, P(x) \Rightarrow \exists x\, P(x)\)
• B. \(\exists x\, P(x) \Rightarrow \forall x\, P(x)\)
• C. \(\exists x\, P(x) \Leftrightarrow \forall x\, P(x)\)
• D. \(\forall x\, P(x) \Rightarrow \exists x\, \neg P(x)\)

Hint:

Try a small two-element domain with mixed truth values for P; a formula is valid only if it stays true under every such assignment.

Answer 1

The Correct Option is B, C, D

To test validity of these predicate-logic statements, use a small two-element domain $\{a, b\}$ and try every combination of truth values for $P(a)$ and $P(b)$. If any single combination makes a statement false, the statement is not valid; if every combination makes it true, it is valid.

1. $\forall x\, P(x) \Rightarrow \exists x\, P(x)$: check all four combinations of $P(a), P(b) \in \{T, F\}$. The antecedent $\forall x\, P(x)$ is only true in the single case $P(a)=T, P(b)=T$, and in that exact case the consequent $\exists x\, P(x)$ is also true. In every other case the antecedent is false, which makes the implication true automatically. So it is true in all four cases: this statement is valid.
2. $\exists x\, P(x) \Rightarrow \forall x\, P(x)$: take $P(a)=T, P(b)=F$. The antecedent $\exists x\, P(x)$ is true (because of $a$), but the consequent $\forall x\, P(x)$ is false (because of $b$). True implies false is false, so this combination breaks the statement: not valid.
3. $\exists x\, P(x) \Leftrightarrow \forall x\, P(x)$: with the same $P(a)=T, P(b)=F$, the left side is true and the right side is false, so the biconditional is false: not valid.
4. $\forall x\, P(x) \Rightarrow \exists x\, \neg P(x)$: take $P(a)=T, P(b)=T$. The antecedent $\forall x\, P(x)$ is true, but the consequent $\exists x\, \neg P(x)$ asks for some element where $P$ fails, and there is none, so it is false. True implies false is false: not valid.

Running through all four truth-value combinations on a small domain shows the same answer as picking targeted counterexamples: option (A) survives every combination, while (B), (C) and (D) each fail for at least one assignment of $P(a)$ and $P(b)$.

Let's summarize:

• (A) holds for every truth assignment, so it is valid.
• (B) fails when $P(a)=T, P(b)=F$.
• (C) fails under the same assignment as (B).
• (D) fails when $P(a)=T, P(b)=T$.

The statements that are NOT valid are (B), (C) and (D).