离散数学/逻辑

简介

在传统代数中，字母和符号用来表示数字及其相关的运算：+，-，×，÷等。这样做可以帮助简化和解决复杂问题。在逻辑中，我们试图用代数符号来表达语句以及它们之间的联系——再次以简化复杂想法为目标。不幸的是，就像普通代数一样，起初似乎相反。这可能是因为简单的例子总是显得更容易通过常识方法来解决！

命题

命题是一个具有真值的语句：它要么是真(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) 不一样，我们可能不知道真值，因为我们没有足够的了解。参见下一段。

命题函数

函数，通俗地讲，是一个操作，它接收一个或多个参数值作为输入，并产生一个明确定义的输出。

例如，您可能熟悉三角学中的正弦和余弦函数。这些是函数的例子，它们接收一个数字（角度的大小）作为输入，并产生一个十进制数字（实际上介于 +1 和 -1 之间）作为输出。

如果我们愿意，可以定义我们自己的函数，例如RectangleArea，它可以接收两个数字（矩形的长和宽）作为输入，并产生一个数字作为输出（通过将两个输入数字相乘形成的）。

在上面的 (f) 中，我们有一个命题函数的例子。这是一个函数，它产生的输出不是像正弦、余弦或RectangleArea那样的数字，而是一个真值。然后，它是一个语句，当它被提供一个或多个参数值时，它就变成了一个命题。在 (f) 中，参数是x和y。因此，如果x = 2 且 y = 7，则其输出为False；如果x = 4 且 y = -10，则其输出为True。

关于命题函数的更多内容将在后面介绍。

符号

我们通常用小写字母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 和 q 的值如何，(p $\scriptstyle \wedge$ 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)

永真式

一个表达式，始终具有值true，称为永真式。

此外，任何冗余或幂等的语句也被称为永真式，原因与上述相同。如果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 是与运算的“指纹”。因此，我们可以将 ¬(¬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.