跳转到内容

形式逻辑/谓词逻辑/自由变量与约束变量

来自维基教科书,开放的书籍,开放的世界
← 形式语法 ↑ 谓词逻辑 非正式约定 →



自由变量与约束变量

[编辑 | 编辑源代码]

非正式概念

[编辑 | 编辑源代码]

以下两个英语句子:

如果苏格拉底是人,那么苏格拉底是凡人。
如果亚里士多德是人,那么亚里士多德是凡人。

都是真的。但是,在没有提供“它”的引用的上下文中,

(1)    如果它是人,那么它是凡人。

既不是真也不是假。“它”不是名词,而是一个空占位符。“它”可以通过从周围上下文中获取引用来指代一个对象。但是,如果没有这样的上下文,就没有引用,也没有真假。同样的道理也适用于变量“x”在以下句子中:

(2)    如果x是人,那么x是凡人。

情况随着以下两个句子的出现而改变:

(3)    对于任何对象,如果它是人,那么它是凡人。
(4)    对于任何对象x,如果x是人,那么x是凡人。

这些句子中的“它”和“x”都没有像“苏格拉底”或“亚里士多德”那样指代特定的对象。但是 (3) 和 (4) 仍然是真的。(3) 为真当且仅当:

(5)    将 (3) 中的“它”的所有出现都替换为任何对象的引用(两次都替换为同一个对象)会导致一个真结果。

但是 (5) 是真的,所以 (3) 也是真的。类似地,(4) 为真当且仅当:

(6)    将 (4) 中的“x”的所有出现都替换为任何对象的引用(两次都替换为同一个对象)会导致一个真结果。

但是 (3) 是真的,所以 (4) 也是真的。我们可以将 (1) 中的“它”的出现称为自由变量,而将 (3) 中的“它”的出现称为约束变量。事实上,(3) 中的“它”的出现是由短语“对于任何”约束的。类似地,(2) 中的“x”的出现是自由变量,而 (4) 中的“x”的出现是约束变量。事实上,(4) 中的“x”的出现是由短语“对于任何”约束的。

正式定义

[编辑 | 编辑源代码]

变量 的出现 中是约束变量,如果 的该出现位于 的子公式中,该子公式具有以下两种形式之一:

考虑公式

所有 的出现都是 (7) 中的约束变量,因为它们位于子公式中

类似地, 在 (7) 中的两个实例都是绑定的,因为它们位于子公式中


变量 中是自由的,当且仅当 中没有绑定。

中是自由的,因为它们都没有在 (8) 中绑定。


我们说变量 的出现是由 的特定出现绑定的,如果该出现也是 中最短的子公式的第一个(可能也是唯一的)符号,该子公式具有形式

考虑公式

公式 (9) 中, 的第三和第四个出现被 (9) 中的第二个 绑定。但是,它们没有被 (9) 中的第一个 绑定。公式

在 (9) 中的出现 - 以及 (9) 本身在 (9) 中的出现 - 都是以量词开头的 (9) 的子公式。也就是说,它们都是 (9) 的子公式,形式为

两者都包含 (9) 中的第三和第四个 的出现。然而,(10) 在 (9) 中的出现是满足这些条件的 (9) 的最短子公式。也就是说,(10) 在 (9) 中的出现是 (9) 的最短子公式,它既 (i) 具有这种形式,又 (ii) 包含 (9) 中的第三和第四个 的出现。因此,绑定 (9) 中的第三和第四个 的是 (9) 中的第二个,而不是第一个, 的出现。(9) 中的第一个 的出现确实绑定了 (9) 中的前两个 的出现。


我们还说,变量 的一个出现被 的特定出现绑定,如果该出现也是 的最短子公式中的第一个(也许是唯一的)符号,形式为


最后,我们说变量(不是它的特定出现)在公式中是绑定(或自由),如果公式包含的绑定(或自由)出现。因此 在以下公式中既是绑定又是自由的:

因为这个公式包含 的绑定和自由出现。特别地, 的前两次出现是绑定的,而最后一次是自由的。

句子和公式

[edit | edit source]

句子 是一个没有自由变量的公式。命题逻辑根本没有变量,所以 中的所有公式也是 的句子。但在谓词逻辑及其语言 中,我们有不是句子的公式。上面 (7)、(8)、(9) 和 (10) 都是公式。在这些公式中,只有 (7)、(9) 和 (10) 是句子。(8) 不是句子,因为它包含自由变量。

例子

[edit | edit source]

在以下公式中的所有出现:

在公式中绑定。唯一出现的 是自由的。因此,(11) 是一个公式,但不是一个句子。

只有 的前两次出现

在公式中绑定。最后出现的 和唯一出现的 在公式中是自由的。因此,(12) 是一个公式,但不是一个句子。

所有四次出现的

是绑定的。前两个被全称量词绑定,后两个被存在量词绑定。唯一出现的 在公式中是自由的。因此,(13) 是一个公式,但不是一个句子。

所有三个出现的

被全称量词绑定。所有出现的 在公式中被存在量词绑定。因此,(14) 没有自由变量,因此是一个句子,也是一个公式。

华夏公益教科书