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.

  • 2
    $\begingroup$ This seems more suitable to Mathematics. $\endgroup$ Mar 19 '21 at 18:10
  • $\begingroup$ 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... $\endgroup$
    – mohottnad
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy