量化 (數理邏輯)

量化 (數理邏輯) （简体）

在語言和邏輯中，量化是指定一個謂詞的有效性的廣度的構造，就是說指定謂詞在一定範圍的事物上成立的程度。產生量化的語言元素叫做量詞。結果的句子是量化的句子，我們稱我們已經量化了這個謂詞。量化在自然語言和形式語言中都使用。在自然語言中，量詞的例子有「所有」、「某些」；「很多」、「少量」、「大量」也是量詞。在形式語言中，量化是從舊公式產生新公式的公式構造子(constructor)。語言的語義指定了如何把這個構造子解釋為一個有效性的廣度。量化是變數約束操作的實例。

在謂詞邏輯的兩類基本量化是全稱量化和存在量化。這些概念被更詳細的敘述於在單獨文章中；下面我們討論適用於二者的特徵。其他種類的量化包括唯一量化。

自然語言中的量化

所有已知人類語言都使用量化，即使是那些沒有完整的數字系統的語言(Wiese 2004)。例如:

「我最近訂的所有玻璃都碎了」。
「站在河邊的一些人帶著白臂章」。
「我交談的多數人都沒有從屬的俱樂部」。
「在候診室里的所有人都對 Ballyhoo 醫生有至少一個抱怨」。
「在他的班級中有些人能夠正確的回答我提出的所有問題」。
「大量的人是聰明的」。

不存在簡單的方式把這些表達重新公式化為句子們的合取或析取，它們每個都有個體的簡單謂詞如「酒杯碎了」。這些例子也暗示了在自然語言中的量化表達式構造可以是語法上非常複雜的。幸運的是，對於數學斷言，量化過程在語法上是更加直接的。

研究自然語言中的量化比研究形式語言的量化要難很多。這部分的由於自然語言句子的文法結構可能隱藏了邏輯結構的事實。而數學約定嚴格的為形式語言量詞指定了有效範圍；為自然語言指定有效性的範圍要求處理不平凡的語義問題。

Montague文法給出了新穎的自然語言的形式語義。它提起爭論說它比弗雷格、羅素和蒯因的傳統處理更加自然的對自然語言的形式化表現。

數學論斷中的量詞

我們開始討論在非正式數學討論中的量化。考慮下列陳述

1·2 = 1 + 1，且 2·2 = 2 + 2，且 3 · 2 = 3 + 3，....，且 n · 2 = n + n 等等。

在外觀上這是命題的無限合取。從形式語言的觀點看這立即是一個問題，因為我們希望語法規則生成有限個對象。把這個缺陷放到一邊，還要注意在這個例子中我們幸運的有一個生成所有結合項(conjunct)的過程。但是，如果我們想要斷言關於無理數的某個事物，我們沒有辦法枚舉所有結合項，因為無理數不能被枚舉。避免這些問題的一個簡潔的公式化是使用全稱量化:

對於任何自然數 n, n·2 = n + n。

類似的分析適用於析取，

1 是質數, 或 2 是質數，或 3 是質數等等。

它可以使用存在量化重組:

對於某些自然數 n, n 是質數。

量詞的嵌套

考慮下列語句:

對於任何自然數 n，有一個自然數 s 使得 s = n × n。

這明顯是真的；它只是斷言了沒有自然都有一個平方。

下面這個斷言中的量詞的意義就非常不同了:

有一個自然數 s 使得對於所有自然數 n，有 s = n × n。

這明顯是假的；它斷言了有一個單一的自然數是 s 是所有自然數的平方。

這展示了量詞嵌套的時候的基本要點: 量詞間隔的次序是絕對重要的。不平常些的例子是來自數學分析的一致連續的概念，只是通過對換了兩個量詞的位置，它就不同於更加熟悉的逐點連續的概念。

量詞的範圍

每個量詞都涉及一個特定的變數和這個變數的論域或「量化範圍」。量化的範圍指定這個變數採用的值的集合。在上面的例子中，量化的範圍是自然數的集合。量化範圍的指定允許我們表達出，在斷言一個謂詞對某些自然數成立和對某些實數成立之間的區別。說明性的約定經常保留某些變數名字，比如 n 保留給自然數，x 保留給實數，儘管依賴於命名約定一般不能工作，因為變數的範圍在數學論證過程中是可以變更的。

限制論域的更自然的方式是使用「監控量化」。例如：

對於某些自然數 n，n 是偶數且 n 是質數。

意味著

對於某些偶數 n，n 是質數。

早某些數學理論中你可以預先假定一個固定的單一論域。例如，在 Zermelo Fraenkel 集合論中，變數範圍是在所有集合之上。在這種情況下，可以監控量詞來模擬更小的量化範圍。如上述例子中

對於所有自然數 n，n·2 = n + n

在 Zermelo-Fraenkel 集合論中，你可以說

對於任意 n，如果 n 屬於 N，則 n·2 = n + n，

這裡的 N 是所有自然數的集合。

量詞的記號

