离散数学/逻辑/第 2 页

条件命题

示例 8

讨论安迪对伯纳德说：“如果你想要更多咖啡，壶里还有。”这句话是什么意思。

安迪可能的意思是“壶里还有咖啡，如果你想要，自己来。”几乎可以肯定，他并不是真的想暗示壶里是否有咖啡取决于伯纳德是否想要。你可能已经意识到，我们在使用英语时有时非常不严谨！如果我们想用逻辑符号表示一个句子，我们需要做的一件事是弄清楚它的真正含义。

⇒ 蕴涵

示例 9

假设

p 是“天气很暖和”；以及

q 是“我在午餐时间去游泳”。

那么我们可以用符号表示条件命题“如果天气很暖和，那么我在午餐时间去游泳”。

p ⇒ q

所以 ⇒ 的意思是：“如果……那么”，或“蕴涵（或意味着）”。

其他表达相同意思的方式是

• “天气很暖和意味着我在午餐时间去游泳。”

• “无论何时天气很暖和，我都在午餐时间去游泳。”

• “天气很暖和，当且仅当我在午餐时间去游泳。”

请注意最后一句话。它不遵循（也不对应于）我们表达式 p ⇒ q 的逻辑。它改变了 ⇒ 的方向。这句话中使用“如果”这个词改变了命题的因果关系，比如我在午餐时间去游泳意味着天气很暖和。这将是 q ⇒ p，是我们原始表达式中条件的逆转。“当且仅当”这个词意味着如果在某一天我没有在午餐时间去游泳，那么那天天气不可能很暖和，这也是一个逆向蕴涵。当然，我们的表达式并不意味着我去游泳（或者不去）决定了那天天的天气，正好相反！

必要条件和充分条件

假设上周二我在午餐时间去游泳了。给定 p 和 q 如上，并且给定 p ⇒ q，你能确定上周二天气很暖和吗？

答案是否定的，你不能确定。我可能出于其他原因去游泳了。

因此，请注意，p ⇒ q 意味着 p 是 q 的充分条件。然而，它不是必要条件：q 仍然可以在没有 p 的情况下为真。

其他表达方式

“即使天气不暖和，我也可以在午餐时间去游泳。”

“无论天气如何，我都可以去游泳。”

⇒ 的真值表

请注意，p ⇒ q 本身是一个命题；也就是说，它有一个真值——如果天气很暖和，我是否在午餐时间去游泳。这可能或不可能是事实。

现在，命题 p ⇒ q 的值取决于 p 和 q 的值的组合。所以我们可以构造它的真值表

p	q	p ⇒ q
T	T	T
T	F	F
F	T	T
F	F	T

请特别注意这个表中的第三行（可能令人惊讶）！事实上，p ⇒ q 意味着如果 p 为假，我们不能得出关于 q 的任何结论。也就是说，如果p 为假，q 可以同样可能是真或假，而不会与 p ⇒ q 的真值相矛盾。

换句话说，p ⇒ q 仅在 p 为 T 且 q 为 F 时为假；也就是说，一个真命题不能蕴涵一个假命题。

为了进一步澄清这一点，请考虑上面那句话：“如果天气很暖和，那么我在午餐时间去游泳。”这句话没有说明天气不暖和时会发生什么：我可能会去游泳，也可能不会去。只有当天气很暖和，但我没有去游泳时，这句话才是假的。

双条件命题

正如我们已经指出的，我们经常以一种非常不精确的方式使用英语。使用示例 9，假设我真正想说的是

如果天气很暖和，我就去游泳，如果天气不暖和，我就不去。

在这种情况下，p 和 q 都是真，或者都是假：你不能拥有其中一个而没有另一个。我们可以改写一下这句话，说

我只有在天气很暖和的情况下才会去游泳。

短语“当且仅当”用符号 ⇔ 表示，所以我们可以说在这种情况下

p ⇔ q

在这种情况下，p 是 q 的必要且充分条件。

示例 10

p 是“x² = 9”。找到关于 x（而不是 x²）的适当语句 q，使得 p ⇔ q 为真。

解决方案

如果 x = 3，那么当然 x² = 9。所以如果 q 是“x = 3”，那么 q ⇒ p 为真，这将使 q 成为一个充分条件。

但它是必要且充分的吗？不，因为 3 不是唯一一个平方为 9 的数字。x = -3 也将使 x² = 9。

