１＋１＝１になるとき。ブール代数、数理論理学、論理回路

ブール演算が扱う数は0と1の2つだけ。しかも位取くらいどりなし。つまり複数の桁を持たない。

0を偽に、1を真に、真理値として対応付けると、ブール演算を論理演算と同等に扱うことができる。その場合、偽はfalseの頭文字のF、真はtrueの頭文字のTと記されることがある。

あるいはまた、0をOFFに、1をONに、そしてまた、0を電圧の低さに、1を電圧の高さに対応付けることでブール演算をスイッチング演算と同様に見なすことができる。

集合演算もまた、これらと極めて近しい関係にあることを直感できるはず。

ちなみに数理論理学にはFとTに限られない2値以上の値を扱う多値論理演算がある。ここではそれらについては触れない。

ここでは数学としてよりもコンピューター科学としての目的に重きを置くため、ブール演算と2値論理演算とを同じものとして扱う。それらの定理の証明にはほとんど触れない。各々の論理演算は、コンピューターに使われているデジタル集積回路を構成するデジタル電子回路の基本単位となっている論理ゲートと呼ばれるものにそれぞれ対応している。

以下では、ブール演算のパターンと各々の真理値表、それらに対応する論理ゲートを表わすシンボルを記した。\( a, b, c, \cdots \)はここではブール変数を表わすものとする。

論理和 (OR)

ブール代数の加法は、与えられた数の内にどれか1つでも1が含まれていればその出力が必ず1になり、それ以外は0になる函数かんすうと見なすことができる。これに対応する論理演算は論理和。それはOR演算とも呼ばれ、\( a + b \)や\( a \vee b \)などと記されている。

ORは英語でorのこと。日本語では「または」という訳語が当てられていることが多いが、日本語の「または」には後に記す排他はいた的論理和の意味合いがあるので要注意。

\[ \begin{align*} 0 + 0 &= 0 \\ 0 + 1 &= 1 \\ 1 + 0 &= 1 \\ 1 + 1 &= 1 \end{align*} \]

論理和の真理値表は次のとおり。

論理和の真理値表

\( a \)	\( b \)	\( a + b \)
0	0	0
0	1	1
1	0	1
1	1	1

回路図では論理和演算がORゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

論理和は電気回路では並列回路に相当する。

論理積 (AND)

ブール代数の乗法は、1または0が揃った時にのみその出力が1になる函数と見なすことができる。これに対応する論理演算は論理積。それはAND演算とも呼ばれ、\( a \centerdot b \)や\( a \wedge b \)などと記されている。

ANDは英語でandのこと。日本語では「かつ」という訳語が当てられていることが多い。

\[ \begin{align*} 0 \centerdot 0 &= 0 \\ 0 \centerdot 1 &= 0 \\ 1 \centerdot 0 &= 0 \\ 1 \centerdot 1 &= 1 \end{align*} \]

論理積の真理値表は次のとおり。

論理積の真理値表

\( a \)	\( b \)	\( a \centerdot b \)
0	0	0
0	1	0
1	0	0
1	1	1

ちなみに、変数を使った表記では、通常の代数と同様にAND演算子の省略が次のように行われることがある。

\[ a b \]

回路図では論理積はANDゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

論理積は電気回路で直列回路に相当する。

論理否定 (NOT)

論理否定は、0が与えられれば1を出力し、1が与えられれば0を出力する函数と見なすことができる。英語ではthe complementと呼ばれているが、これは集合論で補集合を意味している。0か1しかないブール代数では、1の補集合は0となり、0の補集合は1となる。論理演算では論理否定はNOT演算とも呼ばれ、\( a^{\prime} \)や\( \overline{a} \)や\( \lnot a \)や\( \sim a \)などと記されている。

日本語では「ではない」という訳語が当てられていることがある。

\[ \begin{align*} \overline{0} &= 1 \\ \overline{1}&= 0 \end{align*} \]

論理否定の真理値表は次のとおり。

論理否定の真理値表

\( a \)	\( \overline{a} \)
0	1
1	0

回路図では論理否定はNOTゲートとして次のようなシンボルによって伝統的に記されてきた。ちなみにNOTゲートはインバーターとも呼ばれている。

あなたのブラウザはCanvas要素に対応していません。

以上のブール演算が最も基本となる論理演算として用いられている。この他にも次のような論理演算（論理ゲート）がある。

否定論理和 (NOR)

否定論理和は論理和を論理否定する論理演算。それは論理和の補集合を意味するので、\( \overline{a + b} \)や\( \lnot(a + b) \)と記されている。NOR演算子として\( a \downarrow b \)が用いられることがある。

