形式逻辑/谓词逻辑/模型

← 非正式约定

↑ 谓词逻辑

满足 →

模型

解释

我们之前说过，对于像${\mathcal {L_{S}}}\,\!$（现在是${\mathcal {L_{P}}}\,\!$）这样的形式语言的形式语义分为两部分。

• 指定解释的规则。一个解释为形式语法中非逻辑符号分配语义值。就像一个赋值是对命题语言的解释一样，一个模型是对谓词语言的解释。

• 为语言中较大的表达式分配语义值的规则。命题语言${\mathcal {L_{S}}}\,\!$的所有公式都是句子。这使得能够直接为较大的公式分配真值。对于谓词语言${\mathcal {L_{P}}}\,\!$，情况更加复杂。并非${\mathcal {L_{P}}}\,\!$的所有公式都是句子。我们需要定义辅助概念满足，并在分配真值时使用它。

模型

一个模型是对谓词语言的解释。它包括两个部分：域和解释函数。在此过程中，我们将逐步指定一个示例模型${\mathfrak {M}}\,\!$.

域

• 一个域是一个非空集合。

直观地说，域包含当前考虑的所有对象。它包含量词范围内的所有对象。$\forall x\,\!$然后解释为“对于域中的任何对象$x\,\!$…”；$\exists x\,\!$解释为“存在域中的至少一个对象$x\,\!$，使得…”。我们的谓词逻辑要求域是非空的，即它至少包含一个对象。

我们示例模型${\mathfrak {M}}\,\!$的域，记为$|{\mathfrak {M}}|\,\!$，是 {0, 1, 2}。

解释函数

• 解释函数是将语义值分配给每个运算符字母和谓词字母的函数。

模型 ${\mathfrak {M}}\,\!$ 的解释函数是 $I_{\mathfrak {M}}\,\!$。

运算符字母

• 对每个常数符号（即零元运算符字母）分配一个域中的成员。

直观地，常数符号命名该对象，该对象是域中的一个成员。如果域是上面的 $|{\mathfrak {M}}|\,\!$ 并且 $a_{0}^{0}\,\!$ 被分配到 0，那么我们认为 $a_{0}^{0}\,\!$ 命名 0，就像名字'苏格拉底'命名苏格拉底这个人，或者数字'0'命名数字 0 一样。将 0 分配给 $a_{0}^{0}\,\!$ 可以表示为

$I_{\mathfrak {M}}(a_{0}^{0})=0\ .\,\!$

• 对每个n元运算符字母，其中n大于零，分配一个n+1元函数，该函数以对象（域中的成员）的有序n元组作为其参数，并以对象（域中的成员）作为其值。该函数必须在域中的所有n元组上定义。

假设域是上面的 $|{\mathfrak {M}}|\,\!$，我们有一个二元运算符字母 $f_{0}^{2}\,\!$。分配给 $f_{0}^{2}\,\!$ 的函数必须在域中的每个有序对上定义。例如，它可以是函数 ${\mathfrak {f}}_{0}^{2}\,\!$，使得

${\mathfrak {f}}_{0}^{2}(0,0)=2,\quad {\mathfrak {f}}_{0}^{2}(0,1)=1,\quad {\mathfrak {f}}_{0}^{2}(0,2)=0,\,\!$

${\mathfrak {f}}_{0}^{2}(1,0)=1,\quad {\mathfrak {f}}_{0}^{2}(1,1)=0,\quad {\mathfrak {f}}_{0}^{2}(1,2)=2,\,\!$

${\mathfrak {f}}_{0}^{2}(2,0)=0,\quad {\mathfrak {f}}_{0}^{2}(2,1)=2,\quad {\mathfrak {f}}_{0}^{2}(2,2)=1\ .\,\!$

对操作符的赋值写成

$I_{\mathfrak {M}}(f_{0}^{2})={\mathfrak {f}}_{0}^{2}\ .\,\!$