为了确保必要且充分的 q，我们需要说

q 是“x = ±3”。

逻辑等价

我们已经说过 p ⇔ q 意味着 p 和 q 都是真，或者都是假，因此我们可以说在这种情况下，它们是逻辑等价的。

⇔ 的真值表

由于 p ⇔ q 表示 p 和 q 同时为真或同时为假，所以 ⇔ 的真值表如下

p	q	p ⇔ q
T	T	T
T	F	F
F	T	F
F	F	T

示例 11

通过绘制真值表，证明：

p ⇔ q ≡ (p ⇒ q) $\scriptstyle \wedge$ (q ⇒ p)

解决方案

(p ⇒ q) $\scriptstyle \wedge$ (q ⇒ p) 的真值表如下

p	q	(p ⇒ q)	$\scriptstyle \wedge$	(q ⇒ p)
T	T	T	T	T
T	F	F	F	T
F	T	T	F	F
F	F	T	T	T
		1	3 输出	2

输出结果为 T, F, F, T，与 p ⇔ q 的输出结果相同，因此

p ⇔ q ≡ (p ⇒ q) $\scriptstyle \wedge$ (q ⇒ p)

⇐ 符号

我们有时使用 ⇐ 表示“被蕴涵”。因此，q ⇐ p 是 p ⇒ q 的另一种写法，我们可以将 示例 11 写成

p ⇔ q ≡ (p ⇒ q) $\scriptstyle \wedge$ (p ⇐ q)

逻辑练习 4

点击链接访问 逻辑练习 4。

谓词逻辑

到目前为止，我们只考虑了 命题逻辑，其中语句如：

p 是“所有红头发的人脾气暴躁”。

q 是“Joe 有红头发”。

假设 p 和 q 如上所述，并且 r 是“Joe 脾气暴躁”，我们可以写成：

p $\scriptstyle \wedge$ q ⇒ r

如果我们想要对 Brenda 有红头发，因此脾气暴躁的论述，则需要进一步的命题，例如：

s 是“Brenda 有红头发”。

t 是“Brenda 脾气暴躁”。

因此

p $\scriptstyle \wedge$ s ⇒ t

… 等等。

每次我们想要对另一个有红头发，因此脾气暴躁的人（这可能是真的，也可能不是真的）进行论述，都需要进一步的命题。一个更好的表示这些想法的方法是使用 谓词，例如：

redHair 表示“... 有红头发”。

(注意，redHair 不是一个命题。为什么呢？)

现在我们可以使用这个谓词来形成关于所有有红头发的人的论述，例如：

redHair(Joe) 是“Joe 有红头发”。

redHair(Brenda) 是“Brenda 有红头发”。

… 等等。

同样地，我们可以定义谓词 fieryTemper 来表示短语

"... 脾气暴躁”。

因此，语句“如果 Joe 有红头发，那么他脾气暴躁”可以表示为：

redHair(Joe) ⇒ fieryTemper(Joe)

语句“如果 Brenda 有红头发，那么她脾气暴躁”可以表示为：

redHair(Brenda) ⇒ fieryTemper(Brenda)

符号

我们将使用单个单词或多个连接在一起的单词，并使用如上所示的大写和小写字母来表示谓词。

谓词应用的“对象” - 人，数字或任何事物 - 将在谓词之后用括号括起来。

否定

假设 red Hair 的定义如上所述

¬with red Hair 是“并非有红头发”。

逻辑练习 5

点击链接访问 逻辑练习 5。

命题函数

如果我们想要谈论一般的、未定义的谓词，我们将使用大写字母：P, Q, ..., 如果我们想要一个一般的、未定义的对象，我们将使用小写字母：x, y, ...

因此，如果 P 是“... 具有属性 P”，那么 P(x) 是“x 具有属性 P”。

• P(x) 可以被描述为一个 命题函数，其谓词为 P。

函数具有这样的属性：当我们知道传递给它的任何参数的值时，它将返回一个唯一的值。P(x) 因此是一个函数，因为它返回一个取决于参数 x 值的真值。

例如，如果 American(x) 是命题函数“x 是美国人”，那么 American(x) 将返回以下值

如果 x = 比尔·克林顿，则为 T；

如果 x = 女王陛下，则为 F

量词

现在我们来扩展上面练习 5 中的思路。假设我们想要做出像这样的陈述：

