離散數學/邏輯/第 2 頁

條件命題

示例 8

討論安迪對伯納德說：“如果你想要更多咖啡，壺裡還有。”這句話是什麼意思。

安迪可能的意思是“壺裡還有咖啡，如果你想要，自己來。”幾乎可以肯定，他並不是真的想暗示壺裡是否有咖啡取決於伯納德是否想要。你可能已經意識到，我們在使用英語時有時非常不嚴謹！如果我們想用邏輯符號表示一個句子，我們需要做的一件事是弄清楚它的真正含義。

⇒ 蘊涵

示例 9

假設

p 是“天氣很暖和”；以及

q 是“我在午餐時間去游泳”。

那麼我們可以用符號表示條件命題“如果天氣很暖和，那麼我在午餐時間去游泳”。

p ⇒ q

所以 ⇒ 的意思是：“如果……那麼”，或“蘊涵（或意味著）”。

其他表達相同意思的方式是

• “天氣很暖和意味著我在午餐時間去游泳。”

• “無論何時天氣很暖和，我都在午餐時間去游泳。”

• “天氣很暖和，當且僅當我在午餐時間去游泳。”

請注意最後一句話。它不遵循（也不對應於）我們表示式 p ⇒ q 的邏輯。它改變了 ⇒ 的方向。這句話中使用“如果”這個詞改變了命題的因果關係，比如我在午餐時間去游泳意味著天氣很暖和。這將是 q ⇒ p，是我們原始表示式中條件的逆轉。“當且僅當”這個詞意味著如果在某一天我沒有在午餐時間去游泳，那麼那天天氣不可能很暖和，這也是一個逆向蘊涵。當然，我們的表示式並不意味著我去游泳（或者不去）決定了那天天的天氣，正好相反！

必要條件和充分條件

假設上週二我在午餐時間去游泳了。給定 p 和 q 如上，並且給定 p ⇒ q，你能確定上週二天氣很暖和嗎？

答案是否定的，你不能確定。我可能出於其他原因去游泳了。

因此，請注意，p ⇒ q 意味著 p 是 q 的充分條件。然而，它不是必要條件：q 仍然可以在沒有 p 的情況下為真。

其他表達方式

“即使天氣不暖和，我也可以在午餐時間去游泳。”

“無論天氣如何，我都可以去游泳。”

⇒ 的真值表

請注意，p ⇒ q 本身是一個命題；也就是說，它有一個真值——如果天氣很暖和，我是否在午餐時間去游泳。這可能或不可能是事實。

現在，命題 p ⇒ q 的值取決於 p 和 q 的值的組合。所以我們可以構造它的真值表

p	q	p ⇒ q
T	T	T
T	F	F
F	T	T
F	F	T

請特別注意這個表中的第三行（可能令人驚訝）！事實上，p ⇒ q 意味著如果 p 為假，我們不能得出關於 q 的任何結論。也就是說，如果p 為假，q 可以同樣可能是真或假，而不會與 p ⇒ q 的真值相矛盾。

換句話說，p ⇒ q 僅在 p 為 T 且 q 為 F 時為假；也就是說，一個真命題不能蘊涵一個假命題。

為了進一步澄清這一點，請考慮上面那句話：“如果天氣很暖和，那麼我在午餐時間去游泳。”這句話沒有說明天氣不暖和時會發生什麼：我可能會去游泳，也可能不會去。只有當天氣很暖和，但我沒有去游泳時，這句話才是假的。

雙條件命題

正如我們已經指出的，我們經常以一種非常不精確的方式使用英語。使用示例 9，假設我真正想說的是

如果天氣很暖和，我就去游泳，如果天氣不暖和，我就不去。

在這種情況下，p 和 q 都是真，或者都是假：你不能擁有其中一個而沒有另一個。我們可以改寫一下這句話，說

我只有在天氣很暖和的情況下才會去游泳。

短語“當且僅當”用符號 ⇔ 表示，所以我們可以說在這種情況下

p ⇔ q

在這種情況下，p 是 q 的必要且充分條件。

示例 10

p 是“x² = 9”。找到關於 x（而不是 x²）的適當語句 q，使得 p ⇔ q 為真。

解決方案

如果 x = 3，那麼當然 x² = 9。所以如果 q 是“x = 3”，那麼 q ⇒ p 為真，這將使 q 成為一個充分條件。

但它是必要且充分的嗎？不，因為 3 不是唯一一個平方為 9 的數字。x = -3 也將使 x² = 9。

