集合の演算

4.集合の演算1

共通集合

\(A \cap B=\{x|x\in A \land x\in B\}\)

和集合

\(A \cup B=\{x|x\in A \lor x\in B\}\)

差集合

\(A \setminus B=\{x|x\in A \land x\notin B\}\)

直積集合

\(A×B=\{(a,b)|a\in A \land b\in B\}\)

補集合

\(A^c=U \backslash A=\{x|x\in U \land x\notin A\}\)
(\(U\)は全体集合)

5.集合の演算2

\(n\)個

\(\displaystyle\bigcup_{k=1}^{n}{A_k}=A_1 \cup A_2 \cup...\cup A_n \\ ~~~~~~~~~~ = \{x|\exists k\in \{1,2,...n\}(x\in A_k)\}\)
\(\displaystyle\bigcap_{k=1}^{n}{A_k}=A_1 \cap A_2 \cap...\cap A_n \\ ~~~~~~~~~~ = \{x|\forall k\in \{1,2,...n\}(x\in A_k)\}\)

無限個

\(\displaystyle\bigcup_{n=1}^{\infty }{A_n}=A_1 \cup A_2 \cup... = \{x|\exists n\in \mathbb{N}(x\in A_n)\}\)
\(\displaystyle\bigcap_{n=1}^{\infty}{A_n}=A_1 \cap A_2 \cap... = \{x|\forall n\in \mathbb{N}(x\in A_n)\}\)

6. 集合の主な演算法則

基本法則1

\( \overline U = \phi \\ \overline \phi =U\)

基本法則2

\( A \cap U = A\)    \(A \cap \phi = \phi\)
\( A \cup U = U\)    \(A \cup \phi \Leftrightarrow A\)

排中律,矛盾律から導かれる法則

\(A\cup A^c = U\)
\(A \cap A^c = \phi\)

二重否定の法則

\( (A^c)^c = A\)

巾等法則

\(A \cap A = A \\A \cup A = A\)

交換法則

\(A\cap B = B \cap A\)
\(A\cup B = B \cup A\)

結合法則

\((A\cap B) \cap C = A\cap ( B \cap C)\)
\((A\cup B) \cup C= A\cup ( B \cup C)\)

分配法則

\(A\cap (B \cup C) = (A\cap  B) \cup(B \cap C)\)
\(A\cup (B \cap C) = (A\cup B)\cap ( B \cup C)\)

分配法則 一般形

\(A\cap (\displaystyle\bigcup_{i\in I}{B_i}) =  \displaystyle\bigcup_{i\in I}{(A\cap B_i)}\)
\(A\cup (\displaystyle\bigcap_{i\in I}{B_i}) =  \displaystyle\bigcap_{i\in I}{(A\cup B_i)}\)

吸収法則

\(A\cap (A \cup B) = A\)
\(A\cup (A \cap B)= A\)

ドモルガンの法則

\( (A\cap B)^c =   A^c \cup B^c \\  (A\cup B)^c = (A)^c \cap (B)^c\)

述語論理による証明の例1

\(A=B\)とは
\(x\in A \Leftrightarrow x\in B\)であった

\(x \in  (A\cap B)^c  \Leftrightarrow x\in U \land x\notin A\cap B \\~~~~~~~~~~~~~~~~\, \Leftrightarrow x\in U \land \lnot (x\in A \cap B) \\~~~~~~~~~~~~~~~~\, \Leftrightarrow x\in U \land \lnot (x\in A \land x\in B)\\~~~~~~~~~~~~~~~~\, \Leftrightarrow x\in U \land (x\notin A \land x\notin B) \\ ~~~~~~~~~~~~~~~~\,\Leftrightarrow (x\in U \land x\notin A)\lor (x\in U \land x\notin B)\\ ~~~~~~~~~~~~~~~~\,\Leftrightarrow x\in A^c \lor x\in B^c\\ ~~~~~~~~~~~~~~~~\,\Leftrightarrow x\in A^c \cup B^c\)

