高中數學擴充套件

補充章節 — 素數和模算術 — 邏輯

矩陣 — 更深入的模算術 — 數學規劃 — 馬爾可夫鏈

介紹

邏輯是研究我們推理方式的學科。在本章中，我們重點關注邏輯推理的方法，即數字邏輯、謂詞演算、應用於證明以及（瘋狂）有趣的邏輯謎題。

布林代數

在理想的黑與白世界裡，存在絕對的真理。也就是說，所有事物要麼是真，要麼是假。帶著這種哲學背景，我們考慮以下例子

"一加一等於二。"真或假？

這是（毫無疑問）真的！

"1 + 1 = 2 並且 2 + 2 = 4。"真或假？

這也是真的。

但關於

"1 + 1 = 3 或者悉尼在澳大利亞"真或假？

它是真的！雖然 1 + 1 = 3 不正確，但語句中的“或者”使得整個語句在至少一個語句為真時為真。

現在讓我們考慮一個更令人費解的例子

"2 + 2 = 4 或者 1 + 1 = 3 並且 1 - 3 = -1"真或假？

語句的真或假取決於你評估語句的順序。如果你先評估 "2 + 2 = 4 或者 1 + 1 = 3"，那麼該語句為假，否則為真。就像在普通代數中一樣，我們有必要定義一些規則來控制評估順序，這樣我們就不用處理歧義。

在我們決定評估語句的順序之前，我們做大多數數學家喜歡做的事情——用符號替換句子。
讓x表示語句 2 + 2 = 4 的真或假。
讓y表示語句 1 + 1 = 3 的真或假。
讓z表示語句 1 - 3 = -1 的真或假。

那麼上面的例子可以用更緊湊的方式重寫

x 或者 y 並且 z

更進一步，數學家還用 + 替換“或者”，用 × 替換“並且”，該語句變為

x+y\times z

現在優先順序順序很清楚。我們首先評估 (y 並且 z)，然後將其與 x 運算“或者”。語句 "x + yz" 為真，或者用符號表示

x+yz=1

其中數字 1 代表“真”。

我們選擇將“並且”運算用乘號表示是有充分理由的。正如我們將在後面看到的，我們可以將“並且”運算與乘法進行一些類比。

我們即將研究的布林代數以英國數學家喬治·布林命名。布林代數是關於兩件事——“真”或“假”，它們通常分別用數字 1 和 0 表示。或者，也可以用 T 和 F 表示。

布林代數有與我們熟悉和喜愛的普通代數類似的運算（“並且”和“或者”）。

基本真值表

我們都必須記住 9 乘 9 的乘法表，現在我們已經熟記於心了。在布林代數中，真值表的概念有點類似。

讓我們考慮與乘法類似的“並且”運算。我們要考慮

x 並且 y

其中x和y分別表示一個真或假語句（例如，今天在下雨）。當且僅當x和y都為真時，它才為真，用表格形式表示

“並且”函式
x	y	x 並且 y
F	F	F
F	T	F
T	F	F
T	T	T

我們將從現在開始使用 1 代替 T，使用 0 代替 F。

“並且”函式
x	y	x 並且 y
0	0	0
0	1	0
1	0	0
1	1	1

現在你應該能夠理解為什麼我們說“並且”類似於乘法，我們將用 × 替換“並且”，所以x 並且 y變為x×y（或者只是xy）。從“並且”真值表中，我們有

0 × 0 = 0

0 × 1 = 0

1 × 0 = 0

1 × 1 = 1

到“或者”運算。x 或者 y當且僅當x和y都為假時才為假。用表格形式表示

“或者”函式
x	y	x 或者 y
0	0	0
0	1	1
1	0	1
1	1	1

我們說“或者”幾乎類似於加法。我們將用 + 替換“或者”來說明這一點

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1（就像 1 或者 1 等於 1）

非運算不是像與運算和或運算那樣的二元運算，而是**一元運算**，這意味著它只處理一個引數。**非 x** 如果 x 為假則為真，如果 x 為真則為假。以表格形式

