教材一覧
教材検索
SET

集合演算における双対原理

目次

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

集合の双対

集合演算子として\(c,\cap,\cup ,\backslash ,\triangle \)を定義しましたが、先に示したように\(\backslash \)と\(\triangle \)はともに\(c,\cap ,\cup \)によって言い換え可能であるため、結局、集合演算子として\(c,\cap ,\cup \)だけ与えられれば任意の集合を表現することができます。具体的には、集合\(A,B\)がそれぞれ任意に与えられたとき、\begin{eqnarray*}&&\left( a\right) \ A\backslash B=A\cap B^{c} \\
&&\left( b\right) \ A\triangle B=\left( A\backslash B\right) \cup \left(
B\backslash A\right)
\end{eqnarray*}などの関係が成り立つため、これらの関係を適用することにより、集合中の\(\backslash,\triangle \)を\(c,\cap ,\cup \)に置き換えることができます。

以上を踏まえると、集合\(A\)を任意に選んだとき、そこに含まれる可能性のある集合演算子を\(c,\cap ,\cup \)に限定しても一般性は失われません。その上で、集合\(A\)にして以下の操作を加えることにより得られる新たな集合を\(A\)の双対(dual)と呼びます。\begin{eqnarray*}&&\left( 1\right) \ A\text{中の}\cap \text{を}\cup \text{に入れ替え、}\cup \text{を}\cap
\text{に入れ替える。} \\
&&\left( 2\right) \ A\text{中の}U\text{を}\phi \text{に入れ替え、}\phi \text{を}U\text{に入れ替える。}
\end{eqnarray*}ただし、\(U\)は全体集合であり、\(\phi \)は空集合です。

例(双対)
集合\(A,B\)を被演算子とする集合\((A\cap B)\cup A\)の双対は\((A\cup B)\cap A\)です。
例(双対)
集合\(A,B\)を被演算子とする集合\(\left( A\cap B\right) \cup \left( A^{c}\cap B^{c}\right) \)の双対は\(\left( A\cup B\right)^{c}\cap \left( A^{c}\cup B^{c}\right) \)です。
例(双対)
集合\(A,B,C\)と全体集合\(U\)を被演算子とする集合\(\left( A^{c}\cap B\right) \cup \left( U\cap C^{c}\right) ^{c}\)の双対は\(\left( A^{c}\cup B\right) \cap \left( \phi\cup C^{c}\right) ^{c}\)です。

 

第1双対原理

集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合を、\begin{equation*}A\left( A_{1},\cdots ,A_{n},U,\phi \right)
\end{equation*}で表記します。集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)中の\(A_{1},\cdots,A_{n}\)を補集合\(A_{1}^{c},\cdots ,A_{n}^{c}\)に入れ替えることで得られる集合を、\begin{equation*}A\left( A_{1}^{c},\cdots ,A_{n}^{c},U,\phi \right)
\end{equation*}で表記し、さらにその補集合を、\begin{equation}
A^{c}\left( A_{1}^{c},\cdots ,A_{n}^{c},U,\phi \right) \quad \cdots (1)
\end{equation}で表記します。また、集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)の双対を、\begin{equation}A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) \quad \cdots (2)
\end{equation}で表記します。実は、\(\left( 1\right) \)と\(\left( 2\right) \)は常に一致します。まずは例を通じて確認しましょう。

