離散數學/邏輯

簡介

在傳統代數中，字母和符號用來表示數字及其相關的運算：+，-，×，÷等。這樣做可以幫助簡化和解決複雜問題。在邏輯中，我們試圖用代數符號來表達語句以及它們之間的聯絡——再次以簡化複雜想法為目標。不幸的是，就像普通代數一樣，起初似乎相反。這可能是因為簡單的例子總是顯得更容易透過常識方法來解決！

命題

命題是一個具有真值的語句：它要麼是真(T)，要麼是假(F)。

示例 1

以下哪些是命題？

(a) 17 + 25 = 42

(b) 7 月 4 日發生在北半球的冬季。

(c) 美國的總人口少於 2.5 億。

(d) 月亮是圓的嗎？

(e) 7 大於 12。

(f) x 大於 y。

答案

(a) 是一個命題；當然，它的‘真值’是真。

(b) 是一個命題。當然，它是假的，但它仍然是一個命題。

(c) 是一個命題，但我們可能不知道它是真還是假。然而，事實是，語句本身是一個命題，因為它絕對是真或假。

(d) 不是一個命題。這是一個問題。

(e) 是一個命題。當然，它是假的，因為 7<12。

(f) 有點值得商榷！它當然是一個潛在的命題，但直到我們知道x和y的值，我們才能確定它是真還是假。請注意，這與 (c) 不一樣，我們可能不知道真值，因為我們沒有足夠的瞭解。參見下一段。

命題函式

函式，通俗地講，是一個操作，它接收一個或多個引數值作為輸入，併產生一個明確定義的輸出。

例如，您可能熟悉三角學中的正弦和餘弦函式。這些是函式的例子，它們接收一個數字（角度的大小）作為輸入，併產生一個十進位制數字（實際上介於 +1 和 -1 之間）作為輸出。

如果我們願意，可以定義我們自己的函式，例如RectangleArea，它可以接收兩個數字（矩形的長和寬）作為輸入，併產生一個數字作為輸出（透過將兩個輸入數字相乘形成的）。

在上面的 (f) 中，我們有一個命題函式的例子。這是一個函式，它產生的輸出不是像正弦、餘弦或RectangleArea那樣的數字，而是一個真值。然後，它是一個語句，當它被提供一個或多個引數值時，它就變成了一個命題。在 (f) 中，引數是x和y。因此，如果x = 2 且 y = 7，則其輸出為False；如果x = 4 且 y = -10，則其輸出為True。

關於命題函式的更多內容將在後面介紹。

符號

我們通常用小寫字母p，q，...來表示命題。

複合命題

命題可以透過一個或多個邏輯運算子進行修改，形成所謂的複合命題。

有三個邏輯運算子

• 合取：$\scriptstyle \wedge$ 表示 AND

• 析取：∨ 表示 OR

• 否定：¬ 表示 NOT

示例 2

p 表示命題“亨利八世有六個妻子”。

q 表示命題“英國內戰發生在 19 世紀”。

(a) 用 OR 連線這兩個命題。得到的複合命題是真還是假？

(b) 現在用 AND 連線它們。這個複合命題是真還是假？

(c) p 的‘反面’是真還是假？

答案

(a) p ∨ q 是“亨利八世有六個妻子，或者英國內戰發生在 19 世紀”。

這是真的。複合命題的第一部分是真的，這足以使整個語句為真——即使聽起來有點奇怪！

如果您認為這個例子聽起來很牽強，想象一下您正在參加一個歷史測驗；還有兩個問題，您需要至少答對一個才能贏得測驗。您對亨利八世和內戰做出了上面兩個陳述。您贏得了測驗嗎？是的，因為“亨利八世有六個妻子，或者英國內戰發生在 19 世紀”是真的。

請注意，這是一個包含的 OR：換句話說，我們並不排除兩部分都為真。因此，p ∨ q 表示“要麼p為真，要麼q為真，要麼兩者都為真”。

(b) p $\scriptstyle \wedge$ q 是“亨利八世有六個妻子，而且英國內戰發生在 19 世紀”。

這是假的。

為了為真，兩部分都必須為真。這相當於您需要兩個問題都答對才能贏得測驗。您失敗了，因為您答錯了第二個問題。

