| Line 1: | Line 1: | ||
| − | <br><br> | + | <br><br> |
= Alternative Proof for DeMorgan's Second Law = | = Alternative Proof for DeMorgan's Second Law = | ||
| Line 5: | Line 5: | ||
By Oluwatola Adeola | By Oluwatola Adeola | ||
| − | [[ECE302|<font color="#0066cc">ECE 302,</font>]] [[ | + | [[ECE302|<font color="#0066cc">ECE 302,</font>]] [[List of Course Wikis#2013|<font color="#0066cc">Spring 2013</font>]], [[User:Mboutin|Professor Boutin]] |
| − | <br> | + | <br> |
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. | 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. | ||
| Line 19: | Line 19: | ||
#If <math>x \notin {(\bigcap^{n}{S_n})}^{c}</math> | #If <math>x \notin {(\bigcap^{n}{S_n})}^{c}</math> | ||
#<math>\Rightarrow x \in {\bigcap^{n}{S_n}}</math> | #<math>\Rightarrow x \in {\bigcap^{n}{S_n}}</math> | ||
| − | #<math>\Rightarrow \forall{n}, x \in {S_n}</math> | + | #<math>\Rightarrow \forall{n}, x \in {S_n}</math> |
| − | #<math>\Rightarrow \forall{n}, x \notin {(S_n)}^{c}</math> | + | #<math>\Rightarrow \forall{n}, x \notin {(S_n)}^{c}</math> |
| − | #<math>\Rightarrow x \notin {\bigcup^{n}{(S_n)}^{c}}</math> | + | #<math>\Rightarrow x \notin {\bigcup^{n}{(S_n)}^{c}}</math> |
#By lines 1 through 5: <math>x \notin {(\bigcap^{n}{S_n})}^{c} \Rightarrow x \notin {\bigcup^{n}{(S_n)}^{c}}</math> | #By lines 1 through 5: <math>x \notin {(\bigcap^{n}{S_n})}^{c} \Rightarrow x \notin {\bigcup^{n}{(S_n)}^{c}}</math> | ||
#By line 6; <math>{(\bigcap^{n}{S_n})}^{c} \subseteq \bigcup^{n}{(S_n)}^c</math> | #By line 6; <math>{(\bigcap^{n}{S_n})}^{c} \subseteq \bigcup^{n}{(S_n)}^c</math> | ||
#If <math>x \notin {\bigcup^{n}{(S_n)}^{c}}</math> | #If <math>x \notin {\bigcup^{n}{(S_n)}^{c}}</math> | ||
| − | #<math>\Rightarrow \forall{n}, x \notin {(S_n)}^{c}</math> | + | #<math>\Rightarrow \forall{n}, x \notin {(S_n)}^{c}</math> |
| − | #<math>\Rightarrow \forall{n}, x \in {S_n}</math> | + | #<math>\Rightarrow \forall{n}, x \in {S_n}</math> |
| − | #<math>\Rightarrow x \in {\bigcup^{n}{S_n}}</math> | + | #<math>\Rightarrow x \in {\bigcup^{n}{S_n}}</math> |
| − | #<math>\Rightarrow x \notin {(\bigcup^{n}{S_n})}^{c}</math> | + | #<math>\Rightarrow x \notin {(\bigcup^{n}{S_n})}^{c}</math> |
#By lines 8 through 12:<math>x \notin {\bigcup^{n}{(S_n)}^{c}} \Rightarrow x \notin {(\bigcup^{n}{S_n})}^{c}</math> | #By lines 8 through 12:<math>x \notin {\bigcup^{n}{(S_n)}^{c}} \Rightarrow x \notin {(\bigcup^{n}{S_n})}^{c}</math> | ||
#By line 13:<math>{(\bigcap^{n}{S_n})}^{c} \supseteq \bigcup^{n}{(S_n)}^c</math> | #By line 13:<math>{(\bigcap^{n}{S_n})}^{c} \supseteq \bigcup^{n}{(S_n)}^c</math> | ||
| − | #By lines 7 and | + | #By lines 7 and 14 <math>{(\bigcap^{n}{S_n})}^{c} = \bigcup^{n}{(S_n)}^c</math> <span class="texhtml"> </span> |
<br>[[2013 Spring ECE 302 Boutin|Back to 2013 Spring ECE 302 Boutin]] | <br>[[2013 Spring ECE 302 Boutin|Back to 2013 Spring ECE 302 Boutin]] | ||
[[Category:ECE302Spring2013Boutin]] [[Category:ECE]] [[Category:ECE302]] [[Category:Probability]] [[Category:Proofs]] [[Category:DeMorgan's_Second_Law]] | [[Category:ECE302Spring2013Boutin]] [[Category:ECE]] [[Category:ECE302]] [[Category:Probability]] [[Category:Proofs]] [[Category:DeMorgan's_Second_Law]] | ||
Revision as of 18:04, 18 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:
- If $ x \notin {(\bigcap^{n}{S_n})}^{c} $
- $ \Rightarrow x \in {\bigcap^{n}{S_n}} $
- $ \Rightarrow \forall{n}, x \in {S_n} $
- $ \Rightarrow \forall{n}, x \notin {(S_n)}^{c} $
- $ \Rightarrow x \notin {\bigcup^{n}{(S_n)}^{c}} $
- By lines 1 through 5: $ x \notin {(\bigcap^{n}{S_n})}^{c} \Rightarrow x \notin {\bigcup^{n}{(S_n)}^{c}} $
- By line 6; $ {(\bigcap^{n}{S_n})}^{c} \subseteq \bigcup^{n}{(S_n)}^c $
- If $ x \notin {\bigcup^{n}{(S_n)}^{c}} $
- $ \Rightarrow \forall{n}, x \notin {(S_n)}^{c} $
- $ \Rightarrow \forall{n}, x \in {S_n} $
- $ \Rightarrow x \in {\bigcup^{n}{S_n}} $
- $ \Rightarrow x \notin {(\bigcup^{n}{S_n})}^{c} $
- By lines 8 through 12:$ x \notin {\bigcup^{n}{(S_n)}^{c}} \Rightarrow x \notin {(\bigcup^{n}{S_n})}^{c} $
- By line 13:$ {(\bigcap^{n}{S_n})}^{c} \supseteq \bigcup^{n}{(S_n)}^c $
- By lines 7 and 14 $ {(\bigcap^{n}{S_n})}^{c} = \bigcup^{n}{(S_n)}^c $
