集合の基礎集合に関するド・モルガンの法則の証明、和集合、共通部分、補集合

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第2章(集合の基礎)、章末問題の2.3の解答を求めてみる。

任意のaに対して、

\begin{array}{l} a \in {(P \cap Q)}^{c} \\ \Leftrightarrow \neg (a \in P \cap Q) \\ \Leftrightarrow \neg (a \in P \land a \in Q) \\ \Leftrightarrow \neg (a \in P) \lor (\neg a \in Q) \\ \Leftrightarrow a \in P^{c} \lor a \in Q^{c} \\ \Leftrightarrow a \in P^{c} \cup a \in Q^{0} \end{array}

よって、

{(P \cap Q)}^{c} = P^{c} \cup Q^{c}

また、

\begin{array}{l} a \in {(P \cup Q)}^{c} \\ \Leftrightarrow \neg (a \in P \cup Q) \\ \Leftrightarrow \neg (a \in P \lor a \in Q) \\ \Leftrightarrow \neg (a \in P) \land \neg (a \in Q) \\ \Leftrightarrow a \in P^{c} \land a \in Q^{c} \\ \Leftrightarrow a \in P^{c} \cap Q^{c} \end{array}

よって、

{(P \cup Q)}^{c} = P^{c} \cap Q^{c}

計算機科学のブログ