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)→∃xBorrows(x,b))∀b(Book(b) → ∃x Borrows(x,b))∀b(Book(b)→∃xBorrows(x,b)) 讀成中文。

答案

嵌入式檢查

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

先讀呢一頁

先備知識

本單元重點詞彙

本系列更多筆記

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

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

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

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