1.3 量詞與否定

量詞的作用，是將開放句變成命題。在本課之中，它們令我們可以說明「所有允許的對象」或者「至少有一個允許的對象」，而不需要逐個個案寫全部出來。

謂詞與定義域

定義

謂詞

謂詞是含有一個或多個自由變量的陳述。只有當每個自由變量都已經被賦值，或者被量詞綁定之後，它先會變成命題。

定義

定義域

定義域是變量允許取值的集合。

每次見到 ∀ 或 ∃，都要先問：變量可以在邊個集合之中取值？同一個形式，在不同定義域下可以有不同意思。

例如 $x^2 = 1$ 在自然數、整數、有理數同實數之中，會有不同答案。若果你沒有說明定義域，陳述其實還未完整。

常見錯誤

不好漏掉定義域

∀x P(x) 如果不清楚 x 可以取哪些值，就不算完整。實際上，定義域通常會明示，或者由上下文默認。

全稱量詞與存在量詞

定義

量詞

∀x P(x) 表示對每一個允許的 x，P(x) 都真。

∃x P(x) 表示至少有一個允許的 x 使得 P(x) 真。

如果想用口語說明：

∀ 是「對所有」或「對每個」。
∃ 是「存在」。

句子要到量詞加上去之後才算完成。所以 P(x) 本身不是命題，但 ∀x P(x) 同 ∃x P(x) 都是。

例題

把帶量詞的句子讀成英文

設 P(x) 代表「x 可以被 2 整除」，定義域是整數。

那麼 ∀x P(x) 就是：

「每個整數都可以被 2 整除。」

這句是假。相反，∃x P(x) 是：

「存在一個整數可以被 2 整除。」

這句是真，例如 $x = 2$ 。

解答

量詞做甚麼事

否定量詞

定理

量詞否定

最基本的否定規則是：

¬∀x\,P(x) \equiv ∃x\,¬P(x)

¬∃x\,P(x) \equiv ∀x\,¬P(x)

讀這兩條規則時，要記住兩件事：

外層量詞要翻轉。
內部謂詞要否定。

就是那麼簡單。

例題

否定質數的定義

一個典型練習使用以下方式定義 n 是質數：對每個自然數 d，如果 d 整除 n，那麼 $d = 1$ 或 $d = n$ 。

符號寫法是：

∀d ∈ N,\; d \mid n \to (d = 1 \lor d = n).

它的否定是：

∃d ∈ N \text{ 使得 } d \mid n \text{,而且 } d \neq 1 \text{ 並且 } d \neq n

這個正正就是「n 不是質數」的意思：存在一個非平凡除數。

解答

否定為甚麼正確

例題

否定一個學生陳述

設 Student(x) 表示「x 是學生」，Submitted(x) 表示「x 已提交表格」。

則

∃x\,(Student(x) \land Submitted(x))

表示至少有一個學生已提交表格。

它的否定是

∀x\,(\neg Student(x) \lor \neg Submitted(x)).

也就是話：每個允許的對象都至少欠缺其中一個性質。

解答

讀法

為甚麼量詞次序好重要

量詞次序是意思的一部分。

∀x ∃y P(x, y) 表示對每個 x，都可以找到一個可能不同的 y。

∃y ∀x P(x, y) 表示有同一個 y 對所有 x 都有效。

兩者差好遠。第一句容許 y 依賴 x，第二句不容許。

例題

每本書有借閱者，不等於同一個人借全部所有書

設 Book(b) 代表 b 是書，Borrows(x, b) 代表 x 借咗 b。

∀b\,(Book(b) \to ∃x\,Borrows(x, b))

意思是每本書至少有一個借閱者。

∃x\,∀b\,(Book(b) \to Borrows(x, b))

意思是有一個人借全部所有書。

第一句可以真，而第二句可以假。

解答

這個例子要記住甚麼

常見的錯誤形式化

常見錯誤

蘊含不等於合取

如果意思是「對每個學生，如果它有註冊，那麼它就滿足先修要求」，正確形式應該是

∀x\,((Student(x) \land Enrolls(x)) \to Prereq(x)).