假设 $a_{0}^{0}\,\!$ 如上所述赋值为 0，并且 $b_{0}^{0}\,\!$ 赋值为 1。 然后我们可以直观地认为非正式书写形式 $f(a,b)\,\!$ 代表（指代、具有值）1。 这类似于 “苏格拉底最著名的学生” 代表（指代）柏拉图，或 “2 + 3” 代表（具有值）5。

谓词符号

• 每个句子符号（即零元谓词符号）都被分配一个真值。 对于 $\pi \,\!$ 一个句子符号，要么

$I_{\mathfrak {M}}(\pi )=\mathrm {True} \,\!$

或

$I_{\mathfrak {M}}(\pi )=\mathrm {False} \ .\,\!$

这与句子符号在命题逻辑中所接受的处理方式相同。 直观地说，句子是真还是假，取决于句子符号是否被赋值为 “真” 或 “假”。

• 每个n元谓词符号，其中n大于零，都被分配一个n元关系（一个域成员的有序n元组集）。

直观地说，谓词对分配集中每个n元组都是真的。 令域为 $|{\mathfrak {M}}|\,\!$ 如上，并假设赋值

$I_{\mathfrak {M}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle 0,\ 1\rangle ,\ \langle 1,\ 2\rangle ,\ \langle 2,\ 1\rangle \}.$

假设$a_{0}^{0}\,\!$被赋值为0，$b_{0}^{0}\,\!$被赋值为1，$c_{0}^{0}\,\!$被赋值为2。然后直观地，$\mathrm {F} (a,b)\,\!$，$\mathrm {F} (b,c)\,\!$和$\mathrm {F} (c,b)\,\!$都应该是真的。然而，$\mathrm {F} (a,c)\,\!$等应该为假。这类似于“是否鹰钩鼻”对苏格拉底为真，而“是否大于”对$\langle 2,3\rangle$为真。

摘要

这个定义穿插着例子，因此比较分散。这里是一个更紧凑的总结。模型由两个部分组成：域和解释函数。

• 一个域是一个非空集合。

• 一个解释函数是将语义值赋予每个运算符字母和谓词字母。此分配按以下步骤进行

• 将每个常量符号（即零元运算符字母）分配给域中的一个成员。
• 将每个n元运算符字母（n大于零）分配给一个n+1元函数，该函数以对象的有序n元组（域的成员）作为其参数，并以对象（域的成员）作为其值。
• 将每个句子字母（即零元谓词字母）分配给一个真值。
• 将每个n元谓词字母（n大于零）分配给一个n元关系（一个有序n元组的集合），这些关系都是域中的成员。

例子

一个有限模型

一个例子模型在上面以片段的形式指定。这些片段，在${\mathfrak {M}}\,\!$这个名字下收集在一起，是

$|{\mathfrak {M}}|\ =\ \{0,\ 1,\ 2\}\ .\,\!$

$I_{\mathfrak {M}}(a_{0}^{0})\ =\ 0\ .\,\!$

$I_{\mathfrak {M}}(b_{0}^{0})\ =\ 1\ .\,\!$

$I_{\mathfrak {M}}(c_{0}^{0})\ =\ 2\ .\,\!$

$I_{\mathfrak {M}}(f_{0}^{2})\ =\ {\mathfrak {f}}_{0}^{2}\ {\mbox{such that:}}\quad {\mathfrak {f}}_{0}^{2}(0,0)=2,\ {\mathfrak {f}}_{0}^{2}(0,1)\ =\ 1,\ {\mathfrak {f}}_{0}^{2}(0,2)=0,\,\!$

${\mathfrak {f}}_{0}^{2}(1,0)=1,\ {\mathfrak {f}}_{0}^{2}(1,1)\ =\ 0,\ {\mathfrak {f}}_{0}^{2}(1,2)=2,\ {\mathfrak {f}}_{0}^{2}(2,0)=0,\,\!$

${\mathfrak {f}}_{0}^{2}(2,1)=2,\ {\mbox{and}}\ {\mathfrak {f}}_{0}^{2}(2,2)=1\ .\,\!$

$I_{\mathfrak {M}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle 0,\ 1\rangle ,\ \langle 1,\ 2\rangle ,\ \langle 2,\ 1\rangle \}.$

