高中数学扩展/逻辑

高中数学扩展

---

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

数学证明 — 集合论和无限过程 — 计数和生成函数 — 离散概率

矩阵 — 进一步的模算术 — 数学规划 — 马尔可夫链

介绍

逻辑是对我们推理方式的研究。在本章中，我们重点关注逻辑推理的方法，即数字逻辑、谓词演算、对证明的应用以及（令人难以置信地）有趣的逻辑谜题。

布尔代数

在理想的黑白世界中，存在绝对真理。也就是说，一切要么是真，要么是假。有了这种哲学背景，我们考虑以下例子

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

那（毫无疑问）是正确的！

"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

练习

为以下运算生成真值表

1. NAND：x NAND y = NOT (x AND y)
2. NOR：x NOR y = NOT (x OR y)
3. XOR：x XOR y 为真，当且仅当 x 或 y 中只有一个为真。

为以下表达式生成真值表

1. xyz
2. x'y'z'
3. xyz + xy'z
4. xz
5. (x + y)'
6. x'y'
7. (xy)'
8. 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. 将以下表达式简化为最简的积之和形式
   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'
2. 证明 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 美元。”

有四种情况

1. 约翰成为百万富翁并向红十字会捐赠了 500,000 美元
2. 约翰成为百万富翁但没有向红十字会捐赠 500,000 美元
3. 约翰没有成为百万富翁但向红十字会捐赠了 500,000 美元
4. 约翰没有成为百万富翁也没有向红十字会捐赠 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. 如果 1 + 2 = 3，那么 2 + 2 = 5
   2. 如果 1 + 1 = 3，那么男孩不喜欢泥巴
2. 证明下列一对命题是等价的
   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哈利，他们每个周末都会一起点鸡尾酒，遵循以下规则

1. 如果 A 点了一杯鸡尾酒，B 也点一杯。
2. B 或 C 总会点鸡尾酒，但绝不会在同一个午餐时间点。
3. A 或 C 总会点鸡尾酒（或两者都点）。
4. 如果 C 点了一杯鸡尾酒，A 也点一杯。

1. $A\Rightarrow B$ 或 $A'+B=1$（从：$AB+A'B'+A'B=1$ 简化而来）
2. $B'C+BC'=1$
3. $A+C=1$
4. $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}}$

练习

请访问 Puzzles/Logic puzzles.

习题集

1. 判断以下命题是否等价

$x'\Rightarrow y'$

$y\Rightarrow x$

2. 将以下命题以最简单的和积形式表示

$(x\Leftrightarrow y)\Rightarrow z$

3. 将以下句子翻译成符号形式并判断真假

a. 对所有x，如果x² = 9，则x² - 6x - 3 = 0

b. 我们可以找到一个x，使得x² = 9 和x² - 6x - 3 = 0 同时成立。

4. NAND 是一种二元运算

x NAND y = (xy)'

找到一个仅包含 NAND 运算符的命题，等价于

(x + y)w + z

5. 对 NOR 运算符执行相同的操作。回想一下 x NOR y = (x + y)'

反馈

你有什么想法？ 太简单了还是太难了？ 信息太多还是不够？ 我们该如何改进？ 请在讨论标签中留下评论告诉我们。 更好的是，自己编辑它并使其变得更好。