1.3 量詞與否定

動機

命題邏輯把完整句子當作一個不可分割的命題，但「所有人都會死」和「有一個人不喜歡芝士」還需要說明對象及其性質。謂詞邏輯加入變數、謂詞和量詞，使質數定義、先修要求、函數和關係中的對象及條件得以明確表達。可靠的方法是由外向內閱讀：先確定定義域，再確定每個量詞的作用域、連接詞和見證的依賴關係。否定時也要由外向內，保留變數所受的每個條件。

「所有人都會死；某人是人；所以某人會死」可以寫成 $\forall x\,(H(x)\to M(x))$ 、 $H(s)$ ，從而得到 $M(s)$ 。先把全稱前提代入指定的 $s$ ，再使用蘊含。

定義

謂詞與命題

謂詞是其真值可能依賴一個或多個變數的公式。沒有被量詞控制的變數出現稱為自由出現。給自由變數賦值，可以在該賦值下評估公式的真值，但不會消除自由變數。用量詞綁定所有自由出現，才得到語法上封閉的句子。

定義

定義域與賦值

定義域是量詞變數可以選取的集合。賦值為自由變數指定值。若定義域為整數， $P(x,y)$ 表示 $x=y$ ，賦值 $x=1$ 、 $y=2$ 使 $P(x,y)$ 為假。在 $\forall x\,P(x,y)$ 中， $x$ 被綁定而 $y$ 仍然自由，所以公式在語法上仍然開放；賦值可以評估 $y$ ，但自由狀態本身不預設真值一定改變。量詞只在自己的作用域內控制變數；內層量詞重用字母時，指的是內層綁定。

定義域是陳述的一部分。 $x^2=1$ 在自然數中有一個解，在整數、有理數和實數中有兩個解。因此 $\forall x\,P(x)$ 在說明定義域前並不完整。有界寫法把集合直接寫出： $\forall x\in S\,P(x)$ 和 $\exists x\in S\,P(x)$ 。

定義

全稱量詞與存在量詞

$\forall x\,P(x)$ 表示定義域內每個 $x$ 都使 $P(x)$ 為真。 $\exists x\,P(x)$ 表示至少有一個允許的 $x$ 使 $P(x)$ 為真；這個值叫做見證。證明全稱句要從任意元素開始，證明存在句要給出並檢驗一個見證。否定全稱句只需一個反例，否定存在句則必須說明所有候選都失敗。

例題

賦值後再觀察量詞

令有界定義域 $D=\{1,2\}$ ，賦值的環境域為 $\mathbb Z$ ， $P(x,y)$ 表示 $x=y$ 。賦值 $x=1$ 、 $y=2$ 時開放公式為假。在 $\forall x\in D\,P(x,y)$ 中， $x$ 已綁定而 $y$ 自由，所以它在語法上仍是開放公式；自由變數不保證真值一定隨賦值改變。例如 $\forall x\in\mathbb Z\,(x=y)$ 仍因 $y$ 自由而開放，卻對每個整數賦值都為假，因為 $x=y+1$ 是反例。回到有界公式， $y=1$ 時因 $x=2$ 失敗而為假， $y=3$ 雖不屬於有界見證域，卻可作為環境中的外部賦值。公式 $\forall x\in D\,\exists y\in D\,P(x,y)$ 則是命題：對每個 $x$ 取 $y=x$ 即可。量詞綁定變數，但沒有改變謂詞本身。

量詞的語法與作用域

量詞的作用域是緊接其後的公式，括號可以把作用域擴大。例如

\forall x\,(P(x)\to\exists y\,(Q(x,y)\land R(y)))

外層 $\forall$ 控制括號中的 $x$ ，內層 $\exists$ 只控制自己的括號中的 $y$ 。 $y$ 可以依賴已選定的 $x$ ，但不能在內層作用域外使用。綁定變數只是局部佔位符；若 $z$ 在公式體內沒有出現，可把 $\forall x\,P(x)$ 改寫為 $\forall z\,P(z)$ 。若替換字母已被內層量詞使用，就可能發生變數捕獲，真值隨之改變。

