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.

  • 2
    $\begingroup$ You may also note that $\neg(p\leftrightarrow q)\iff (\neg p)\leftrightarrow q$ $\endgroup$ Oct 16, 2013 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, 2013 at 18:09

1 Answer 1


$$\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.

  • $\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$ Oct 16, 2013 at 18:22
  • $\begingroup$ You can simply remove that negation by moving it progressively inward. $\endgroup$
    – amWhy
    Oct 16, 2013 at 18:32
  • $\begingroup$ @amWhy: Nice write up +1 $\endgroup$
    – Amzoti
    Oct 18, 2013 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.