3.2 コンピュータープログラムにおける命題論理
命題と論理結合子はコンピュータープログラムで絶え間なく現れる。例えば、C とも C++ とも Java とも解釈できる次のコードを見てほしい:
\[ \begin{aligned} & \text{\texttt{if (x > 0 || (x <= 0 \&\& y > 100)) \{}} \\ & \text{\texttt{\quad \quad (\,\(\cdots\)\,何らかの命令\,\(\cdots\)\,)}} \\ & \text{\texttt{\}}} \end{aligned} \]
多くのプログラミング言語では記号列 \(\texttt{||}\) が \(\operatorname{\text{\footnotesize OR}}\) を表し、記号列 \(\texttt{\&\&}\) が \(\operatorname{\text{\footnotesize AND}}\) を表す。そして \(\texttt{(\,\(\cdots\)\,何らかの命令\,\(\cdots\)\,)}\) の部分は \(\texttt{if}\) に続く命題 (条件式) が真のときに限って実行される。上記のプログラムをよく見ると、長い条件式は二つの単純な命題から構成されることが分かる。つまり \(A\) を命題「\(\texttt{x > 0}\)」、\(B\) を命題「\(\texttt{y > 100}\)」と定めれば、条件式は次のように書き替えられる:
\[ A \ \operatorname{\text{\footnotesize OR}}\ (\operatorname{\text{\footnotesize NOT}} (A) \ \operatorname{\text{\footnotesize AND}} \ B) \tag{3.2}\]
真理値表を計算すると、複雑な論理式 \(\text{(3.2)}\) が次の単純な論理式と常に同じ真理値を持つと分かる:
\[ A \ \operatorname{\text{\footnotesize OR}}\ B \tag{3.3}\]
この事実を確認する手順を示す。まず、\(A\) と \(B\) の真理値の組み合わせだけを書き込んだ真理値表を作る:
\[ \def\arraystretch{1.2}\begin{array}{cc|ccccc|c} A & B & A & \operatorname{\text{\footnotesize OR}} & (\operatorname{\text{\footnotesize NOT}} (A) & \operatorname{\text{\footnotesize AND}} & B) & A \ \operatorname{\text{\footnotesize OR}}\ B \\ \hline \textbf{T} & \textbf{T} & & & & & & \\ \textbf{T} & \textbf{F} & & & & & & \\ \textbf{F} & \textbf{T} & & & & & & \\ \textbf{F} & \textbf{F} & & & & & & \end{array} \]
これら二つの値があれば、二つの列の値を埋められる:
\[ \def\arraystretch{1.2}\begin{array}{cc|ccccc|c} A & B & A & \operatorname{\text{\footnotesize OR}} & (\operatorname{\text{\footnotesize NOT}} (A) & \operatorname{\text{\footnotesize AND}} & B) & A \ \operatorname{\text{\footnotesize OR}}\ B \\ \hline \textbf{T} & \textbf{T} & & & \textbf{F} & & & \textbf{T} \\ \textbf{T} & \textbf{F} & & & \textbf{F} & & & \textbf{T} \\ \textbf{F} & \textbf{T} & & & \textbf{T} & & & \textbf{T} \\ \textbf{F} & \textbf{F} & & & \textbf{T} & & & \textbf{F} \end{array} \]
次は \(\operatorname{\text{\footnotesize AND}}\) の列が埋まる:
\[ \def\arraystretch{1.2}\begin{array}{cc|ccccc|c} A & B & A & \operatorname{\text{\footnotesize OR}} & (\operatorname{\text{\footnotesize NOT}} (A) & \operatorname{\text{\footnotesize AND}} & B) & A \ \operatorname{\text{\footnotesize OR}}\ B \\ \hline \textbf{T} & \textbf{T} & & & \textbf{F} & \textbf{F} & & \textbf{T} \\ \textbf{T} & \textbf{F} & & & \textbf{F} & \textbf{F} & & \textbf{T} \\ \textbf{F} & \textbf{T} & & & \textbf{T} & \textbf{T} & & \textbf{T} \\ \textbf{F} & \textbf{F} & & & \textbf{T} & \textbf{F} & & \textbf{F} \end{array} \]
これで、最後の \(\operatorname{\text{\footnotesize OR}}\) の列が埋められるようになった:
\[ \def\arraystretch{1.2}\begin{array}{cc|ccccc|c} A & B & A & \operatorname{\text{\footnotesize OR}} & (\operatorname{\text{\footnotesize NOT}} (A) & \operatorname{\text{\footnotesize AND}} & B) & A \ \operatorname{\text{\footnotesize OR}}\ B \\ \hline \textbf{T} & \textbf{T} & & \text{\LARGE\mathstrut} {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{F} & \textbf{F} & & {\color{red}\text{\Large \(\textbf{T}\)}} \\ \textbf{T} & \textbf{F} & & {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{F} & \textbf{F} & & {\color{red}\text{\Large \(\textbf{T}\)}} \\ \textbf{F} & \textbf{T} & & {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{T} & \textbf{T} & & {\color{red}\text{\Large \(\textbf{T}\)}} \\ \textbf{F} & \textbf{F} & & {\color{red}\text{\Large \(\textbf{F}\)}} & \textbf{T} & \textbf{F} & & {\color{red}\text{\Large \(\textbf{F}\)}} \end{array} \]
真理値が常に一致する二つの論理式は同値 (equivalent) であると言う。最後の真理値表で強調した二つの列は同一だから、対応する二つの論理式は同値である。つまり、上述のプログラムの条件式をより単純で同値な論理式に置き換えれば、プログラムの振る舞いを変化させずに単純化できる:
\[ \begin{aligned} & \text{\texttt{if (x > 0 || y > 100) \{}} \\ & \text{\texttt{\quad \quad (\,\(\cdots\)\,何らかの命令\,\(\cdots\)\,)}} \\ & \text{\texttt{\}}} \end{aligned} \]
論理式 \(\text{(3.2)}\) と論理式 \(\text{(3.3)}\) の同値性は場合分けを使った議論でも示せる:
[\(A\) が \(\textbf{T}\) のとき] 「\(\textbf{T} \ \operatorname{\text{\footnotesize OR}}\ \cdots\,\)」の形をした任意の論理式は真理値 \(\textbf{T}\) を持つ。\(A\) が \(\textbf{T}\) のとき、論理式 \(\text{(3.2)}\) と論理式 \(\text{(3.3)}\) は「\(\textbf{T} \ \operatorname{\text{\footnotesize OR}}\ \cdots\,\)」の形をしているので、どちらも同じ真理値 \(\textbf{T}\) を持つ。
[\(A\) が \(\textbf{F}\) のとき] 「\(\textbf{F} \ \operatorname{\text{\footnotesize OR}}\ \cdots\,\)」の形をした論理式は「\(\,\cdots\,\)」と同値である。よって \(A\) が \(\textbf{F}\) なら論理式 \(\text{(3.3)}\) は \(B\) と同値である。
さらに、「\(\textbf{T} \ \operatorname{\text{\footnotesize AND}} \ \cdots\,\)」の形をした論理式は「\(\,\cdots\,\)」と同値である。よって \(A\) が \(\textbf{F}\) のとき \(A \ \operatorname{\text{\footnotesize OR}}\ (\operatorname{\text{\footnotesize NOT}} (A) \ \operatorname{\text{\footnotesize AND}} \ B)\) は \(\operatorname{\text{\footnotesize NOT}} (A) \ \operatorname{\text{\footnotesize AND}} \ B\) と同値であり、\(B\) とも同値である。
よって論理式 \(\text{(3.2)}\) と論理式 \(\text{(3.3)}\) は同じ真理値 (具体的には \(B\) と同じ値) を持つ。
■
論理式の単純化は実用上の重要性を持つ情報科学の問題である。上述したようなプログラムに含まれる論理式の単純化ができれば、プログラムの読み書きが容易になる。さらに、論理式の単純化によって命令が減ればプログラムの実行が速くなる可能性もある。また、ハードウェアの設計では論理式の単純化によってチップ上の論理ゲートの個数が減少する。デジタル回路は論理式を使って表現できる (問題 3.6, 問題 3.7) ので、論理式を単純化すれば回路内のゲートも減少する。ゲートを減らすことの恩恵は非常に大きい: ゲートが少ないチップは高速であり、消費電力が抑えられ、欠陥率が低く、安価に生産できる。
Java などの言語は \(\operatorname{\text{\footnotesize AND}}\) と \(\operatorname{\text{\footnotesize OR}}\) を表すのに \(\texttt{\&\&}\) と \(\texttt{||}\) を使う。デジタル回路設計者は \(\cdot\) と \(\texttt{+}\) を使い、さらに \(\operatorname{\text{\footnotesize AND}}\) を「乗算」と呼び、\(\operatorname{\text{\footnotesize OR}}\)を「加算」と呼ぶ。数学者も次の表に示す異なる記法を使うことがある:
\[ \def\arraystretch{1.2}\begin{array}{ll} \quad\quad \textbf{英語} & \quad\quad \textbf{記号} \\ \hline \text{\Large\mathstrut}\operatorname{\text{\footnotesize NOT}} (P) & \lnot P,\ \overline{\mathstrut P} \\ P \ \operatorname{\text{\footnotesize AND}} \ Q & P \land Q \\ P \ \operatorname{\text{\footnotesize OR}}\ Q & P \lor Q \\ P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q & P \longrightarrow Q \\ P \ \operatorname{\text{\footnotesize IFF}}\ Q & P \longleftrightarrow Q \\ P \ \operatorname{\text{\footnotesize XOR}}\ Q & P \oplus Q \end{array} \]
例えば、この記法を使うと \((P \ \operatorname{\text{\footnotesize AND}} \ \operatorname{\text{\footnotesize NOT}} (Q)) \ \operatorname{\text{\footnotesize IMPLIES}}\ R\) は次のように書ける:
\[ (P \land \overline{\mathstrut Q}) \longrightarrow R \]
数学者が用いる記法は簡潔ではあるものの理解しにくい。「\(\operatorname{\text{\footnotesize AND}}\)」や「\(\operatorname{\text{\footnotesize OR}}\)」といった単語は覚えやすく、命題に関する演算であることがすぐに分かる。本書では \(\operatorname{\text{\footnotesize NOT}} (P)\) を \(\overline{\mathstrut P}\) と書く場合があることを除けば、基本的に単語を使った記法を使用する ── ただし論理式が複雑でページの幅に収まらないときは例外である。