一階述語論理 論理式の真偽

ウィキペディア

一階述語論理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/05/15 09:03 UTC 版)

論理式の真偽

構造

はじめに述べたように、一階述語論理の論理式の解釈は構造と呼ぶものによって与えられる。構造は変数が動く領域とそれぞれの非論理記号に対する "意味" の割り当てからなる。正式には、構造は次のように定義される。

一階の言語に対する構造 (structure) とは、空でない集合 $D$ と、非論理記号全体の集合を定義域とする関数 $F$ の組 $M=(D,\,F)$ で次をみたすものをいう：

1. $P$ がアリティ $n$ の述語記号ならば、$F(P)\subseteq D^{n}$ 、すなわち $F(P)$ は $D$ 上の $n$ 項関係である。
2. $f$ がアリティ $n$ の関数記号ならば、$F(f):D^{n}\to D$ 、すなわち $F(f)$ は $D$ 上の $n$ 項演算である。
3. $c$ が定数記号ならば、$F(c)\in D$ 、すなわち $F(c)$ は　$D$ のある要素である。

集合 $D$ を $M$ の領域 (universe, domain) と呼び、通常 $|M|$ で表す。また、$F(P)$ , $F(f)$ , $F(c)$ などは通常 $P^{M}$ , $f^{M}$ , $c^{M}$ と表される。

$M$ が一階の言語に対する構造であるとき、$M$ の領域 $|M|$ の要素を M の個体 (individual) と呼ぶ。

論理式の充足

上で見たように、自由変数を持たない論理式（すなわち文）は解釈（構造）を一つ与えることで、正しいか正しくないかが定まる。構造 M を与えたとき、文 φ が正しい命題になっているならば、φ は解釈 M において真 (true) であるといい、正しくない命題である場合、φ は M において偽 (false) であるという。以下で、これらの真偽の概念をより正確に定義する。ただし、論理式の真偽の定義にはいくつかの異なる（同値な）方法があり、ここで述べる定義はその内の一つである。

M が一階の言語に対する構造であるとき、変数全体の集合 V から M の領域 |M| への関数を、変数に対する M の個体の割り当て関数と呼ぶ。変数に対する M の個体の割り当て関数 s を一つとったとき、それぞれの項 t に対して、t の値 (value) t ^M(s) が次のように再帰的に定義される：

1. 変数 x に対しては、x ^M(s) = s(x) 。
2. 定数記号 c に対しては、c ^M(s) = c ^M 。
3. t₁ , ..., t_n が項で、f がアリティ n の関数記号ならば、(f t₁ … t_n)^M(s) = f ^M (t₁^M(s), ..., t_n^M(s)) 。

直観的には、項 t の値 t ^M(s) とは、各変数 x が Mの個体 s(x) を表すとしたとき、t が表す M の個体のことである。

次に、「構造 M が個体の割り当て関数 s によって論理式 φ を充足する」と言うことを定義する。M が s によって φ を充足するとは、各変数 x は s(x) を表すとし、各非論理記号は M によって与えられた意味を表すとしたとき、φ が正しい命題になっているということである。

M が一階の言語に対する構造であるとき、各論理式 φ と M の個体の割り当て関数 s に対して、M(φ, s) ∈ { 0, 1 } を次のように再帰的に定義する：

1. M(t₁ = t₂ , s) = 1 　⇔　 t₁^M(s) = t₂^M(s) 。
2. P がアリティ n の非論理述語記号ならば、　M(P t₁ … t_n , s) = 1　 ⇔　 (t₁^M(s), ..., t_n^M(s)) ∈ P ^M 。
3. M((¬ φ), s) = 1 　⇔　 M(φ, s) = 0 。
4. M((φ ∧ ψ), s) = 1 　⇔　 M(φ, s) = 1 かつ M(ψ, s) = 1 。
5. M((φ ∨ ψ), s) = 1 　⇔　 M(φ, s) = 1 または M(ψ, s) = 1 。
6. M((φ → ψ), s) = 1 　⇔　 M(φ, s) = 0 または M(ψ, s) = 1 。
7. M((φ ↔ ψ), s) = 1 　⇔　 M(φ, s) = M(ψ, s) 。
8. M(∀x φ, s) = 1 　⇔　 すべての m ∈ |M| に対して M(φ, s[x|m]) = 1 。
9. M(∃x φ, s) = 1 　⇔　 ある m ∈ |M| に対して M(φ, s[x|m]) = 1 。

ただし、s[x|m] は変数 x には m を割り当て、x 以外の変数に対しては s と同じ個体を割り当てる関数を表す。

M(φ, s) = 1 であるとき M は s によって φ を充足するという。

特に φ が文である場合は、すべての個体の割り当て関数 s に対して M(φ, s) = 1 であるか、すべての個体の割り当て関数 s に対して M(φ, s) = 0 であるかのいずれかであることが示される。そこで、前者の場合に φ は M において真であるといい、後者の場合に φ は M において偽であるという。すなわち、構造 M と文 φ に対して、

φ は M において真 (true) 　⇔　 任意の M の個体の割り当て関数 s に対して、M(φ, s) = 1 。

φ は M において偽 (false) 　⇔　 任意の M の個体の割り当て関数 s に対して、M(φ, s) = 0 。

と定義する。φ が M において真であるとき、M は φ のモデル (model) であるともいう。また、M が文の集合 Σ のすべての要素のモデルであるとき、単に M は Σ のモデルであるという。

論理的帰結

Σ を論理式の集合とし、φ を論理式とする。Σ に属するすべての論理式 ψ に対して M(ψ, s) = 1 であるような任意の構造 M と M の個体の割り当て関数 s が M(φ, s) = 1 をみたすとき、φ は Σ の論理的帰結 (logical consquence) であるといい、$\Sigma \vDash \varphi$ と書く。論理式 φ と ψ が $\{\varphi \}\vDash \psi$ かつ $\{\psi \}\vDash \varphi$ をみたすとき、φ と ψ は論理的に同値 (logically equivalent) であるという。また、φ が ∅ の論理的帰結である場合、すなわち任意の構造 M と M の個体の割り当て関数 s に対して M(φ, s) = 1 であるとき、φ は恒真 (valid) であるという。φ と ψ が論理的に同値であることは、(φ ↔ ψ) が恒真であることと同値である。