基本的な性質

$\forall$ や $\exists$ の基本的性質を調べていく。 ここで簡単のため${\bf D}$を有限集合

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

としておく。

$b \in {\bf D}$は $a_1,a_2,a_3,\cdots,a_n$ のどれかと一致するはずであるから$b=a_k$としておく。

定義と定理$1.2$のド・モルガン則，交換則を使えば

$$\begin{eqnarray*} &&(\forall x \in {\bf D})( {\bf P}(x)) \Rightarrow {\bf P}(a_... ... {\bf P}(a_k) \cdots \lor \lnot {\bf P}(a_n) \lor {\bf P}(a_k) \end{eqnarray*}$$

$$= \lnot {\bf P}(a_1) \lor \lnot {\bf P}(a_2) \lor \cdots \lor \ln... ...{k+1}) \cdots \lor \lnot {\bf P}(a_n) \lor \lnot {\bf P}(a_k) \lor {\bf P}(a_k)$$

$$= \lnot {\bf P}(a_1) \lor \lnot {\bf P}(a_2) \lor \cdots \lor \ln... ...f P}(a_{k-1}) \lor \lnot {\bf P}(a_{k+1}) \cdots \lor \lnot {\bf P}(a_n) \lor T$$

$$=T$$ (3.26)

結局，任意の対象 $b \in {\bf D}$ に対し

$$(\forall x)({\bf P}(x)) \Rightarrow {\bf P}(b)$$ (3.27)

は恒真論理式である。

次にすべての$i$について

$$A \Rightarrow {\bf P}(a_i)$$

が恒真論理式ならば，

$$A \Rightarrow (\forall x \in {\bf D})( {\bf P}(x))$$

$$= \lnot A \lor \Bigl( {\bf P}(a_1) \land {\bf P}(a_2) \land \cdots \land {\bf P}(a_n) \Bigr )$$

$$= (\lnot A \lor {\bf P}(a_1)) \land ( \lnot A \lor {\bf P}(a_2)) \land \cdots \land (\lnot A \lor {\bf P}(a_n) )$$

$$=T \land \cdots \land T$$

$$=T$$ (3.28)

よって 任意の対象 $b \in {\bf D}$ に対し $A \Rightarrow {\bf P}(b)$ が恒真論理式ならば

$$A \Rightarrow (\forall x)({\bf P}(x))$$

$$(ただしA は任意の命題)$$ (3.29)

も恒真論理式である。

また 定義と定理$1.2$のド・モルガン則，交換則を使えば

$$\begin{eqnarray*} &&{\bf P}(a_k) \Rightarrow (\exists x \in {\bf D})( {\bf P}(x... ...bf P}(a_2) \cdots \lor {\bf P}(a_k) \cdots \lor {\bf P}(a_n) \end{eqnarray*}$$

$$= \lnot {\bf P}(a_k) \lor {\bf P}(a_k) \lor {\bf P}(a_1) \lor {\b... ...lor \cdots \lor {\bf P}(a_{k-1}) \lor {\bf P}(a_{k+1}) \cdots \lor {\bf P}(a_n)$$

$$= T \lor {\bf P}(a_1) \lor {\bf P}(a_2) \lor \cdots \lor {\bf P}(a_{k-1}) \lor {\bf P}(a_{k+1}) \cdots \lor {\bf P}(a_n)$$

$$=T$$ (3.30)

よって任意の対象 $a \in {\bf D}$ に対し

$${\bf P}(a) \Rightarrow (\exists x)({\bf P}(x))$$ (3.31)

は恒真論理式である。

同様にすべての$k$について

$${\bf P}(a_k) \Rightarrow A$$

が恒真論理式ならば，定義と定理$1.2$のド・モルガン則，交換則を使えば

$$\begin{eqnarray*} && (\exists x)({\bf P}(x)) \Rightarrow A \\ && = \lnot \Bi... ...P}(a_3) \land \cdots \land \lnot {\bf P}(a_n) \Bigr ) \lor A \end{eqnarray*}$$