(c) p 的相反，我們寫作 ¬p，意思是“亨利八世沒有六個妻子”。這顯然是假的。一般來說，如果 p 為真，則 ¬p 為假，反之亦然。

示例 3

p 是“印表機處於離線狀態”

q 是“印表機缺紙”

“r” 是“文件已完成列印”

儘可能用自然的方式寫成英文句子

(a) p ∨ q

(b) r $\scriptstyle \wedge$ q

(c) q $\scriptstyle \wedge$ ¬r

(d) ¬(p ∨ q)

答案

(a) 印表機處於離線狀態或缺紙。

注意，我們在寫或說英語時經常省略一些詞。這聽起來比“印表機處於離線狀態或印表機缺紙”更自然。

(b) 文件已完成列印，並且印表機缺紙。

現在句子的每個部分的主語都不同，因此這次沒有省略任何詞。

(c) 印表機缺紙，並且文件尚未完成列印。

但和並且

(c) 中的陳述可能是某人報告問題，他們可能也同樣會說

(c) 印表機缺紙，但文件尚未完成列印。

因此請注意，在邏輯中，但和並且的意思相同。只是我們使用但來引入對比或意外的含義。例如，我們可能會說

• 陽光明媚，但外面很冷。

在邏輯上，我們可以使用並且來連線句子的兩個部分，但(!) 使用但更自然。

在 (d) 中，¬(p ∨ q) 是什麼意思？那麼，p ∨ q 意味著p 為真或q 為真（或兩者都為真）。當我們在前面加上 ¬ 時，我們就對其進行了否定。所以它（字面上的意思是）

• 印表機處於離線狀態或缺紙並不正確。

換句話說

(d) 印表機既不處於離線狀態也不缺紙。

注意，用短語“它並不正確……”來翻譯 ¬ 通常很方便。

邏輯練習 1

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

真值表

考慮複合命題 p $\scriptstyle \wedge$ q 在 p 和 q 的各種組合值下可能的取值。使 p $\scriptstyle \wedge$ q 為真的唯一值組合是 p 和 q 都為真；任何其他組合都將包含一個假，這將使整個複合命題為假。另一方面，複合命題 p ∨ q 將在p 或 q（或兩者）為真的情況下為真；只有在p 和 q 都為假時，p ∨ q 才為假。

我們在所謂的真值表中總結了這些結論，AND 的真值表為

p	q	p $\scriptstyle \wedge$ q
T	T	T
T	F	F
F	T	F
F	F	F

OR 的真值表為

p	q	p ∨ q
T	T	T
T	F	T
F	T	T
F	F	F

真值表中行的順序

注意上面每個真值表的前兩列中 T 和 F 的模式。在第一列（p 的真值）中，有 2 個 T 接著 2 個 F；在第二列（q 的值）中，T 和 F 在每行上變化。我們將在本文的整個內容中採用這種行的順序。為真值表中的行順序採用約定有兩個優點

• 它確保了 T 和 F 的所有組合都被包含在內。（對於只有兩個命題和真值表中只有四行的情況來說，這可能很容易；對於比如有 4 個命題的情況來說，真值表中將有 16 行，那就沒那麼容易了。）

• 它產生了 T 和 F 的標準、可識別的輸出模式。因此，例如，T、F、F、F 是 AND（$\scriptstyle \wedge$）的輸出模式（或“足跡”，如果你喜歡的話），而 T、T、T、F 是 OR（∨）的足跡。

NOT 的真值表

上面的兩個真值表都有兩列“輸入”（一列用於 p 的值，一列用於 q 的值），以及一列“輸出”。它們都需要四行，因為當兩個命題組合在一起時，T 和 F 的可能組合有四種。NOT（¬）的真值表將更簡單，因為 ¬ 是一個一元運算——一個需要單個命題作為輸入的運算。所以它只有兩列——輸入和輸出——以及兩行。

p	¬p
T	F
F	T

繪製真值表

下面描述了為任何複合表示式繪製真值表的方法，然後是四個例子。採用嚴格的方法並保持工作整潔非常重要：有很多機會讓錯誤潛入，但只要小心，無論表示式多麼複雜，這是一個非常直接的過程。因此

