Negation of the statement

Question

I need to negate the following expression to obtain the formula that does not contain $\neg$ , $\land$ and $\lor$: $(\forall x) (\exists y) (\neg P(x,y) \land Q(x,y)) \land (\exists x) (\forall y) (\neg R(x,y) \land Q(x,y))$

I attempted the question the following way but I am not sure if my solution is correct since there is a lot of back and forth going on:

So I need to find

$\neg [(\forall x) (\exists y) (\neg P(x,y) \land Q(x,y)) \land (\exists x) (\forall y) (\neg R(x,y) \land Q(x,y))]$ $= [\neg (\forall x) (\exists y) (\neg P(x,y)\land Q(x,y)] \lor [\neg (\exists x) (\forall y) (\neg R(x,y) \land Q(x,y))]$ $= [(\exists x) (\forall y) \neg (\neg P(x,y) \land Q(x,y))] \lor (\forall x) (\exists y) \neg(\neg P(x,y) \land Q(x,y))]$ $= \neg[(\exists x) (\forall y) \neg (\neg P(x,y) \land Q(x,y))] \implies [(\forall x) (\exists y) \neg(\neg P(x,y) \land Q(x,y))]$ $= [(\forall x) (\exists y) (\neg P(x,y) \land Q(x,y)] \implies [(\forall x) (\exists y)(P(x,y) \land \neg Q(x,y))]$ $= [(\forall x) (\exists y) \neg(\neg P(x,y) \implies \neg Q(x,y))] \implies [(\forall x) (\exists y) \neg ((P(x,y) \implies Q(x,y))]$ $= [(\exists x) (\forall y) (Q(x,y) \implies P(x,y))] \implies [(\exists x) (\forall y) ((P(x,y) \implies Q(x,y))]$

Thank you in advance!

Answer 1

From Step 2 to Step 3, you make a typo and replace $R$ with $P$, which is easily fixed.

However, from Step 4 to Step 5, you seem to apply De Morgan's Law incorrectly and say $\neg(\neg R(x, y) \wedge Q(x, y)) \iff R(x, y) \wedge \neg Q(x, y)$ even though it should $R(x, y) \vee \neg Q(x, y)$. I will continue from there: $$[(\forall x) (\exists y) (\neg P(x,y) \land Q(x,y))] \implies [(\forall x) (\exists y)(R(x,y) \vee \neg Q(x,y))]$$ Use material implication to change $R(x,y) \vee \neg Q(x,y)$ into $Q(x,y) \implies R(x,y)$: $$[(\forall x) (\exists y) (\neg P(x,y) \land Q(x,y))] \implies [(\forall x) (\exists y)(Q(x,y) \implies R(x,y))]$$ At this point, I am also stuck, so hopefully someone else can continue from here.

Answer 2

Note the following:

$\neg A \equiv A \to \bot$.

$\neg A \lor B \equiv A \to B$.

$\neg A \land B \equiv \neg( \neg B \lor A ) \equiv \neg( B \to A ) \equiv ( B \to A ) \to \bot$.

$A \lor B \equiv \neg A \to B \equiv ( A \to \bot ) \to B$.

We cannot rewrite "$\bot$" using only propositional variables and "$\to$", because any proposition would be of the form "$A \to B$", which we can make true by making $B$ true recursively.