消去量词的方法

Section 6.9 消去量词的方法

全称量词 \(\quad \forall \quad\)的展开式.

设个体域\(D = \{ b_1,b_2,\cdots,b_n \} \)
\(\displaystyle \forall x A(x) = A(b_1) \wedge A(b_2) \wedge \cdots \wedge A(b_n) \)

存在量词 \(\quad \exists \quad\)的展开式.

设个体域\(D = \{ b_1,b_2,\cdots,b_n \} \)
\(\displaystyle \exists x A(x) = A(b_1) \vee A(b_2) \vee \cdots \vee A(b_n) \)

Objectives: 给定解释\(\quad I \quad\)如下

设个体域\(D =\{2,3\} \)
\(\displaystyle \bar{a} = 2 \)
\(\displaystyle \bar{f}(x) \text{为} \quad \bar{f}(2)=3 \quad \bar{f}(3) =2 \)
\(\displaystyle \bar{G}(x,y) \text{为} \quad \bar{G}(2,2)=\bar{G}(2,3)=\bar{G}(3,2)=1 \quad \bar{G}(3,3)=0 \)
\(\displaystyle \bar{F} \text{为} \quad \bar{F}(2) = 0 \quad \bar{F}(3) =1 \)

请在解释\(\quad I \quad\)下求出以下公式的真值.

\(\displaystyle \forall x ( F(x) \wedge G(x,a) ) \)
\(\displaystyle \exists x ( F(f(x)) \wedge G(x,f(x)) ) \)

Answer 1

\begin{align*} \forall x (F(x) \wedge G(x,a) ) \amp \Iff \forall x (\bar{F}(x) \wedge \bar{G}(x,{\color{green}{2}}) ) \\ \amp \Iff (\bar{F}({\color{Blue}{2}}) \wedge \bar{G}({\color{Blue}{2}},{\color{green}{2}}) ) \wedge (\bar{F}({\color{Blue}{3}}) \wedge \bar{G}({\color{Blue}{3}},{\color{green}{2}}) ) \\ \amp \Iff (0 \wedge 1 ) \wedge (1 \wedge 1) \\ \amp \Iff 0 \end{align*}

Answer 2

\begin{align*} \amp \exists x ( F(f(x)) \wedge G(x,f(x)) ) \\ \amp \Iff (\bar{F} (\bar f(2)) \wedge \bar{G} (2, \bar{f}(2) )) \vee (\bar{F} (\bar f(3)) \wedge \bar{G} (3, \bar{f}(3) ))\\ \amp \Iff (\bar{F} (3) \wedge \bar{G} (2, 3 )) \vee (\bar{F} (2) \wedge \bar{G} (3, 2)) \\ \amp \Iff (1 \wedge 1) \vee (0 \wedge 1)\\ \amp \Iff 1 \vee 0 \\ \amp \Iff 1 \end{align*}