How to simplify this logical expression

Question

Full Disclaimer, this is a homework problem.

Negate the following logical expression and transform it so that negations only appear before individual predicates: ∀x∃y∀z, P(x) ∧ ¬Q(x) → R(x) ∨ (R(y) ∧ ¬Q(z))

I'm not sure how to start with this problem. I thought that it would make sense to try to bring out the individual not's to the front but I'm not sure because I only know a handful of basic negations like p → q = ¬p ∨ q, which I don't know if it would work here.

I put parentheses afterwords to more clearly highlight the order of precedence:

∀x∃y∀z, ((P(x) ∧ ¬Q(x)) → (R(x) ∨ (R(y) ∧ ¬Q(z))))

Answer 1

Here is an explanation in words rather than logical symbols:

The negation of "for every/for all" ($\forall$) is "there exits" ($\exists$).

Example: The negation of the statement "$\forall x, p(x)$" is "$\exists x$, ~$p(x)$" (~ stands for "not").

The negation of "there exists" ($\exists$) is "for every/for all" ($\forall$).

Example: The negation of the statement "$\exists x$ such that $p(x)$" is "$\forall x$, ~$p(x)$".

The negation of "if $p$, then $q$" is "$p$ and ~$q$" (note: the negation of an "if, then" statement is NOT an "if, then" statement).

Example: The negation of the statement "if $p(x)$, then $q(x)$" is "$p(x)$ and not $q(x)$".

The negation of "$p$ or $q$" is "~$p$ and ~$q$".

The negation of "$p$ and $q$" is "~$p$ or ~$q$".

Now, we need to negate $\forall x$ $\exists y$ $\forall z$ ($P(x) \land$ ~$Q(x)$) $\implies (R(x) \lor (R(y) \land $ ~$Q(z)$).

You need to start negating from left to right, just as if you were reading. The first three negations are easy. $\forall x$ $\exists y$ $\forall z$ becomes $\exists x$ $\forall y$ $\exists z$.

Now, the next largest statement if the "if, then" statement. Using the rules above, we know that the negation of $p \implies q$ is $p \land $ ~$q$. So, applying this to the implication gives that ($P(x) \land$ ~$Q(x)$) $\implies (R(x) \lor (R(y) \land $ ~$Q(z)$) becomes ($P(x) \land$ ~$Q(x)$) $\land$ ~$ [(R(x) \lor (R(y) \land $ ~$Q(z)$)].

Now, we see that we need to negate $(R(x) \lor (R(y) \land $ ~$Q(z)$). The outer statement is an "or" statement, and so using the rules above, its negation is ~$R(x) \land$ ~$(R(y) \land $ ~$Q(z)$).

Finally, we need to negate the "and" statement $R(y) \land $ ~$Q(z)$. But using the rules above, the negation becomes ~$R(y) \lor Q(z)$.

So, putting it all together, the negation of $\forall x$ $\exists y$ $\forall z$ ($P(x) \land$ ~$Q(x)$) $\implies (R(x) \lor (R(y) \land $ ~$Q(z)$) is:

$\exists x$ $\forall y$ $\exists z$ ($P(x) \land$ ~$Q(x)$) $\land$ (~$R(x) \land$ (~$R(y) \lor Q(z)$)).

Answer 2

Firstly, negate your quantifiers.

Negation of Universal quantifier:

$$\neg \forall s: S(s) \quad\equiv\quad \exists s: \neg S(s)$$

Negation of Existential quantifier:

$$\neg \exists s: S(s) \quad\equiv\quad \forall s: \neg S(s)$$

Note that these iterate, thusly: $$\neg \forall x \exists y \forall z : S(x,y,z) \quad\equiv\quad \exists x\forall y \exists z: \neg S(x,y,z)$$

---

Next negate your predicated statements, by applying Implication Equivalence and DeMorgan's Laws repeatedly to each bracketed expression until all negations are before a predicate.

Material Implication Equivalence:

$$(S\to T) \quad\equiv\quad (\neg S\lor T)$$

Negation of Conjunction: 

$$\neg (S\land T) \quad\equiv\quad (\neg S \lor \neg T)$$

Negation of Disjunction: 

$$\neg (S\lor T) \quad\equiv\quad (\neg S \land \neg T)$$

Answer 3

What's the negation of '$\forall x \phi$? Let's recall the following first-order logical equivalences.

For the universal quantifier:

$\neg \forall x \phi \equiv \exists x \neg \phi$

For the existencial one:

$\neg \exists x \phi \equiv \forall x \neg \phi$

So, can you continue from there? In case of any doubt leave a comment.