4
$\begingroup$

I'm not quite sure how to go about doing this. When negating I know the quantifiers themselves will be negated meaning that $\forall$ would become $\exists$ and vice-versa. Also I know that $\leftrightarrow$ can be written for example as $(\lnot a\in C \lor b \in C)\land(\not b \in C \lor a \in C)$. And this can be negated using De Morgan's laws. However what about the $\in$ would I have to negate those too? Can you please show me how that's done.

$\endgroup$
2
  • 2
    $\begingroup$ You may also note that $\neg(p\leftrightarrow q)\iff (\neg p)\leftrightarrow q$ $\endgroup$ – Hagen von Eitzen Oct 16 '13 at 18:09
  • 1
    $\begingroup$ $\neg a\in A$ is the negation of $a\in A$. It is also written as $a\notin A$ $\endgroup$ – drhab Oct 16 '13 at 18:09
3
$\begingroup$

$$\lnot(x \in X) \equiv x \notin X$$


$$\lnot\Big((\forall a \in A)(\exists b \in B)(a \in C \leftrightarrow b\in C)\Big)\tag{1}$$

$$\equiv \lnot \Big[(\forall a \in A)(\exists b \in B)\Big((a \notin C \lor b \in C)\land( b \notin C \lor a \in C)\Big)\Big]\tag{2}$$

$$\equiv (\exists a \in A)(\forall b \in B) \Big( \lnot(a\notin C \lor b \in C) \lor \lnot(b\notin C \lor a\in C)\Big)\tag{3}$$

$$ \equiv (\exists a \in A)(\forall b \in B) \Big((a\in C \land b \notin C) \lor (b\in C \land a\notin C)\Big)\tag{4}$$

$(1)$ is the negation of the given proposition.

$(2)$ is equivalent to the negated proposition, as you note.

$(3)$ Negation moves inward, changing the quantifiers, respectively, finally negating the quantified expression, and applies DeMorgan's Rule.

$(4)$ By DeMorgan's.

$\endgroup$
3
  • $\begingroup$ Oh, I see. Also just wondering when negating the expression $(\forall a \in A)$ would I only negate the $\forall$ or would I have to negate the $\in$ as well? What I mean is would the negation be $\exists a\in A$ or would it be $\exists a\notin A$ $\endgroup$ – JustAnotherUser Oct 16 '13 at 18:22
  • $\begingroup$ You can simply remove that negation by moving it progressively inward. $\endgroup$ – amWhy Oct 16 '13 at 18:32
  • $\begingroup$ @amWhy: Nice write up +1 $\endgroup$ – Amzoti Oct 18 '13 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.