# Checking validity of formulas in first-order logic

Given four formulas in first order logic. Which of the following formulas are not valid? (In logic a proposition is valid if it never evaluates to $$\bot$$.)

1. $$(\exists x P(x)\to Q)\to (\forall x (P(x)\to Q))$$
2. $$((\neg P\to Q)\wedge(P\to R))\to (\neg P\to R)$$
3. $$(\exists x(P(x)\to Q(x)))\leftrightarrow (\forall x P(x)\to\exists x P(x))$$
4. $$(\forall xP(x)\to Q)\to (\forall x (P(x)\to Q))$$

According to proof by negation, for example if we negate formula in $$1$$ then we get $$\bot$$, as a result this shows that $$1$$ is valid. Instructor said only $$4$$ is not valid, but I think both $$2$$ and $$4$$ are not valid according to proof by negation.

• This seems more suitable to Mathematics. Mar 19 '21 at 18:10
• I suspect you had a typo in your above formula 3. where the last term should be $Q(x)$ (not $P(x)$), then it's true, which can be easily derived from prenex normal form's implication rule. The intuition 2. is false is that there's no possible implication link from $\neg P$ to $R$ from the outermost antecedent. The intuition 4. is false is that $\forall x P(x)$ is much stricter/stronger than $\forall x(P(x)..)$ logically while ranging over same domain of discourse, so it's easier to be false, and thus conditional vacuously holds... Oct 3 '21 at 2:10

First of all, the following heuristic comes from this post

Heuristic: To try to determine whether $$\phi$$ is valid: If the answer's not obvious, look for an interpretation where $$\phi$$ is false.

So try to proof by negation. Consider $$1:$$

Let $$\begin{gather*} \phi\equiv(\exists xP(x)\to Q )\to(\forall x(P(x)\to Q)). \end{gather*}$$

Now negate $$\phi$$ then we have: $$\begin{gather*} \neg\phi\equiv \neg(\neg(\exists xP(x)\to Q )\vee(\forall x(P(x)\to Q)))\equiv (\exists xP(x)\to Q )\wedge \neg(\forall x(P(x)\to Q))\equiv (\forall x\neg P(x)\vee Q )\wedge (\exists x(P(x) \wedge \neg Q)) \end{gather*}$$

so after elimination of quantifiers:

$$\begin{gather*} \neg P(x)\vee Q \end{gather*}$$ $$\begin{gather*} P(C_1) \end{gather*}$$ $$\begin{gather*} \neg Q \end{gather*}$$

oblivious that if we use resolution, and resolve each clause we achieve $$\bot$$.

As a result we can say $$1$$ is valid.

$$2$$ is not valid, you can use above method or if we set

$$\begin{gather*} Q\equiv \top \end{gather*}$$ $$\begin{gather*} P\equiv R\equiv \bot \end{gather*}$$

as a result $$2$$ is $$\bot$$.

Repeat idea that used in $$1$$ for $$3$$:(as you know from logic, $$A\leftrightarrow B\equiv (A\to B) \wedge (B\to A)$$) so we have:

$$\begin{gather*} \neg(((\exists x(P(x)\to Q(x)) \to (\forall xP(x)\to \exists xP(x))) \end{gather*}$$ $$\begin{gather*} \wedge \end{gather*}$$ $$\begin{gather*} (\forall xP(x)\to \exists xP(x)) \to ((\exists x(P(x)\to Q(x)) )) \end{gather*}$$

After applying negation: $$\begin{gather*} \equiv \end{gather*}$$

$$\begin{gather*} (((\exists x(\neg P(x)\vee Q(x)) \wedge (\forall xP(x)\wedge \forall x\neg P(x))) \end{gather*}$$ $$\begin{gather*} \vee \end{gather*}$$ $$\begin{gather*} (\exists x\neg P(x)\vee \exists xP(x)) \wedge ((\forall x(P(x)\wedge \neg Q(x)) )) \end{gather*}$$ Eliminate quantifiers:

$$\begin{gather*} (\neg P(C_1)\vee Q(C_1)) \wedge (P(x)\wedge\neg P(x)) \end{gather*}$$ $$\begin{gather*} \vee \end{gather*}$$ $$\begin{gather*} (\neg P(C_2)\vee P(C_3)) \wedge (P(x)\wedge \neg Q(x) )) \end{gather*}$$ As you know

$$\begin{gather*} (\neg P(C_1)\vee Q(C_1)) \wedge (P(x)\wedge\neg P(x))\equiv \bot \end{gather*}$$

So we have:

$$\begin{gather*} \bot \end{gather*}$$ $$\begin{gather*} \vee \end{gather*}$$ $$\begin{gather*} (\neg P(C_2)\vee P(C_3)) \wedge (P(x)\wedge \neg Q(x) )) \end{gather*}$$

$$\begin{gather*} \equiv \end{gather*}$$ $$\begin{gather*} (\neg P(C_2)\vee P(C_3)) \wedge (P(x)\wedge \neg Q(x) )) \end{gather*}$$ As a result above formula can't equal to $$\top$$ because we can't resolve some clauses to get $$\bot$$. So $$3$$ isn't valid.

$$4$$ remain as exercise, if you follow described approach for other options, you can see $$4$$ is not valid.