命題論理 — トートロジーの世界

第2章 No.1 ／ 真理表で見る論理演算の体系

論理学では「真」(T)、「偽」(F) を入力として、論理演算 (AND, OR, NOT, ⊃, ⇔, XOR …) を組み合わせて命題を作る。命題が 常に真 であるとき、それを トートロジー (恒真式) という。

例えば「三段論法」

((P ⊃ Q) ∩ (Q ⊃ R)) ⊃ (P ⊃ R)

は、変数 P, Q, R がどんな組み合わせでも常に真となることが、真理表を書けば確かめられる。

主なトートロジー

• P ∪ ￢P   (排中律)
• ￢(P ∩ ￢P)   (矛盾律)
• P ⊃ ￢￢P, ￢￢P ⊃ P   (二重否定)
• (P ⊃ Q) ⇔ (￢Q ⊃ ￢P)   (対偶)
• (P ⊃ Q) ⇔ (￢P ∪ Q)   (含意の書き換え)

真理表の組み合わせは何通り？

P, Q を変数とする 2 変数論理の真理表は 2⁴ = 16 通り。我々が普段使うのはそのうちの数通りに過ぎない。

課題