Why is $∧$ used in the right-hand side of $¬(∀x, P(x) → (Q(x) ∧ R(x))) ≡ ∃x, P(x) ∧ (¬Q(x) ∨ ¬R(x))$?

Question

According to my textbook, the negation of $\forall x, P(x) \to (Q(x) \land R(x))$ is $\exists x, P(x) \land (\lnot Q(x) \lor \lnot R(x))$, so $\lnot(\forall x, P(x) \to (Q(x) \land R(x))) \equiv \exists x, P(x) \land (\lnot Q(x) \lor \lnot R(x))$.

Why is $\lnot (\forall x, P(x) \to (Q(x) \land R(x)))$ not equivalent to $\exists x, P(x) \to (\lnot Q(x) \lor \lnot R(x))$, rather than $\exists x, P(x) \land (\lnot Q(x) \lor \lnot R(x))$? From what I can tell,

\begin{align} F \land T &\equiv F & F \to T &\equiv T \\ F \land F &\equiv F & F \to F &\equiv T \\ T \land F &\equiv F & T \to T &\equiv T \\ T \land T &\equiv T & T \to F &\equiv F \\ \end{align}

Beyond this, I'm not sure how to deduce the above conclusion; any help or intuition would be appreciated.

Answer 1

$$¬(∀x, P(x) → (Q(x) ∧ R(x))) \equiv \exists x, \lnot(P(x) \to (Q(x) \land R(x)))$$

$$\equiv \exists x, \lnot (\lnot P(x) \lor (Q(x)\land R(x)))\tag{$p\to q \equiv \lnot p \lor q$}$$

$$\equiv \exists x, (P(x) \land \lnot (Q(x) \land R(x)))\tag{DeMorgan's}$$

$$\equiv \exists x, (P(x) \land (\lnot Q(x) \lor \lnot R(x)))\tag{DeMorgan's}$$

Answer 2

We have $P(x)\to \phi(x)\,\equiv\,\lnot P(x)\lor \phi(x)$ for any formula $\phi$.
Its negation is $P(x)\,{\pmb\land}\,\lnot\phi(x)$.

Answer 3

$\begin{split}&\neg\forall x~(P(x)\to(Q(x)\land R(x))) &\qquad&\\\equiv~ & \exists x~\neg(P(x)\to(Q(x)\land R(x)))&&\neg \forall x~\phi\equiv \exists x~\neg\phi\\\equiv~&\exists x~(P(x)\wedge\neg(Q(x)\land R(x)))&& \neg(\phi\to\psi)\equiv \phi\wedge\neg\psi\\\equiv~&\exists x~(P(x)\land(\neg Q(x)\lor \lnot R(x)))&&\neg(\phi\wedge\psi)\equiv\neg\phi\vee\neg\psi\end{split}$

Intuition:

Not every x that is P will be Q and R.

Some x is P and not Q or not R.

Answer 4

You have $\forall x~Z(x) $.  The negation of this is $\exists x~\lnot Z(x) $.  Now negate $Z(x)$, in your case some $p(x)\to q(x)$.  The negation of this is $p(x) \land \lnot q(x)~$ (can check this with tables for example).