我们还没有定义生成较大表达式语义值的规则。但是，我们可以看到一些我们希望该定义能够实现的简单结果。已经描述了一些这样的结果。

$f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (a,b),\ \mathrm {F} (b,c),\ {\mbox{and}}\ \mathrm {F} (c,b)\ {\mbox{are True in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (a,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

可以添加一些更多期望的结果

$\mathrm {F} (a,f(a,b))\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (f(a,b),a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (c,b)\rightarrow \mathrm {F} (a,b)\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (c,b)\rightarrow \mathrm {F} (b,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

我们可以暂时假设数字 '0'、'1' 和 '2' 被添加到 ${\mathcal {L_{P}}}\,\!$ 并分别为它们分配数字 0、1 和 2。那么我们想要

$(1)\quad \mathrm {F} (0,1)\rightarrow \mathrm {F} (1,0)\quad {\mbox{False in}}\ {\mathfrak {M}}\ .\,\!$

$(2)\quad \mathrm {F} (1,2)\land \mathrm {F} (2,1)\quad {\mbox{True in}}\ {\mathfrak {M}}\ .\,\!$

由于 (1)，我们希望得到这样的结果

$\forall x\,\forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\ {\mbox{is false in }}\ {\mathfrak {M}}\ .\,\!$

由于 (2)，我们希望得到这样的结果

$\exists x\,\exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\ {\mbox{is true in}}\ {\mathfrak {M}}\ .\,\!$

一个无限模型

域 $|{\mathfrak {M}}|\,\!$ 只有有限多个成员；准确来说是 3 个。域可以有无限多个成员。下面是一个具有无限大域的示例模型 ${\mathfrak {M}}_{2}\,\!$ 。

域 $|{\mathfrak {M}}_{2}|\,\!$ 是自然数的集合

$|{\mathfrak {M}}_{2}|=\{0,1,2,...\}\,\!$

对单个常量符号的赋值可以与之前相同

$I_{{\mathfrak {M}}_{2}}(a_{0}^{0})\ =\ 0\ .\,\!$

$I_{{\mathfrak {M}}_{2}}(b_{0}^{0})\ =\ 1\ .\,\!$

$I_{{\mathfrak {M}}_{2}}(c_{0}^{0})\ =\ 2\ .\,\!$

例如，可以将二元运算符字母 $f\,\!$ 赋值为加法函数

$I_{{\mathfrak {M}}_{2}}(f_{0}^{2})\ =\ {\mathfrak {f}}_{0}^{2}\ {\mbox{such that}}\ {\mathfrak {f}}_{0}^{2}(u,v)=u+v\ .\,\!$

例如，可以将二元谓词字母 $\mathrm {F_{0}^{2}} \,\!$ 赋值为 *小于* 关系

$I_{{\mathfrak {M}}_{2}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle x,\ y\rangle :\ x<y\}\ .\,\!$

扩展模型的规范应该产生一些结果。

$f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}_{2}\ .\,\!$

$\mathrm {F} (a,b)\ {\mbox{and}}\ \mathrm {F} (b,c)\ {\mbox{are True in}}\ {\mathfrak {M}}_{2}\ .\,\!$

$\mathrm {F} (c,b)\ {\mbox{and}}\ \mathrm {F} (a,a)\ {\mbox{are False in}}\ {\mathfrak {M}}_{2}\ .\,\!$

对于每个 *x*，都存在一个 *y* 使得 *x* < *y*。因此我们希望得到的结果是

$\forall x\,\exists y\,\mathrm {F} (x,y)\ {\mbox{is true in}}\ {\mathfrak {M}}_{2}\ .\,\!$

不存在 *y* 使得 *y* < 0 （记住，我们把自己限制在没有小于 0 的数字的域中）。因此，并非对于每个 *x* 来说，都存在一个 *y* 使得 *y* < *x*。因此我们希望得到的结果是

$\forall x\,\exists y\,\mathrm {F} (y,x)\ {\mbox{is false in}}\ {\mathfrak {M}}_{2}\ .\,\!$