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.

Given:

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

Problem:

Show how the identity above can be proved using two steps of De Morgan's Law along with some other basic set rules (i.e. an algebraic proof).


I wasn't aware that De Morgan's Law had multiple steps. I thought De Morgan's Law was just De Morgan's Law. Perhaps it means, use two steps used in a direct proof for proving De Morgan's Law? If that is the case, I find myself a bit lost in determining which two steps to use.

Here is my direct proof of the above. I'm very new at this, and expect there might be an error or three below. Any corrections for the direct proof below are welcome in addition to this question.

Let $x\in$$(A'$ $\cup$ $B'$ $\cup$ $C')$ (assumption)

$\Rightarrow$ $x\in$$A'$ $\lor$ $x\in$$B'$ $\lor$ $x\in$$C'$ (by definition of union)

$\Rightarrow$ $x\notin$$A$ $\lor$ $x\notin$$B$ $\lor$ $x\notin$$C$ (by definition of complement)

$\Rightarrow$ $x\notin$$(A$ $\cap$ $B)$ $\lor$ $x\notin$$C$ (by definition of intersection)

$\Rightarrow$ $x\notin$$(A$ $\cap$ $B)$ $\cap$ $C$ (by definition of intersection)

$\Rightarrow$ $x\notin$$(A$ $\cap$ $B$ $\cap$ $C)$ (by associative law)

$\Rightarrow$ $x\in$$(A$ $\cap$ $B$ $\cap$ $C)'$ (by definition of complement)


Let $x\in$$(A$ $\cap$ $B$ $\cap$ $C)'$ (assumption)

$\Rightarrow$ $x\notin$$(A$ $\cap$ $B$ $\cap$ $C)$ (by definition of complement)

$\Rightarrow$ $(x\notin$$A$ $\lor$ $x\notin$$B)$ $\cap$ $C$ (by definition of intersection)

$\Rightarrow$ $x\notin$$A$ $\lor$ $x\notin$$B$ $\lor$ $x\notin$$C$ (by definition of intersection)

$\Rightarrow$ $x\in$$A'$ $\lor$ $x\in$$B'$ $\lor$ $x\in$$C'$ (by definition of complement)

$\Rightarrow$ $x\in$$(A'$ $\cup$ $B'$ $\cup$ $C')$ (by definition of union)


So I guess it comes down to, if the above is an accurate direct proof, what is the algebraic proof that uses "two steps" and "some other basic set rules"?

share|improve this question
    
Wow, answers came in ridiculously fast! Thanks! –  CptSupermrkt Jul 7 '13 at 1:21
    
Yep! It seems like those answerers know the way to answer your problem! –  NasuSama Jul 7 '13 at 1:26
    
Not exactly a duplicate of Prove$\overline{(A \cap B \cap C)} = \overline{A} \cup \overline{B} \cup \overline{C}$ By Subsets, but closely related. –  Marnix Klooster Aug 1 '13 at 4:25

2 Answers 2

up vote 4 down vote accepted

An algebraic proof is not very hard using basic properties of $\cap,\cup,\bullet'$ and the two sets DeMorgan law.

$$A'\cup B'\cup C'=(A'\cup B')\cup C'=(A\cap B)'\cup C'=((A\cap B)\cap C)'=(A\cap B\cap C)'.$$

We use the fact that $X''=X$, and that $\cap,\cup$ are associative.

share|improve this answer
    
But how does this work out for sets? How does the definition of sets implicit here make such manipulations permissible? –  Doug Spoonwood Jul 7 '13 at 1:50
    
I don't understand your question Doug. –  Asaf Karagila Jul 7 '13 at 1:56
    
As I understand the definition of a (conventional) set, it says that two sets X and Y qualify as equal if and only if X qualifies as a subset of Y and Y qualifies as a subset of X. So, in order to show two sets equal you either have to show A a subset of B and conversely, or at least have some argument that indicates that you could show A a subset of B and conversely. I only see algebraic manipulations. I don't see any indication that showing one set A as the subset of B, and conversely could in principle happen (and in the books I've read, I haven't seen that). So, how could you do that? –  Doug Spoonwood Jul 7 '13 at 2:08
1  
@DougSpoonwood Showing that $X \subseteq Y$ and $Y \subseteq X$ is an effective strategy many people use to show that $X=Y$. But it isn't the only strategy. We are allowed to use DeMorgan's Law for two sets: $$ (X \cap Y)' = X' \cup Y' $$ in order to prove DeMorgan's Law for three sets. –  Adriano Jul 7 '13 at 4:09
1  
@Doug: Note that there was no given definition of what are "basic set rules". The question asked for an algebraic manipulation using the two-step DeMorgan and "basic set rules". The basic set rules are really just the axioms of Boolean algebra, or immediate consequences of those, with regards to the Boolean operations. I still don't feel that I understand your comments, or your inquiry about/objection(?) to this proof. –  Asaf Karagila Jul 7 '13 at 13:32

The algebraic proof using two steps of de Morgan's would be

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

where each step uses $X' \cup Y' = (X \cap Y)'$.

share|improve this answer
    
You also use that $X''=X$. –  Asaf Karagila Jul 7 '13 at 1:20

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.