數學證明與數學/邏輯原理/存在量詞

如果全稱量詞是合取的擴充套件版本，那麼關於析取的擴充套件版本呢？這是唯一一個這種擴充套件有意義的連線詞，你應該能夠說服自己。

存在量詞

我們透過以下方式定義存在量詞，它基於全稱量詞：

對於一些 $x$，$P(x)$

意味著

非（對於所有 $x$，非 $P(x)$）。

第二個語句有點複雜，讓我們分解它看看這個定義是否有意義。對於語句

對於所有 $x$，$Q(x)$

要為假，需要一個 $x$ 的值，使得 $Q(x)$ 為假。當 $Q(x)$ 是非 $P(x)$ 時，這意味著對於語句

對於所有 $x$，非 $P(x)$

要為假，需要一個 $x$ 的值，使得 $P(x)$ 為真。換句話說

非（對於所有 $x$，非 $P(x)$)

等同於說存在一個 $x$ 的值，使得 $P(x)$ 為真，或者更簡潔地說

對於一些 $x$，$P(x).$

還有關於語句

非（對於所有 $x$，非 $P(x)$)

需要注意的一點是，它取決於量詞和兩個否定符號的順序。更具體地說，

並非不是（對於所有$x$，$P(x)$)

以及

對於所有$x$，並非不是$P(x)$

都等價於

對於所有$x$，$P(x)$

這不是我們想要的。

從邏輯上解釋存在量詞的一種方式是說，對於所有 x，P(x) 等同於所有語句 P(a) 的析取，其中 a 取遍論域中的所有值。如果論域是有限的，則可以明確地寫出來。因此，如果論域包含兩個物件'a' 和 'b'，則

對於一些 $x$，$P(x)$

等同於

$P(a)$ 或 $P(b).$

這在我們的定義中是有意義的，因為

$P(a)$ 或 $P(b)$

等價於

並非（並非$P(a)$ 且 並非$P(b)$)

如果我們的論域沒有物件，那麼定義說

對於一些 $x$，$P(x)$

無論$P(x)$ 是什麼都是 False。這可能看起來有點奇怪，但它確實有意義，因為如果你把這個語句改成

存在某個$x$ 使得$P(x)$

那麼，如果

存在某個$x$

部分是 False，則它必須是 False。

如果我們的論域包含一個物件，$a,$ 那麼定義說

對於一些 $x$，$P(x)$

等同於

非（對於所有 $x$，非 $P(x)$)

或者

並非不是$P(a)$

或者

$P(a)$

巧合的是，事實證明

對於一些 $x$，$P(x)$

等價於

對於所有$x$，$P(x)$

在一個包含一個物件的宇宙中。

證明存在量詞

與這種型別的定義一樣，我們得到兩個推理規則

從

非（對於所有 $x$，非 $P(x)$)

推斷

對於一些 $x$，$P(x)$)

以及

從

對於一些 $x$，$P(x)$

推斷

非（對於所有 $x$，非 $P(x)$)

這些對於進行證明非常實用，所以我們將根據這些新增一些其他內容。首先，我們將證明，作為一個例子

命題 1：$P(a)$ 意味著對於一些 $x$，$P(x).$

以通常的方式設定蘊含的證明，得到

行	語句	證明
1	$P(a)$	假設
(某事物)
n	對於一些 $x$，$P(x)$	?
n+1	$P(a)$ 意味著對於一些 $x$，$P(x)$	從 1 和 n

此時，我們除了定義之外別無他物可以證明

對於一些 $x$，$P(x)$

所以對上一行使用它。

行	語句	證明
1	$P(a)$	假設
(某事物)
n−1	非（對於所有 $x$，非 $P(x)$)	?
n	對於一些 $x$，$P(x)$	從 n−1
n+1	$P(a)$ 意味著對於一些 $x$，$P(x)$	從 1 和 n

現在我們需要證明否定，所以假設該語句為真並推匯出矛盾。

行	語句	證明
1	$P(a)$	假設
2	對於所有 $x$，非 $P(x)$	假設
(某事物)
n−2	$False$	?
n−1	非（對於所有 $x$，非 $P(x)$)	從 2 和 n−2
n	對於一些 $x$，$P(x)$	從 n−1
n+1	$P(a)$ 意味著對於一些 $x$，$P(x)$	從 1 和 n

但是從 2 我們可推斷出非 $P(a)$，這會導致必要的矛盾，證明可以完成。

行	語句	證明
1	$P(a)$	假設
2	對於所有 $x$，非 $P(x)$	假設
3	非 $P(a)$	從 2
4	$False$	從 1 和 3
5	非（對於所有 $x$，非 $P(x)$)	從 2 和 4
6	對於一些 $x$，$P(x)$	從 5
7	$P(a)$ 意味著對於一些 $x$，$P(x)$	從 1 和 6