量詞也決定證明的開頭。證明 $\forall x\in D\,P(x)$ 時寫「令 $x\in D$ 任意」，不能只檢驗一個方便的數。證明 $\exists x\in D\,P(x)$ 時要先說出候選，再驗證它屬於 $D$ 並滿足 $P$ 。在 $\forall x\,\exists y\,P(x,y)$ 中先給定任意 $x$ ， $y$ 可以依賴 $x$ ；在 $\exists y\,\forall x\,P(x,y)$ 中必須先選一個固定 $y$ 。

若有界定義域為空，則由展開式可見： $\forall x\in\varnothing,P(x)$ 為真，因為每個蘊含 $x\in\varnothing\to P(x)$ 的前件都為假；而 $\exists x\in\varnothing,P(x)$ 為假，因為不存在能使合取 $x\in\varnothing\land P(x)$ 為真的對象。

否定如何翻轉量詞

定理

量詞否定律

在固定定義域上，

\neg\forall x\,P(x)\equiv\exists x\,\neg P(x), \qquad \neg\exists x\,P(x)\equiv\forall x\,\neg P(x).

否定會翻轉外層量詞並否定其完整作用域，定義域不變。

定理

有界量詞與德摩根律

有界寫法是縮寫：

\forall x\in S\,P(x)\equiv\forall x\,(x\in S\to P(x)), \qquad \exists x\in S\,P(x)\equiv\exists x\,(x\in S\land P(x)).

所以

\neg\forall x\in S\,P(x)\equiv\exists x\in S\,\neg P(x), \qquad \neg\exists x\in S\,P(x)\equiv\forall x\in S\,\neg P(x).

內部還要使用 $\neg(A\land B)\equiv(\neg A\lor\neg B)$ 、 $\neg(A\lor B)\equiv(\neg A\land\neg B)$ 以及 $\neg(A\to B)\equiv A\land\neg B$ 。

證明思路

「並非每個對象都滿足 $P$ 」的意思，正是「存在一個對象使 $P$ 失敗」；「沒有對象滿足 $P$ 」的意思，則是「每個對象都使 $P$ 失敗」。遇到巢狀量詞時一次只翻轉一個，由外向內進行：

\begin{aligned} \neg\forall x\,\exists y\,P(x,y) &\equiv\exists x\,\neg\exists y\,P(x,y)\\ &\equiv\exists x\,\forall y\,\neg P(x,y). \end{aligned}

最後的 $x$ 是使原全稱句失敗的對象；對這個 $x$ ，所有 $y$ 都使 $P$ 失敗。若只翻轉第一層，就會漏掉內層作用域。

保留定義域並追蹤見證

例題

否定質數的定義

全程固定自然數 $n\ge 2$ ；這個假設不能刪除，因為 1 不是質數。質數定義為

\forall d\in\mathbb N\,\bigl(d\mid n\to(d=1\lor d=n)\bigr).

逐層否定：

\begin{aligned} \neg\forall d\in\mathbb N\,\bigl(d\mid n\to(d=1\lor d=n)\bigr) &\equiv\exists d\in\mathbb N\,\neg\bigl(d\mid n\to(d=1\lor d=n)\bigr)\\ &\equiv\exists d\in\mathbb N\,\bigl(d\mid n\land\neg(d=1\lor d=n)\bigr)\\ &\equiv\exists d\in\mathbb N\,\bigl(d\mid n\land d\ne1\land d\ne n\bigr). \end{aligned}

讀法是：存在自然數 $d$ ，它整除 $n$ ，而且既不是 1 也不是 $n$ 。這正是非平凡除數。否定保留了 $n\ge2$ 這個例子的假設。

例題