• 步驟 1：行

  確定表格需要多少行。一個輸入只需要兩行；兩個輸入需要 4 行；三個需要 8 行，等等。如果表示式中有 n 個命題，則需要 2ⁿ 行。

• 步驟 2：空表

  繪製一個空表，具有適當數量的輸入列和行，以及一個足夠寬的單個輸出列，以便舒適地容納輸出表達式。如果需要 8 行或更多行，你可能會發現每四行在表格上劃一條水平線有助於保持行整齊。

• 步驟 3：輸入值

  填寫所有輸入值，使用上面關於真值表中行順序的約定；也就是說，從最右側的輸入列開始，填寫值 T 和 F，在每行上交替。然後移到左側的下一列，填寫 T 和 F，在每隔一行上變化。對所有剩餘的列重複此操作。然後，最左側的列將在表格中所有行的前半部分包含 T，而在後半部分包含 F。

• 步驟 4：規劃你的策略

  仔細研究用於計算表示式的運算的順序，注意可能出現的任何括號。如同傳統的代數，你並不一定從左到右進行運算。例如，表示式p ∨ ¬q 需要先計算 ¬q，然後使用 ∨ 將結果與 p 組合。當你計算出執行每個運算的順序後，在輸出表示式下新增額外的列 - 每個計算階段對應一列。然後在每個列的下方（底部）用數字標註計算順序。表示最終輸出的列將是計算過程的最後階段，因此其底部將有最高的數字。

• 步驟 5：向下逐列運算

  最後階段是按照你在步驟 4 中寫下的順序向下逐列進行運算。要做到這一點，你需要使用上面 AND、OR 和 NOT 的真值表，利用來自輸入列以及已經完成的任何其他列的值。記住：向下逐列運算，而不是橫向逐行運算。這樣，你只需要每次考慮一個運算。

你可能認為這聽起來非常複雜，但一些示例應該可以使這個方法清晰明瞭。

示例解析

示例 4

為以下表達式生成真值表：

(a) ¬(¬p)

(b) p $\scriptstyle \wedge$ (¬q)

(c) (p $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬q)

(d) q $\scriptstyle \wedge$ (p ∨ r)

解答

(a) ¬(¬p) 很明顯等同於 p 本身，但為了說明方法，我們將在這種簡單的例子中仍然使用上述方法，然後再處理更復雜的例子。所以

• 步驟 1：行

這裡只有一個輸入變數，所以我們需要兩行。

• 步驟 2：空表

因此，表格是

p	¬(¬p)
.
.

• 步驟 3：輸入值

接下來，我們填寫輸入值：在這種情況下，只有一個 T 和一個 F

p	¬(¬p)
T
F

• 步驟 4：規劃你的策略

如同“普通”代數一樣，我們先計算括號內的表示式，所以我們首先 (1) 完成 (¬p) 的值，然後 (2) 完成左邊的 ¬ 符號，這將得到整個表示式的最終輸出值。我們在表格中新增一列來區分這兩個步驟，並在這兩列的底部寫上 (1) 和 (2)。因此

p	¬	(¬p)
T
F
	(2) 輸出	(1)

• 步驟 5：向下逐列運算

最後，我們將值插入到列 (1) 中 - F 後面是 T - 然後使用這些值將值插入到列 (2) 中。所以完成的真值表是

p	¬	(¬p)
T	T	F
F	F	T
	(2) 輸出	(1)

正如我們在本例開頭所說，¬(¬p) 明顯等同於 p，因此輸出值的模式，T 後面是 F，與輸入值的模式完全相同。雖然這似乎微不足道，但相同的技巧在更復雜的例子中也有效，其結果並不明顯！

(b) p $\scriptstyle \wedge$ (¬q)

• 步驟 1

有兩個輸入變數，p 和 q，因此我們需要表格中有四行。

• 步驟 2 和 3

在q 列中，每行交替寫 T 和 F；在p 列中，每兩行交替寫一次。在此階段，表格如下所示

p	q	p $\scriptstyle \wedge$ (¬q)
T	T
T	F
F	T
F	F

• 步驟 4 和 5

如同示例 (a)，我們開始 (1) 計算括號內的表示式，(¬q)，然後 (2) 使用 $\scriptstyle \wedge$ 運算子將這些結果與 p 組合。所以我們將表格的輸出部分分成兩列；然後向下運算列 (1)，最後運算列 (2)。完成的表格是

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