\[ \begin{align*} 0 \downarrow 0 &= 1 \\ 0 \downarrow 1 &= 0 \\ 1 \downarrow 0 &= 0 \\ 1 \downarrow 1 &= 0 \end{align*} \]

否定論理和の真理値表は次のとおり。

否定論理和の真理値表

\( a \)	\( b \)	\( a \downarrow b \)
0	0	1
0	1	0
1	0	0
1	1	0

回路図では否定論理和がNORゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

否定論理積 (NAND)

否定論理積は論理積を論理否定する論理演算。それは論理積の補集合を意味しているので、\( \overline{a \centerdot b} \)や\( \lnot(a \centerdot b) \)と記されている。NAND演算子には\( a \uparrow b \)が用いられることがある。

\[ \begin{align*} 0 \uparrow 0 &= 1 \\ 0 \uparrow 1 &= 1 \\ 1 \uparrow 0 &= 1 \\ 1 \uparrow 1 &= 0 \end{align*} \]

否定論理積の真理値表は次のとおり。

否定論理積の真理値表

\( a \)	\( b \)	\( a \uparrow b \)
0	0	1
0	1	1
1	0	1
1	1	0

回路図では否定論理積がNANDゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

排他的論理和 (XOR/EOR)

排他はいた的論理和は、1同士、0同士のときに0（偽）になり、互いに不一致のときに1（真）になる論理演算。XOR演算子として\( a \oplus b \)や\( a \veebar b \)が用いられている。

\[ \begin{align*} 0 \oplus 0 &= 0 \\ 0 \oplus 1 &= 1 \\ 1 \oplus 0 &= 1 \\ 1 \oplus 1 &= 0 \end{align*} \]

排他的論理和の真理値表は次のとおり。

排他的論理和の真理値表

\( a \)	\( b \)	\( a \oplus b \)
0	0	0
0	1	1
1	0	1
1	1	0

回路図では排他的論理和はXORゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

排他的否定論理和 (XNOR/ENOR)

排他的否定論理和は排他的論理和を論理否定する論理演算。排他的論理和の補集合を意味するので、\( \overline{a \oplus b} \)と記されている。XNOR演算子として\( a \odot b \)が用いられることがある。

\[ \begin{align*} 0 \odot 0 &= 1 \\ 0 \odot 1 &= 0 \\ 1 \odot 0 &= 0 \\ 1 \odot 1 &= 1 \end{align*} \]

排他的否定論理和の真理値表は次のとおり。

排他的否定論理和の真理値表

\( a \)	\( b \)	\( a \odot b \)
0	0	1
0	1	0
1	0	0
1	1	1

回路図では排他的否定論理和はXNORゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

論理包含 (IMPLY)

論理包含は条件付き論理を意味している。IMPLY演算子は\( a \Rightarrow b \)と記されている。数理論理学の\( P \Rightarrow Q \)に等しい。日本語では「ならば」という訳語が当てられていることが多い。

Pが前件、Qが後件と呼ばれることがある。前件が0（偽）の場合は後件が0（偽）でも1（真）でもいずれも1（真）になる。

\[ \begin{align*} 0 \Rightarrow 0 &= 1 \\ 0 \Rightarrow 1 &= 1 \\ 1 \Rightarrow 0 &= 0 \\ 1 \Rightarrow 1 &= 1 \end{align*} \]

論理包含の真理値表は次のとおり。

論理包含の真理値表

\( a \)	\( b \)	\( a \Rightarrow b \)
0	0	1
0	1	1
1	0	0
1	1	1

回路図では論理包含はIMPLYゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

このシンボルを見ると分かるとおり、論理包含演算\( a \Rightarrow b \)は次のような論理和\( \overline{a} + b \)と等しい。論理和の片方の入力変数（独立変数、すなわち引数）を論理否定すると論理包含演算になる。

ブール代数の公理と定理

ブール代数には次のような公理またはその定理がある。

同一則 (Identity Law)

論理和では0が単位元。論理積では1が単位元。

\[ \begin{align*} 0 + a &= a \tag{1} \\ 1 \centerdot a &= a \tag{2} \end{align*} \]

単位元たんいげんとは、その演算対象になる数を変えることがない数。

可換則 (Commutative Law)

通常の代数と同様に和と積において交換法則が成り立つ。

\[ \begin{align*} a + b &= b + a \tag{1} \\ a \centerdot b &= b \centerdot a \tag{2} \end{align*} \]

分配則 (Distributive Law)

\[ \begin{align*} (a + b) \centerdot (a + c) &= a + (b \centerdot c) \tag{1} \\ (a \centerdot b) + (a \centerdot c) &= a \centerdot (b + c) \tag{2} \end{align*} \]