有界條件必須隨見證保留

否定

\forall n\in\mathbb Z\,(n\gt 0\to n^2\gt n)

得到

\exists n\in\mathbb Z\,(n\gt 0\land n^2\le n).

$n=1$ 同時滿足 $n\gt0$ 和 $n^2\le n$ ，所以是見證。0 雖滿足 $0^2\le0$ ，卻不滿足 $n\gt0$ ，不能作為見證。

一個固定見證，還是隨輸入選擇

例題

量詞次序與依賴見證

在 $\mathbb N$ 上，

\forall x\in\mathbb N\,\exists y\in\mathbb N\,(x\lt y)

為真，給定任意 $x$ 後取 $y=x+1$ 。但

\exists y\in\mathbb N\,\forall x\in\mathbb N\,(x\lt y)

為假，因為固定的 $y$ 會被允許的 $x=y$ 反駁。有限集合也有相同現象：在 $X=\{1,2\}$ 、 $P(x,y)$ 表示 $x=y$ 時， $\forall x\in X\,\exists y\in X\,P(x,y)$ 由 $y=x$ 成立； $\exists y\in X\,\forall x\in X\,P(x,y)$ 為假，因為 $y=1$ 在 $x=2$ 失敗， $y=2$ 在 $x=1$ 失敗。

例題

量詞的分配與同類交換

在固定定義域上，有以下兩個恆等式

\forall x\,(P(x)\land Q(x))\equiv(\forall x\,P(x))\land(\forall x\,Q(x)), \qquad \exists x\,(P(x)\lor Q(x))\equiv(\exists x\,P(x))\lor(\exists x\,Q(x))

第一個從任意元素出發：同一元素的合取為真，當且僅當兩個性質都成立。第二個按見證屬於哪個析取分支分類，反向則直接使用該見證。同類量詞也可交換，但含義要說準確： $\forall x\forall y,P(x,y)$ 檢查每個有序對， $\exists x\exists y,P(x,y)$ 只需一個有序對。不同類量詞通常不可交換。

在 $\{1,2\}$ 上令 $P(x)$ 為 $x=1$ 、 $Q(x)$ 為 $x=2$ ，則 $\forall x(P(x)\lor Q(x))$ 為真，而 $(\forall xP(x))\lor(\forall xQ(x))$ 為假；同樣， $\exists x(P(x)\land Q(x))$ 為假，而 $(\exists xP(x))\land(\exists xQ(x))$ 為真。這是兩個交叉失敗的具體反例。

定理

見證傳遞

若 $\forall x\,(P(x)\to Q(x))$ 且 $\exists x\,P(x)$ ，則 $\exists x\,Q(x)$ 。取滿足 $P(a)$ 的見證 $a$ ；把全稱前提代入 $a$ 得 $P(a)\to Q(a)$ ，所以 $Q(a)$ ，同一個 $a$ 就是結論的見證。

例題

否定存在合取

由外向內使用量詞否定律和德摩根律：

\neg\exists x\,(P(x)\land Q(x)) \equiv\forall x\,\neg(P(x)\land Q(x)) \equiv\forall x\,(\neg P(x)\lor\neg Q(x))

最後一句表示每個對象至少有一個性質失敗，並不表示每個對象兩個性質都失敗。

例題

在指定定義域中讀回有序量詞

公式

\exists y\,\forall x\,(x\le y)

表示存在一個固定的 $y$ ，使定義域中的每個 $x$ 都滿足 $x\le y$ 。它是否為真取決於定義域；未說明定義域時，不能把它誤讀成關於所有數的斷言。

例題

不同圖書與不同借閱者

設 $People$ 和 $Books$ 分別為人和書的集合。兩句陳述是

\forall b\in Books\,\exists x\in People\,Borrows(x,b)

和

\exists x\in People\,\forall b\in Books\,Borrows(x,b).

