Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How to prove DeMorgan's Law?

$$A - (B \cup C) = (A - B) \cap (A - C)$$ $$A - (B \cap C) = (A - B) \cup (A - C)$$

EDIT:
Here is what I have tried so far:

Considering the first equation, assuming $x \in A - (B \cup C)$ then $x \in A$ and $x \not\in B$ and $x \not\in C$, while the right hand means ($x \in A$ and $x \not\in B$) or ($x \in A $ and $x \not\in C$) which is the same as $x \in A$ and $x \not\in B$ and $x \not\in C$. So the two set is the same.

But I do not know whether this is sufficient for a proof. Am I wrong?

share|improve this question
    
What methods do you know to prove two sets are equal? What have you tried so far? –  Jonas Meyer Nov 29 '10 at 10:06
    
@Jonas: I do know exactly two methods to prove two sets are equal: the first method is to show that if an element $x$ is in one set, then it will be in another set and this is the method I have tried; the second method is to show that $A \subset B$ and $B \subset A$, then we should get $A = B$. –  Jichao Nov 29 '10 at 10:19
    
Thanks. The first method you mention is a particular way to show that $A\subset B$ and $B\subset A$, as seen in yunone's answer. As seen in Elazar's answer, you can also prove logical equivalence of the conditions for membership. –  Jonas Meyer Nov 29 '10 at 10:25
1  
Tip: LaTeX has a \setminus command ($\setminus$) –  kahen Nov 29 '10 at 10:29
    
@kahen: Also, \backslash: $\backslash$ which has the same look as \setminus: $\setminus$. –  AD. Nov 29 '10 at 13:47

3 Answers 3

up vote 5 down vote accepted

I'd "reduce" it to logic

$x\in A-(B\cup C) \iff x\in A \text{ and not } (x\in B \text{ or } x\in C)$

thus by DeMorgan in logic (which can be proved with truth table)

$x\in A \text{ and } x\notin B \text{ and } x\notin C$

Thus $(x \in A \text{ and } x \notin B) \text{ and } (x \in A \text{ and } x \notin C)$. Thus

$x\in (A- B)\cap (A- C)$

and vice versa.

share|improve this answer

Maybe you're familiar with the fact that if $A\subseteq B$ and $B\subseteq A$, then $A=B$?

Since you're viewing $A,B,C$ as sets, you can prove these by showing the set on the left of $=$ is a subset of the set on the right of $=$, and vice versa.

For example, suppose $x\in A-(B\cup C)$. So $x\in A$, but $x\not\in B\cup C$. In particular, $x\not\in B$, and $x\not\in C$. It follows that $x\in A-B$ and $x\in A-C$, that is, $x\in (A-B)\cap (A-C)$. Thus $A-(B\cup C)\subseteq (A-B)\cap (A-C)$.

Try using a similar method to show the reverse containment, and you'll get your result. This works for the second law also.

share|improve this answer

In words

http://www.youtube.com/watch?v=bED-wffoK_g4

If you need an explanation and have noone to discuss with.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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