一階述語論理に関する定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 09:48 UTC 版)
「一階述語論理」の記事における「一階述語論理に関する定理」の解説
以下、健全性定理と完全性定理以外の重要な定理を列挙する。 コンパクト性定理 ： 文の集合 Σ のすべての有限部分集合がモデルを持つならば、Σ 自身もモデルを持つ。 レーヴェンハイム・スコーレムの定理 ： κ を無限基数とする。論理式全体の集合の濃度が κ であるような一階の言語における文の集合がモデルを持つなら、それは濃度 κ 以下のモデルも持つ。 恒真論理式全体の集合は（言語にアリティ 2 以上の述語が一つでも含まれていると）決定可能でない。つまり、任意に論理式が与えられたとき、それが恒真であるか否かを判定するアルゴリズムは存在しない（「チューリングマシンの停止問題」を参照）。この結果はアロンゾ・チャーチとアラン・チューリングがそれぞれ独立に導き出した。正確には、恒真論理式のゲーデル数全体の集合は帰納的でないということである。 それでも、与えられた論理式が恒真であるとき、かつそのときにのみ 1 (yes) を出力して停止するアルゴリズムは存在する。ただし、恒真でない論理式を入力した場合はこのアルゴリズムは停止しないかもしれない。これを、恒真論理式全体の集合は準決定可能であるという。これは正確に述べれば、恒真論理式のゲーデル数全体の集合が帰納的可算であるということである。 1 変数述語記号だけを非論理記号に持つ言語の恒真論理式全体の集合は決定可能である。
※この「一階述語論理に関する定理」の解説は、「一階述語論理」の解説の一部です。
「一階述語論理に関する定理」を含む「一階述語論理」の記事については、「一階述語論理」の概要を参照ください。
- 一階述語論理に関する定理のページへのリンク
