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"?
Best Answer
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.