# Negated Existential Quantifier of a conjunction

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?

• Your answer is right ($\lnot$ is affecting the entire term). Notice that both are different answers. – 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}$$