$$= ( \lnot {\bf P}(a_1) \lor A ) \land ( \lnot {\bf P}(a_2) \lor A... ... ( \lnot {\bf P}(a_3) \lor A ) \land \cdots \land ( \lnot {\bf P}(a_n) \lor A )$$ (3.32)

$$= ({\bf P}(a_1) \Rightarrow A ) \land ({\bf P}(a_2) \Rightarrow A... ... ({\bf P}(a_3) \Rightarrow A ) \land \cdots \land ({\bf P}(a_n) \Rightarrow A )$$ (3.33)

よって, ある対象 $b \in {\bf D}$ に対し

$${\bf P}(b) \Rightarrow A$$ (3.34)

が恒真論理式ならば

$$(\exists x)({\bf P}(x)) \Rightarrow A$$

$$(ただしA は任意の命題)$$ (3.35)

も恒真論理式である。

${\bf P}$ と ${\bf Q}$を${\bf D}$ 上の述語とする。

$$(\forall x)[{\bf P}(x) \land {\bf Q}(x)]$$

$$ =({\bf P}(a_1) \land {\bf Q}(a_1) ) \land \cdots \land ({\bf P}(a_n) \land {\bf Q}(a_n) )$$

$$= ({\bf P}(a_1) \land \cdots \land {\bf P}(a_n) ) \land ({\bf Q}(a_1) \land \cdots \land {\bf Q}(a_n) )$$

$$=(\forall x)({\bf P}(x)) \land (\forall x)({\bf Q}(x))$$ (3.36)

従って 論理式としての等式

$$(\forall x)[{\bf P}(x) \land {\bf Q}(x)] = (\forall x)({\bf P}(x)) \land (\forall x)({\bf Q}(x))$$ (3.37)

が成り立つ。

次に

$$(\exists x)[{\bf P}(x) \lor {\bf Q}(x)]$$

$$ =({\bf P}(a_1) \lor {\bf Q}(a_1) ) \lor \cdots \lor ({\bf P}(a_n) \lor {\bf Q}(a_n) )$$

$$= ({\bf P}(a_1) \lor \cdots \lor {\bf P}(a_n) ) \lor ({\bf Q}(a_1) \lor \cdots \lor {\bf Q}(a_n) )$$

$$=(\exists x)({\bf P}(x)) \lor (\exists x)({\bf Q}(x))$$ (3.38)

従って 論理式としての等式

$$(\exists x)[{\bf P}(x) \lor {\bf Q}(x)] = (\exists x)({\bf P}(x)) \lor (\exists x)({\bf Q}(x))$$ (3.39)

が成り立つ。

束縛変数は見かけ上の変数であることに注意すれば $1$変数の述語${\bf P}(x)$について

$$(\forall x)({\bf P}(x)) = ({\bf P}(a_1) \land \cdots \land {\bf P}(a_n) ) = (\forall y)({\bf P}(y))$$ (3.40)

$$(\exists x) ({\bf P}(x)) ={\bf P}(a_1) \lor \cdots \lor {\bf P}(a_n) = (\exists y)({\bf P}(y))$$ (3.41)

すなわち変数名を変更しても変わりない。

$2$変数の述語${\bf P}(x,y)$について,定義と定理$1.2$のド・モルガン則，交換則を使えば

$$(\forall x)( \forall y)({\bf P}(x,y)) = (\forall x) \Bigl ( \bigwedge_{k=1}^{k=n} ({\bf P}(x,a_k) \Bigr )$$

$$= \bigwedge_{i=1}^{i=n} \Bigl ( \bigwedge_{k=1}^{k=n} ({\bf P}(a_i,a_k) \Bigr )$$

$$= \bigwedge_{k=1}^{k=n} \Bigl ( \bigwedge_{i=1}^{i=n} ({\bf P}(a_i,a_k) \Bigr )$$

$$= (\forall y)( \forall x)({\bf P}(x,y))$$ (3.42)

$$(\exists x)( \exists y)({\bf P}(x,y)) = (\exists x) \Bigl ( \bigvee_{k=1}^{k=n} ({\bf P}(x,a_k) \Bigr )$$

$$= \bigvee_{i=1}^{i=n} \Bigl ( \bigvee_{k=1}^{k=n} ({\bf P}(a_i,a_k) \Bigr )$$

$$= \bigvee_{k=1}^{k=n} \Bigl ( \bigvee_{i=1}^{i=n} ({\bf P}(a_i,a_k) \Bigr )$$

$$= (\exists y)( \exists x)({\bf P}(x,y))$$ (3.43)

すなわち,ひき続いて現れる同種の限定記号の順序を変えても変わりない。

定義と定理$1.2$のド・モルガン則，交換則を使えば

$$\Bigl[(\forall x)({\bf P}(x)) \Rightarrow (\exists x)({\bf P}(x)) \Bigr]$$

$$=\lnot (\forall x)({\bf P}(x)) \lor (\exists x)({\bf P}(x))$$

$$=\lnot \Bigl ( \bigwedge_{i=1}^{i=n} ({\bf P}(a_i) \Bigr ) \lor \Bigl ( \bigvee_{i=1}^{i=n} ({\bf P}(a_i) \Bigr )$$ (3.44)

さらに右辺は

$$= \bigvee_{i=1}^{i=n} \Bigl ( \lnot {\bf P}(a_i) \Bigr ) \lor \Bigl ( \bigvee_{i=1}^{i=n} ({\bf P}(a_i) \Bigr )$$

$$=\bigvee_{i=1}^{i=n} \Bigl ( \lnot {\bf P}(a_i) \lor {\bf P}(a_i) \Bigr )$$

$$=\bigvee_{i=1}^{i=n} \Bigl (T \Bigr )$$

$$=T$$ (3.45)

すなわち

$$(\forall x)({\bf P}(x)) \Rightarrow (\exists x)({\bf P}(x))$$ (3.46)

は恒真論理式である。

　同様に定義と定理$1.2$のド・モルガン則，交換則を使えば

$$(\exists y)( \forall x)({\bf P}(x,y)) \Rightarrow (\forall x)( \exists y)({\bf P}(x,y)) =T$$

すなわち

$$(\exists y)( \forall x)({\bf P}(x,y)) \Rightarrow (\forall x)( \exists y)({\bf P}(x,y))$$ (3.47)

は恒真論理式である。

同様に,${\bf P}$ と ${\bf Q}$を${\bf D}$ 上の述語とすると,

$$(\forall x)[{\bf P}(x) \Rightarrow {\bf Q}(x)] \Rightarr... ...(\forall x)({\bf P}(x)) \Rightarrow (\forall x)({\bf Q}(x))]$$ (3.48)

と

$$(\exists x)[{\bf P}(x) \Rightarrow {\bf Q}(x)] \Rightar... ...(\exists x)({\bf P}(x)) \Rightarrow (\exists x)({\bf Q}(x))]$$ (3.49)

は恒真論理式である。

以上は${\bf D}$が無限集合の場合も成り立つ。これを 定理としてまとめておく。

定理7

(i).

${\bf D}$ 上の述語 ${\bf P}$ について 　

1. 任意の対象 $a \in {\bf D}$ に対し
   
   $$(\forall x)({\bf P}(x)) \Rightarrow {\bf P}(a)$$
   
   
   　は恒真論理式である。

2. 任意の対象 $a \in {\bf D}$ に対し $A\Rightarrow {\bf P}(a)$ が恒真論理式ならば
   $$\begin{eqnarray*} && A \Rightarrow (\forall x)({\bf P}(x)) \\ && (ただしA は任意の命題) \end{eqnarray*}$$
   
   
   も恒真論理式である。
3. 任意の対象 $a \in {\bf D}$ に対し
   
   $${\bf P}(a) \Rightarrow (\exists x)({\bf P}(x))$$
   
   
   は恒真論理式である。
4. 任意の対象 $a \in {\bf D}$ に対し
   
   $${\bf P}(a) \Rightarrow A$$
   
   
   が恒真式ならば
   $$\begin{eqnarray*} && (\exists x)({\bf P}(x)) \Rightarrow A \\ && (ただしA は任意の命題) \end{eqnarray*}$$
   
   
   も恒真式である。

(ii).

${\bf D}$ 上の述語 ${\bf P}$ と ${\bf Q}$ について

1. 
   
   $$(\forall x)[{\bf P}(x) \land {\bf Q}(x)] \Leftrightarrow (\forall x)({\bf P}(x)) \land (\forall x)({\bf Q}(x))$$
   
   
   は恒真論理式である。 あるいは同じことであるが，論理式としての等式
   
   $$(\forall x)[{\bf P}(x) \land {\bf Q}(x)] = (\forall x)({\bf P}(x)) \land (\forall x)({\bf Q}(x))$$
   
   
   が成り立つ。

2. 
   
   $$(\exists x)[{\bf P}(x) \lor {\bf Q}(x)] \Leftrightarrow (\exists x)({\bf P}(x)) \lor (\exists x)({\bf Q}(x))$$
   
   
   は恒真論理式である。 あるいは同じことであるが，論理式としての等式
   
   $$(\exists x)[{\bf P}(x) \lor {\bf Q}(x)] = (\exists x)({\bf P}(x)) \lor (\exists x)({\bf Q}(x))$$
   
   
   が成り立つ。

^3.1

(iii).

1. 束縛変数を含む述語 ${\bf Q}$ において，その束縛変数記号を ${\bf Q}$ に含 まれない他の束縛変数記号でおきかえて得られる述語を ${\bf G}$ とすれば，
   
   $${\bf Q} \Leftrightarrow {\bf G}$$
   
   
   は恒真論理式である。あるいは同じことであるが 論理式の等号の意味で
   
   $${\bf Q}={\bf G}$$
   
   
   である。 たとえば，
   
   $$(\forall x)({\bf P}(x)) = (\forall y)({\bf P}(y))$$
   
   
   
   
   $$(\exists x)({\bf P}(x)) = (\exists y)({\bf P}(y))$$
   
   

2. 述語 ${\bf Q}$ において，ひき続いて現れる同種の限定記号の順序を変 更して得られる述語を ${\bf G}$ とすれば，
   
   $${\bf Q} \Leftrightarrow {\bf G}$$
   
   
   は恒真論理式である。あるいは同じことであるが 論理式の等号の意味で
   
   $${\bf Q}={\bf G}$$
   
   
   である。

   たとえば，
   

   $$(\forall x)( \forall y)({\bf P}(x,y)) = (\forall y)( \forall x)({\bf P}(x,y)),$$
   
   
   
   
   $$(\exists x)(\exists y)({\bf P}(x,y)) = (\exists y)(\exists x)({\bf P}(x,y))$$
   
   

3. 
   
   $$(\forall x)({\bf P}(x)) \Rightarrow (\exists x)({\bf P}(x))$$
   
   
   は恒真論理式である。

4. 
   
   $$(\exists y)( \forall x)({\bf P}(x,y)) \Rightarrow (\forall x)( \exists y)({\bf P}(x,y))$$
   
   
   は恒真論理式である。

(iv).

${\bf D}$ 上の述語 ${\bf P},{\bf Q}$ について，以下は 恒真論理式である。

1. 
   

   $$(\forall x)[{\bf P}(x) \Rightarrow {\bf Q}(x)] \Rightarr... ...(\forall x)({\bf P}(x)) \Rightarrow (\forall x)({\bf Q}(x))]$$
   
   

2. 
   

   $$(\exists x)[{\bf P}(x) \Rightarrow {\bf Q}(x)] \Rightar... ...(\exists x)({\bf P}(x)) \Rightarrow (\exists x)({\bf Q}(x))]$$
   
   

^3.2