真理値表で命題をとらえる
第2章 No.0.5 ／ AND・OR・NOT・含意・XOR
以下の命題を考えよう。
「太郎は人間である」かつ「人間は空を飛べない」ならば、「太郎は空を飛べない」
このように「 」で囲まれた一つ一つを 命題 という。実は、この文章全体も一つの命題である。論理学では各演算に対して、以下の記号を使う。
| 演算 | 意味 | 記号 |
|---|---|---|
| かつ | 論理積、連言 | AND, /\, ∩ |
| または | 論理和、選言 | OR, \/, ∪ |
| 〜でない | 否定 | NOT, ~, ￢ |
| 〜ならば〜 | 含意 | ⇒, ⊃ |
| 同等 | 同等 | ⇔ |
上のほかに、口語ではあまり使わないが XOR (排他的論理和) もある。「ならば」を表現する ⊃ は、集合論で用いる「包含関係」とは無関係であることに注意しよう。
正確には、論理学は「太郎」「人間」といった具体的な値を代入して扱うのが目的ではなく、それらを変数 (P, Q や、X, Y など) におきかえてそれらの記号を使った 演算の体系 を追求する学問 (代数学) である。無味乾燥した記号 P, Q により表された命題に対して、実際に「太郎」「人間」という値を代入することを 解釈 という。
「P ⊃ Q」という命題は、「￢P ∪ Q」に等しいことが知られている。具体的にそれらの関係を示すために、真理表を定めてみよう (以下、「真」を T、「偽」を F とする)。
| P | Q | ￢P | P ∩ Q | P ∪ Q | P ⊃ Q | P XOR Q | P ⇔ Q |
|---|---|---|---|---|---|---|---|
| T | T | F | T | T | T | F | T |
| T | F | F | F | T | F | T | F |
| F | T | T | F | T | T | T | F |
| F | F | T | F | F | T | F | T |
実はこの表は 24 = 16 通り あることがわかる。ここではそのうちの 5 通りを示したに過ぎない。
XOR は2回適用すると元に戻る
XOR (排他的論理和) は 2 度適用すると元に戻る論理演算として知られている。そのため、カーソルの表示の際に用いられる。
| P | Q | P XOR Q | (P XOR Q) XOR Q |
|---|---|---|---|
| T | T | F | T |
| T | F | T | T |
| F | T | T | F |
| F | F | F | F |
これより (P XOR Q) XOR Q = P であることがわかる。
三段論法はトートロジー
もうすこし真理表を眺めてみよう。以下の命題はどうだろうか。
((P ⊃ Q) ∩ (Q ⊃ R)) ⊃ (P ⊃ R)
| P | Q | R | P⊃Q | Q⊃R | (P⊃Q)∩(Q⊃R) | P⊃R | 結論 |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
これにより、命題 ((P ⊃ Q) ∩ (Q ⊃ R)) ⊃ (P ⊃ R) は変数 P, Q, R が「真」「偽」のどちらであっても必ず「真」になることがわかる。このような命題を 恒真式 または トートロジー という。これは「三段論法」として知られ、ここで説明した論理を 命題論理 という。
課題
以下の式は、トートロジーかどうかを真理表を書いて調べよ。
- P ∩ P
- (P ⊃ Q) ⊃ (￢Q ⊃ ￢P)
- P ⊃ ￢￢P
- (￢P ⊃ ￢Q) ⊃ ((￢P ⊃ Q) ⊃ P)