將命題 1 與其他推理規則結合起來，我們得到

從 $P(a)$ 推斷

對於一些 $x$，$P(x).$

使用存在量詞

使用存在量詞的規則相對複雜。它是基於以下命題，這將是我們第二個例子證明。

命題 2：（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$)) 蘊含 $Q.$

首先以正常方式建立蘊含證明，並將假設分解成單獨的陳述。

以通常的方式設定蘊含的證明，得到

行	語句	證明
1	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$))	假設
2	對於一些 $x$，$P(x)$	從 1
3	對於所有 $x$，($P(x)$ 蘊含 $Q$)	從 1
(某事物)
n	$Q$	?
n+1	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$)) 蘊含 $Q.$	從 1 和 n

使用定義展開第 2 行，因為這是目前為止使用存在量詞的唯一方法。

行	語句	證明
1	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$))	假設
2	對於一些 $x$，$P(x)$	從 1
3	對於所有 $x$，($P(x)$ 蘊含 $Q$)	從 1
4	非（對於所有 $x$，非 $P(x)$)	從 1
(某事物)
n	$Q$	?
n+1	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$)) 蘊含 $Q.$	從 1 和 n

現在我們需要證明 $Q$，由於似乎沒有直接證明，因此建立一個間接證明。

行	語句	證明
1	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$))	假設
2	對於一些 $x$，$P(x)$	從 1
3	對於所有 $x$，($P(x)$ 蘊含 $Q$)	從 1
4	非（對於所有 $x$，非 $P(x)$)	從 1
5	非 $Q$	假設
(某事物)
n−1	$False$	?
n	$Q$	從 5 和 n−1
n+1	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$)) 蘊含 $Q.$	從 1 和 n

為了得出矛盾，我們證明第 4 行是假的，換句話說

對於所有 $x$，非 $P(x)$

是真的。這是一個普遍的命題，因此引入一個任意的常數 $a$ 並推匯出非 $P(a)$

行	語句	證明
1	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$))	假設
2	對於一些 $x$，$P(x)$	從 1
3	對於所有 $x$，($P(x)$ 蘊含 $Q$)	從 1
4	非（對於所有 $x$，非 $P(x)$)	從 1
5	非 $Q$	假設
6	選擇 $a$	任意常數
(某事物)
n−3	非 $P(a)$	?
n−2	對於所有 $x$，非 $P(x)$	從 6 和 n−3
n−1	$False$	從 4 和 n−2
n	$Q$	從 5 和 n−1
n+1	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$)) 蘊含 $Q.$	從 1 和 n

此時 $a$ 可以代入第 3 行，並使用語句的推理規則來完成證明。

行	語句	證明
1	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$))	假設
2	對於一些 $x$，$P(x)$	從 1
3	對於所有 $x$，($P(x)$ 蘊含 $Q$)	從 1
4	非（對於所有 $x$，非 $P(x)$)	從 1
5	非 $Q$	假設
6	選擇 $a$	任意常數
7	$P(a)$ 蘊涵 $Q$	從 3
8	非 $P(a)$	從 5 和 7
9	對於所有 $x$，非 $P(x)$	從 6 和 8
10	$False$	從 4 和 9
11	$Q$	從 5 和 10
12	（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$)) 蘊含 $Q.$	從 1 和 11

散文格式

命題 2：（對於某些 $x$，$P(x)$) 並且（對於所有 $x$，($P(x)$ 蘊含 $Q$)) 蘊含 $Q.$

