Algebraically transform logic expression

Question

Algebraically transform:

$\neg \forall x(P(x) \wedge Q(y) \implies \exists zR(z))$

to

$\exists x\forall z(P(x) \wedge Q(y) \wedge \neg R(z))$

Justify each step with one or more laws.

Unfortunately I don't know even how to begin. I am just learning to be familiar with some of the laws and what they do. However, this is the first time we've been asked to algebraically transform an equation with all/some quantifiers.

I've tried Googling, but I am only finding pages of "Circuit Simplification" and examples in unfamiliar formats, different than shown.

Answer 1

$\neg \forall x(P(x) \wedge Q(y) \implies \exists zR(z))$

By DeMorgan, we have $\exists x\neg (P(x) \wedge Q(y) \implies \exists zR(z))$

Use the equivalence $(p \implies q )\iff (\neg p \vee q)$ to get $$\exists x\neg (\neg(P(x) \wedge Q(y) )\vee \exists zR(z)) $$

Keep using your properties to continue simplifying. Can you take it from here?

Answer 2

This is what I came up with in the end:

1. $\neg \forall x(P(x)\land Q(y)\implies \exists zR(z))$

2. $\exists x\neg (P(x)\land Q(y)\implies \exists zR(z))$ DeMorgan's

3. $\exists x\neg (\neg (P(x)\land Q(y))\lor \exists zR(z))$ Implication

4. $\exists x(P(x)\land Q(y)\land \neg \exists zR(z))$ DeMorgan's

5. $\exists x(P(x)\land Q(y)\land \forall z\neg R(z))$ DeMorgan's

6. $\exists x \forall z(P(x)\land Q(y)\land \neg R(z))$ Associative