(c) (p $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬q)

• 步驟 1 到 3

如同示例 (b)。

• 步驟 4 和 5

表示式 (p $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬q) 的計算將有 5 個階段。按照順序，它們是

(1) 第一個括號： (p $\scriptstyle \wedge$ q)

(2) 第二個括號中的 ¬p

(3) 第二個括號中的 ¬q

(4) 第二個括號中的 ∨

(5) 兩個括號之間的 ∨。因此，這個最後階段代表了整個表示式的輸出。

提醒：不要橫向逐行運算；按照 (1) 到 (5) 的順序向下逐列運算。這樣，你只需要一次處理一個運算。

完成的表格是

p	q	(p $\scriptstyle \wedge$ q)	∨	(¬p	∨	¬q)
T	T	T	T	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	T	F
F	F	F	T	T	T	T
		(1)	(5) 輸出	(2)	(4)	(3)

注意，輸出僅包含 T。這意味著無論 p 和 q 的值如何，(p $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬q) 始終為真。因此，它是一個重言式（參見下面）。

(d) q $\scriptstyle \wedge$ (p ∨ r)

這個簡單的表示式涉及 3 個輸入變數，因此其真值表需要 2³ = 8 行。當用手繪製此真值表時，在第 4 行下方畫一條線，以幫助保持工作整潔。在本表格中，它顯示為雙線。完成的表格如下所示。

p	q	r	q $\scriptstyle \wedge$	(p ∨ r)
T	T	T	T	T
T	T	F	T	T
T	F	T	F	T
T	F	F	F	T
F	T	T	T	T
F	T	F	F	F
F	F	T	F	T
F	F	F	F	F
			(2) 輸出	(1)

永真式

一個表示式，始終具有值true，稱為永真式。

此外，任何冗餘或冪等的語句也被稱為永真式，原因與上述相同。如果P為真，那麼我們可以確定P ∨ P為真，而P ∧ P也為真。

邏輯練習 2

點選連結檢視邏輯練習 2.

優先順序順序

在“普通”代數中，執行運算的優先順序順序為

1 括號

2 指數（冪）

3 × 和 ÷

4 + 和 -

在邏輯代數中，通常會插入括號以明確執行運算的順序。為了避免可能的歧義，商定的優先順序規則是

1 括號

2 非 (¬)

3 與 ($\scriptstyle \wedge$)

4 或 (∨)

因此，例如，p ∨ q $\scriptstyle \wedge$ r 意味著

先計算 q $\scriptstyle \wedge$ r 的結果。

然後將結果與 p ∨ 進行組合。

由於很容易誤解這一點，建議包含括號，即使它們不是嚴格必要的。因此，p ∨ q $\scriptstyle \wedge$ r 通常寫成 p ∨ (q $\scriptstyle \wedge$ r)。

邏輯等價命題

回顧一下你在練習 2中對問題 2 和 3 的答案。在每個問題中，你應該發現每對命題的真值表最後一列都是相同的。

只要兩個命題p和q的真值表最後一列相同，我們就說p和q是邏輯等價的，並寫成

p ≡ q

示例 5

構造以下命題的真值表：

(i) p ∨ (q $\scriptstyle \wedge$ r)，以及

(ii) (p ∨ q) $\scriptstyle \wedge$ (p ∨ r)，

並因此證明這些命題是邏輯等價的。

解答

(i)

p	q	r	p ∨	(q $\scriptstyle \wedge$ r)
T	T	T	T	T
T	T	F	T	F
T	F	T	T	F
T	F	F	T	F
F	T	T	T	T
F	T	F	F	F
F	F	T	F	F
F	F	F	F	F
			(2) 輸出	(1)

(ii)

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

每個情況下的輸出都是 T, T, T, T, T, F, F, F。因此，這些命題是邏輯等價的。

示例 6

構造 ¬(¬p ∨ ¬q) 的真值表，並因此找到一個更簡單的邏輯等價命題。

解答

p	q	¬	(¬p	∨	¬q)
T	T	T	F	F	F
T	F	F	F	T	T
F	T	F	T	T	F
F	F	F	T	T	T
		(4) 輸出	(1)	(3)	(2)

