書記が数学やるだけ#905 述語論理の形式文法

述語論理の基本事項についてまとめていく。

問題

説明

一階述語論理の言語の構成要素：

・論理記号；変数，結合記号，量化記号，括弧，等号

・非論理記号；述語記号，関数記号，定数記号

項は何らかの対象を表す記号列、論理式は何らかの命題を表すものであり，以下のように帰納的に定義される。

論理式中の変数のうち、量化記号（∀, ∃）によって束縛されていない変数を自由変数、束縛されている変数を束縛変数という。特に自由変数をもたない論理式は「文（sentence）」「閉論理式 (closed formula)」と呼ばれる。

論理式 φ 中の変数 x に項 t を代入することを φ[t/x] と書く。このとき、代入によって項 t 中の変数が量化記号の影響を受けて意味が変わる（束縛される）おそれがない場合に限り、項 t は φ においてx へ代入可能であるという。

解答

項とは、対象を指し示す式であり、項と項を関数記号で結んだ記号列として構成される。

論理式とは、次のような記号列からなる。

• 項と項を等号で結んだ記号列（原子論理式）

• 項と項を述語記号で結んだ記号列

• 論理式を結合記号や量化記号で結んだ記号列

以下は項でも論理式でもない記号列の例である。

(1)の場合、論理式 ∀xP(x,y) の中では、変数 x は量化記号 ∀x によって束縛変数となっている。したがって、x に対して代入を行っても、その効果は量化の内側で打ち消されるため、実質的に代入は無意味となる（自由変数 x が存在しないため）。また、代入によって項 f(y) 中の変数 y が新たに束縛されることもない。よって、形式的には代入可能ではあるが、論理式の意味には変化を与えない。

(2)の場合、論理式 ∃yP(x,y) の中では、y は量化記号 ∃y によって束縛されている。代入 x:=y を行うと、項 t=y 中の変数 y が、量化記号 ∃y の作用域の中で束縛変数として扱われるため、代入によって自由変数 y が束縛されてしまう（いわゆる「変数の捕獲（variable capture）」が起こる）。したがって、この場合は代入不可能である。

本記事のもくじはこちら：