解释与赋值

设$A$$A$为一阶逻辑公式, $\{p_1,\cdots ,p_m\}$$\{p_1, \cdots, p_m\}$ 是$A$$A$中所有的谓词, $\{a_1,\cdots ,a_k\}$$\{a_1, \cdots , a_k\}$是$A$$A$中所有的常量。 $A$$A$的一个解释(Interpretation)$I_A$$I_A$是一个三元组:

分别对应于个体域的具体化、谓词的具体化和常量的具体化。 在不引起混淆的情况下，有时候就用$I$$I$表示$I_A$$I_A$.

设$I_A$$I_A$是一阶逻辑公式$A$$A$的解释。一个针对该解释的赋值(Assignment)${\sigma }_{I_A}$$\sigma_{I_A}$是一个将所有变量$v\in V$$v\in V$映射成具体值$d\in D$$d{\in}D$的映射$V\to D$$V{\rightarrow}D$.

一阶逻辑公式一经赋值,就成为具有确定真值的命题。 用$v_{{\sigma }_{I_A}}(A)$$v_{\sigma_{I_A}}(A)$表示一阶逻辑公式$A$$A$ 在解释$I_A$$I_A$和赋值${\sigma }_{I_A}$$\sigma_{I_A}$下的真值。在不引起混淆的情况下, 有时也简写成$v_{\sigma }$$v_{\sigma}$.

例: 给定解释$I$$I$, 试确定: $S(x),\mathrm{\exists }xS(x),S(x)\wedge \mathrm{\exists }xS(x)$$S(x),{\exists}xS(x),S(x){\wedge}{\exists}xS(x)$在不同解释和赋值下的真值。

解释包括:

$I_1$$I_1$​:个体域$D_1=\{3,4\}$$D_{1}=\{3,4\}$​,$S(x)$$S(x)$​表示"$x$$x$​是素数";

$I_2$$I_2$​:个体域$D_2=\{3,4\}$$D_{2}=\{3,4\}$​,$S(x)$$S(x)$​表示"$x$$x$​是偶数";

$I_3$$I_3$:个体域$D_3=\{3,5\}$$D_{3}=\{3,5\}$,$S(x)$$S(x)$表示"$x$$x$是素数";

$I_4$$I_4$​:个体域$D_4=\{3,5\}$$D_{4}=\{3,5\}$​,$S(x)$$S(x)$​表示"$x$$x$​是偶数"。

赋值根据$D_1$$D_{1}$、$D_2$$D_{2}$、$D_3$$D_{3}$和$D_4$$D_{4}$的具体个体域确定。

$S(x)$$S(x)$,$\mathrm{\exists }xS(x)$${\exists}xS(x)$,$S(x)\wedge \mathrm{\exists }xS(x)$$S(x){\wedge}{\exists}xS(x)$的真值如下:

带量词的公式在具体赋值下的真值:

例: $\mathrm{\forall }xp(a,x)$$\forall x\,p(a, x)$:

$I_1=(N,\{\le \},\{0\})$$I_1 = (N , \{\le \}, \{0\})$

$I_2=(N,\{\le \},\{1\})$$I_2 = (N , \{\le \}, \{1\})$

$I_3=(Z,\{\le \},\{0\})$$I_3 = (Z , \{\le \}, \{0\})$

$I_4=(S,\{substr\},{\{}^{\prime }{}^{\prime }\})$$I_4 = (S, \{ substr \}, \{'\,'\})$

若一阶逻辑公式$A$$A$在某一解释$I$$I$下为真, 称$I$$I$是$A$$A$的一个模型(Model), 记作: $I\models A$$I{\models}A$.

若一阶逻辑公式$A$$A$在任意解释$I$$I$下均为真,则称$A$$A$为永真式, 记作: $\models A$${\models}A$. 否则称$A$$A$为存伪式(Falsible)。

若一阶逻辑公式$A$$A$在任意解释$I$$I$下均为假,则称$A$$A$为永假式, 否则称$A$$A$为可满足式(Satisfiable)。

例: $P(x)\vee \mathrm{\neg }P(x)$$P(x){\vee}{\lnot}P(x)$是永真式

$Q(x)\wedge \mathrm{\neg }Q(x)$$Q(x){\wedge}{\lnot}Q(x)$是永假式

$P(x)\vee \mathrm{\exists }xQ(x)$$P(x){\vee}{\exists}xQ(x)$是可满足式

例: 判断谓词公式$\mathrm{\forall }xA(x)\to A(y)$${\forall}xA(x){\rightarrow}A(y)$是否为永真式。

解: 任意给定个体域$D$$D$, 假定在该解释下$\mathrm{\forall }xA(x)$${\forall}xA(x)$为真, 则对于任意$d\in D$$d{\in}D$, 均有$A(d)$$A(d)$为真, 因此$A(y)$$A(y)$也为真。

故$\mathrm{\forall }xA(x)\to A(y)$${\forall}xA(x){\rightarrow}A(y)$为永真式。

例: 判断谓词公式$\mathrm{\forall }x(P(x)\to Q(x))$${\forall}x(P(x){\rightarrow}Q(x))$是否为可满足式。

解:定义解释$I$$I$:个体域$D$$D$上为整数集,

$P(x)$$P(x)$表示$x$$x$是整数, $Q(x)$$Q(x)$表示$x$$x$是有理数。

在解释$I$$I$下, $\mathrm{\forall }x(P(x)\to Q(x))$${\forall}x(P(x){\rightarrow}Q(x))$为真。

所以$\mathrm{\forall }x(P(x)\to Q(x))$${\forall}x(P(x){\rightarrow}Q(x))$是可满足式。

设$U=\{A_1,A_2,\cdots ,A_n\}$$U=\{A_1,A_2,\cdots,A_n\}$为一组一阶逻辑公式, $\{p_1,\cdots ,p_m\}$$\{p_1, \cdots, p_m\}$ 是$U$$U$中所有的谓词, $\{a_1,\cdots ,a_k\}$$\{a_1, \cdots , a_k\}$是$U$$U$中所有的常量。

$U$$U$的一个解释$I_U$$I_U$是一个三元组:

分别对应于个体域的具体化、谓词的具体化和常量的具体化。

针对$I_U$$I_U$的赋值${\sigma }_{I_U}$$\sigma_{I_U}$是将所有变量$v\in V$$v\in V$映射成具体值$d\in D$$d{\in}D$的一个映射$V\to D$$V{\rightarrow}D$.

若一组一阶逻辑公式$U=\{A_1,A_2,\cdots ,A_n\}$$U=\{A_1,A_2,\cdots,A_n\}$在某一解释$I_U$$I_U$下为真(对于任意$i$$i$, $v_{I_U}(A_i)=T$$v_{I_U}(A_i)=T$), 称$I_U$$I_U$是$U$$U$的一个模型, 记作: $I\models U$$I{\models}U$.

若一组一阶逻辑公式$U$$U$在任意解释$I_U$$I_U$下均为真,则称$U$$U$为一组永真式, 记作: $\models U$${\models}U$. 否则称$U$$U$为一组存伪式。

若一组一阶公式$U$$U$在任意解释$U$$U$下均为假,则称$U$$U$为一组永假式, 否则称$U$$U$为一组可满足式。