クエリ: 一階述語論理とはなんですか?
文章: 一階述語論理 一階述語論理(いっかいじゅつごろんり、first-order predicate logic)とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理(にかいじゅつごろんり、second-order predicate logic)と呼ぶ。それにさらなる一般化を加えた述語論理を高階述語論理(こうかいじゅつごろんり、higher-order predicate logic)という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細は「二階述語論理」「高階述語論理」を参照。
文章: 記述計算量 記述計算量の最初の成果として、1974年にロナルド・フェイギンが示した Fagin の定理がある。これは、NPが存在量化二階述語論理の論理式で表現可能な言語の集合と正確に対応していることを示した。存在量化二階述語論理とは、関係・関数・部分集合について全称量化を行わない二階述語論理である。他の多くのクラスについても、主に Neil Immerman によって同様の特徴付けがなされた。以下に主なものを列挙する。 文章: 二階述語論理 standard semantics では、その種の集合や関数すべてに対しての量化と捉える。従って、一階の変項のドメインが明確化されれば、全ての量化の意味が固定される。これにより、二階述語論理の表現能力がもたらされる。 文章: 元 (数学) 形式論理に基づく現代的な集合論は、(相等関係 以外に)一つの記号(二項述語 )を含む一階述語論理で記述される。 文章: 有限モデル理論 有限モデル理論では、論理の有限な制限についても研究する。例えば、変項数を "k" 個に制限された一階述語論理などである。 文章: 高階述語論理 高階述語論理は表現能力が高いが、その特性、特にモデル理論に関わる部分では、多くの応用について性格が良いとは言えない。クルト・ゲーデルの業績により、古典的高階述語論理は(帰納的に公理化された)健全で完全な証明計算が認められないとされた。しかし、Henkin model によれば、健全で完全な証明計算は存在する。 文章: スコーレム標準形 メタレベルとしては、論理式 formula_26 の一階述語論理としての充足可能性は formula_36 と表され、ここで formula_27 がモデル、formula_28 が自由変項群の評価である。一階述語モデルは全関数シンボルの評価を含むので、任意のスコーレム関数 formula_26 は formula_40 によって暗黙のうちに存在量化される。結果として、ある変項への存在量化子を論理式の最初での関数群への存在量化子に置換し、それら存在量化子を除去することで、論理式を一階述語論理式のまま扱うことができる。この最後の段階での formula_33 を formula_29 として扱うことは、関数が formula_40 によって暗黙に存在量化されるという一階述語の充足可能性の定義によるものである。 文章: 一階述語論理 全称化規則とは、"x" が変数のとき、φ から ∀"x" φ を導出してよいという規則である。これは、論理式全体の集合の上の関係としては次のように定義することができる:(φ, φ) ∈ GEN であるとき、φ は φ からの全称化による導出であるという。 文章: 導出原理 一階述語論理での導出は mgu を用いて次のように表現できる。 文章: 一階述語論理 Σ を論理式の集合とし、φ を論理式とする。Σ に属するすべての論理式 ψ に対して "M"(ψ, "s") = 1 であるような任意の構造 "M" と "M" の個体の割り当て関数 "s" が "M"(φ, "s") = 1 をみたすとき、φ は Σ の論理的帰結 (logical consquence) であるといい、formula_1 と書く。論理式 φ と ψ が formula_2 かつ formula_3 をみたすとき、φ と ψ は論理的に同値 (logically equivalent) であるという。また、φ が の論理的帰結である場合、すなわち任意の構造 "M" と "M" の個体の割り当て関数 "s" に対して "M"(φ, "s") = 1 であるとき、φ は恒真 (valid) であるという。φ と ψ が論理的に同値であることは、(φ ψ) が恒真であることと同値である。 文章: ホーア論理 ホーア論理(ホーアろんり、)とは、公理的意味論の立場でプログラムの正当性について厳密に推論するために第一階述語論理を拡張した形式論理の言語を言う。 文章: 一階述語論理 推論規則とは、あるいくつかの論理式から別の論理式を導出するための規則である。これは正確には、論理式全体の集合の上の関係として定義される。推論規則には様々なものが考えられるが、ここで用いる推論規則はモーダス・ポーネンス (modus ponens) と呼ぶ規則と全称化 (generalization) と呼ぶ規則の二つである。 文章: 初等関数算術 EFAは(等号付き)一階述語論理の上の理論である。言語は次のものからなる: 文章: スコーレム標準形 一階述語論理の充足可能性は、関数シンボルの評価に対して暗黙のうちに存在量化を施すような定義になっているため、この等価性が役立つ。ここで、一階述語論理式 formula_26 は、モデル formula_27 が存在し、その論理式を「真」であると評価させるような自由変項の評価の組合せ formula_28 があるとき、充足可能である。このモデルには、全関数シンボルの評価も含まれるので、スコーレム関数も暗黙のうちに存在量化される。上記の例 formula_29 は、formula_29 が真となるような自由変項(この例では自由変項はない)の評価と formula_3 の評価を含むモデル formula_27 が存在するときのみ充足可能であると言える。これを二階述語論理で表すと formula_33 となる。上記の等価性により、これは formula_34 の充足可能性と同じである。 文章: 存在グラフ パースは述語を直観的な英語の語句で記述した。現代の論理学では一般にラテン文字の大文字が使われることが多い。点は、議論領域における何らかの個体の存在を主張するものである。同じオブジェクトの複数のインスタンスは線で結ばれ、これを "line of identity" と呼ぶ。一階述語論理での変項や量化子に相当する記法は存在しない。line of identity で複数の述語を繋いだものは、それら述語が共通の変数を共有していることを意味する。line of identity があるため、アルファグラフにおける同値規則を変更する必要がある。 文章: 二階述語論理 上記のうちドメインの部分集合だけを変項として追加したものを「単項二階述語論理(monadic second-order logic)」と呼ぶ。上記の全種の変項を追加した二階述語論理を「完全二階述語論理(full second-order logic)」と呼んで、単項版と区別することがある。