例(第1双対原理)
集合\(A_{1},A_{2}\)と全体集合\(U\)および空集合\(\phi \)に関する集合が、\begin{equation}A\left( A_{1},A_{2},U,\phi \right) =A_{1}\cap A_{2} \quad \cdots (1)
\end{equation}で与えられているとき、その双対は、\begin{equation}
A^{D}\left( A_{1},A_{2},U,\phi \right) =A_{1}\cup A_{2} \quad \cdots (2)
\end{equation}となります。さて、\begin{eqnarray*}
A^{c}\left( A_{1}^{c},A_{2}^{c},U,\phi \right) &=&\left( A_{1}^{c}\cap
A_{2}^{c}\right) ^{c}\quad \because \left( 1\right) \\
&=&A_{1}\cup A_{2}\quad \because \text{ド・モルガンの法則} \\
&=&A^{D}\left( A_{1},A_{2},U,\phi \right) \quad \because \left( 2\right)
\end{eqnarray*}となるため、\begin{equation*}
A^{D}\left( A_{1},A_{2},U,\phi \right) =A^{c}\left(
A_{1}^{c},A_{2}^{c},U,\phi \right)
\end{equation*}という関係が成り立つことが示されました。つまり、論理式\(A\left( A_{1},A_{2},U,\phi \right) \)の双対は、この論理式中の集合\(A_{1},A_{2}\)を補集合\(A_{1}^{c},A_{2}^{c}\)に入れ替えて得られる集合の補集合と一致します。
例(第1双対原理)
集合\(A_{1},A_{2},A_{3}\)と全体集合\(U\)および空集合\(\phi \)に関する集合が、\begin{equation}A\left( A_{1},A_{2},A_{3},U,\phi \right) =\left( A_{1}\cap A_{2}^{c}\right)
\cup \left( A_{3}^{c}\cap U\right) \quad \cdots (1)
\end{equation}で与えられているとき、その双対は、\begin{equation}
A^{D}\left( A_{1},A_{2},A_{3},U,\phi \right) =\left( A_{1}\cup
A_{2}^{c}\right) \cap \left( A_{3}^{c}\cup \phi \right) \quad \cdots (2)
\end{equation}となります。さて、\begin{eqnarray*}
A^{c}\left( A_{1}^{c},A_{2}^{c},A_{3}^{c},U,\phi \right) &=&\left( \left(
A_{1}^{c}\cap A_{2}\right) \cup \left( A_{3}\cap U\right) \right) ^{c}\quad
\because \left( 1\right) \\
&=&\left( A_{1}^{c}\cap A_{2}\right) ^{c}\cap \left( A_{3}\cap U\right)
^{c}\quad \because \text{ド・モルガンの法則} \\
&=&\left( A_{1}\cup A_{2}^{c}\right) \cap \left( A_{3}^{c}\cup \phi \right)
\quad \because \text{ド・モルガンの法則} \\
&=&A^{D}\left( A_{1},A_{2},A_{3},U,\phi \right) \quad \because \left(
2\right)
\end{eqnarray*}となるため、\begin{equation*}
A^{D}\left( A_{1},A_{2},A_{3},U,\phi \right) =A^{c}\left(
A_{1}^{c},A_{2}^{c},A_{3}^{c},U,\phi \right)
\end{equation*}という関係が成り立つことが示されました。つまり、論理式\(A\left( A_{1},A_{2},A_{3},U,\phi \right) \)の双対は、この論理式中の集合\(A_{1},A_{2},A_{3}\)を補集合\(A_{1}^{c},A_{2}^{c},A_{3}^{c}\)に入れ替えて得られる集合の補集合と一致します。

以上の2つの例が示唆するように、一般に、集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)が与えられたとき、その双対に関して、\begin{equation*}A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) =A^{c}\left( A_{1}^{c},\cdots
,A_{n}^{c},U,\phi \right)
\end{equation*}という関係が成り立ちます。つまり、集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)の双対は、この集合中の\(A_{1},\cdots ,A_{n}\)を補集合\(A_{1}^{c},\cdots,A_{n}^{c}\)に置き換えて得られる集合の補集合と一致します。これを第1双対原理(first principleduality)や第1双対定理(first duality theorem)などと呼びます。証明では論理演算に関する第1双対原理を利用します。

命題(第1双対原理)
集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合\(A\left(A_{1},\cdots ,A_{n},U,\phi \right) \)が任意に与えられたとき、\begin{equation*}A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) =A^{c}\left( A_{1}^{c},\cdots
,A_{n}^{c},U,\phi \right)
\end{equation*}という関係が成り立つ。

証明

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

例(第1双対原理)
集合\(A,B\)を被演算子とする集合\(A\cap B\)が与えられたとき、第1双対原理より、その双対である\(A\cup B\)について、\begin{equation*}A\cup B=\left( A^{c}\cap B^{c}\right) ^{c}
\end{equation*}という関係が成り立ちます。これはド・モルガンの法則に他なりません。