全稱量詞的傳統符號是 ∀，它倒過來的字母 A，表示單詞「all」。存在量詞的相應的符號是 ∃，它是反過來的字母 E，表示單詞「exists」。相應的量化表達式構造如下：

$\exists{n}\, P \quad \forall{n}\, P$

這裡的 P 指示一個公式。有很多變體被使用了，比如

$\exists{n}\, P \quad (\exists{n}) P \quad \exists{n}(P) \quad \exists_{n}\, P \quad \exists{n}{,}\, P \quad \exists{n}{:}\, P \quad \exists{n}{\in}\mathbb{N}\, P \quad \exists\, n \in \mathbb{N}{,}\, P \quad \exists{n}{:}\mathrm{uint}\, P$

所有這些變體都同樣適用於全稱量化和存在量化。

二十世紀早期的文獻不使用 ∀ 符號。典型的記號是用 (x)P 來表達 "對於所有的 x，P" 和 "(∃x)P" 表示"存在 x 使得 P"。∃ 符號是皮亞諾在1890年左右提出的。後在，在1930年左右，Gerhard Gentzen 介入了 ∀ 符號來表示全稱量化。弗雷格的《概念文字》使用完全不同記號，它根本就不包括存在量詞；∃x:P 總是用概念文字表達為等價的 ¬∀x:¬P。

注意某些版本的記號明確的提及了量詞的範圍。量詞的範圍總是必須指定，但是對於給定的數學理論，可以用多種方式來做:

為每個量詞假定一個固定的論域，比如 Zermelo Fraenkel 集合論，
預先固定多個論域並要求每個變數有一個聲明了域，它就是這個變數的類型。這類似於強類型的計算機編程語言，那裡的變數有聲明過的類型。
明確的提及量化的範圍，可能使用在這個域中所有對象的集合或在這個域中對象的類型符號。

還要注意在特定限制下，也就是在不發生變數捕獲條件下，你可以使用任何變數替代任何其他變數作為量化變數。即使這種記號使用了有類型的變數，你仍可以使用這種類型的任何變數。變數捕獲的問題是極其重要的，並在下面的形式語義章節中討論。

非正式的，"∀x" 或 "∃x" 也可以出現在 P(x) 之後，甚至在 P(x) 的中間，如果它是個長短語的話。正式的說，介入虛(dummy)變數的短語在標準上要位於前面。

注意數學公式混合了量詞的符號表達和自然語言量詞，比如：

對於任何自然數 x, ....

存在一個 x 使得 ....

對於至少一個 x....

唯一量化的關鍵字包括:

對於正好一個自然數 x, ....

有一個且只有一個 x 使得 ....

你使用代名詞來避免變數名字如 x。例如：

對於任何自然數，它乘以 2 等於它加以自身

某些自然數是質數。

形式語義

數理語義是用形式化的數學上的特定語言表達的研究意義的數學應用。它有三個要素: 通過語法的一類對象的數學規定，各種語義域的數學規定，和在二者之間的關係，它通常表達為從語法對象到語義對象的函數。在本文中，我們只致力於描述量詞元素如何解釋的問題。

在本文中，我們只考慮帶有函數符號的一階邏輯。我們建議讀者看模型論的文章獲得關於在這個邏輯框架內公式釋義的更詳細信息。公式的語法可以用語法樹給出。量詞有範圍，而變數 x 是自由的，如果它不在這個變數的量化範圍內。所以在

$\forall x (\exists y B(x,y)) \vee C(y,x)$

中，x 和 y 二者在 C(y,x) 中的出現是自由的。

展示範圍和變數捕獲的語法樹

一階謂詞演算的釋義假定給出一個個體域 X。自由變數是 x₁, ..., x_n 的一個公式 A 被解釋為 n 個參數的一個布爾值函數 F(v₁, ..., v_n)，這裡的每個參數都定範圍在域 X 上。布爾值意味著這個函數採用值 T(解釋為真)或 F(解釋為假)中的一個。公式

$\forall x_n A(x_1, \ldots , x_n)$

的釋義是 n-1 個參數的函數 G，使得 G(v₁, ...,v_n-1) = T，若且唯若對於在X 中所的 w 有 F(v₁, ..., v_n-1, w) = T。如果對於至少 w 的一個值，有 F(v₁, ..., v_n-1, w) = F，則 G(v₁, ..,v_n-1) = F。類似的，公式

$\exists x_n A(x_1, \ldots , x_n)$

的釋義為 n-1 個參數的函數 H，使得 H(v₁, ...,v_n-1) = T，若且唯若對於至少一個 w 有 F(v₁, ...,v_n-1, w) = T，否則 H(v₁, ..., v_n-1) = F。

唯一量化的語義要求帶有等號的一階謂詞演算。這意味著這裡要有一個顯著的二元謂詞 "="；語義也要相應的修改來使 "=" 總是被解釋為在 X 上的二元等價關係。

$\exists ! x_n A(x_1, \ldots , x_n)$

被解釋為 n-1 個參數的函數，它是如下兩個釋義的邏輯與

$\exists x_n A(x_1, \ldots , x_n)$