非函式
x	非 x
0	1
1	0

在符號形式中，**非** x 表示為 x' 或 ~x（或在 x 上方加一條線）。

替代符號

x\times y=x\wedge y

和

x+y=x\vee y

複合真值表

上面展示的三個真值表是最基本的真值表，它們是更復雜真值表的構建模組。假設我們想要為 xy + z（即 x 與 y 或 z）構建一個真值表。請注意，此表涉及三個變數（x、y 和 z），因此我們預計它將比之前的表更大。

要構建真值表，首先我們將寫下三個變數的所有可能組合

x	y	z
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

組合的寫法有一個規律。我們總是從 000 開始，以 111 結束。至於中間部分，由讀者自行弄清楚。

然後，我們透過手工計算每個組合使用表示式 xy + z 將產生什麼值來完成表格。例如

000

x = 0、y = 0 和 z = 0

xy + z = 0

001

x = 0、y = 0 和 z = 1

xy + z = 1

我們以這種方式繼續，直到填滿整個表格

x	y	z	xy 或 z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

我們遵循的生成真值表的步驟現在很清楚了。以下是真值表的幾個更多示例。

示例 1 -- x + y + z

x	y	z	x + y + z
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

示例 2 -- (x + yz)'

當一個表示式難以計算時，我們可以先計算中間結果，然後計算最終結果。

x	y	z	x + yz	(x + yz)'
0	0	0	0	1
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	1	0
1	1	0	1	0
1	1	1	1	0