第一句表示每本書至少有一個借閱者；第二句表示同一個人借閱所有書。兩本書由不同的人分別借走時，第一句為真而第二句為假，所以量詞次序確實改變了意思。

「每個人至少讀兩本書」要求對每位讀者給出兩本不同的書：

\forall x\in People\,\exists b_1,b_2\in Books\,(b_1\ne b_2\land Reads(x,b_1)\land Reads(x,b_2))

例題

課程先修要求的否定

設 $Student(x)$ 、 $Enrolls(x)$ 和 $Prereq(x)$ 分別表示學生、選課和符合先修要求。考慮以下陳述

\forall x\,\bigl((Student(x)\land Enrolls(x))\to Prereq(x)\bigr).

否定是

\exists x\,\bigl(Student(x)\land Enrolls(x)\land\neg Prereq(x)\bigr).

見證必須是已選課而又不符合先修要求的學生。沒有選課的人不反駁原蘊含，因為原句沒有對他作出要求。

例題

在學生定義域中翻譯

定義域為某大學的所有學生。若 $S(x)$ 表示「 $x$ 修讀數學」， $P(x)$ 表示「 $x$ 通過考試」，則「所有修讀數學的學生都通過考試」「至少一名學生通過考試」「至少一名修讀數學的學生沒有通過考試」分別寫成

\forall x\,(S(x)\to P(x)),\qquad \exists x\,P(x),\qquad \exists x\,(S(x)\land\neg P(x))

定義域已經包含「學生」；謂詞只表達題目要求的性質。

先表達依賴關係，再寫符號

例題

從英文建立量詞公式

「每個學生至少修過一門數學課」是

\forall x\,\bigl(Student(x)\to\exists m\,(MathCourse(m)\land Taken(x,m))\bigr).

「有一位教授教授系內的每一門課」是

\exists p\,\bigl(Professor(p)\land\forall c\,(DepartmentCourse(c)\to Teaches(p,c))\bigr)

「每場考試都有一道每個學生都覺得困難的題目」是

\forall e\,\bigl(Exam(e)\to\exists q\,(Question(q,e)\land\forall s\,(Student(s)\to Difficult(s,q)))\bigr).

題目可以隨考試改變，但對該考試選定的題目必須對每個學生都困難。把存在量詞移到最外層，就錯誤地聲稱有一道題適用於所有考試。

用見證診斷錯誤的陳述

例題

識別錯誤形式化與安全改名

公式

\exists d\in\mathbb N\,\bigl(d\mid n\to(d=1\lor d=n)\bigr)

太弱。保留 $n\ge2$ 的假設時，取 $d=n+1$ ；它不整除 $n$ ，所以蘊含以前件為假而真，存在式無需檢查所有除數。（當 $n=0$ 時不要用這個特定見證，因為 $1$ 整除 $0$ 。）質數定義需要 $\forall d$ 。事實上，取 $d=1$ 就能對任何 $n$ 成為見證，因為 $1\mid n$ 且 $d=1$ ； $d=n+1$ 則突出了 $n\ge2$ 時的真空成立。同樣， $\forall a\,\exists d\,SubmittedBefore(a,d)$ 允許每份作業有自己的期限；單一期限應寫成 $\exists d\,\forall a\,(Assignment(a)\to SubmittedBefore(a,d))$ 。

$\forall x\,\exists y\,Attends(x,y)$ 也不是「每場講座至少有一名學生參加」的正確寫法；它沒有說明 $x$ 和 $y$ 的類型。正確形式是

\forall \ell\,(Lecture(\ell)\to\exists s\,(Student(s)\land Attends(s,\ell))).

替換字母在公式體內處處不出現是充分的安全保障，並非必要條件；必要條件是改名不能改變相關出現位置的綁定狀態，不能造成變數捕獲。 $X=\{1,2\}$ 上的

\forall x\in X\,\exists y\in X\,(x\ne y)