よって\(  (A\cap B)^c =   A^c \cup B^c\)

ドモルガンの法則 一般形

\(( \displaystyle\bigcup_{k=1 }^{n}{A_k})^c =  \displaystyle\bigcap_{k=1}^{n}{{A_k}^c} \\ ( \displaystyle\bigcap_{k=1}^{n}{A_k})^c =  \displaystyle\bigcup_{k=1}^{n}{{A_k}^c}\)

部分集合の性質

\(A \subset B  \)
\( \Leftrightarrow  B^c \subset A^c~~~~~~\)
\(\Leftrightarrow A \setminus B=\phi\)
\(\Leftrightarrow  A\cap B=A\)
\(\Leftrightarrow A\cup B=B\)

述語論理による証明の例2

\(~~~~~~~A \subset B \Leftrightarrow \forall x(x\in A \rightarrow x\in B) \\~~~~~~~~~~~~~~~~\, \Leftrightarrow \forall x(x\notin A \lor x\in B)\\~~~~~~~~~~~~~~~~\, \Leftrightarrow \forall x\lnot (x\in A \land x\notin B) \\ ~~~~~~~~~~~~~~~~\,\Leftrightarrow \forall x\lnot (x\in A\setminus B)\\ ~~~~~~~~~~~~~~~~\,\Leftrightarrow \forall x (x\notin A\setminus B)\\ ~~~~~~~~~~~~~~~~\,\Leftrightarrow A \setminus B=\phi\)

よって\( A \subset B \Leftrightarrow   A \setminus B=\phi\)

差集合の性質

\(B\setminus A= A^c \cap B\)

直積集合の相等

\((a,b)=(a',b')\Leftrightarrow a=a'\land b=b'\)

直積集合の性質

\(A\times (B \cap C)=(A\times B)\cap (A\times C)\)
\(A\times (B \cup C)=(A\times B)\cup (A\times C)\)
\( (B \cap C)\times A=(B\times A)\cap (C\times A)\)
\( (B \cup C)\times A=(B\times A)\cup (C\times A)\)

7. 集合族の主な演算法則

任意の集合族\(\{A_\lambda\}_{\lambda \in \Lambda}\)と集合\(B\)に対して以下が成り立つ

集合族の和集合と共通部分

\(\displaystyle\bigcup_{\lambda \in \Lambda}{A_\lambda}= \{x|\exists \lambda\in \Lambda(x\in A_\lambda)\}\)
\(\displaystyle\bigcap_{\lambda \in \Lambda}{A_\lambda}= \{x|\forall \lambda \in \Lambda (x\in A_\lambda)\}\)

集合族の結合法則

\( (\displaystyle\bigcup_{\lambda\in \Lambda}{A_\lambda})\cup B =  \displaystyle\bigcup_{\lambda\in \Lambda}{(A_\lambda\cup B)}\)
\( (\displaystyle\bigcap_{\lambda\in \Lambda}{A_\lambda})\cap B =  \displaystyle\bigcap_{\lambda\in \Lambda}{(A_\lambda\cap B)}\)

集合族の分配法則

\( (\displaystyle\bigcup_{\lambda\in \Lambda}{A_\lambda})\cap B =  \displaystyle\bigcup_{\lambda\in \Lambda}{(A_\lambda\cap B)}\)
\( (\displaystyle\bigcap_{\lambda\in \Lambda}{A_\lambda})\cup B =  \displaystyle\bigcap_{\lambda\in \Lambda}{(A_\lambda\cup B)}\)

集合族のドモルガンの法則

\( ( \displaystyle\bigcup_{\lambda\in \Lambda}{A_\lambda})^c =  \displaystyle\bigcap_{\lambda\in \Lambda}{{A_\lambda}^c} \\  (\displaystyle\bigcap_{\lambda\in \Lambda}{A_\lambda})^c =  \displaystyle\bigcup_{\lambda\in \Lambda}{{A_\lambda}^c}\)