Here I have the statement that:

$\neg (\exists x)(P(x)\land Q(x))$

I must simplify it to find an equivalent statement. Here's my answer:

$(\forall x)\neg(P(x)\land Q(x)) \equiv (\forall x)(\neg P(x) \lor \neg Q(x))$

However, I'm being corrected that this doesn't work because we changed the existential quantifier to a universal quantifier thus the answer should be:

$(\forall x)\neg(P(x)\to Q(x))$

Can someone explain why one may think this is the correct answer? I don't quite understand the reasoning for this. I thought that the law of quantifiers allowed me to reduce it to:

$(\forall x)\neg(P(x)\land Q(x)) \equiv (\forall x)(\neg P(x) \lor \neg Q(x))$

Thanks for the help, sorry I couldn't explain the other person's logic. Is my answer wrong? Is their answer wrong? Are they both right?

  • 1
    $\begingroup$ Your answer is right ($\lnot$ is affecting the entire term). Notice that both are different answers. $\endgroup$ – user486983 Nov 5 '19 at 22:52

Well, indeed, you have correctly applied quantifier duality and deMorgan's Law.

After that you may also the apply Conditional Equivalence (aka Implication Equivalence).   Which is that: $(\neg p\vee r)$ and $(p\to r)$ are equivalent for any statements $p,r$ $ \tiny\text{(in classical logic)}$.

$$\begin{align}&\neg(\exists x)~(P(x)\wedge Q(x))\\&(\forall x)~\neg(P(x)\wedge Q(x))&&\raise{2ex}\text{Existential/Universal Duality}\\&(\forall x)~(\neg P(x)\vee\neg Q(x))&&\raise{2ex}\text{DeMorgan's Rule}\\&(\forall x)~(P(x)\to\neg Q(x))&&\raise{2ex}\text{Conditional Equivalence}\end{align}$$

All these statements are considered equivalent.

The last is preferred only because it has the familiar form of "All $P$ are not $Q$," which is the natural language negation of "Some $P$ is $Q$."

That is all.

PS: Do note, however, that is not what you wrote. The negation is only on the consequent ($Q$) not the whole conditional.


You are correct

$$¬(∃x)(P(x)∧Q(x))\equiv\forall x(\neg P(x)\lor\neg Q(x))\not\equiv(∀x)¬(P(x)→Q(x))$$

In short it's simply because: $$\neg(\forall x,P(x))\equiv\exists x,\neg P(x)$$

For the very same reason, we can change $P(x)$ with $P(x)\land Q(x)$, then apply De Morgan's law, that will give us what you got.

We can also show this with a natural deduction proof:

$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}$ $$\fitch{~~ 1.~\neg\exists x(P(x)\land Q(x))}{\fitch{~~ 2.~\boxed{a}}{\fitch{~~ 3.~P(a)\land Q(a)}{~~ 4.~\exists x(P(x)\land Q(x))\hspace{22ex}{\exists}~\textsf{Intro}~3\\~~ 5.~\bot\hspace{36.5ex}{\bot}~\textsf{Intro}~1,4}\\~~ 6.~\neg(P(a)\land Q(a))\hspace{26.4ex}{\neg}~\textsf{Intro}~3-5\\\fitch{~~ 7.~\neg(\neg P(a)\lor\neg Q(a))}{\fitch{~~ 8.~\neg P(a)}{~~ 9.~\neg P(a)\lor Q(a)\hspace{21ex}{\lor}~\textsf{Intro}~8\\~~ 10.~\bot\hspace{31.6ex}{\bot}~\textsf{Intro}~7,9}\\~~ 11.~\neg\neg P(a)\hspace{29.3ex}{\neg}~\textsf{Intro}~8-10\\\fitch{~~ 12.~Q(a)}{~~ 13.~P(a)\hspace{29ex}{\neg}~\textsf{Elim}~11\\\fitch{~~ 14.~\neg(\neg P(a)\lor\neg Q(a))}{~~ 15.~P(a)\land Q(a)\hspace{18ex}{\land}~\textsf{Intro}~12,13\\~~ 16.~\bot\hspace{28ex}{\bot}~\textsf{Intro}~6,15}\\~~ 17.~\neg\neg(\neg P(a)\lor Q(a))\hspace{14.7ex}{\neg}~\textsf{Intro}~14-16\\~~ 18.~\bot\hspace{31.3ex}{\bot}~\textsf{Intro}~7,17}\\~~ 19.~\neg Q(a)\hspace{30.5ex}{\neg}~\textsf{Intro}~12-18\\~~ 20.~\neg P(a)\lor\neg Q(a)\hspace{21.6ex}{\lor}~\textsf{Intro}~19\\~~ 21.~\bot\hspace{35ex}{\bot}~\textsf{Intro}~7,20}\\~~ 22.~\neg P(a)\lor\neg Q(a)\hspace{25.3ex}{\neg}~\textsf{Intro}~7-21}\\~~ 23.~\forall x(\neg P(x)\lor\neg Q(x))\hspace{24.4ex}{\forall}~\textsf{Intro}~2-22}$$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.