例(第1双対原理)
集合\(A,B\)および全体集合\(U\)を被演算子とする集合\(A\cap \left( B^{c}\cup U\right) \)が与えられたとき、第1双対原理より、その双対である\(A\cup \left( B^{c}\cap \phi \right) \)について、\begin{equation*}A\cup \left( B^{c}\cap \phi \right) =\left( A^{c}\cap \left( B\cup U\right)
\right) ^{c}
\end{equation*}という関係が成り立ちます。実際、\begin{eqnarray*}
\left( A^{c}\cap \left( B\cup U\right) \right) ^{c} &=&A\cup \left( B\cup
U\right) ^{c}\quad \because \text{ド・モルガンの法則} \\
&=&A\cup \left( B^{c}\cap \phi \right) \quad \because \text{ド・モルガンの法則}
\end{eqnarray*}であることから確認できます。

例(第1双対原理)
集合\(A,B,C\)と全体集合\(U\)を被演算子とする集合\(\left( B\cap C^{c}\right) \cup \left( D^{c}\cap U\right) \)が与えられたとき、第1双対原理より、その双対である\(\left( B\cup C^{c}\right) \cap \left(D^{c}\cup \phi \right) \)について、\begin{equation*}\left( B\cup C^{c}\right) \cap \left( D^{c}\cup \phi \right) =\left( \left(
B^{c}\cap C\right) \cup \left( D\cap U\right) \right) ^{c}
\end{equation*}という関係が成り立ちます。実際、\begin{eqnarray*}
\left( \left( B^{c}\cap C\right) \cup \left( D\cap U\right) \right) ^{c}
&=&\left( B^{c}\cap C\right) ^{c}\cap \left( D\cap U\right) ^{c}\quad
\because \text{ド・モルガンの法則} \\
&=&\left( B\cup C^{c}\right) \cap \left( D^{c}\cup \phi \right) \quad
\because \text{ド・モルガンの法則}
\end{eqnarray*}であることから確認できます。

 

第2双対原理

集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合である\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)と\(B\left( A_{1},\cdots ,A_{n},U,\phi \right) \)の間に、\begin{equation*}A\left( A_{1},\cdots ,A_{n},U,\phi \right) \subset B\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{equation*}という関係が成り立つものとします。このとき、これらの集合の双対の間に、\begin{equation*}
B^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) \subset A^{D}\left(
A_{1},\cdots ,A_{n},U,\phi \right)
\end{equation*}が成り立つことが示されます。つまり、双対をとると包含関係が逆転するということです。これを第2双対原理(second principle duality)や第2双対定理(second duality theorem)などと呼びます。証明では先に示した第1双対原理を利用します。

命題(第2双対原理)
集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合である\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)と\(B\left( A_{1},\cdots ,A_{n},U,\phi \right) \)がそれぞれ任意に与えられたとき、\begin{equation*}A\left( A_{1},\cdots ,A_{n},U,\phi \right) \subset B\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{equation*}が成り立つ場合には、それらの双対の間に、\begin{equation*}
B^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) \subset A^{D}\left(
A_{1},\cdots ,A_{n},U,\phi \right)
\end{equation*}という関係が成り立つ。

証明

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

例(第2双対原理)
集合\(A,B\)に関して、\begin{equation*}A\cap B\subset A
\end{equation*}が成り立ちますが(確認してください)、このとき、第2双対原理より、\begin{equation*}
A\subset A\cup B
\end{equation*}もまた成り立つことが保証されます。実際、これは正しい主張です(確認してください)。

例(第2双対原理)
集合\(A,B\)に関して、\begin{equation*}\left( A\cap B\right) ^{c}\subset A^{c}\cup B^{c}
\end{equation*}が成り立ちますが(確認してください)、このとき、第2双対原理より、\begin{equation*}
A^{c}\cap B^{c}\subset \left( A\cup B\right) ^{c}
\end{equation*}もまた成り立つことが保証されます。実際、これは正しい主張です(確認してください)。

 

第3双対原理

