もし全ての人間は死ぬ運命にあり、そして全てのギリシャ人は人間なら、全てのギリシャ人は死ぬ運命にある。
3.1 論理結合子
目次
私たちが普段読み書きする文章では、「 \(\cdots\) でない」「 \(\cdots\) かつ \(\cdots\) 」「 \(\cdots\) を意味する」「もし \(\cdots\) なら \(\cdots\) だ」といった言葉を使うことで命題の改変・結合・関連付けが行える。例えば、次の命題は三つの小さな命題から構成される:
これからしばらくは、命題の内容 ── 数学的表明なのか、ギリシャ人の不死性に関する記述なのか ── については考えず、命題がどのように組み合わさり関係付けられるかに注目する。そのため「全ての人間は死ぬ運命にある」や「\(2 + 3 = 5\)」といった特定の命題の代わりに変数 \(P\) や \(Q\) を用いる。こういった変数を命題変数 (propositional variable) と呼ぶ。つまり、命題変数は \(\textbf{T}\) (true, 真) と \(\textbf{F}\) (false, 偽) のいずれかを値に取る変数である。命題変数はブール変数 (Boolean variable) とも呼ばれる。この名称は考案者である十九世紀の数学者 George ── その通り ── Boole から来ている。
3.1.1 \(\small\text{AND}\), \(\small\text{NOT}\), \(\small\text{OR}\)
数学者は命題を改変・結合した結果を \(\operatorname{\text{\footnotesize NOT}}\), \(\operatorname{\text{\footnotesize AND}}\), \(\operatorname{\text{\footnotesize OR}}\) といった記号を使って表現する。こういった特別な記号を論理結合子 (logical connective) と呼び、リテラル \(\textbf{T}\), \(\textbf{F}\) と命題変数を論理結合子で適切に組み合わせた記号列を論理式 (logical formula) あるいは命題論理式 (propositional formula) と呼ぶ。論理結合子の正確な意味は真理値表 (truth table) で表される。例えば \(P\) が命題のとき、\(\operatorname{\text{\footnotesize NOT}} (P)\) も命題となる。そして \(\operatorname{\text{\footnotesize NOT}} (P)\) の値は \(P\) の値から次の真理値表の通りに定まる:
\[ \def\arraystretch{1.2}\begin{array}{c|c} P & \operatorname{\text{\footnotesize NOT}} (P) \\ \hline \textbf{T} & \textbf{F} \\ \textbf{F} & \textbf{T} \end{array} \]
表の最初の行からは、命題 \(P\) が真のとき命題 \(\operatorname{\text{\footnotesize NOT}} (P)\) は偽だと分かる。次の行からは、命題 \(P\) が偽のとき命題 \(\operatorname{\text{\footnotesize NOT}} (P)\) は真だと分かる。これはおそらくあなたの想像通りだろう。
一般に、真理値表は命題変数が取ることのできる値の組み合わせごとに特定の命題の真理値を示す。例えば、命題 \(P \ \operatorname{\text{\footnotesize AND}} \ Q\) は \(2\) 個の命題変数を持つので、それらの値の組み合わせが \(4\) 通りあるのに対応して \(P \ \operatorname{\text{\footnotesize AND}} \ Q\) の真理値表は \(4\) 個の行を持つ:
\[ \def\arraystretch{1.2}\begin{array}{cc|c} P & Q & P \ \operatorname{\text{\footnotesize AND}} \ Q \\ \hline \textbf{T} & \textbf{T} & \textbf{T} \\ \textbf{T} & \textbf{F} & \textbf{F} \\ \textbf{F} & \textbf{T} & \textbf{F} \\ \textbf{F} & \textbf{F} & \textbf{F} \end{array} \]
この表を見ると、命題 \(P \ \operatorname{\text{\footnotesize AND}} \ Q\) は \(P\) と \(Q\) が両方とも真のとき、かつそのときに限って真になると分かる。これは普段の文章で使う「and (かつ)」の多くと同じ意味である。
\(P \ \operatorname{\text{\footnotesize OR}}\ Q\) の真理値表には少し注意が必要な部分がある:
\[ \def\arraystretch{1.2}\begin{array}{cc|c} P & Q & P \ \operatorname{\text{\footnotesize OR}}\ Q \\ \hline \textbf{T} & \textbf{T} & \textbf{T} \\ \textbf{T} & \textbf{F} & \textbf{T} \\ \textbf{F} & \textbf{T} & \textbf{T} \\ \textbf{F} & \textbf{F} & \textbf{F} \end{array} \]
表の最初の行は、\(P\) と \(Q\) の両方が真のときも \(P \ \operatorname{\text{\footnotesize OR}}\ Q\) が真になることを示す。これは普段の文章で使う「or (または)」の意味と必ずしも一致しないものの、数学の文章ではこれが標準的な定義となっている。そのため数学者に「ケーキまたはアイスを食べていいよ」と言われた場合、あなたはケーキとアイスを両方食べて構わない。
ケーキとアイスを両方とも食べてはいけない場合は、次の排他的論理和 (exclusive-or operation, \(\operatorname{\text{\footnotesize XOR}}\)) が利用できる:
\[ \def\arraystretch{1.2}\begin{array}{cc|c} P & Q & P \ \operatorname{\text{\footnotesize XOR}}\ Q \\ \hline \textbf{T} & \textbf{T} & \textbf{F} \\ \textbf{T} & \textbf{F} & \textbf{T} \\ \textbf{F} & \textbf{T} & \textbf{T} \\ \textbf{F} & \textbf{F} & \textbf{F} \end{array} \]
3.1.2 \(\small\text{IFF}\)
数学者が命題を組み合わせるときに使う論理結合子の中には、普段の文章ではまず見られない方法で命題を組み合わせるものが一つある。命題「\(P \ \operatorname{\text{\footnotesize IFF}}\ Q\) (\(P\) if and only if \(Q\), \(P\) のとき、かつそのときに限って \(Q\))」は \(P\) と \(Q\) が同じ真理値を持つことを表す。この命題が正しいとき、\(P\) と \(Q\) は両方とも真であるか、そうでなければ両方とも偽である:
\[ \def\arraystretch{1.2}\begin{array}{cc|c} P & Q & P \ \operatorname{\text{\footnotesize IFF}}\ Q \\ \hline \textbf{T} & \textbf{T} & \textbf{T} \\ \textbf{T} & \textbf{F} & \textbf{F} \\ \textbf{F} & \textbf{T} & \textbf{F} \\ \textbf{F} & \textbf{F} & \textbf{T} \end{array} \]
例えば、\(\operatorname{\text{\footnotesize IFF}}\) が含まれる次の命題は全ての実数 \(x\) で真となる:
\[ x^{2} - 4 \geq 0 \ \operatorname{\text{\footnotesize IFF}}\ | x | \geq 2 \]
両方の不等式が真になる \(x\) の値もあれば、両方の不等式が偽になる \(x\) の値もある。しかし全ての場合で、\(\operatorname{\text{\footnotesize IFF}}\) を含んだ全体の命題は真となる。
3.1.3 \(\small\text{IMPLIES}\)
命題を組み合わせる論理結合子の中で正確な意味が最も分かりにくいのが「\(\operatorname{\text{\footnotesize IMPLIES}}\) (含意する)」である。その真理値表を次に示す。後から参照できるように各行にラベルを付けてある:
\[ \def\arraystretch{1.2}\begin{array}{cc|cc} P & Q & P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q & \\ \hline \textbf{T} & \textbf{T} & \textbf{T} & (\text{tt}) \\ \textbf{T} & \textbf{F} & \textbf{F} & (\text{tf}) \\ \textbf{F} & \textbf{T} & \textbf{T} & (\text{ft}) \\ \textbf{F} & \textbf{F} & \textbf{T} & (\text{ff}) \end{array} \]
\(\operatorname{\text{\footnotesize IMPLIES}}\) の真理値表は次の文章でまとめられる:
命題 \(P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q\) が真になるのは、仮定 \(P\) が偽のとき、または結論 \(Q\) が真のとき
この一文は記憶しておくに値する: 数学的な命題の大部分は「\(P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q\) (もし \(P\) が成り立つなら \(Q\) が成り立つ)」の形をしている！
この定義についてさらに考えよう。例えば、次の命題は真と偽のどちらだろうか？
もし Goldbach の予想が正しいなら、全ての実数 \(x\) で \(x^{2} \geq 0\)
以前に触れたように、Goldbach の予想 (予想 1.1.6) が正しいかどうかは誰にも分からない。しかしそうであっても、この命題の真偽は決定する！ \(P\) を命題「Goldbach の予想が正しい」と定め、\(Q\) を命題「全ての \(x\) で \(x^{2} \geq 0\) が成り立つ」と定めると、この命題は \(P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q\) の形をしている。そして結論 \(Q\) は正しいので、見るべきは真理値表の \(\text{(ft)}\) または \(\text{(ff)}\) の行である。つまり仮定が正しいかどうかに関係なく、全体の命題は真となる！
本章の最初で示した文章の真偽を考えてみよう:
ブタが空を飛べるなら、あなたのアカウントはハッキングされない。
ブタは忘れて、この命題の真偽だけを考える: ブタは空を飛べないから、ここで見るべきは真理値表の \((\text{ft})\) と \((\text{ff})\) の行である。つまり、結論の真偽に関わらず命題は真となる！
偽の仮定
論理的含意は仮定が偽のとき真になる。この数学的慣習に対して、一般的な言葉の使い方だと含意「 \(\cdots\) なら \(\cdots\) だ」は仮定と結論の間にある因果関係を意味することが多い。
例えば、多くの人は次の文章を正しいと感じるだろう:
セキュリティプロトコルに従えば、アカウントはハッキングされない。
なぜなら、セキュリティプロトコルとアカウントのハッキングの間に因果関係がある (と多くの人は考える) からである。
一方で、次の文章は正しくない、もしくは馬鹿げた文章だと受け取られる:
ブタが空を飛べるなら、あなたのアカウントはハッキングされない。
なぜなら、ブタの航空工学的特性とアカウントのハッキングの間には何の関係もない (と多くの人は考える) からである。しかし数学的には、この含意は真である。
論理的含意が因果関係を意味しない事実を受け入れることは重要である。このために論理的含意は因果関係より単純な条件となるものの、有用でなくなるわけではない。例えば、たくさん (\(1\) ダース) の規則1から構成される次のシステム仕様を考えてみてほしい:
\[ \begin{aligned} \text{もし、} & \text{システムセンサーが条件 } 1 \text{ を満たすなら、} \\ & \text{システムは操作 } 1 \text{ を実行する。} \\[3pt] \text{もし、} & \text{システムセンサーが条件 } 2 \text{ を満たすなら、} \\ & \text{システムは操作 } 2 \text{ を実行する。} \\ & \qquad \qquad \qquad \vdots \\ \text{もし、} & \text{システムセンサーが条件 } 12 \text{ を満たすなら、} \\ & \text{システムは操作 } 12 \text{ を実行する。} \end{aligned} \]
\(C_{i}\) を命題「システムセンサーが条件 \(i\) を満たす」、\(A_{i}\) を命題「システムが操作 \(i\) を実行する」と定めると、上の仕様は論理式を使って簡潔に表現できる:
\[ \begin{aligned} C_{1} &\ \operatorname{\text{\footnotesize IMPLIES}}\ A_{1} \\ C_{2} &\ \operatorname{\text{\footnotesize IMPLIES}}\ A_{2} \\ & \quad\ \vdots \\ C_{12} &\ \operatorname{\text{\footnotesize IMPLIES}}\ A_{12} \\ \end{aligned} \]
さらに、命題「システムは仕様通りに動作している」はこれらの論理式を \(\operatorname{\text{\footnotesize AND}}\) で連結するだけで得られる:
\[ \small [C_{1} \ \operatorname{\text{\scriptsize IMPLIES}}\ A_{1}] \ \operatorname{\text{\scriptsize AND}} \ [C_{2} \ \operatorname{\text{\scriptsize IMPLIES}}\ A_{2}] \ \operatorname{\text{\scriptsize AND}} \ \cdots \ \operatorname{\text{\scriptsize AND}} \ [C_{12} \ \operatorname{\text{\scriptsize IMPLIES}}\ A_{12}] \tag{3.1}\]
例えば \(C_{2}\) と \(C_{5}\) だけが真の状態で、システムが指定された操作 \(A_{2}\) と \(A_{5}\) を実行しているとしよう。このときシステムは仕様通りに動作しているので、論理式 \(\text{(3.1)}\) は真になることが期待される。論理的含意 \(C_{2} \ \operatorname{\text{\footnotesize IMPLIES}}\ A_{2}\) と \(C_{5} \ \operatorname{\text{\footnotesize IMPLIES}}\ A_{5}\) は仮定と結論が成り立っているために真である。論理式 \(\text{(3.1)}\) が真となるには、仮定が成り立っていない他の論理的含意が真にならなくてはいけないが、これはまさに数学における論理的含意の規則である。