Revision as of 05:47, 19 March 2013

Alternative Proof for DeMorgan's Second Law

By Oluwatola Adeola

ECE 302, Spring 2013, Professor Boutin

During lecture, a proof of DeMorgan’s second law was given as a possible solution to the quiz which was based on showing that both sets are subsets of each other and are therefore equivalent. Here’s is an alternative method of proving the law that relies on determining a subset based on the exclusion of an element rather than inclusion.

DeMorgan's Second Law:  $ {(\bigcap^{n}{S_n})}^{c} = \bigcup^{n}{(S_n)}^c $ 

Proof:

1. If    $ x \notin {(\bigcap^{n}{S_n})}^{c} $
2. $ \Rightarrow x \in {\bigcap^{n}{S_n}} $ 
3. $ \Rightarrow \forall{n}, x \in {S_n} $
4. $ \Rightarrow \forall{n}, x \notin {(S_n)}^{c} $ 
5. $ \Rightarrow x \notin {\bigcup^{n}{(S_n)}^{c}} $ 
6. By lines 1 through 5: $ x \notin {(\bigcap^{n}{S_n})}^{c} \Rightarrow x \notin {\bigcup^{n}{(S_n)}^{c}} $
7. By line 6; $ {(\bigcap^{n}{S_n})}^{c} \subseteq \bigcup^{n}{(S_n)}^c $
8. If $ x \notin {\bigcup^{n}{(S_n)}^{c}} $
9. $ \Rightarrow \forall{n}, x \notin {(S_n)}^{c} $ 
10. $ \Rightarrow \forall{n}, x \in {S_n} $ 
11. $ \Rightarrow x \in {\bigcup^{n}{S_n}} $ 
12. $ \Rightarrow x \notin {(\bigcup^{n}{S_n})}^{c} $ 
13. By lines 8 through 12:$ x \notin {\bigcup^{n}{(S_n)}^{c}} \Rightarrow x \notin {(\bigcup^{n}{S_n})}^{c} $
14. By line 13:$ {(\bigcap^{n}{S_n})}^{c} \supseteq \bigcup^{n}{(S_n)}^c $
15. By lines 7 and 14 $ {(\bigcap^{n}{S_n})}^{c} = \bigcup^{n}{(S_n)}^c $   

Formatting help: $ \begin{align} x \notin {(\bigcap^{n}{S_n})}^{c} & \Rightarrow x \in {\bigcap^{n}{S_n}}\\ &\Rightarrow \forall{n}, x \in {S_n} \end{align} $

Example of alignments: $ x+y $ $ x_3^7+y $ $ x_3^7+y $

Back to 2013 Spring ECE 302 Boutin