ド・モルガンの法則
集合\(A,B\)を任意に選んだとき、以下の相等関係\begin{eqnarray*}\left( a\right) \ \left( A\cap B\right) ^{c} &=&A^{c}\cup B^{c} \\
\left( b\right) \ \left( A\cup B\right) ^{c} &=&A^{c}\cap B^{c}
\end{eqnarray*}が成り立ちます。共通部分と和集合の間に成立する以上の性質をド・モルガンの法則（De Morgan’s law）と呼びます。
共通部分の補集合\(\left(A\cap B\right) ^{c}\)をとると補集合どうしの和集合\(A^{c}\cup B^{c}\)になるというのが\(\left(a\right) \)の主張であり、和集合の補集合\(\left( A\cup B\right) ^{c}\)をとると補集合どうしの共通部分\(A^{c}\cap B^{c}\)になるというのが\(\left( b\right) \)の主張です。
\left( b\right) \ \left( A\cup B\right) ^{c} &=&A^{c}\cap B^{c}
\end{eqnarray*}が成り立つ。
A &=&\left\{ 4,5,6,7,8\right\} \\
B &=&\left\{ 2,4,6,8,10\right\}
\end{eqnarray*}と定義されているとき、\begin{eqnarray*}
\left( A\cap B\right) ^{c} &=&U\backslash \left( A\cap B\right) \\
&=&\left\{ 1,2,3,4,5,6,7,8,9,10\right\} \backslash \left\{ 4,6,8\right\} \\
&=&\left\{ 1,2,3,5,7,9,10\right\}
\end{eqnarray*}である一方で、\begin{eqnarray*}
A^{c}\cup B^{c} &=&\left( U\backslash A\right) \cup \left( U\backslash
B\right) \\
&=&\left\{ 1,2,3,9,10\right\} \cup \left\{ 1,3,5,7,9\right\} \\
&=&\left\{ 1,2,3,5,7,9,10\right\}
\end{eqnarray*}となるため、\begin{equation*}
\left( A\cap B\right) ^{c}=A^{c}\cup B^{c}
\end{equation*}が成立しています。これはド・モルガンの法則と整合的です。また、\begin{eqnarray*}
\left( A\cup B\right) ^{c} &=&U\backslash \left( A\cup B\right) \\
&=&\left\{ 1,2,3,4,5,6,7,8,9,10\right\} \backslash \left\{
2,4,5,6,7,8,10\right\} \\
&=&\left\{ 1,3,9\right\}
\end{eqnarray*}である一方で、\begin{eqnarray*}
A^{c}\cap B^{c} &=&\left( U\backslash A\right) \cap \left( U\backslash
B\right) \\
&=&\left\{ 1,2,3,9,10\right\} \cap \left\{ 1,3,5,7,9\right\} \\
&=&\left\{ 1,3,9\right\}
\end{eqnarray*}となるため、\begin{equation*}
\left( A\cup B\right) ^{c}=A^{c}\cap B^{c}
\end{equation*}が成立しています。これはド・モルガンの法則と整合的です。
&&B\backslash C
\end{eqnarray*}はともに集合であるため、ド・モルガンの法則より、\begin{eqnarray*}
\left( a\right) \ \left( \left( A\backslash B\right) \cap \left( B\backslash
C\right) \right) ^{c} &=&\left( A\backslash B\right) ^{c}\cup \left(
B\backslash C\right) ^{c} \\
\left( b\right) \ \left( \left( A\backslash B\right) \cup \left( B\backslash
C\right) \right) ^{c} &=&\left( A\backslash B\right) ^{c}\cap \left(
B\backslash C\right) ^{c}
\end{eqnarray*}がともに成り立ちます。
\end{equation*}が成り立ちます。実際、\begin{eqnarray*}
\left( A^{c}\cap B\right) ^{c} &=&\left( A^{c}\right) ^{c}\cup B^{c}\quad
\because \text{ド・モルガンの法則} \\
&=&A\cup B^{c}\quad \because \text{ベキ等律}
\end{eqnarray*}となるからです。
2つの条件を満たす対象からなる集合の補集合
単純化のため、すべての人間は男性または女性のどちらか一方であるものとします。その上で、以下の集合\begin{equation}
\text{20歳以上の男性からなる集合} \quad \cdots (1)
\end{equation}について考えます。この集合の補集合を、\begin{equation*}
\text{20歳未満の女性からなる集合}
\end{equation*}としてしまいそうですが、これは誤りです。
2つの条件\(P,Q\)が与えられたとき、「\(P,Q\)の双方を満たす対象からなる集合」の補集合は「\(P,Q\)の双方を満たさない対象からなる集合」ではありません。実際、集合\(A,B\)をそれぞれ、\begin{eqnarray*}A &:&\text{20歳以上の人からなる集合} \\
B &:&\text{男性からなる集合}
\end{eqnarray*}とおくと、もとの集合\(\left( 1\right) \)は共通部分\begin{equation*}A\cap B
\end{equation*}として定式化されますが、その補集合は、\begin{equation*}
\left( A\cap B\right) ^{c}
\end{equation*}であり、さらにド・モルガンの法則より、これは、\begin{equation*}
A^{c}\cup B^{c}
\end{equation*}と一致します。つまり、もとの集合\(\left( 1\right) \)の補集合は、\begin{equation}\text{20歳未満または女性からなる集合} \quad \cdots (2)
\end{equation}です。\(\left( 1\right) \)の補集合\(\left( 2\right) \)に属する人を選んだ場合、可能性としては、その人が (a) 20未満の男性、(b) 20歳以上の女性、(c) 20歳未満の女性、の3通りが起こり得ます。つまり、\(\left( 2\right) \)を正確に表現すると、\begin{equation*}\text{20歳未満または女性の少なくとも一方であるような人からなる集合}
\end{equation*}となります。
結論をまとめると、2つの条件\(P,Q\)が与えられたとき、「\(P,Q\)の双方を満たす対象からなる集合」の補集合は「\(P,Q\)の双方を満たさない対象からなる集合」ではなく、「\(P,Q\)のうちの少なくとも一方を満たさない対象からなる集合」であるということです。
B &:&20\text{以下の整数からなる集合}
\end{eqnarray*}と定義すると、「\(10\)以上かつ\(20\)以下の整数からなる集合」は共通部分\begin{equation*}A\cap B
\end{equation*}として表現されます。その補集合は、\begin{equation*}
\left( A\cap B\right) ^{c}
\end{equation*}ですが、ド・モルガンの法則より、これは、\begin{equation*}
A^{c}\cup B^{c}
\end{equation*}と一致します。これは、\begin{equation*}
10\text{未満であるか、}20\text{より大きいか、その少なくとも一方であるような整数からなる集合}
\end{equation*}です。
ド・モルガンの法則の一般化
3つの集合\(A,B,C\)が任意に与えられたとき、\begin{align*}(A\cap B\cap C)^{c}& =(\left( A\cap B\right) \cap C)^{c}\quad \because \text{結合律} \\
& =\left( A\cap B\right) ^{c}\cup C^{c}\quad \because \text{ド・モルガンの法則} \\
& =\left( A^{c}\cup B^{c}\right) \cup C^{c}\because \text{ド・モルガンの法則} \\
& =A^{c}\cup B^{c}\cup C^{c}\quad \because \text{結合律}
\end{align*}すなわち、\begin{equation*}
\left( A\cap B\cap C\right) ^{c}=A^{c}\cup B^{c}\cup C^{c}
\end{equation*}を得ます。共通部分と和集合の立場を逆にした場合にも、\begin{align*}
(A\cup B\cup C)^{c}& =(\left( A\cup B\right) \cup C)^{c}\quad \because \text{結合律} \\
& =\left( A\cup B\right) ^{c}\cap C^{c}\quad \because \text{ド・モルガンの法則} \\
& =\left( A^{c}\cap B^{c}\right) \cap C^{c}\because \text{ド・モルガンの法則} \\
& =A^{c}\cap B^{c}\cap C^{c}\quad \because \text{結合律}
\end{align*}すなわち、\begin{equation*}
(A\cup B\cup C)^{c}=A^{c}\cap B^{c}\cap C^{c}
\end{equation*}を得ます。
集合の個数を増やした場合にも同様の議論が成立します。つまり、有限\(n\)個の集合\(A_{1},\cdots ,A_{n}\)を任意に選んだとき、\begin{eqnarray*}&&\left( a\right) \ \left( A_{1}\cap \cdots \cap A_{n}\right)
^{c}=A_{1}^{c}\cup \cdots \cup A_{n}^{c} \\
&&\left( b\right) \ \left( A_{1}\cup \cdots \cup A_{n}\right)
^{c}=A_{1}^{c}\cap \cdots \cap A_{n}^{c}
\end{eqnarray*}すなわち、\begin{eqnarray*}
\left( a\right) \ \left( \bigcap_{i=1}^{n}A_{i}\right) ^{c}
&=&\bigcup_{i=1}^{n}A_{i}^{c} \\
\left( b\right) \ \left( \bigcup_{i=1}^{n}A_{i}\right) ^{c}
&=&\bigcap_{i=1}^{n}A_{i}^{c}
\end{eqnarray*}がともに成り立つということです。これは集合の個数\(n\)に関する数学的帰納法により証明できます（演習問題）。
&=&\bigcup_{i=1}^{n}A_{i}^{c} \\
\left( b\right) \ \left( \bigcup_{i=1}^{n}A_{i}\right) ^{c}
&=&\bigcap_{i=1}^{n}A_{i}^{c}
\end{eqnarray*}が成り立つ。
演習問題
A &=&\phi \\
B &=&\left\{ 2,4,6,\cdots \right\}
\end{eqnarray*}で与えられているものとします。このとき、ド・モルガンの法則\begin{equation*}
\left( A\cap B\right) ^{c}=A^{c}\cup B^{c}
\end{equation*}が成り立つことを確認してください。
A &=&\text{すべての母音からなる集合} \\
B &=&\text{すべての子音からなる集合}
\end{eqnarray*}で与えられているものとします。このとき、ド・モルガンの法則\begin{equation*}
\left( A\cap B\right) ^{c}=A^{c}\cup B^{c}
\end{equation*}が成り立つことを確認してください。
B^{c}\right) \cap \left( A^{c}\cup C^{c}\right)
\end{equation*}が成り立つことを示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】