證明：假設對於某些$x$，$P(x).$ 也假設對於所有$x$，($P(x)$ 意味著 $Q.$ 我們透過反證法證明 $Q$，所以假設不是$Q.$ 為了得到矛盾，足以證明對於所有 $x$，不是$P(x)$，因為它與第一個假設相矛盾。 選擇$a.$ 從第二個假設，$P(a)$ 意味著 $Q.$ 但這和不是$Q$ 意味著不是$P(a).$ 對於任何$a$，所以對於所有 $x$，不是$P(x)$，這與第一個假設相矛盾。

透過將此命題與其他推理規則（包括證明普遍性的規則）結合起來，我們可以將其改寫為推理規則

如果有

對於某些$x$，P(x)

並且如果透過選擇$a$ 作為任意常數，可以推匯出

$P(a)$ 蘊涵 $Q$

然後推斷$Q$.

為了證明蘊含，需要假設 $P(a)$ 並推匯出 $Q$。將

選擇 $a$

與

假設 $P(a)$

步驟合併為一個，得到

選擇 $a:P(a).$

可以理解為

選擇 $a$ 使得 $P(a).$

透過這種簡化，推理規則變為

如果有

對於一些 $x$，$P(x)$

如果透過選擇 $a:P(a)$ 可以推匯出 $Q$，那麼可以推斷出 $Q$。

對於每個和所有

這兩個量詞可以以兩種方式組合

對於某些 $x$，對於所有 $y$，$P(x,y).$

對於所有 $y$，對於某些 $x$，$P(x,y)$

以及

為了清楚起見，最好將第一個重新表述為

存在一些 $x$，使得對於每個 $y$，$P(x,y).$

對於每個 $y$，存在一些 $x$ 使得 $P(x,y)$

第二個表述為

儘管只是量詞順序的變化，這兩個陳述卻不同。為了說明這一點，假設論域包含魔法戒指，並設 $P(x,y)$ 代表 "$x$ 統治 $y$"。第二個陳述僅僅說明每個戒指都被某個戒指統治。人們可以很容易地想象每個戒指都統治著自己，所以這並沒有太多意義。但第一個陳述說存在一個戒指，我們可以稱之為至尊魔戒，它統治著所有其他戒指；這可是一個相當厲害的戒指。請注意，我們使用第一個陳述中的“每個”來強調 $x$ 對每個 $y$ 都適用，而在第二個陳述中，我們使用“每個”來強調 $x$ 的值取決於 $y.$

所以第二個陳述並不意味著第一個，但我們可以證明，作為我們的第三個例子，第一個陳述意味著第二個。

命題 3: 存在某個 $x$ 使得對於每個 $y$，$P(x,y)$ 蘊涵著對於每個 $y$，存在某個 $x$ 使得 $P(x,y).$

按照常規方法設定直接證明，然後根據新規則使用存在量詞。

行	語句	證明
1	存在一些 $x$，使得對於每個 $y$，$P(x,y).$	假設
2	選擇 $a$：對於所有 $y$，$P(a,y).$	滿足條件的常數
(某事物)
n−1	對於每個 $y$，存在某個 $x$ 使得 $P(x,y).$	?
n	對於每個 $y$，存在某個 $x$ 使得 $P(x,y).$	從 1、2 和 n−1
n+1	存在一些 $x$ 使得對於每個 $y$，$P(x,y)$ 意味著對於每個 $y$，存在一些 $x$ 使得 $P(x,y).$	從 1 和 n

現在我們需要證明

對於每個 $y$，存在一些 $x$ 使得 $P(x,y)$

這是一個全稱量詞，因此我們對於任意 $b$ 來證明它

行	語句	證明
1	存在一些 $x$，使得對於每個 $y$，$P(x,y).$	假設
2	選擇 $a$：對於所有 $y$，$P(a,y).$	滿足條件的常數
3	選擇 $b$	任意常數
(某事物)
n−2	存在一些 $x$ 使得 $P(x,b).$	?
n−1	對於每個 $y$，存在某個 $x$ 使得 $P(x,y).$	根據3和n−2
n	對於每個 $y$，存在某個 $x$ 使得 $P(x,y).$	從 1、2 和 n−1
n+1	存在一些 $x$ 使得對於每個 $y$，$P(x,y)$ 意味著對於每個 $y$，存在一些 $x$ 使得 $P(x,y).$	從 1 和 n

現在我們可以將 $b$ 代入第2行，證明完成。

行	語句	證明
1	存在一些 $x$，使得對於每個 $y$，$P(x,y).$	假設
2	選擇 $a$：對於所有 $y$，$P(a,y).$	滿足條件的常數
3	選擇 $b$	任意常數
4	$P(a,b)$	從 2
5	存在一些 $x$ 使得 $P(x,b).$	根據4
6	對於每個 $y$，存在某個 $x$ 使得 $P(x,y).$	根據3和5
7	對於每個 $y$，存在某個 $x$ 使得 $P(x,y).$	根據1，2和6
8	存在一些 $x$ 使得對於每個 $y$，$P(x,y)$ 意味著對於每個 $y$，存在一些 $x$ 使得 $P(x,y).$	根據1和7

在散文版本中，不需要重複第6行和第7行，因此它變成了

命題 3: 存在某個 $x$ 使得對於每個 $y$，$P(x,y)$ 蘊涵著對於每個 $y$，存在某個 $x$ 使得 $P(x,y).$

證明： 假設存在一個 $x$，使得對於任意 $y$，$P(x,y).$ 選擇 $a$，使得對於任意 $y$，$P(a,y)$，並令 $b$ 為任意值。則 $P(a,b)$，因此存在一個 $x$，使得 $P(x,b).$ 由於 $b$ 為任意值，因此對於每個 $y$，存在一個 $x$，使得 $P(x,y).$