我們認識到輸出：T, F, F, F 是與運算的“指紋”。因此，我們可以將 ¬(¬p ∨ ¬q) 簡化為

p $\scriptstyle \wedge$ q

邏輯定律

與集合一樣，邏輯命題構成所謂的布林代數：適用於集合的定律也有相應的適用於命題的定律。即

交換律

p $\scriptstyle \wedge$ q ≡ q $\scriptstyle \wedge$ p

p ∨ q ≡ q ∨ p

結合律

(p $\scriptstyle \wedge$ q) $\scriptstyle \wedge$ r ≡ p $\scriptstyle \wedge$ (q $\scriptstyle \wedge$ r)

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

分配律

p $\scriptstyle \wedge$ (q ∨ r) ≡ (p $\scriptstyle \wedge$ q) ∨ (p $\scriptstyle \wedge$ r)

p ∨ (q $\scriptstyle \wedge$ r) ≡ (p ∨ q) $\scriptstyle \wedge$ ( p ∨ r)

冪等律

p $\scriptstyle \wedge$ p ≡ p

p ∨ p ≡ p

恆等律

p $\scriptstyle \wedge$ T ≡ p

p ∨ F ≡ p

支配律

p ∨ T ≡ T

p $\scriptstyle \wedge$ F ≡ F

對合律

¬(¬p) ≡ p

德摩根律

¬(p ∨ q) ≡ (¬p) $\scriptstyle \wedge$ (¬q)

(有時寫成 p NOR q)

¬(p $\scriptstyle \wedge$ q) ≡ (¬p) ∨ (¬q)

(有時寫成 p NAND q)

補律

p $\scriptstyle \wedge$ ¬p ≡ F

p ∨ ¬p ≡ T

¬T ≡ F

¬F ≡ T

習題解答

例 7

命題函式 p, q 和 r 定義如下

p 是 "n = 7"

q 是 "a > 5"

r 是 "x = 0"

用 p, q 和 r 表示以下表達式，並證明每對錶達式在邏輯上是等價的。仔細說明在每個步驟中使用了哪些上述定律。

(a)

((n = 7) ∨ (a > 5)) $\scriptstyle \wedge$ (x = 0)

((n = 7) $\scriptstyle \wedge$ (x = 0)) ∨ ((a > 5) $\scriptstyle \wedge$ (x = 0))

(b)

¬((n = 7) $\scriptstyle \wedge$ (a ≤ 5))

(n ≠ 7) ∨ (a > 5)

(c)

(n = 7) ∨ (¬((a ≤ 5) $\scriptstyle \wedge$ (x = 0)))

((n = 7) ∨ (a > 5)) ∨ (x ≠ 0)

解答

(a)

(p ∨ q) $\scriptstyle \wedge$ r

(p $\scriptstyle \wedge$ r) ∨ (q $\scriptstyle \wedge$ r)

(p ∨ q) $\scriptstyle \wedge$ r	= r $\scriptstyle \wedge$ (p ∨ q)	交換律
	= (r $\scriptstyle \wedge$ p) ∨ r $\scriptstyle \wedge$ q)	分配律
	= (p $\scriptstyle \wedge$ r) ∨ (q $\scriptstyle \wedge$ r)	交換律 (兩次)

(b)

首先，我們注意到

¬q 是 "a ≤ 5"; 以及

¬p 是 "n ≠ 7"。

因此，表示式為

¬(p $\scriptstyle \wedge$ ¬q)

¬p ∨ q

¬(p $\scriptstyle \wedge$ ¬q)	= ¬p ∨ ¬(¬q)	德摩根定律
	= ¬p ∨ q	對合律

(c)

首先，我們注意到

¬r 是 "x ≠ 0"。

因此，表示式為

p ∨ (¬(¬q $\scriptstyle \wedge$ r))

(p ∨ q) ∨ ¬r

p ∨ (¬(¬q $\scriptstyle \wedge$ r))	= p ∨ (¬(¬q) ∨ ¬r)	德摩根定律
	= p ∨ (q ∨ ¬r)	對合律
	= (p ∨ q) ∨ ¬r	結合律

邏輯練習 3

點選連結檢視 邏輯練習 3.