高中數學擴充套件

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

矩陣 — 進一步的模算術 — 數學規劃 — 馬爾可夫鏈

介紹

邏輯是對我們推理方式的研究。在本章中，我們重點關注邏輯推理的方法，即數字邏輯、謂詞演算、對證明的應用以及（令人難以置信地）有趣的邏輯謎題。

布林代數

在理想的黑白世界中，存在絕對真理。也就是說，一切要麼是真，要麼是假。有了這種哲學背景，我們考慮以下例子

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

那（毫無疑問）是正確的！

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

那也是正確的。

但關於

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

這是真的！雖然 1 + 1 = 3 不正確，但語句中的 OR 使整個語句在至少一個語句為真的情況下為真。

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

"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 OR y AND z

為了更進一步，數學家還用 + 替換 OR，用 × 替換 AND，語句變成

x+y\times z

現在優先順序順序很清楚了。我們先評估 (y AND z)，然後用 x 與之 OR。語句 "x + yz" 為真，或者用符號表示

x+yz=1

其中數字 1 代表 "真"。

我們選擇 AND 操作的乘號是有充分理由的。正如我們將在後面看到的那樣，我們可以從 AND 操作和乘法之間畫出一些平行線。

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

布林代數有類似於我們所知和喜歡的普通代數的操作（AND 和 OR）。

基本真值表

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

讓我們考慮與乘法類似的 AND 操作。我們想考慮

x AND y

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

AND 函式
x	y	x AND y
F	F	F
F	T	F
T	F	F
T	T	T

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

AND 函式
x	y	x AND y
0	0	0
0	1	0
1	0	0
1	1	1

現在你應該能夠看到為什麼我們說 AND 類似於乘法，我們將用 × 替換 AND，所以x AND y 變為 x×y（或僅僅是xy）。從 AND 真值表中，我們有

0 × 0 = 0

0 × 1 = 0

1 × 0 = 0

1 × 1 = 1

對 OR 操作。 x OR y 為假，當且僅當x 和y都為假。表格形式

OR 函式
x	y	x OR y
0	0	0
0	1	1
1	0	1
1	1	1

我們說 OR 幾乎類似於加法。我們將透過用 + 替換 OR 來說明這一點

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1（就像 1 OR 1 是 1）

非運算與 AND 和 OR 運算不同，它不是 *二元運算*，而是 *一元運算*，這意味著它只作用於一個引數。**NOT *x*** 為真，如果 *x* 為假，為假，如果 *x* 為真。表格形式如下

非函式
x	NOT x
0	1
1	0

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

備選符號

x\times y=x\wedge y

和

x+y=x\vee y

組合真值表

上面介紹的三個真值表是最基本的真值表，它們是構建更復雜真值表的基石。假設我們想要構建表示式 xy + z 的真值表（即 x AND y OR 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	xyORz
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

練習

為以下運算生成真值表

NAND：x NAND y = NOT (x AND y)
NOR：x NOR y = NOT (x OR y)
XOR：x XOR 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}}

有人說：“數學裡唯一要記住的就是沒有東西要記住。記住這一點！”。您不應該試圖記住這些定律的陳述方式，因為一旦您熟悉了 AND、OR 和 NOT 運算，其中一些定律就會變得非常明顯。您只需要記住最基本的東西，一旦您對它們有了充分的瞭解，您就會同意真的沒有什麼需要記住的。

化簡

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

{\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。因此命題是一個重言式，因為輸出為 1，無論輸入（即 x、y 和 z）是什麼。

示例 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萊利和C哈利，他們每個週末都會一起點雞尾酒，遵循以下規則

如果 A 點了一杯雞尾酒，B 也點一杯。
B 或 C 總會點雞尾酒，但絕不會在同一個午餐時間點。
A 或 C 總會點雞尾酒（或兩者都點）。
如果 C 點了一杯雞尾酒，A 也點一杯。

$A\Rightarrow B$ 或 $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}}$