為了確保必要且充分的 q，我們需要說

q 是“x = ±3”。

邏輯等價

我們已經說過 p ⇔ q 意味著 p 和 q 都是真，或者都是假，因此我們可以說在這種情況下，它們是邏輯等價的。

⇔ 的真值表

由於 p ⇔ q 表示 p 和 q 同時為真或同時為假，所以 ⇔ 的真值表如下

p	q	p ⇔ q
T	T	T
T	F	F
F	T	F
F	F	T

示例 11

透過繪製真值表，證明：

p ⇔ q ≡ (p ⇒ q) $\scriptstyle \wedge$ (q ⇒ p)

解決方案

(p ⇒ q) $\scriptstyle \wedge$ (q ⇒ p) 的真值表如下

p	q	(p ⇒ q)	$\scriptstyle \wedge$	(q ⇒ p)
T	T	T	T	T
T	F	F	F	T
F	T	T	F	F
F	F	T	T	T
		1	3 輸出	2

輸出結果為 T, F, F, T，與 p ⇔ q 的輸出結果相同，因此

p ⇔ q ≡ (p ⇒ q) $\scriptstyle \wedge$ (q ⇒ p)

⇐ 符號

我們有時使用 ⇐ 表示“被蘊涵”。因此，q ⇐ p 是 p ⇒ q 的另一種寫法，我們可以將 示例 11 寫成

p ⇔ q ≡ (p ⇒ q) $\scriptstyle \wedge$ (p ⇐ q)

邏輯練習 4

點選連結訪問 邏輯練習 4。

謂詞邏輯

到目前為止，我們只考慮了 命題邏輯，其中語句如：

p 是“所有紅頭髮的人脾氣暴躁”。

q 是“Joe 有紅頭髮”。

假設 p 和 q 如上所述，並且 r 是“Joe 脾氣暴躁”，我們可以寫成：

p $\scriptstyle \wedge$ q ⇒ r

如果我們想要對 Brenda 有紅頭髮，因此脾氣暴躁的論述，則需要進一步的命題，例如：

s 是“Brenda 有紅頭髮”。

t 是“Brenda 脾氣暴躁”。

因此

p $\scriptstyle \wedge$ s ⇒ t

… 等等。

每次我們想要對另一個有紅頭髮，因此脾氣暴躁的人（這可能是真的，也可能不是真的）進行論述，都需要進一步的命題。一個更好的表示這些想法的方法是使用 謂詞，例如：

redHair 表示“... 有紅頭髮”。

(注意，redHair 不是一個命題。為什麼呢？)

現在我們可以使用這個謂詞來形成關於所有有紅頭髮的人的論述，例如：

redHair(Joe) 是“Joe 有紅頭髮”。

redHair(Brenda) 是“Brenda 有紅頭髮”。

… 等等。

同樣地，我們可以定義謂詞 fieryTemper 來表示短語

"... 脾氣暴躁”。

因此，語句“如果 Joe 有紅頭髮，那麼他脾氣暴躁”可以表示為：

redHair(Joe) ⇒ fieryTemper(Joe)

語句“如果 Brenda 有紅頭髮，那麼她脾氣暴躁”可以表示為：

redHair(Brenda) ⇒ fieryTemper(Brenda)

符號

我們將使用單個單詞或多個連線在一起的單詞，並使用如上所示的大寫和小寫字母來表示謂詞。

謂詞應用的“物件” - 人，數字或任何事物 - 將在謂詞之後用括號括起來。

否定

假設 red Hair 的定義如上所述

¬with red Hair 是“並非有紅頭髮”。

邏輯練習 5

點選連結訪問 邏輯練習 5。

命題函式

如果我們想要談論一般的、未定義的謂詞，我們將使用大寫字母：P, Q, ..., 如果我們想要一個一般的、未定義的物件，我們將使用小寫字母：x, y, ...

因此，如果 P 是“... 具有屬性 P”，那麼 P(x) 是“x 具有屬性 P”。

• P(x) 可以被描述為一個 命題函式，其謂詞為 P。

函式具有這樣的屬性：當我們知道傳遞給它的任何引數的值時，它將返回一個唯一的值。P(x) 因此是一個函式，因為它返回一個取決於引數 x 值的真值。

例如，如果 American(x) 是命題函式“x 是美國人”，那麼 American(x) 將返回以下值

如果 x = 比爾·克林頓，則為 T；

如果 x = 女王陛下，則為 F

量詞

現在我們來擴充套件上面練習 5 中的思路。假設我們想要做出像這樣的陳述：