$\forall y,z \left\{ A(x_1, \ldots ,x_{n-1}, y) \wedge A(x_1, \ldots ,x_{n-1}, z) \implies y = z \right\}$

幾個、多個和其他程度的量詞

我們只考慮了在數學中的全稱、存在和唯一量化。它們都不能用來量化如下

今晚在舞場有很多舞女。

儘管在本文中我們沒有考慮自然語言的語義，我們將嘗試用如下類型的自然語言為斷言提供語義

有很多 n < 100 的整數，使得 n 能被 2 或 3 或 5 整除。

一種可能的解釋機制可以獲得如下: 假設除了語義域 X 之外，我們還給出在 X 上定義一個機率測度 P 和截斷數 0 < a ≤ b ≤ 1。如果 A 是帶有自由變數 x₁,...,x_n 的公式，它的釋義是變數 v₁,...,v_nthe 的函數 F，則

$\exists^{\mathrm{many}} x_n A(x_1, \ldots, x_{n-1}, x_n)$

的釋義是 v₁,...,v_n-1 的函數，它是 T 若且唯若

$\operatorname{P} \{w: F(v_1, \ldots, v_{n-1}, w) = \mathbf{T} \} \geq b$

，否則是 F。類似的，

$\exists^{\mathrm{few}} x_n A(x_1, \ldots, x_{n-1}, x_n)$

的釋義是 v₁,...,v_n-1 的函數，它是 F 若且唯若

$0< \operatorname{P} \{w: F(v_1, \ldots, v_{n-1}, w) = \mathbf{T}\} \leq a$

，否則是 T。我們已經完全避免了關於釋義函數的測度性的技術問題的討論；其中某些技術問題要求Fubini 定理。

我們還要警告讀者這種語義相應的邏輯是非常複雜的。

形式化的歷史

在形式邏輯中的量化的第一個基於變數的處理直到19世紀才出現，儘管詞項邏輯以同在自然語言很緊密的方式處理量化，但不適合於形式分析。亞里士多德邏輯在公元前1世紀給出了「所有」、「某些」和「沒有」量詞和對真勢模態的處理。

第一個基於變數的邏輯處理是弗雷格的《概念文字》，緊隨在查爾斯·皮爾士獨立的公式化了存在圖之後。弗雷格的方法被證明更有影響，因為它被皮亞諾接受，儘管 Pierce 的邏輯最近更加引起邏輯學家對異類推理和圖表推理的興趣。

量化的第一個嚴格的表示法出現在弗雷格的《概念文字》。弗雷格使用在變數名下划的曲線來指示在它隨後的公式中這個變數是被全稱量化的。弗雷格沒有給存在量化特殊的記號，而是使用等價的 $\sim\forall x:\sim\ldots$ 。

在懷特海和羅素的《數學原理》中，弗雷格的記號被簡化了。使用公式「 $(x)φ$ 」來指示這個公式 φ 對於 x 的所有的值都是真的。存在量化被寫為「 $(\exists x)\phi$ 」；∃ 符號自身是皮亞諾在1897年首次使用的。

∀ 符號是後來發明的，它是格哈德·根岑在1935年模仿皮亞諾的 ∃ 符號而發明。

引用

Jon Barwise and John Etchemendy, 2000. Language Proof and Logic. CSLI (University of Chicago Press) and New York: Seven Bridges Press. A gentle introduction to first-order logic by two first-rate logicians.
Crosby, Alfred W. (1996) The Measure of Reality: Quantification and Western Society, 1250-1600. Cambridge University Press.
Gottlob Frege, 1879. Begriffsschrift. Translated in Jean van Heijenoort, 1967. From Frege to Godel: A Source Book on Mathematical Logic, 1879-1931. Harvard Univ. Press. The first appearance of quantification.
David Hilbert and Wilhelm Ackermann, 1950 (1928). Principles of Theoretical Logic. Chelsea. Translation of Grundzüge der theoretischen Logik. Springer-Verlag. The 1928 first edition is the first time quantification was consciously employed in the now-standar manner, namely as binding variables ranging over some fixed domain of discourse. This is the defining aspect of first-order logic.
Charles Peirce, 1885, "On the Algebra of Logic: A Contribution to the Philosophy of Notation, American Journal of Mathematics 7: 180-202. Reprinted in Kloesel, N. et al, eds., 1993. Writings of C. S. Peirce, Vol. 5. Indiana Univ. Press. The first appearance of quantification in anything like its present form.
Hans Reichenbach, 1975 (1947). Elements of Symbolic Logic, Dover Publications. The quantifiers are discussed in chapters §18 "Binding of variables" through §30 "Derivations from Synthetic Premises".
Wiese, 2003. Numbers, language, and the human mind. Cambridge University Press. ISBN 0-521-83182-2.
Westerstahl, Dag, 2001, "Quantifiers," in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic. Blackwell.

參見

外部連結

http://www.stanford.edu/group/nasslli/courses/peters-wes/PWbookdraft2-3.pdf

1個分類: 數理邏輯

性

stock | retire | vm
Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History