私が空腹なら、私は不機嫌である。
3.3 同値性と恒真性
目次
3.3.1 含意と対偶
次の二つの文章は同じことを言っているだろうか？
私が不機嫌でないなら、私は空腹でない。
二つの文章を命題論理で書き換えると、この質問に答えられる。\(P\) を命題「私は空腹である」、\(Q\) を命題「私は不機嫌である」とする。このとき一つ目の文章は「\(P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q\)」と書き換えられ、二つ目の文章は「\(\operatorname{\text{\footnotesize NOT}} (Q) \ \operatorname{\text{\footnotesize IMPLIES}}\ \operatorname{\text{\footnotesize NOT}} (P)\)」と書き換えられる。そして、真理値表を使えば両者を比較できる:
\[ \def\arraystretch{1.2}\begin{array}{cc|c|ccc} P & Q & P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q & \operatorname{\text{\footnotesize NOT}} (Q) & \ \operatorname{\text{\footnotesize IMPLIES}}\ & \operatorname{\text{\footnotesize NOT}} (P) \\ \hline \textbf{T} & \textbf{T} & \text{\LARGE\mathstrut} {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{F} & {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{F} \\ \textbf{T} & \textbf{F} & {\color{red}\text{\Large \(\textbf{F}\)}} & \textbf{T} & {\color{red}\text{\Large \(\textbf{F}\)}} & \textbf{F} \\ \textbf{F} & \textbf{T} & {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{F} & {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{T} \\ \textbf{F} & \textbf{F} & {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{T} & {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{T} \end{array} \]
強調した二つの列を見ると、注目していた二つの文章に対応する命題が常に同じ真理値を持つと分かる。「\(\operatorname{\text{\footnotesize NOT}} (Q) \ \operatorname{\text{\footnotesize IMPLIES}}\ \operatorname{\text{\footnotesize NOT}} (P)\)」の形をした命題を含意「\(P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q\)」の対偶 (contrapositive) と呼ぶ。真理値表からは、含意とその対偶が同値 ── 同じことを意味する異なる表現 ── だと分かる。
また、「\(Q \ \operatorname{\text{\footnotesize IMPLIES}}\ P\)」は含意「\(P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q\)」の逆 (converse) と呼ばれる。含意「私が空腹なら、私は不機嫌である」の逆は次の含意である:
私が不機嫌なら、私は空腹である。
この文章は元の文章と意味が異なるように思える。真理値表を書くと、その疑念が正しいと分かる:
\[ \def\arraystretch{1.2}\begin{array}{c|c|c|c} P & Q & P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q & Q \ \operatorname{\text{\footnotesize IMPLIES}}\ P \\ \hline \textbf{T} & \textbf{T} & \text{\LARGE\mathstrut} {\color{red}\text{\Large \(\textbf{T}\)}} & {\color{red}\text{\Large \(\textbf{T}\)}} \\ \textbf{T} & \textbf{F} & {\color{red}\text{\Large \(\textbf{F}\)}} & {\color{red}\text{\Large \(\textbf{T}\)}} \\ \textbf{F} & \textbf{T} & {\color{red}\text{\Large \(\textbf{T}\)}} & {\color{red}\text{\Large \(\textbf{F}\)}} \\ \textbf{F} & \textbf{F} & {\color{red}\text{\Large \(\textbf{T}\)}} & {\color{red}\text{\Large \(\textbf{T}\)}} \end{array} \]
強調した二つの列を見ると、一般に含意とその逆は同値でないことが確認できる。
最後にもう一つ: 含意とその逆が両方成り立つという命題は、含意の仮定と結論を \(\operatorname{\text{\footnotesize IFF}}\) で結んだ命題と同値である。例えば
私が不機嫌なら私は空腹である。そして私が空腹なら私は不機嫌である。
は、次の一つの文章と同じことを言っている:
私は不機嫌なとき、かつそのときに限って空腹である。
ここでも、この事実は真理値表を使って確認できる:
\[ \def\arraystretch{1.2}\begin{array}{cc|ccc|c} P & Q & (P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q) & \ \operatorname{\text{\footnotesize AND}} \ & (Q \ \operatorname{\text{\footnotesize IMPLIES}}\ P) & P \ \operatorname{\text{\footnotesize IFF}}\ Q \\ \hline \textbf{T} & \textbf{T} & \textbf{T} & \text{\LARGE\mathstrut} {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{T} & {\color{red}\text{\Large \(\textbf{T}\)}} \\ \textbf{T} & \textbf{F} & \textbf{F} & {\color{red}\text{\Large \(\textbf{F}\)}} & \textbf{T} & {\color{red}\text{\Large \(\textbf{F}\)}} \\ \textbf{F} & \textbf{T} & \textbf{T} & {\color{red}\text{\Large \(\textbf{F}\)}} & \textbf{F} & {\color{red}\text{\Large \(\textbf{F}\)}} \\ \textbf{F} & \textbf{F} & \textbf{T} & {\color{red}\text{\Large \(\textbf{T}\)}} & \textbf{T} & {\color{red}\text{\Large \(\textbf{T}\)}} \end{array} \]
この真理値表の四列目は次の論理式の真理値を示している:
\[ (P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q) \ \operatorname{\text{\footnotesize AND}} \ (Q \ \operatorname{\text{\footnotesize IMPLIES}}\ P) \]
そして、この列の値は最後の列が示す \(P \ \operatorname{\text{\footnotesize IFF}}\ Q\) の真理値と等しい。つまり含意とその逆の \(\operatorname{\text{\footnotesize AND}}\) は、含意の仮定と結論の \(\operatorname{\text{\footnotesize IFF}}\) と同値である。
3.3.2 恒真性と充足可能性
論理式が恒真 (valid) とは、命題変数にどんな値を割り当てても真になることを言う。恒真な論理式の最も単純な例を示す:
\[ P \ \operatorname{\text{\footnotesize OR}}\ \operatorname{\text{\footnotesize NOT}} (P) \]
恒真な論理式は基礎的な論理的真理を捉えていると考えられる。例えば「ある命題が別の命題を含意し、その別の命題がさらに別の命題を含意するとき、最初の命題は最後の命題を含意する」という性質は当然のものとして扱われている。この性質の正しさは次の論理式の恒真性によって確認できる:
\[ [(P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q) \ \operatorname{\text{\footnotesize AND}} \ (Q \ \operatorname{\text{\footnotesize IMPLIES}}\ R)] \ \operatorname{\text{\footnotesize IMPLIES}}\ (P \ \operatorname{\text{\footnotesize IMPLIES}}\ R) \]
論理式の同値性は恒真性の特殊ケースである。なぜなら、論理式 \(F\), \(G\) が同値になるのは \(F \ \operatorname{\text{\footnotesize IFF}}\ G\) が恒真のとき、かつそのときに限るからである。例えば、論理式 \(\text{(3.2)}\) と \(\text{(3.3)}\) の同値性は次の論理式の恒真性を意味する:
\[ (A \ \operatorname{\text{\footnotesize OR}}\ B) \ \operatorname{\text{\footnotesize IFF}}\ (A \ \operatorname{\text{\footnotesize OR}}\ (\operatorname{\text{\footnotesize NOT}} (A) \ \operatorname{\text{\footnotesize AND}} \ B)) \]
もちろん、恒真性を同値性の一種と捉えることもできる。つまり、論理式は \(\textbf{T}\) と同値なとき、かつそのときに限って恒真である。
論理式が充足可能 (satisfiable) とは、真になる場合がある ── 命題変数に特定の真理値を割り当てると真になる ── ことを言う。充足可能性が現れる問題の例として、複数の制約が存在する状況でシステムを構築する問題がある。全ての制約を \(\operatorname{\text{\footnotesize AND}}\) で結んだ論理式が充足可能でないとき、システムの構築はそもそも不可能となる (参照: 問題 3.17)。
恒真性と充足可能性の間にも密接な関係がある: 「論理式 \(P\) が充足可能」と「その否定 \(\operatorname{\text{\footnotesize NOT}} (P)\) が恒真でない」と同値である。