3
$\begingroup$

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?

  • 0
    @Myself: No biggie. If I were you, I could say I wasn't Myself today!2011-01-26

1 Answers 1

6

The best way to approach these problems is to go step by step by the definition and tautologies that you know. For example:

  • $\lnot \exists x\varphi \iff \forall x\lnot\varphi$, and
  • $\lnot\forall x\varphi\iff \exists x\lnot\varphi$

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}$