高中数学扩展

补充章节 — 素数和模算术 — 逻辑

矩阵 — 更深入的模算术 — 数学规划 — 马尔可夫链

介绍

逻辑是研究我们推理方式的学科。在本章中，我们重点关注逻辑推理的方法，即数字逻辑、谓词演算、应用于证明以及（疯狂）有趣的逻辑谜题。

布尔代数

在理想的黑与白世界里，存在绝对的真理。也就是说，所有事物要么是真，要么是假。带着这种哲学背景，我们考虑以下例子

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

这是（毫无疑问）真的！

"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}}$