束縛変数と自由変数

$$(\forall x \in {\bf D})( {\bf P}(x,y))=\bigwedge_{x \in {\bf D}} {\bf P}(x,y)$$ (3.21)

$$(\exists x \in {\bf D})( {\bf P}(x,y))=\bigvee_{x \in {\bf D}} {\bf P}(x,y)$$ (3.22)

あるいは ${\bf D}$が有限集合

$${\bf D}=\{a_1,a_2,a_3,\cdots,a_n \}$$

の場合の，

$$(\forall x \in {\bf D})( {\bf P}(x,y)) ={\bf P}(a_1,y) \land {\bf P}(a_2,y) \land \cdots \land {\bf P}(a_n,y)$$ (3.23)

$$(\exists x \in {\bf D})( {\bf P}(x,y)) ={\bf P}(a_1,y) \lor {\bf P}(a_2,y) \lor \cdots \lor {\bf P}(a_n,y)$$ (3.24)

の$x$は見かけ上の変数にすぎない。このような変数を束縛変数(bound variable)と呼ぶ。束縛変数に対象を代入することはできない。 これとは逆に$y$のような本来の意味の変数 を自由変数(free variable)という。自由変数には対象を代入すること ができる。

述語 $x<y$ は2変数の述語であったが， $(\exists x)(x<y)$ や $(\forall x)(x<y)$ は$1$変数の述語であり，

$$(\exists y)(\exists x)(x<y), (\exists y)(\forall x)(x<y), (\forall y)(\exists x)(x<y), (\forall y)(\forall x)(x<y)$$

は$0$変数の述語，すなわち命題である。