(a) 我的所有朋友都很有錢。

(b) 我的一些朋友很無聊。

這裡的問題是，我們在做關於我朋友的總體陳述，而沒有提到特定的個人。因此，我們需要定義命題函式如下：

friend(x) 表示 “x 是我的朋友”

wealthy(x) 表示 “x 很富有”

boring(x) 表示 “x 很無聊”

然後我們可以將上面的兩個陳述寫成：

(a) 對所有的 x，friend(x) ⇒ wealthy(x)

(b) 對某些 x，friend(x) $\scriptstyle \wedge$ boring(x)

符號：∀ 和 ∃

符號 ∀（稱為全稱量詞）代表短語“對所有……”

因此我們可以將上面的 (a) 寫成

(a) ∀ x，friend(x) ⇒ wealthy(x)

符號 ∃（稱為存在量詞）代表短語“對某些……”

因此我們可以將上面的 (b) 寫成

(b) ∃ x，friend(x) $\scriptstyle \wedge$ boring(x)

複數還是單數？

請注意，雖然上面的陳述 (a) 和 (b) 使用了複數詞語 - 所有的，是，一些，朋友 - 但是當我們用符號表示它們時，謂詞和變數是單數：x 是富有的，x 是無聊的等等。因此，重要的是要意識到，x 一次只能代表一個值。

因此，符號陳述

∀ x，friend(x) ⇒ wealthy(x)

可以用單數詞語逐字翻譯成

“對x 的每個值，如果x 是我的朋友，那麼x 很富有”。

而

∃ x，friend(x) $\scriptstyle \wedge$ boring(x)

更確切地翻譯成

“對x 的至少一個值，x 是我的朋友，並且x 很無聊”。

為了強調這一點，你可能會發現使用以下內容來翻譯符號很有幫助：

∀ 表示 “對每個（值的）……”

而

∃ 表示 “對至少一個（值的）……”

現在我們可以使用命題函式符號來表示我們之前關於“所有紅頭髮的人都脾氣暴躁”的陳述，如下所示：

redHair(x) 表示：“x 有紅頭髮”

fieryTemper(x) 表示：“x 有暴脾氣”

現在“所有紅頭髮的人都脾氣暴躁”用單數重寫為

對x 的每個值，如果x 有紅頭髮，那麼x 就有暴脾氣。

用符號表示，就是

∀ x，redHair(x) ⇒ fieryTemper(x)

示例 12

定義合適的命題函式，然後用符號表示

(a) 一些貓懂法語。

(b) 沒有足球運動員會唱歌。

(c) 至少有一位講師不無聊。

(d) 我每天陽光明媚的時候都會去游泳。

解答

(a) 用單數重寫：“至少有一隻貓懂法語”。因此，我們需要定義命題函式為

cat(x) 表示 “x 是一隻貓”

French(x) 表示 “x 懂法語”

因此，至少有一個x 既是貓又懂法語；用符號表示就是

∃x，cat(x) $\scriptstyle \wedge$ French(x)

(b) 用單數重寫：“至少有一位足球運動員會唱歌是不對的”。因此

footballer(x) 表示 “x 是一位足球運動員”

sing(x) 表示 “x 會唱歌”

用符號表示，就是

¬ (∃x，footballer(x) $\scriptstyle \wedge$ sing(x))

或者，我們可以將“沒有足球運動員會唱歌”重寫為“對每個x，如果x 是一位足球運動員，那麼x 不會唱歌”。用符號表示，就會得到同樣有效的解

∀ x，footballer(x) ⇒ ¬ sing(x)

(c) 這句話已經是單數了；因此

lecturer(x) 表示 “x 是一位講師”

boring(x) 表示 “x 很無聊”

所以

∃ x，lecturer(x) $\scriptstyle \wedge$ ¬ boring(x)

(d) 在這個例子中，重要的是要意識到變數代表什麼。在 (a) 到 (c) 中，變數x 表示動物或人。在句子“我每天陽光明媚的時候都會去游泳”中，變化的是時間，隨之變化的是天氣和我去游泳。因此，我們必須圍繞一個代表時間的變數x 來形成命題函式。因此

sunny(x) 表示 “x 是一個陽光明媚的日子”

swimming(x) 表示 “x 是我去游泳的一天”

然後，將“我每天陽光明媚的時候都會去游泳”用單數重寫，就會得到

“對每一天，如果那是一個陽光明媚的日子，那麼它就是一個我去游泳的日子”。

