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?
Best Answer
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.