命題論理

命題を、それ以上分解せずに真偽値だけで扱う論理体系。

$P$、$Q$ を原子命題とし、 論理演算子で組み合わせた式の真偽を調べる。

決定可能#

命題論理は真理値表で機械的に判定できる。 $n$ 個の原子命題なら $2^n$ 行の表を全部埋めればよい。

つまり原理的には必ず答えが出る（決定可能）。 ただし $2^n$ 行なので、$n$ が大きいと現実的でない。

充足可能性問題#

「その式を真にする割り当てが存在するか」が SAT。

• 最初に NP 完全性が示された問題（Cook-Levin の定理）
• 現代の SAT ソルバは数百万変数の実問題を解く
• 検証、プランニング、組合せ最適化の実装基盤

理論的に難しい（NP 完全）ことと、 実問題が解けることは両立する、という好例。

限界#

「すべての人間は死ぬ」のような内部構造を持つ命題を扱えない。 命題全体を 1 つの記号として見るしかないため。 これを扱うのが述語論理。

参考文献#

• Herbert B. Enderton. A Mathematical Introduction to Logic, 2nd ed. Academic Press, 2001. https://doi.org/10.1016/b978-0-08-049646-7.50005-9
• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html
• Stephen A. Cook. The complexity of theorem-proving procedures. STOC, 1971. https://doi.org/10.1145/800157.805047