跳轉到內容

形式邏輯/謂詞邏輯/自由變數與約束變數

來自華夏公益教科書,開放的書籍,開放的世界
← 形式語法 ↑ 謂詞邏輯 非正式約定 →



自由變數與約束變數

[編輯 | 編輯原始碼]

非正式概念

[編輯 | 編輯原始碼]

以下兩個英語句子:

如果蘇格拉底是人,那麼蘇格拉底是凡人。
如果亞里士多德是人,那麼亞里士多德是凡人。

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

(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) 沒有自由變數,因此是一個句子,也是一個公式。

華夏公益教科書