次のような定理を導き出すことができることがよく知られている。

対合則／二重否定則 (Involution Law / Double Negation Law)

二重の否定によって元に戻る。

\[ \begin{align*} \overline{\overline{a}} &= a \tag{1} \\ \overline{\overline{\overline{a}}} &= \overline{a} \tag{2} \end{align*} \]

ただし、三重の否定によってまた否定になる。一般に、偶数回の否定では肯定になり、奇数回の否定では否定になる。

有界則／破棄則 (Domination/Annulment Law)

論理和の吸収元は1、論理積の吸収元は0。

\[ \begin{align*} a + 1 &= 1 \tag{1} \\ a \centerdot 0 &= 0 \tag{2} \end{align*} \]

吸収元きゅうしゅうげんとは、演算によってすべての数をその数に変えてしまう吸血鬼やゾンビのような数のこと。

相補則 (Complement Law)

\[ \begin{align*} a \centerdot \overline{a} &= 0 \tag{1} \\ a + \overline{a} &= 1 \tag{2} \end{align*} \]

べき等則 (Idempotent Law)

同じ数同士の論理和も論理積もその同じ数になる。

\[ \begin{align*} a + a &= a \tag{1} \\ a \centerdot a &= a \tag{2} \end{align*} \]

\( a + a = a \)の証明は次のとおり。

\[ \begin{align*} a + a &= (a + a) \centerdot 1 \\ &= (a + a) \centerdot (a + \overline{a}) \\ &= a + a \centerdot \overline{a} \\ &= a + 0\\ &= a \end{align*} \]

吸収則 (Absorption Law)

\[ \begin{align*} a + (a \centerdot b) &= a \tag{1} \\ a \centerdot (a + b) &= a \tag{2} \\ \end{align*} \]

結合則 (Associative Law)

論理和同士または論理積同士ならば演算の順番が自由。

\[ \begin{align*} a + (b + c) &= (a + b) + c \tag{1} \\ a \centerdot(b \centerdot c) &= (a \centerdot b) \centerdot c \tag{2} \end{align*} \]

対偶則 (Contraposition Law)

\[ a \Rightarrow b = \overline{b} \Rightarrow \overline{a} \]

ド・モルガンの定理 (DeMorgan’s Law)

論理積全体の論理否定は論理否定同士の論理和と等しく、論理和全体の論理否定は論理否定同士の論理積と等しい。

\[ \begin{align*} \overline{a \centerdot b} &= \overline{a} + \overline{b} \tag{1} \\ \overline{a + b} &= \overline{a} \centerdot \overline{b} \tag{2} \end{align*} \]

あなたのブラウザはCanvas要素に対応していません。

ド・モルガンの定理は任意の数の変数においても通用する。

\[ \begin{align*} \overline{a \centerdot b} + \overline{c \centerdot d} &= \overline{a} + \overline{b} + \overline{c} + \overline{d} \tag{1} \end{align*} \] \[ \begin{align*} \overline{(a + b) \centerdot (c + d)} &= \overline{a} \centerdot \overline{b} + \overline{c} \centerdot \overline{d} \tag{2} \end{align*} \]

さらに二重否定の場合でも通用する。

\[ \begin{align*} \overline{(\overline{a} + b) \centerdot (c + \overline{d})} &= a \centerdot \overline{b} + \overline{c} \centerdot d \end{align*} \]

双対性 (Duality)

ブール代数の公理または定理で示された(1)式と(2)式との関係を見ると、互いに対になっていることが分かる。定数の0と定数の1とを互いに置き換え、論理和と論理積とを互いに置き換えると、(1)式が(2)式へ、(2)式が(1)式へと置き換わる。この性質は双対性そうついせいと呼ばれている。

機能的完全性 (Functional Completeness)

論理和(OR)と論理積(AND)と論理否定(NOT)は基本論理演算もしくは基本論理ゲートと呼ばれている。

否定論理和(NOR)と否定論理積(NAND)は実用論理演算もしくは実用論理ゲートと呼ばれている。

それだけを互いに接続して他の論理ゲートを作ることができる論理ゲートは汎用はんようゲート(Universal Gates)とも呼ばれている。

汎用ゲートの代表格として最も利用されているのがNANDゲートとNORゲート。NANDゲートはこれだけを組み合わせて他の論理ゲートや様々な論理関数を作り出すことができる。NORゲートも同様にこれだけを組み合わせて他の論理ゲートや様々な論理関数を作り出すことができる。

NANDゲートやNORゲートが持っているこのような万能な特質は機能的完全性と呼ばれている。

今回はここまで。さらに詳しくはまたの機会に。

関連記事

• HTML5 Canvasで基本論理ゲート記号を描いてみた