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.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ You may also note that $\neg(p\leftrightarrow q)\iff (\neg p)\leftrightarrow q$ $\endgroup$– Hagen von EitzenOct 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$– drhabOct 16, 2013 at 18:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
$$\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$– amWhyOct 16, 2013 at 18:32
-