クエリ: 一階述語論理とはなんですか?
文章: 本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細は「二階述語論理」「高階述語論理」を参照。それにさらなる一般化を加えた述語論理を<b data-parsoid='{"dsr":[291,303,3,3]}'>高階述語論理(こうかいじゅつごろんり、higher-order predicate logic)という。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。一階述語論理 一階述語論理(いっかいじゅつごろんり、first-order predicate logic)とは、個体の量化のみを許す述語論理 (predicate logic) である。個体の量化に加えて述語や関数の量化を許す述語論理を<b data-parsoid='{"dsr":[198,210,3,3]}'>二階述語論理(にかいじゅつごろんり、second-order predicate logic)と呼ぶ。
文章: 一階述語論理 次に、「構造 M が個体の割り当て関数 s によって論理式 φ を充足する」と言うことを定義する。M が s によって φ を充足するとは、各変数 x は s(x) を表すとし、各非論理記号は M によって与えられた意味を表すとしたとき、φ が正しい命題になっているということである。 文章: 一階述語論理 φx [ t ] は、論理式 φ において "束縛されていない" 変数 x をすべて項 t で置き換えて得られる論理式を表すと述べた。正確には、φx [ t ] は再帰によって次に述べるような仕方で定義される。 文章: 一階述語論理 GEN = { (φ, ∀x φ) | φ は論理式かつ x は変数 } 。 文章: 二階述語論理 近年、二階述語論理は一種の回復の途上にある。この傾向をもたらしたのは George Boolos による二階の量化の解釈であり、彼は一階の量化と同じドメインでの複数形の量化として二階の量化を解釈した。Boolos はさらに一階述語論理では記述できない文を例に挙げ、完全な二階述語論理の量化でのみそれらを表現可能であるとした。しかし、その一部は二階述語論理を持ち出すまでもなく、一階述語論理に若干の拡張を加えるだけで表現可能である。 文章: 冠頭標準形 全ての一階述語論理の論理式には(古典論理では)論理的に等価な冠頭標準形の論理式が存在する。いくつかの変換規則を再帰的に適用することで、論理式を冠頭標準形に変換できる。規則は、論理式に出現する論理演算子の種類によって異なる。 文章: 一階述語論理 Σ φ Σ φ {\displaystyle \Sigma \vdash \varphi \Longrightarrow \Sigma \vDash \varphi } 文章: 計算木論理 CTL は一階述語論理の語彙を構成要素として利用し、それにさらに時相の様相作用素を交えた論理式を生成する。 文章: スコーレム標準形 トアルフ・スコーレムによるスコーレムの定理により、第一階述語論理における任意の論理式に対して、演繹的に等価(deductive equivalence)なスコーレム標準形の論理式が存在する。 文章: 導出原理 述語論理のリテラルには個体変数が含まれるため、リテラルと否定リテラルとを単純に比較するだけでは削除できるかどうか分からない。一階述語論理ではリテラルと否定リテラルそれぞれの原子論理式が単一化できる場合に導出を行う。 文章: 一階述語論理 コンパクト性定理 : 文の集合 Σ のすべての有限部分集合がモデルを持つならば、Σ 自身もモデルを持つ。 レーヴェンハイム・スコーレムの定理 : κ を無限基数とする。論理式全体の集合の濃度が κ であるような一階の言語における文の集合がモデルを持つなら、それは濃度 κ 以下のモデルも持つ。 恒真論理式全体の集合は(言語にアリティ 2 以上の述語が一つでも含まれていると)決定可能でない。つまり、任意に論理式が与えられたとき、それが恒真であるか否かを判定するアルゴリズムは存在しない(「チューリングマシンの停止問題」を参照)。この結果はアロンゾ・チャーチとアラン・チューリングがそれぞれ独立に導き出した。正確には、恒真論理式のゲーデル数全体の集合は帰納的でないということである。 それでも、与えられた論理式が恒真であるとき、かつそのときにのみ 1 (yes) を出力して停止するアルゴリズムは存在する。ただし、恒真でない論理式を入力した場合はこのアルゴリズムは停止しないかもしれない。これを、恒真論理式全体の集合は<b data-parsoid='{"dsr":[21696,21707,3,3]}'>準決定可能</b>であるという。これは正確に述べれば、恒真論理式のゲーデル数全体の集合が帰納的可算であるということである。 1 変数述語記号だけを非論理記号に持つ言語の恒真論理式全体の集合は決定可能である。 文章: 一階述語論理 数理論理学 コンパクト性定理 ゲーデルの完全性定理 ゲーデルの不完全性定理 Prolog 文章: 二階述語論理 standard semantics では、その種の集合や関数すべてに対しての量化と捉える。従って、一階の変項のドメインが明確化されれば、全ての量化の意味が固定される。これにより、二階述語論理の表現能力がもたらされる。 文章: 一階述語論理 全称化規則とは、x が変数のとき、φ から ∀x φ を導出してよいという規則である。これは、論理式全体の集合の上の関係としては次のように定義することができる: 文章: 二階述語論理 二階述語論理の文法から、どの式が整論理式かが示される。一階述語論理の文法に加えて、二階述語論理では変項に様々な「種(sort)」または「型(type)」がある。 文章: 一階述語論理 原子論理式は論理式である。 φ と ψ が論理式ならば、(¬ φ) , (φ ∧ ψ) , (φ ∨ ψ) , (φ → ψ) , (φ ψ) は論理式である。 φ が論理式で x が変数ならば、∀x φ , ∃x φ は論理式である。 上記の 1. と 2. と 3. によって論理式とされるものだけが論理式である。