論理式

• 述語記号と項から作られる式を原子論理式(atomic formula)という。

Q(f(x,c), g(f(c, d)))
は原子論理式である。

• 述語論理式(predicate formula)は、原子論理式と論理記号から作られる式である。
  • 命題論理の論理記号である¬,∧,∨,→,⇔などはそのまま使える。
  • ∀を全称記号(universal quantifier)、∃を存在記号(existential quantifier)、両者を併せて、量化記号(quantifier)もしくは限定子などという。

∀x∃yQ(x,y)

• 量化記号の後に書く記号を一階の変数に限るような述語論理を一階述語論理(first-order predicate logic)という。

この本における記号の優先順位は以下のような感じ。
∀,∃は¬と同じ優先順位
∀xP(x)∧Q(x,y) は、 (∀xP(x))∧Q(x,y) を意味する。
量化記号(と変数)の後ろに、. を付与した場合の結合力は他の論理記号より弱くなる。
∀x.P(x)∧Q(x,y) は、 ∀x(P(x)∧Q(x,y)) を意味する。