為真。若把外層 $x$ 草率改成已有的 $y$ ，便得到 $\forall y\in X\,\exists y\in X\,(y\ne y)$ ，內層量詞捕獲了兩個出現位置，公式為假。改用全新的 $z$ 才得到等價的 $\forall z\in X\,\exists y\in X\,(z\ne y)$ 。

例題

唯一性包含兩個證明要求

「存在唯一的 $x\in D$ 使 $P(x)$ 」表示存在性和至多一個：

\exists x\in D\,\bigl(P(x)\land\forall y\in D\,(P(y)\to y=x)\bigr).

先給一個見證並驗證 $P$ ，再令 $y$ 為任意滿足 $P$ 的元素並證明 $y=x$ 。在整數中 $x^2=1$ 有 $1$ 和 $-1$ 兩個見證，存在但不唯一。對 $x^2=0$ ， $0$ 是見證；若整數 $y$ 滿足 $y^2=0$ ，平方非負且只有 $y=0$ 時平方為零，所以 $y=0$ ，這就完成了至多一個的證明。「我的同學恰有一個朋友」也用同一模式：以人為定義域、 $o$ 指定該同學時， $\exists!x\,Friend(o,x)$ 同時要求朋友存在且至多一人。

例題

函數與關係的量詞定義

把「 $f:X\to Y$ 是單射」寫成

\forall x_1,x_2\in X\,(f(x_1)=f(x_2)\to x_1=x_2).

證明時先取任意 $x_1,x_2\in X$ ，假設像相等，再推出輸入相等；反例則給出兩個不同輸入而像相等。偏序的完整條件是

\forall x\in X\,(xRx),\quad \forall x,y\in X\,(xRy\land yRx\to x=y),\quad \forall x,y,z\in X\,(xRy\land yRz\to xRz)

等價關係把中間一項換成 $\forall x,y\in X\,(xRy\to yRx)$ 。每一項都要單獨履行證明要求，不能用一個樣本代替全稱證明。

從符號讀回句子

若人的定義域滿足

\forall x\,\exists y\,(x\ne y\land Friend(x,y)),

它表示每個人都有一個與自己不同的朋友。若定義域包含人和學生，

\exists x\,\forall y\,(Student(y)\to Older(x,y))

表示存在一個人比每一名學生年長，並不表示每個人都比每名學生年長，也不自動要求這個人是學生。讀回句子時，要明確第一個見證是誰，以及後面的見證是否可以依賴它。

常見錯誤

在 $\exists x\,(Student(x)\to P(x))$ 中，非學生就能令蘊含為真而成為見證，即使他不滿足 $P$ ；若見證必須是學生，應寫成 $\exists x\,(Student(x)\land P(x))$ 。「只有學生可以提交」是 $\forall x\,(Submitted(x)\to Student(x))$ ，而「所有學生都提交」是 $\forall x\,(Student(x)\to Submitted(x))$ ；「只有」決定蘊含方向。

常見錯誤

蘊含不等於合取

否定 $A\to B$ 得 $A\land\neg B$ 。不要寫成 $\neg A\to\neg B$ ，也不要丟掉原蘊含的前件。普遍量化的反例必須屬於限制的類別並且使結論失敗。

常見錯誤

不要交換混合量詞

同類量詞有時可以交換，但 $\forall x\exists y$ 和 $\exists y\forall x$ 通常不同。有限集合 $X=\{1,2\}$ 的等式例子給出了具體反例。

常見錯誤

真值表不能枚舉無限定義域

謂詞邏輯擴展命題邏輯。真值表可以處理連接詞的真值，卻不能代替在 $\mathbb N$ 上對所有元素作證明。全稱句要用任意元素證明或一個反例否定，存在句要給見證或說明所有候選失敗。

逐步追蹤否定

使用 stepper 逐層在陳述和否定之間轉換：翻轉一個量詞，否定完整作用域，再化簡連接詞。它只是輔助檢查，不替代書面證明。

