プログラミングのための「論理関数の基本法則」

はじめに

　この記事は N/S高等学校通学プログラミングコースに向けたものです。

　知っているとコンピュータの理解が深まるので論理関数の基本法則を紹介します。これらは全て覚えておく必要はありません。必要になったときに「そういえば、あんなものがあったなぁ」と思い出せるように知っておきましょう。

基本法則

　以下、参考文献の 27 ページからの一部改変して引用します。以下は論理演算ということに注意をしてください。
　$A,B$ に 0,1 を代入すると次の各恒等式が成立します。

1+A=1 \\
A+ \overline{A}=1 \\
A+A=A \\
\overline{\overline{A}}=A \\
0 \cdot A=0 \\
A \cdot \overline{A}=0 \\
A \cdot A=A \\
A \ge B ならば, \overline{A} \le \overline{B}

　また $A \oplus B=\overline{A} \cdot B + A \cdot \overline{B}$　を使うと、XOR に関する次の恒等式が成立する。

A \oplus 1=\overline{A} \\
A \oplus A=0 \\
A \oplus 0=A \\
A \oplus  \overline{A}=1

　これらから次の公式が成立する。

A+A \cdot B=A \\
A \cdot (\overline{A} + B)=A \cdot B \\
(A+B) \cdot (A+C)=A+B \cdot C \\
A \cdot X + B \cdot \overline{X} + A \cdot B=A \cdot X + B \cdot \overline{X} \\
A \cdot (A+B)=A \\
A  + \overline{A} \cdot B=A+B \\
(A+B) \cdot (A+ \overline{B})=A \\
(A+B) \cdot (\overline{A} + C)=A \cdot C + \overline{A} \cdot B

ド・モルガン(De Morgan)の定理（法則）

　以下は参考文献の 28 ページからの引用です。

$X=A+B$ ならば、$\overline{X}=\overline{A} \cdot \overline{B}$
$Y=A \cdot B$ ならば、$\overline{Y}=\overline{A} + \overline{B}$
この関数は多変数に対して成立するから、

\overline{A+B+C+\cdots}=\overline{A} \cdot \overline{B} \cdot \overline{C} \cdot \cdots \\
\overline{A \cdot B \cdot C \cdot \cdots}=\overline{A} + \overline{B} + \overline{C} + \cdots

　この 2 つの式をド・モルガン(De Morgan)の定理という。この定理は、式の変形にたいへん有用である。「屋根を分割し、$+$と$\cdot$を置き換える」として、容易に記憶できる。
　論理関数はすべて、論理積の論理和の形(AND-OR形)で表せる。これを論理関数の標準展開という。

　同じことを数学の教科書では次のように書いていることもあります。

\overline{A \cup B}=\overline{A} \cap \overline{B} \\
\overline{A \cap B}=\overline{A} \cup \overline{B} 

プログラミングへの適用例

　参考文献からの例をプログラミングに適用すると、どのようになるか見てみましょう。次のようにド・モルガンの定理を適用すると

(A+C) \cdot (\overline{\overline{A \cdot B} + \overline{A} \cdot C} + \overline{B})=(A+C) \cdot (A \cdot B \cdot \overline{\overline{A} \cdot C} + \overline{B}) \\
=(A+C) \cdot (A \cdot B \cdot (A + \overline{C}) + \overline{B}) \\
=(A+C) \cdot (A \cdot B + \overline{B}) \\
=A+ \overline{B} \cdot C

のようになります。これを変数 $a,b,c$ をブール型であるとして JavaScript で書くと

let a, b, c;
if ((a || c) && (!(!(a && b) || (!a && c)) || !b)) {
	...
}

は次のように簡潔に書くことが出来ます。

let a, b, c;
if (a || (!b && c)) {
	...
}

　注意点としては、素直に書いてある分、複雑な形の方がプログラムの意図をくみ取りやすい場合があります。そのような場合は相応の理由（処理速度が大きく変わるなど）がなければ読みやすい状態のままで構わないと思います。

双対の理

　もう一つの基本法則として「双対の理」があります。各自で調べてみましょう。

参考文献

松本　光功，井澤　裕司，「例題と演習で学ぶコンピュータ回路」、森北出版株式会社（1997/5/30）