(a) 我的所有朋友都很有钱。

(b) 我的一些朋友很无聊。

这里的问题是，我们在做关于我朋友的总体陈述，而没有提到特定的个人。因此，我们需要定义命题函数如下：

friend(x) 表示 “x 是我的朋友”

wealthy(x) 表示 “x 很富有”

boring(x) 表示 “x 很无聊”

然后我们可以将上面的两个陈述写成：

(a) 对所有的 x，friend(x) ⇒ wealthy(x)

(b) 对某些 x，friend(x) $\scriptstyle \wedge$ boring(x)

符号：∀ 和 ∃

符号 ∀（称为全称量词）代表短语“对所有……”

因此我们可以将上面的 (a) 写成

(a) ∀ x，friend(x) ⇒ wealthy(x)

符号 ∃（称为存在量词）代表短语“对某些……”

因此我们可以将上面的 (b) 写成

(b) ∃ x，friend(x) $\scriptstyle \wedge$ boring(x)

复数还是单数？

请注意，虽然上面的陈述 (a) 和 (b) 使用了复数词语 - 所有的，是，一些，朋友 - 但是当我们用符号表示它们时，谓词和变量是单数：x 是富有的，x 是无聊的等等。因此，重要的是要意识到，x 一次只能代表一个值。

因此，符号陈述

∀ x，friend(x) ⇒ wealthy(x)

可以用单数词语逐字翻译成

“对x 的每个值，如果x 是我的朋友，那么x 很富有”。

而

∃ x，friend(x) $\scriptstyle \wedge$ boring(x)

更确切地翻译成

“对x 的至少一个值，x 是我的朋友，并且x 很无聊”。

为了强调这一点，你可能会发现使用以下内容来翻译符号很有帮助：

∀ 表示 “对每个（值的）……”

而

∃ 表示 “对至少一个（值的）……”

现在我们可以使用命题函数符号来表示我们之前关于“所有红头发的人都脾气暴躁”的陈述，如下所示：

redHair(x) 表示：“x 有红头发”

fieryTemper(x) 表示：“x 有暴脾气”

现在“所有红头发的人都脾气暴躁”用单数重写为

对x 的每个值，如果x 有红头发，那么x 就有暴脾气。

用符号表示，就是

∀ x，redHair(x) ⇒ fieryTemper(x)

示例 12

定义合适的命题函数，然后用符号表示

(a) 一些猫懂法语。

(b) 没有足球运动员会唱歌。

(c) 至少有一位讲师不无聊。

(d) 我每天阳光明媚的时候都会去游泳。

解答

(a) 用单数重写：“至少有一只猫懂法语”。因此，我们需要定义命题函数为

cat(x) 表示 “x 是一只猫”

French(x) 表示 “x 懂法语”

因此，至少有一个x 既是猫又懂法语；用符号表示就是

∃x，cat(x) $\scriptstyle \wedge$ French(x)

(b) 用单数重写：“至少有一位足球运动员会唱歌是不对的”。因此

footballer(x) 表示 “x 是一位足球运动员”

sing(x) 表示 “x 会唱歌”

用符号表示，就是

¬ (∃x，footballer(x) $\scriptstyle \wedge$ sing(x))

或者，我们可以将“没有足球运动员会唱歌”重写为“对每个x，如果x 是一位足球运动员，那么x 不会唱歌”。用符号表示，就会得到同样有效的解

∀ x，footballer(x) ⇒ ¬ sing(x)

(c) 这句话已经是单数了；因此

lecturer(x) 表示 “x 是一位讲师”

boring(x) 表示 “x 很无聊”

所以

∃ x，lecturer(x) $\scriptstyle \wedge$ ¬ boring(x)

(d) 在这个例子中，重要的是要意识到变量代表什么。在 (a) 到 (c) 中，变量x 表示动物或人。在句子“我每天阳光明媚的时候都会去游泳”中，变化的是时间，随之变化的是天气和我去游泳。因此，我们必须围绕一个代表时间的变量x 来形成命题函数。因此

sunny(x) 表示 “x 是一个阳光明媚的日子”

swimming(x) 表示 “x 是我去游泳的一天”

然后，将“我每天阳光明媚的时候都会去游泳”用单数重写，就会得到

“对每一天，如果那是一个阳光明媚的日子，那么它就是一个我去游泳的日子”。

因此，用符号表示就是