集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合である\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)と\(B\left( A_{1},\cdots ,A_{n},U,\phi \right) \)の間に、\begin{equation*}A\left( A_{1},\cdots ,A_{n},U,\phi \right) =B\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{equation*}という関係が成り立つものとします。これは、\begin{eqnarray*}
A\left( A_{1},\cdots ,A_{n},U,\phi \right) &\subset &B\left( A_{1},\cdots
,A_{n},U,\phi \right) \\
B\left( A_{1},\cdots ,A_{n},U,\phi \right) &\subset &A\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{eqnarray*}がともに成り立つことを意味するため、第2双対原理より、\begin{eqnarray*}
B^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) &\subset &A^{D}\left(
A_{1},\cdots ,A_{n},U,\phi \right) \\
A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) &\subset &B^{D}\left(
A_{1},\cdots ,A_{n},U,\phi \right)
\end{eqnarray*}を得ます。これは、\begin{equation*}
A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) =B^{D}\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{equation*}であることを意味します。これを第3双対原理(third principle duality)や第3双対定理(third duality theorem)などと呼びます。つまり、集合\(A,B\)が等しいとき、それらの双対どうしも等しいことが保証されます。

命題(第3双対原理)
集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合である\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)と\(B\left( A_{1},\cdots ,A_{n},U,\phi \right) \)がそれぞれ任意に与えられたとき、\begin{equation*}A\left( A_{1},\cdots ,A_{n},U,\phi \right) =B\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{equation*}が成り立つ場合には、それらの双対の間に、\begin{equation*}
A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) =B^{D}\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{equation*}という関係が成り立つ。

例(双対原理)
ベキ等律とは、任意の集合\(A\)に対して、\begin{eqnarray*}\left( a\right) \ A\cap A &=&A \\
\left( b\right) \ A\cup A &=&A
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
交換律とは、任意の集合\(A,B\)に対して、\begin{eqnarray*}\left( a\right) \ A\cap B &=&B\cap A \\
\left( b\right) \ A\cup B &=&B\cup A
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
結合律とは、任意の集合\(A,B,C\)に対して、\begin{eqnarray*}\left( a\right) \ (A\cap B)\cap C &=&A\cap (B\cap C) \\
\left( b\right) \ (A\cup B)\cup C &=&A\cup (B\cup C)
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
分配律とは、任意の集合\(A,B,C\)について、\begin{eqnarray*}\left( a\right) \ A\cap (B\cup C) &=&(A\cap B)\cup (A\cap C) \\
\left( b\right) \ A\cup (B\cap C) &=&(A\cup B)\cap (A\cup C)
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
吸収律とは、任意の集合\(A,B\)について、\begin{eqnarray*}\left( a\right) \ A\cap \left( A\cup B\right) &=&A \\
\left( b\right) \ A\cup \left( A\cap B\right) &=&A
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\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*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
補集合法則とは、空集合\(\phi \)と全体集合\(U\)について、\begin{eqnarray*}&&\left( a\right) \ \phi ^{c}=U \\
&&\left( b\right) \ U^{c}=\phi
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。もう一つの補集合法則とは、任意の集合\(A\)について、\begin{eqnarray*}&&\left( c\right) \ A\cap A^{c}=\phi \\
&&\left( d\right) \ A\cup A^{c}=U
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(c\right) \)に双対原理を適用すれば\(\left( d\right) \)を得て、逆に、\(\left( d\right) \)に双対原理を適用すれば\(\left( c\right) \)を得ます。
例(双対原理)
恒等法則とは、任意の集合\(A\)について、\begin{eqnarray*}&&\left( a\right) \ A\cap \phi =\phi \\
&&\left( b\right) \ A\cup U=U
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。もう一つの補集合法則とは、任意の集合\(A\)について、\begin{eqnarray*}&&\left( c\right) \ A\cup \phi =A \\
&&\left( d\right) \ A\cap U=A
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(c\right) \)に双対原理を適用すれば\(\left( d\right) \)を得て、逆に、\(\left( d\right) \)に双対原理を適用すれば\(\left( c\right) \)を得ます。

次回からは集合族について学びます。

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

双対原理

命題論理における双対原理

論理的に同値な 2 つの論理式が与えられたとき、それらの双対をとるとそれらもまた論理的に同値となります。これを双対原理と呼びます。

DISCUSSION

質問とコメント

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