| Line 12: | Line 12: | ||
| | ||
| − | + | DeMorgan's Second Law: <math class = "center">{(\bigcap^{n}{S_n})}^{c} = \bigcup^{n}{(S_n)}^c</math> | |
| − | DeMorgan's Second Law: <math>{(\bigcap^{n}{S_n})}^{c} = \bigcup^{n}{(S_n)}^c</math> | + | |
Proof: | Proof: | ||
| + | #<math class = "center"> | ||
| + | \begin{align} | ||
| + | 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}} | ||
| + | \end{align} | ||
| + | </math> | ||
| + | #<math class = "center">{(\bigcap^{n}{S_n})}^{c} \subseteq \bigcup^{n}{(S_n)}^c</math> | ||
| + | #<math class = "center"> | ||
| + | \begin{align} | ||
| + | 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} | ||
| + | \end{align} | ||
| + | </math> | ||
| + | #<math class = "center>{(\bigcap^{n}{S_n})}^{c} \supseteq \bigcup^{n}{(S_n)}^c</math> | ||
| + | #By lines 2 and 4: <math class = "center">{(\bigcap^{n}{S_n})}^{c} = \bigcup^{n}{(S_n)}^c</math> <span class="texhtml"> </span> | ||
| + | |||
| + | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
---- | ---- | ||
Formatting help: | Formatting help: | ||
Latest revision as of 11:01, 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:
- $ \begin{align} 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}} \end{align} $
- $ {(\bigcap^{n}{S_n})}^{c} \subseteq \bigcup^{n}{(S_n)}^c $
- $ \begin{align} 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} \end{align} $
- $ {(\bigcap^{n}{S_n})}^{c} \supseteq \bigcup^{n}{(S_n)}^c $
- By lines 2 and 4: $ {(\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 $