因此，用符號表示就是

∀x，sunny(x) ⇒ swimming(x)

邏輯練習 6

單擊連結以檢視邏輯練習 6。

論域

練習 5 和6 中的許多命題都提到了“我的朋友”。例如，考慮命題：“我所有朋友要麼有錢要麼聰明”。

使用謂詞，我們可以用符號表示為

∀ x，friend(x) ⇒ (wealthy(x) ∨ clever(x))

但是，如果我們同意變數x 只能代表我的一個朋友，那麼我們可以將其更簡單地表示為

∀ x，wealthy(x) ∨ clever(x)

對於給定的命題函式P(x)，論域 是可以從中選擇x 的值的集合。定義論域可以簡化命題函式的符號表示。如果沒有定義論域，那麼我們必須假設可以將任何物件或個人代入x。

示例 13

在每種情況下，定義一個合適的論域和謂詞來符號化

(a) 一些學生勤奮或酗酒。

(b) 每個人都很熱，有人暈倒了。

解答

(a) 定義以下內容

論域 = {學生}

hardWorking(x) 是“x 勤奮”

drink(x) 是“x 酗酒”

用單數形式寫作：“對於至少一個 x，x 勤奮或 x 酗酒”，我們得到

∃ x, hardWorking(x) ∨ drink(x)

(b) 在給定句子中，“每個人”顯然不代表全世界所有人，只是故事中提到的每個人。因此，我們可以定義如下

論域 = {故事中的人物}

hot(x) 是“x 很熱”

fainted(x) 是“x 暈倒了”

然後，用單數形式，我們有“對於每個 x，x 很熱，並且對於至少一個 x，x 暈倒了”。所以

∀ x, hot(x) $\scriptstyle \wedge$ ∃ x, fainted(x)

二元謂詞

我們之前看到的謂詞都是一元謂詞。為了將每個謂詞轉換為命題，我們必須提供一個單一的物件或個體——如果你願意，可以是單個引數的值。

我們可以建立需要兩個物件（或引數值）才能轉換為命題的謂詞。這樣的謂詞稱為二元謂詞。

示例 14

考慮以下謂詞

greaterThan 是“……大於……”

loves 是“……愛……”

belongsTo 是“……屬於……”

那麼以下就是二元命題函式

greaterThan(x, y) 是“x 大於 y”

loves(x, y) 是“x 愛 y”

belongsTo(x, y) 是“x 屬於 y”

因此，例如，以下是命題

greaterThan(5, 2) 是“5 大於 2”

loves(Bob, Lizzie) 是“Bob 愛 Lizzie”

belongsTo(This coat, Harry) 是“這件外套屬於 Harry”

二元謂詞和量詞

對於上面的謂詞，我們可以對一個變數進行量化

∀ x, belongsTo(x, me) 是“所有東西都屬於我”

∃ x, greaterThan(2, x) 是“2 大於某些東西”

∀ x, loves(Mary, x) 是“Mary 愛所有人”

……或兩個變數

∀ x, ∃y, loves(x, y) 是“每個人都愛某人”

∃ x, ∀ y, loves(x, y) 是“某人愛所有人”

∃ x, ∃ y, loves(x, y) 是“某人愛某人”

∀ x, ∀ y, loves(x, y) 是“每個人都愛所有人”

量化命題函式的否定

在練習 1的第 5 題中，我們必須說明哪些選項代表了命題的否定。讓我們再次看看，使用我們的量化命題函式符號。

示例 15

考慮命題的否定

“所有綿羊都是黑色的”。

否定是

“所有綿羊都是黑色的並不正確”。

這等同於

“至少有一隻綿羊不是黑色的”。

如果我們將論域定義為 {綿羊}，並以明顯的方式定義 isBlack，那麼我們可以用以下符號來表示所有這些

¬ (∀ x, isBlack(x)) ≡ ∃ x, ¬isBlack(x)

現在考慮命題

“有些綿羊是黑色的”。

這的否定是

“有些綿羊是黑色的並不正確”

這等同於

“所有綿羊都不是黑色的”

這可以用以下符號表示

¬ (∃ x, isBlack(x)) ≡ ∀ x, ¬isBlack(x)

我們可以將我們在此處發現的內容推廣到任何命題函式 P(x)，如下所示

¬(∀ x, P(x)) ≡ ∃ x, ¬ P(x)

¬(∃ x, P(x)) ≡ ∀ x, ¬P(x)

邏輯練習 7

點選連結檢視邏輯練習 7。