∀x，sunny(x) ⇒ swimming(x)

逻辑练习 6

单击链接以查看逻辑练习 6。

论域

练习 5 和6 中的许多命题都提到了“我的朋友”。例如，考虑命题：“我所有朋友要么有钱要么聪明”。

使用谓词，我们可以用符号表示为

∀ x，friend(x) ⇒ (wealthy(x) ∨ clever(x))

但是，如果我们同意变量x 只能代表我的一个朋友，那么我们可以将其更简单地表示为

∀ x，wealthy(x) ∨ clever(x)

对于给定的命题函数P(x)，论域 是可以从中选择x 的值的集合。定义论域可以简化命题函数的符号表示。如果没有定义论域，那么我们必须假设可以将任何对象或个人代入x。

示例 13

在每种情况下，定义一个合适的论域和谓词来符号化

(a) 一些学生勤奋或酗酒。

(b) 每个人都很热，有人晕倒了。

解答

(a) 定义以下内容

论域 = {学生}

hardWorking(x) 是“x 勤奋”

drink(x) 是“x 酗酒”

用单数形式写作：“对于至少一个 x，x 勤奋或 x 酗酒”，我们得到

∃ x, hardWorking(x) ∨ drink(x)

(b) 在给定句子中，“每个人”显然不代表全世界所有人，只是故事中提到的每个人。因此，我们可以定义如下

论域 = {故事中的人物}

hot(x) 是“x 很热”

fainted(x) 是“x 晕倒了”

然后，用单数形式，我们有“对于每个 x，x 很热，并且对于至少一个 x，x 晕倒了”。所以

∀ x, hot(x) $\scriptstyle \wedge$ ∃ x, fainted(x)

二元谓词

我们之前看到的谓词都是一元谓词。为了将每个谓词转换为命题，我们必须提供一个单一的对象或个体——如果你愿意，可以是单个参数的值。

我们可以创建需要两个对象（或参数值）才能转换为命题的谓词。这样的谓词称为二元谓词。

示例 14

考虑以下谓词

greaterThan 是“……大于……”

loves 是“……爱……”

belongsTo 是“……属于……”

那么以下就是二元命题函数

greaterThan(x, y) 是“x 大于 y”

loves(x, y) 是“x 爱 y”

belongsTo(x, y) 是“x 属于 y”

因此，例如，以下是命题

greaterThan(5, 2) 是“5 大于 2”

loves(Bob, Lizzie) 是“Bob 爱 Lizzie”

belongsTo(This coat, Harry) 是“这件外套属于 Harry”

二元谓词和量词

对于上面的谓词，我们可以对一个变量进行量化

∀ x, belongsTo(x, me) 是“所有东西都属于我”

∃ x, greaterThan(2, x) 是“2 大于某些东西”

∀ x, loves(Mary, x) 是“Mary 爱所有人”

……或两个变量

∀ x, ∃y, loves(x, y) 是“每个人都爱某人”

∃ x, ∀ y, loves(x, y) 是“某人爱所有人”

∃ x, ∃ y, loves(x, y) 是“某人爱某人”

∀ x, ∀ y, loves(x, y) 是“每个人都爱所有人”

量化命题函数的否定

在练习 1的第 5 题中，我们必须说明哪些选项代表了命题的否定。让我们再次看看，使用我们的量化命题函数符号。

示例 15

考虑命题的否定

“所有绵羊都是黑色的”。

否定是

“所有绵羊都是黑色的并不正确”。

这等同于

“至少有一只绵羊不是黑色的”。

如果我们将论域定义为 {绵羊}，并以明显的方式定义 isBlack，那么我们可以用以下符号来表示所有这些

¬ (∀ x, isBlack(x)) ≡ ∃ x, ¬isBlack(x)

现在考虑命题

“有些绵羊是黑色的”。

这的否定是

“有些绵羊是黑色的并不正确”

这等同于

“所有绵羊都不是黑色的”

这可以用以下符号表示

¬ (∃ x, isBlack(x)) ≡ ∀ x, ¬isBlack(x)

我们可以将我们在此处发现的内容推广到任何命题函数 P(x)，如下所示

¬(∀ x, P(x)) ≡ ∃ x, ¬ P(x)

¬(∃ x, P(x)) ≡ ∀ x, ¬P(x)

逻辑练习 7

点击链接查看逻辑练习 7。