4
$\begingroup$

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?

  • 0
    What methods do you know to prove two sets are equal? What have you tried so far?2010-11-29
  • 0
    @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$.2010-11-29
  • 0
    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.2010-11-29
  • 1
    Tip: LaTeX has a `\setminus` command ($\setminus$)2010-11-29
  • 0
    @kahen: Also, \backslash: $\backslash$ which has the same look as \setminus: $\setminus$.2010-11-29

3 Answers 3

6

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.

3

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.

0

In words

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

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