=============================== ド・モルガンの法則 =============================== ド・モルガンの法則は集合論の基本的な法則です。この法則は、簡単なベン図を描いて考えることで直ぐに理解できると思います。ド・モルガンの法則は丸覚えではなく、わからないときはその度にベン図を描くことをお勧めします。 ド・モルガンの法則〜まずはここから〜 ======================================== ド・モルガンの法則は、和集合と共通集合をそれぞれの形に言い直すときに使う定理です。つまり、「または」の記号で表していた集合を、「かつ」の記号で表したりできるということを教えてくれる法則なのです(もちろん、「かつ」の記号で表していたものを「または」の記号で表すこともできますよ)。 全体集合 $S$ の部分集合である二つの集合 $A$ 、 $B$ に対して、ド・モルガンの定理はこのように表せます。 (A\cup B)^c &= A^c \cap B^c \tag{1}\\ (A\cap B)^c &= A^c \cup B^c \tag{2} では、最初は二つの集合 $A$ と $B$ を使って、「または」の記号で表した集合と「かつ」の記号で表した集合の関係について考えてみましょう。 (1)の場合 ------------ .. image:: (AcupB)complement.jpg まず、 $(1)$ をベン図で描くとこのようになります。上は $(1)$ の左辺、下はそれぞれ $A^c$ と $B^c$ です。下の二つ並んでいるベン図の(色がついている部分の)共通集合を考えれば、上の図と一致することは直ぐに分かりますね。また、ベン図を使わなくても、私たちの感覚としてこの法則を直感的に理解することもできます。例えば、あなたが友達の好みのケーキを買ってあげるとき、友達の嫌いなものがチョコレートと栗ならば「チョコレートを使っていなくて、かつ栗も使っていないものケーキ」すなわち「チョコレートもしくは栗を使っていないケーキ」を買わなければいけないと考えますよね。これは、まさにド・モルガンの法則です！ 今度は直感的な理解ではなく、集合の定義を使って証明してみましょう。 .. admonition:: proof $A^c=S-A$ であるので、 $x\in A^c\Leftrightarrow (x\in S$ かつ $x\notin A)$ であるのだから、 $x\in (A\cup B)^c\Leftrightarrow (x\in S$ かつ $x\notin (A\cup B))$ となる。 $x$ は $A$ または $B$ の要素ではないのだから、 $A$ の要素でもなく $B$ の要素でもないことになる。したがって、 $x\in (A\cup B)^c\Leftrightarrow (x\in S$ かつ $x\notin A)$ かつ $(x\in S$ かつ $x\notin A)\Leftrightarrow x\in A^c \cap B^c$ ■ $(2)$ に関しても、同じ手順でベン図を描いたり証明したりできますよね。 .. [*] 集合の等号が成り立つことを証明するには、 $A\subset B$ かつ $A\supset B$ を示すのが一般的ですが、今回の場合は命題の左辺を定義にしたがって書き換えることで証明するほうが分かりやすいですね。 ド・モルガンの法則〜一般的な記述〜 =============================== 二つの部分集合についてのド・モルガンの法則を考えましたが、この法則はもちろんもっとたくさんの部分集合についても成り立ちます。 \left( \bigcup _{\alpha \in \Lambda} A_{\alpha} \right) ^c &= \bigcap _{\alpha \in \Lambda} {A_{\alpha}}^c \tag{3}\\ \left( \bigcap _{\alpha \in \Lambda} A_{\alpha} \right) ^c &= \bigcup _{\alpha \in \Lambda} {A_{\alpha}}^c \tag{4} これはベン図を描いて理解することは難しいのですね。でも、上の二式が成り立つことを示すためには最初に行った証明と同じベクトルで証明を進めていけばいいのです。 (3)の場合 ---------------- .. admonition:: proof $x\in \left( \bigcup _{\alpha \in \Lambda} A_{\alpha} \right) ^c$ であるから、 $x$ はどの $A_{\alpha}$ にも含まれない要素である。つまり、 $x\in \Leftrightarrow \forall \alpha \in \Lambda;\ x\in {A_{\alpha}}^c\Leftrightarrow \bigcap _{\alpha \in \Lambda} {A_{\alpha}}^c$ ■ コラム〜論理演算でのド・モルガンの法則〜 ========================================= デジタル回路を作成するときに、論理演算(ブール演算)というものを考えます。デジタル回路では回路の入力・出力・状態をブール代数( $0$ 、 $1$ の二進数を使う代数)で表し、回路によってこの代数に演算(論理演算)を施して、所望の出力を得るという考え方をします。 つまり、デジタル回路は $0$ 、 $1$ で表す数に、和算、積算などの簡単な論理演算を繰り返し行っているだけの回路なのです。このため、複雑な動作をする回路を考えるときには、論理演算も簡単な演算をゴチャゴチャと繰り返さなければいけません。そんなゴチャゴチャしたものは、誰でも嫌になってきます。なので、回路を設計する前には、できるだけ簡単な論理演算を探す必要があります。 ここで、登場するのがド・モルガンの法則なのです。ブール代数の $1$ を集合の $A$ と考え、 $0$ を $A^c$ と考えれば、論理演算にド・モルガンの法則を適用できます！ 数学の集合よりもデジタル回路で考えるブール代数や論理演算はとても単純なものですが、これらはいくつかの集合の定理を基礎として成り立っています。今のコンピュータやデジタル機器が産声を上げたころには、集合の定理がデジタル回路の中で大活躍していたのです!! @@author: 黒子@@ @@accept: @@ @@category: @@ @@id:deMorgan@@