如果寫成純粹 $Student(x) \land Enrolls(x)$ ，就會變成更強、而且完全不同的說法。

例題

把課程要求寫成量詞公式

設 Taken(x, m) 表示「學生 x 修過數學課 m」。「每個學生至少修過一門數學課」可寫成

∀x\,(Student(x) \to ∃m\,(MathCourse(m) \land Taken(x, m))).

這個寫法比起壓成一句模糊陳述更加清楚。

解答

為甚麼內層要有存在量詞

快速檢查

寫出 `∀x P(x)` 的否定，並化簡。

把外層量詞翻轉，再否定內部謂詞。

解答

答案

快速檢查

`∃x (x 是學生且 x 已提交表格)` 的否定是甚麼？

用德摩根律處理內部合取。

解答

答案

快速檢查

`∀x∃y P(x,y)` 同 `∃y∀x P(x,y)`，邊個較強？

想想是否只需一個 y 就能對所有 x 成立。

解答

答案

快速檢查

把 $∀b(Book(b) → ∃x Borrows(x,b))$ 讀成中文。

由外到內讀量詞。

解答

答案

嵌入式檢查

用 stepper 練習在帶量詞的陳述同其否定之間來回轉換。

邊讀邊試

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

互動步驟器會逐步顯示量詞否定的每一步。

例子

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

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

先讀這一頁

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

MATH1090：集合論

謂詞與定義域

謂詞

定義域

不好漏掉定義域

全稱量詞與存在量詞

量詞

把帶量詞的句子讀成英文

量詞做甚麼事

否定量詞

量詞否定

否定質數的定義

否定為甚麼正確

否定一個學生陳述

讀法

為甚麼量詞次序好重要

每本書有借閱者，不等於同一個人借全部所有書

這個例子要記住甚麼

常見的錯誤形式化

蘊含不等於合取

把課程要求寫成量詞公式

為甚麼內層要有存在量詞

快速檢查

寫出 `∀x P(x)` 的否定，並化簡。

答案

`∃x (x 是學生且 x 已提交表格)` 的否定是甚麼？

答案

`∀x∃y P(x,y)` 同 `∃y∀x P(x,y)`，邊個較強？

答案

把 $∀b(Book(b) → ∃x Borrows(x,b))$ 讀成中文。

答案

嵌入式檢查

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

先讀這一頁

本節掌握 checkpoint

填空："對所有 x，P(x)" 的否定是 "存在某個 x，使得 ____"。

先備知識

本單元重點詞彙

本系列更多筆記

1.3 量詞與否定

MATH1090：集合論

謂詞與定義域

謂詞

定義域

不好漏掉定義域

全稱量詞與存在量詞

量詞

把帶量詞的句子讀成英文

量詞做甚麼事

否定量詞

量詞否定

否定質數的定義

否定為甚麼正確

否定一個學生陳述

讀法

為甚麼量詞次序好重要

每本書有借閱者，不等於同一個人借全部所有書

這個例子要記住甚麼

常見的錯誤形式化

蘊含不等於合取

把課程要求寫成量詞公式

為甚麼內層要有存在量詞

快速檢查

寫出 ∀x P(x) 的否定，並化簡。

答案

∃x (x 是學生 且 x 已提交表格) 的否定是甚麼？

答案

∀x∃y P(x,y) 同 ∃y∀x P(x,y)，邊個較強？

答案

把 ∀b(Book(b)→∃xBorrows(x,b))∀b(Book(b) → ∃x Borrows(x,b))∀b(Book(b)→∃xBorrows(x,b)) 讀成中文。

答案

嵌入式檢查

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

先讀這一頁

本節掌握 checkpoint

先備知識

本單元重點詞彙

本系列更多筆記

寫出 `∀x P(x)` 的否定，並化簡。

`∃x (x 是學生且 x 已提交表格)` 的否定是甚麼？

`∀x∃y P(x,y)` 同 `∃y∀x P(x,y)`，邊個較強？

把 $∀b(Book(b) → ∃x Borrows(x,b))$ 讀成中文。