北田 発見への道 5章

5章 述語計算の無矛盾性

今度は述語計算。統語論を定め、推論規則を3つ(MP, GEN, SPEC)提示し、命題論理の公理系11こを引き継ぎ、新たに4つの公理を追加する。

真理値の付与は命題論理の場合よりやや複雑になる。すなわち命題の真理値は、述語関数の意味と、述語関数に渡す定項の意味を与える必要がある。例として 「∃b A(a,b) 」の真理値の付与で、変数の変域が {zero,one} の場合を考える。二変数述語は、引数として、(zero,zero), (zero,one), (one,zero), (one,one) の４通りに対して、どのような真理値を与えるかを考え 2^4 = 16 種類の述語が存在することがわかる。「∃b A(a,b)」はAとしてこの16種類のどの述語に対しても、そして、任意のa への付値（すなわち zero もしくは one）に対しても、その真理値が 1 であるかを分析する。実際には充足はするものの、恒真でないことがわかる。

述語論理の無矛盾性は命題論理の時と同様に示される。すなわち、全ての公理＝11の命題計算の公理＋4つの追加された公理が恒真であることを示す。そののち、3つの推論規則MP, GEN, SPEC に対して真理値が保存されることを示す。これにより全ての定理が恒真であることが示されるので、矛盾式が定理でないことがわかり、無矛盾性が確かめられる。

注：上記の無矛盾性の議論は変数の領域が有限の場合にのみ有効であり、例えば領域がNの場合にどのようになるかは次章で説明する。

上記了解。少し複雑になっただけで、特に引っかかる部分はないかな。野矢先生は述語論理の場合は恒真式ではなく、妥当式と言っていた気がするが・・・まぁいいか。