論理式の充足

ウィキペディア小見出し辞書

論理式の充足

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/25 04:10 UTC 版)

「一階述語論理」の記事における「論理式の充足」の解説

上で見たように、自由変数を持たない論理式（すなわち文）は解釈（構造）を一つ与えることで、正しいか正しくないかが定まる。構造 M を与えたとき、文 φ が正しい命題になっているならば、φ は解釈 M において真 (true) であるといい、正しくない命題である場合、φ は M において偽 (false) であるという。以下で、これらの真偽の概念をより正確に定義する。ただし、論理式の真偽の定義にはいくつかの異なる（同値な）方法があり、ここで述べる定義はその内の一つである。 M が一階の言語に対する構造であるとき、変数全体の集合 V から M の領域 |M| への関数を、変数に対する M の個体の割り当て関数と呼ぶ。変数に対する M の個体の割り当て関数 s を一つとったとき、それぞれの項 t に対して、t の値 (value) t M(s) が次のように再帰的に定義される：変数 x に対しては、x M(s) = s(x) 。 定数記号 c に対しては、c M(s) = c M 。 t1 , ..., tn が項で、f がアリティ n の関数記号ならば、(f t1 … tn)M(s) = f M (t1M(s), ..., tnM(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 } を次のように再帰的に定義する：M(t1 = t2 , s) = 1 ⇔ t1M(s) = t2M(s) 。 P がアリティ n の非論理述語記号ならば、 M(P t1 … tn , s) = 1 ⇔ (t1M(s), ..., tnM(s)) ∈ P M 。 M((¬ φ), s) = 1 ⇔ M(φ, s) = 0 。 M((φ ∧ ψ), s) = 1 ⇔ M(φ, s) = 1 かつ M(ψ, s) = 1 。 M((φ ∨ ψ), s) = 1 ⇔ M(φ, s) = 1 または M(ψ, s) = 1 。 M((φ → ψ), s) = 1 ⇔ M(φ, s) = 0 または M(ψ, s) = 1 。 M((φ ↔ ψ), s) = 1 ⇔ M(φ, s) = M(ψ, s) 。 M(∀x φ, s) = 1 ⇔ すべての m ∈ |M| に対して M(φ, s[x|m]) = 1 。 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 は Σ のモデルであるという。