邊讀邊試

仔細否定一個帶量詞的陳述

這個示範逐步顯示量詞否定的每一步。

例子

對每個實數 x，都有 x^2 >= 0。

1. 先從外層量詞開始：「對每個 x」。

總結

量詞在固定定義域內綁定變數；自由變數仍需要賦值。有界全稱使用蘊含，有界存在使用合取，否定時定義域不變。由外向內翻轉量詞並使用德摩根律，尤其要記住 $\neg(A\to B)\equiv A\land\neg B$ 。量詞次序決定見證能否依賴輸入；全稱證明從任意元素開始，存在證明給出已檢驗的見證，唯一性則要分別證明存在與至多一個。

練習：作用域、見證與證明

練習 1

在固定定義域上，完全化簡 $\neg\forall x\,\exists y\,P(x,y)$ 。

解答 · 提示

逐層翻轉量詞，並否定最後的謂詞。

解答 · 參考解答

$\exists x\,\forall y\,\neg P(x,y)$ 。第一個見證使原全稱句失敗，並且對它所有 $y$ 都失敗。

練習 2

形式化：有一名學生，在每場考試中都覺得至少一道題目困難。使用 Student、Exam、Question 和 Difficult。

解答 · 提示

先固定學生，再考慮考試；題目可以隨考試改變。

解答 · 參考解答

\exists s\,\bigl(Student(s)\land\forall e\,(Exam(e)\to\exists q\,(Question(q,e)\land Difficult(s,q)))\bigr).

學生的見證位於考試的量詞之外。給定任意考試後，再為同一名學生選擇一道題目。

練習 3

假設 $n\ge2$ 。為甚麼 $\exists d\in\mathbb N\,(d\mid n\to(d=1\lor d=n))$ 太弱，不能定義質數？

解答 · 提示

給出使蘊含因前件為假而成立的自然數見證。

解答 · 參考解答

在 $n\ge2$ 下取 $d=n+1$ 。它不整除 $n$ ，所以蘊含以前件為假而真；存在式沒有檢查所有除數，質數定義必須使用 $\forall d$ 。

練習 4

當定義域為 $\mathbb N$ 時，有限真值表能單獨判定 $\forall x\,P(x)$ 嗎？請說明正確的證明方法。

解答 · 提示

區分連接詞的真值賦值與對無限定義域元素的量化。

解答 · 參考解答

不能。真值表只處理有限個原子命題的真值，不能枚舉所有自然數。應對任意自然數作全稱證明，或給出一個自然數反例。

先讀這一頁

如果想先重溫命題邏輯，請讀 1.1 命題邏輯。

1.3 量詞與否定

動機

定義

謂詞與命題

定義域與賦值

全稱量詞與存在量詞

賦值後再觀察量詞

量詞的語法與作用域

否定如何翻轉量詞

量詞否定律

有界量詞與德摩根律

證明思路

保留定義域並追蹤見證

否定質數的定義

有界條件必須隨見證保留

一個固定見證，還是隨輸入選擇

量詞次序與依賴見證

量詞的分配與同類交換

見證傳遞

否定存在合取

在指定定義域中讀回有序量詞

不同圖書與不同借閱者

課程先修要求的否定

在學生定義域中翻譯

先表達依賴關係，再寫符號

從英文建立量詞公式

用見證診斷錯誤的陳述

識別錯誤形式化與安全改名

唯一性包含兩個證明要求

函數與關係的量詞定義

從符號讀回句子

常見錯誤

蘊含不等於合取

不要交換混合量詞

真值表不能枚舉無限定義域

逐步追蹤否定

仔細否定一個帶量詞的陳述

總結

練習：作用域、見證與證明

練習 1

練習 2

練習 3

練習 4

先讀這一頁

練習

先備知識

本單元重點詞彙

本系列更多筆記