离散数学/逻辑

引言

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

命题

命题是一个具有真值的陈述：它要么是真（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) 不完全相同，在 (c) 中，我们可能不知道真值，因为我们没有足够的了解。见下一段。

命题函数

函数，简单来说，是一种操作，它以一个或多个参数值作为输入，并产生一个明确定义的输出。

例如，您可能熟悉三角学中的正弦和余弦函数。这些是函数的例子，它们以单个数字（角度大小）作为输入，并产生小数数字（事实上将位于 +1 和 -1 之间）作为输出。

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

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

稍后将详细介绍 命题函数。

符号

我们通常用小写字母 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 $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬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)

重言式

始终具有 *真* 值的表达式称为 *重言式*。

此外，任何冗余或幂等的语句也被称为重言式，原因与前面提到的相同。 如果 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 作为 AND 操作的“足迹”。所以我们可以将 ¬(¬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.