示例 3 -- (x + yz')w

x	y	z	w	(x + yz')w
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	1
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	0
1	1	1	1	1

練習

為以下運算生成真值表

與非：x 與非 y = 非（x 與 y）
或非：x 或非 y = 非（x 或 y）
異或：x 異或 y 當且僅當 x 或 y 之一為真時為真。

為以下表達式生成真值表

xyz
x'y'z'
xyz + xy'z
xz
(x + y)'
x'y'
(xy)'
x' + y'

布林代數定律

在普通代數中，兩個表示式可以等效，例如 xz + yz = (x + y)z。布林代數也是如此。讓我們為以下表達式構建真值表

xz + yz

(x + y)z

xz + yz

x	y	z	xz + yz
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

(x + y)z

x	y	z	(x + y)z
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

透過比較這兩個表，您會注意到這兩個表的輸出（即最後一列）相同！

定義

如果兩個布林表示式的真值表輸出相同，則稱這兩個布林表示式**等效**。

我們列出了一些彼此等效的表示式

x + 0 = x

x × 1 = x

xz + yz = (x + y)z

x + x' = 1

x × x' = 0

x × x = x

x + yz = (x + y)(x + z)

花幾分鐘思考一下為什麼每個定律都可能是真的。

最後一個定律並不明顯，但我們可以使用其他定律證明它是真的

{\begin{matrix}(x+y)(x+z)&=&x(x+z)+y(x+z)\\&=&xx+xz+xy+yz\\&=&x+xz+xy+yz\\&=&x(1+z+y)+yz\\&=&x+yz\end{matrix}}

有人說過：“數學中唯一需要記住的是，什麼都不需要記住。記住這一點！”你不應該試圖記住這些定律，因為一旦你熟悉了與運算、或運算和非運算，其中一些定律就變得非常明顯。你只需要記住那些最基本的東西，一旦你發展了很高的熟悉度，你就會同意實際上沒有東西需要記住。

簡化

一旦我們有了這些定律，我們就會想要簡化布林表示式，就像我們在普通代數中做的那樣。我們都可以輕鬆地簡化以下示例

{\begin{matrix}xyzw'+xyzw&=&xyz(w+w')\\&=&xyz\end{matrix}}

同樣可以對以下表達式進行簡化

{\begin{matrix}(x+y)(x'+y')&=&x(x'+y')+y(x'+y')\\&=&xx'+xy'+yx'+yy'\\&=&0+xy'+yx'+0\\&=&xy'+yx'\end{matrix}}

從這兩個示例我們可以看出，看起來很複雜的表示式可以被大大簡化。特別令人感興趣的是形式為積之和的表示式，例如

xyz + xyz' + xy'z + x'yz + x'y'z' + x'y'z

我們可以對錶達式進行因式分解和簡化，如下所示

xyz+xyz'+xy'z+x'yz+x'y'z'+x'y'z

=\ xy(z+z')+xy'z+x'yz+x'y'(z'+z)

=\ xy+xy'z+x'yz+x'y'

=\ x(y+y'z)+x'(yz+y')

儘管我們可以繼續簡化，但接下來的步驟會比較困難。我們使用以下恆等式：

x + yz = (x + y)(x + z)

如果下一步不清楚，可以嘗試構建真值表來幫助理解。

{\begin{matrix}&=&\ x(y+z)+x'(z+y')\\&=&\ xy+xz+x'z+x'y'\\&=&\ xy+(x+x')z+x'y'\\&=&\ xy+z+x'y'\\\end{matrix}}

這就是我們使用代數方法（或任何其他方法）所能達到的極限。代數方法的簡化依賴於消元的原則。在普通代數中，考慮以下表達式：

x + y - x

我們透過以下方式重新排列表達式來進行簡化：

(x - x) + y = y

儘管我們只是在腦海中完成這個過程，但思路很清晰：我們將可以互相抵消的項合併在一起，從而簡化了表示式。

德摩根定律

到目前為止，我們只處理了積之和形式的表示式，例如 xyz + x'z + y'z'。德摩根定律幫助我們處理另一種型別的布林表示式。我們回顧一下 AND 和 OR 的真值表：

{

}

你可能會懷疑這兩個運算之間存在某種聯絡，因為這兩個表非常相似。實際上，如果你對 AND 運算進行取反，即對 x AND y 進行 NOT 運算。這兩個運算的輸出幾乎相同。

{

}

AND、OR 和 NOT 之間的聯絡透過反轉 x + y 的輸出，將其替換為 x' + y' 來揭示。

{

}

現在這兩個輸出匹配，所以我們可以將它們等同起來。

(xy)' = x' + y'

這是德摩根定律之一。另一個定律可以使用類似的過程推匯出，即：

(x + y)' = x'y'

我們可以應用這兩個定律來簡化方程式。

示例 1
將x 表示為積之和形式：

{\begin{matrix}x&=&(ab'+c)'\\&=&(ab')'c'\\&=&(a'+b)c'\\&=&a'c'+bc'\end{matrix}}

示例 2
將x 表示為積之和形式：

{\begin{matrix}x&=&(a+b+c)'\\&=&(a+b)'c'\\&=&a'b'c'\\\end{matrix}}

這表明德摩根定律可以擴充套件到 3 個或更多變數。

示例 3
將x 表示為積之和形式：

{\begin{matrix}x&=&[(a'+c)\cdot (b+d')]'\\&=&(a'+c)'+(b+d')'\\&=&ac'+b'd\\\end{matrix}}

示例 4
將x 表示為積之和形式：

{\begin{matrix}x&=&[(a+bc)\cdot (d+ef)]'\\&=&(a+bc)'+(d+ef)'\\&=&a'(bc)'+d'(ef)'\\&=&a'(b'+c')+d'(e'+f')\\&=&a'b'+a'c'+d'e'+d'f'\\\end{matrix}}

我們還發現，我們可以透過將表示式中的每個變數替換為其相反數來反轉表示式的真值表，即用 x' 替換 x，用 y 替換 y' 等。這個結果並不令人驚訝，你可以自己嘗試幾個例子。

德摩根定律

$(x+y)'=x'y'$

$(xy)'=x'+y'$

練習

將表示式簡化為最簡的積之和形式
1. z = ab'c' + ab'c + abc
2. z = ab(c + d)
3. z = (a + b)(c + d + f)
4. z = a'c(a'bd)' + a'bc'd' + ab'c
5. z = (a' + b)(a + b + d)d'
證明 x + yz 等價於 (x + y)(x + z)

命題

從本章開始，我們就一直在處理命題，儘管我們沒有被告知它們是命題。命題只是一個真或假陳述（或句子）。因此，我們可以使用布林代數來處理命題。

命題有兩種特殊型別——重言式和矛盾式。重言式是一個總是為真的命題，例如“1 + 1 = 2”。矛盾式是重言式的反面，它是一個總是為假的命題，例如 1 + 1 = 3。像往常一樣，我們使用 1 表示真，使用 0 表示假。請注意，觀點不是命題，例如“42 是一個很棒的數字”只是一個觀點，它的真假不是普遍的，這意味著有些人認為它是真的，有些人則不認為它是真的。

示例

“今天下雨”是一個命題。
“悉尼在澳大利亞”是一個命題。
“1 + 2 + 3 + 4 + 5 = 16”是一個命題。
“地球是一個完美的球體”是一個命題。
“你好嗎？”不是命題 - 這是一個問題。
“去打掃你的房間！”不是命題 - 這是一個命令。
“火星人存在”是一個命題。

由於每個命題只能取兩個值（真或假），我們可以用一個變數來表示每個命題，並透過使用布林代數來確定複合命題是否為真，就像我們一直在做的那樣。例如，“南極洲總是很熱或 1 + 1 = 2”將被評估為真。

蘊涵

型別為如果某事某事那麼某事某事的命題稱為蘊涵。蘊涵的邏輯廣泛應用於數學、計算機科學和日常生活中！讓我們從一個簡單的例子開始

“如果 1 + 1 = 2 那麼 2 - 1 = 1”

是一個蘊涵的例子，它只是說 2 - 1 = 1 是 1 + 1 = 2 的結果。它就像一個因果關係。考慮這個例子

約翰說：“如果我成為百萬富翁，那麼我會捐贈 500,000 美元給紅十字會。”

有四種情況

約翰成為百萬富翁並向紅十字會捐贈了 500,000 美元
約翰成為百萬富翁但沒有向紅十字會捐贈 500,000 美元
約翰沒有成為百萬富翁，但向紅十字會捐贈了 500,000 美元
約翰沒有成為百萬富翁，也沒有向紅十字會捐贈 500,000 美元

在四種情況下，約翰哪一種沒有履行他的承諾？顯然，當且僅當第二種情況發生時。因此，我們說命題為假當且僅當約翰成為百萬富翁但沒有捐贈。如果約翰沒有成為百萬富翁，那麼他不會違反他的承諾，因為他的承諾現在沒有聲稱任何東西，因此必須被評估為真。

如果x 和y 是兩個命題，x 蘊涵 y（如果x 那麼y），或者符號表示為

x\Rightarrow y

有以下真值表

x	y	$x\Rightarrow y$
0	0	1
0	1	1
1	0	0
1	1	1

為了強調， $x\Rightarrow y$ 為假當且僅當x 為真而y 為假。如果x 為假，那麼無論y 取什麼值，命題都自動為真。順便說一句，兩個命題x 和y 之間不需要有任何關係，例如，“1 + 1 = 2 蘊涵澳大利亞位於南半球”評估為真！

如果

(x\Rightarrow y)\ {\mbox{AND}}\ (y\Rightarrow x)

那麼我們用符號表示為

x\Leftrightarrow y

.

它是一個雙向蘊涵，它翻譯成x 為真當且僅當y 為真。當且僅當運算有以下真值表

x	y	$x\Leftrightarrow y$
0	0	1
0	1	0
1	0	0
1	1	1

我們介紹的這兩個新運算實際上並不是新的，它們只是 AND、OR 和 NOT 的組合。例如

x\Rightarrow y=x'+y

用真值表檢查它。因為我們可以用 AND、OR 和 NOT 來表示蘊涵運算，所以我們可以透過布林代數和德摩根定律來對它們進行操作。

示例 1
以下命題是否是重言式（一個總是為真的命題）

[(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)

解 1

=\ [(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)

=\ [(x'+y)(y'+z)]'+(x'+z)

=\ (x'+y)'+(y'+z)'+x'+z

=\ xy'+yz'+x'+z

=\ y'+y+x'+z

=\ 1

因此，這是一個永真式。

解法 2
一個稍微簡單的解決方案是繪製命題的真值表，並注意到輸出列都是 1。因此，命題是一個永真式，因為無論輸入（即 x、y 和 z）如何，輸出都是 1。

示例 2
證明命題 z 是一個矛盾式（一個總是為假的命題）

z = xy(x + y)'

解法

{\begin{matrix}z&=&xy(x+y)'\\&=&xy(x'y')\\&=&0\\\end{matrix}}

因此，這是一個矛盾式。

回到示例 1，: $[(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)$ 。這不僅僅是一堆符號，你應該能夠把它翻譯成日常語言，並直觀地理解為什麼它是真的。

練習

判斷以下命題是真還是假
1. 如果 1 + 2 = 3，那麼 2 + 2 = 5
2. 如果 1 + 1 = 3，那麼男孩不喜歡泥土
證明以下一對命題是等價的
1. $x\Rightarrow y$ : $y'\Rightarrow x'$

邏輯謎題

謎題是一個包羅永珍的詞，它指的是任何需要解決的瑣碎問題。這裡有一系列可以用布林代數解決的邏輯謎題。

示例 1

我們有兩種人——騎士或奸詐的人。騎士總是說實話，但奸詐的人總是撒謊。

兩個人，亞歷克斯和芭芭拉，正在聊天。亞歷克斯說：“我們倆都是奸詐的人”。

誰是誰？

我們可能能在腦海裡推斷出亞歷克斯是一個奸詐的人，但確定亞歷克斯身份的代數方法如下

如果亞歷克斯是騎士，則令 A 為 TRUE

如果芭芭拉是騎士，則令 B 為 TRUE

有兩種情況，要麼

亞歷克斯是一個騎士，他所說的是 TRUE，或者

他不是一個騎士，他所說的是 FALSE。

我們已經有了，我們只需要把它翻譯成符號

A(A'B') + A'[(A'B')'] = 1

我們簡化

(AA')B' + A'[A + B] = 1

A'A + A'B = 1

A'B = 1

因此 A 為 FALSE，B 為 TRUE。因此，亞歷克斯是一個奸詐的人，芭芭拉是一個騎士。

示例 2

有三名商人，方便起見分別命名為阿奇、比利和查理，他們每個週末都會一起點馬提尼酒，遵循以下規則

如果 A 點馬提尼酒，B 也點。
B 或 C 總會點馬提尼酒，但不會在同一頓午餐點。
A 或 C 總是點馬提尼酒（或兩者都點）
如果 C 點馬提尼酒，A 也點。

$A\Rightarrow B$ or $A'+B=1$ (從 $AB+A'B'+A'B=1$ 簡化而來）
$B'C+BC'=1$
$A+C=1$
$C\Rightarrow A$ 或 $C'+A=1$ （簡化自： $CA+C'A'+C'A=1$

將所有這些公式合併並簡化

${\begin{matrix}1&=&(A'+B)(B'C+BC')(A+C)(C'+A)\\&=&(A'+B)(B'C+BC')(AC'+AA+CC'+AC)\\&=&(A'+B)(B'C+BC')(AC'+A+0+AC)\\&=&(A'+B)(B'C+BC')(AC'+A+AC)\\&=&(A'+B)(B'C+BC')(C'+1+C)A\\&=&(A'+B)(B'C+BC')(1)A\\&=&(A'+B)(B'C+BC')A\\&&{\mbox{Now that we know that }}A=1{\mbox{ we can substitute that in:}}\\&=&(0+B)(B'C+BC')1\\&=&(B)(B'C+BC')\\&&{\mbox{Now that we know that }}B=1{\mbox{ we can substitute that in:}}\\&=&(1)(0C+1C')\\&=&C'\\&&{\mbox{If }}1=C'{\mbox{ then }}C=0\\&&ABC'=1\end{matrix}}$