WIIS

集合

集合演算におけるド・モルガンの法則

目次

次のページ:

補集合法則

Mailで保存
Xで共有

ド・モルガンの法則

集合\(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) \)の主張です。

命題(ド・モルガンの法則)
任意の集合\(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*}が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(ド・モルガンの法則)
全体集合\(U\)および集合\(A,B\)がそれぞれ、\begin{eqnarray*}U &=&\left\{ 1,2,3,4,5,6,7,8,9,10\right\} \\
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*}が成立しています。これはド・モルガンの法則と整合的です。

例(ド・モルガンの法則)
集合\(A,B,C\)を任意に選んだとき、\begin{eqnarray*}&&A\backslash B \\
&&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*}がともに成り立ちます。

例(ド・モルガンの法則)
任意の集合\(A,B\)について、\begin{equation*}\left( A^{c}\cap B\right) ^{c}=A\cup B^{c}
\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\)のうちの少なくとも一方を満たさない対象からなる集合」であるということです。

例(ド・モルガンの法則)
「\(10\)以上かつ\(20\)以下の整数からなる集合」の補集合について考えます。集合\(A,B\)をそれぞれ、\begin{eqnarray*}A &:&10\text{以上の整数からなる集合} \\
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\)に関する数学的帰納法により証明できます(演習問題)。

命題(ド・モルガンの法則)
有限\(n\)個の集合集合\(A_{1},\cdots ,A_{n}\)が任意に与えられたとき、\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*}が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

演習問題

問題(ド・モルガンの法則)
全体集合\(U\)および集合\(A,B\)がそれぞれ、\begin{eqnarray*}U &=&\left\{ 1,2,3,\cdots \right\} \\
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*}が成り立つことを確認してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(ド・モルガンの法則)
全体集合\(U\)および集合\(A,B\)がそれぞれ、\begin{eqnarray*}U &=&\text{すべてのアルファベットからなる集合} \\
A &=&\text{すべての母音からなる集合} \\
B &=&\text{すべての子音からなる集合}
\end{eqnarray*}で与えられているものとします。このとき、ド・モルガンの法則\begin{equation*}
\left( A\cap B\right) ^{c}=A^{c}\cup B^{c}
\end{equation*}が成り立つことを確認してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(ド・モルガンの法則)
任意の集合\(A,B,C\)について、\begin{equation*}\left( A\cap \left( B\cup C\right) \right) ^{c}=\left( A^{c}\cup
B^{c}\right) \cap \left( A^{c}\cup C^{c}\right)
\end{equation*}が成り立つことを示してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(ド・モルガンの法則)
任意の集合\(A,B\)について、\begin{equation*}\left( \left( A\cap B^{c}\right) \cup \left( B\cap A^{c}\right) \right)
^{c}=\left( A^{c}\cap B^{c}\right) \cup \left( B\cap A\right)
\end{equation*}が成り立つことを示してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

関連知識

次のページ:

補集合法則

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員専用コンテンツです
ログイン】【会員登録