離散數學/邏輯

引言

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

命題

命題是一個具有真值的陳述：它要麼是真（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) 不完全相同，在 (c) 中，我們可能不知道真值，因為我們沒有足夠的瞭解。見下一段。

命題函式

函式，簡單來說，是一種操作，它以一個或多個引數值作為輸入，併產生一個明確定義的輸出。

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

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

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

稍後將詳細介紹 命題函式。

符號

我們通常用小寫字母 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 $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬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)

重言式

始終具有 *真* 值的表示式稱為 *重言式*。

此外，任何冗餘或冪等的語句也被稱為重言式，原因與前面提到的相同。 如果 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 作為 AND 操作的“足跡”。所以我們可以將 ¬(¬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.