The negation of :
∃x ∀y (P(x,y) ⇒ Q(x,y))
is:
∀x ∃y ¬(P(x,y) ⇒ Q(x,y))
But I am not sure about the last part (¬(...)). Is that negation well done, in the sense that couldn't be done more concisely?
The negation of :
∃x ∀y (P(x,y) ⇒ Q(x,y))
is:
∀x ∃y ¬(P(x,y) ⇒ Q(x,y))
But I am not sure about the last part (¬(...)). Is that negation well done, in the sense that couldn't be done more concisely?
The best way to approach these problems is to go step by step by the definition and tautologies that you know. For example:
Both useful in the case of the quantifiers, we want to negate an implication we use two facts, $x\rightarrow y \iff \lnot x\lor y$ and DeMorgan's law. Together we have:
$\lnot(x\rightarrow y)\iff \lnot(\lnot x\lor y) \iff x\land\lnot y$.
Now we proceed to negate the sentence at hand: $ \begin{align} \lnot ( \exists x\forall y\ (P(x,y)\rightarrow Q(x,y)) &\iff \forall x \lnot (\forall y\ (P(x,y)\rightarrow Q(x,y)) \\ &\iff \forall x \exists y\ \lnot(P(x,y)\rightarrow Q(x,y)) \\ &\iff \forall x \exists y\ \lnot(\lnot P(x,y)\lor Q(x,y)) \\ &\iff \forall x \exists y\ (P(x,y)\land\lnot Q(x,y)) \end{align}$