1.1 命题与联结词

1.1.1 命题的概念

定义1.1.1 命题 是用陈述句表示的一个或者为真或者为假，但不能同时既为真又为假的判断语句。

命题代表人们进行思维活动时的一种判断，或者是肯定，或者是否定，因此命题只能为真或假，把这种真假的结果称为命题的 真值 。如果命题的真值为真，称该命题为 真命题 ，其真值可用“T”或“1”表示；如果命题的真值为假，称该命题为 假命题 ，其真值可用“F”或“0”表示。

例1.1.1 判断下列句子哪些是命题？若是命题，判断其真值。

1）2+3=5。

2）2+3=6。

3）北京是中国的首都。

4）2013年5月1日是星期日。

5）3 -x =5。

6）请关上门。

7）几点了？

8）除地球外的星球有生物。

9）多漂亮的花啊！

10）对每一对实数 x 、 y ，都有 x + y = y + x 。

解 1）、2）、3）、4）、8）、10）是命题，5）、6）、7）、9）不是命题。1）、3）、10）的真值为1，2）、4）的真值为0。8）是命题，能判断真假，且其真值是唯一确定的，只是目前人们不知道。5）不是命题，因为 x 是变元，它的真值不确定。6）是祈使句，7）是疑问句，9）是感叹句。祈使句、疑问句、感叹句表示的语义没有真假，所以6）、7）、9）都不是命题。

◀

注意：表示命题的陈述句可判断真假，具有唯一真值。悖论是陈述句，但不能判断其真假，因此不是命题。例如，“我只给所有不给自己理发的人理发”不是命题。

引入英文字母表示任意的命题，就像用字母表示数学变元那样。表示命题的符号称为 命题变元 ，通常用 p 、 q 、 r …或 P 、 Q 、 R …来表示。命题变元没有真值，只有表示一个确定的命题后，才有真值。如用 p 表示命题“2+3=6”，这时 p 的真值为0，也可以用 p 表示命题“2+3=5”，这时 p 的真值为1。

定义1.1.2 表示命题的陈述语句如果不能分解为更简单的陈述语句，称为 简单命题 或 原子命题； 表示命题的陈述句由几个简单句和连词组合而成，称为 复合命题 。

本书中用小写英文字母表示简单命题，如用 p 表示简单命题“北京是中国的首都”。数理逻辑中定义了对应于自然语言中连词的联结词，通常用英文字母和联结词的组合表示复合命题。

定义1.1.3 用英文字母或英文字母和联结词的组合表示命题，称为 命题的符号化 。

1.1.2 联结词

定义1.1.4 设 p 是一个命题， 表示一个新命题“非 p ”。“ ”是否定联结词，命题 称为 p 的 否定 。当且仅当 p 为假时， 为真。

真值表给出命题真值之间的关系。表1.1.1给出命题变元 p 及其否定的所有可能的真值，称为否定联结词“ ”的 真值表 。

例如， p 表示“今天是晴天”，则 表示“今天不是晴天”。注意， 不能理解为“今天是雨天”，因为“今天是晴天”的否定并不是“今天是雨天”，还可能是“今天是阴天”“今天是下雪天”等。

自然语言中表示否定的连词“非”“不”“没有”“无”“并非”等都可用 来表示。

定义1.1.5 设 p 、 q 表示任意两个命题， p ∧ q 可表示复合命题“ p 并且 q ”。“∧”称为 合取 联结词。命题 p ∧ q 称为 p 和 q 的合取。当且仅当 p 和 q 同时为真时， p ∧ q 为真。真值表见表1.1.2。

例如， p 表示“今天是晴天”， q 表示“今天去公园”。则 p ∧ q 表示“今天是晴天并且今天去公园”。

自然语言中的“和”“与”“也”“并且”“既……又……”“不仅……而且……”“虽然……但是……”等表示同时的连词都可用∧来表示。假设 p 表示“小李聪明”； q 表示“小李用功”，则“小李既聪明又用功”和“小李不仅聪明而且用功”均可符号化为 p ∧ q 。

定义1.1.6 设 p 、 q 是任意两个命题， p ∨ q 可表示复合命题“ p 或 q ”，“∨”称为 析取 联结词。命题 p ∨ q 称为 p 和 q 的析取。当且仅当 p 和 q 都为假时， p ∨ q 为假。真值表见表1.1.3。

例如， p 表示“电灯不亮是灯泡有问题所致”， q 表示“电灯不亮是线路有问题所致”，则 p ∨ q 表示电灯不亮是灯泡或线路有问题所致。

析取联结词可表示自然语言中的“或”“可能……可能……”“或者……或者……”等。自然语言中的“或”具有二义性，有时表示兼容性或，有时表示不兼容性或。由定义可以看出， p ∨ q 表示的是兼容性或，即容许 p 和 q 的真值中一个为真，或 p 与 q 的真值都为真。而对于命题“派小王或小李中的一人去开会”，其中的“或”表达的是不兼容性或（又称排斥或）。假设 p 表示命题“派小王去开会”， q 表示命题“派小李去开会”，该句不能符号化为 p ∨ q 的形式，而应符号化为 。在命题逻辑中，将不兼容性或称为 异或 。

定义1.1.7 设 p 、 q 为任意两个命题， p → q 可表示复合命题“如果 p ，则 q ”，“→”称为 蕴涵 联结词。命题 p → q 称为 p 与 q 的蕴涵式。当且仅当 p 为真、 q 为假时， p → q 为假。真值表见表1.1.4。

例如， p 表示“今天天气晴朗”， q 表示“我们去海滩”，则 p → q 表示“如果今天天气晴朗，我们就去海滩”。

蕴涵式 p → q 表示的逻辑关系是： p 是 q 的充分条件， q 是 p 的必要条件。因此形如“如果 p ，则 q ”“如果 p ，那么 q ”“当 p 则 q ”“ p 仅当 q ”等复合命题都可以符号化为 p → q 的形式。形如 p → q 的蕴涵式中，称 p 为 蕴涵前件 ， q 为 蕴涵后件 。

例1.1.2 将下列命题符号化。

1）如果天气晴朗，我们去海滩。

2）仅当天气晴朗，我们去海滩。

解 假设 p 表示“天气晴朗”， q 表示“我们去海滩”。

1）可符号化为 p → q ，因为“天气晴朗”是“我们去海滩”的充分条件。

2）可符号化为 q → p ，这句的“天气晴朗”是“我们去海滩”的必要条件。

◀

注意，只有 p 的真值为真而 q 的真值为假时， p → q 的真值才为假；当 p 和 q 的真值都为真或 p 的真值为假（无论 q 的真值为真还是假）时， p → q 的真值都为真。蕴涵式的前件的真值为假、后件的真值为任何值时，蕴涵式的真值都为真，对此，可以理解为当规定的前提条件不成立时，得出任何结论都是有效的。例如，命题“如果2+3=6，则太阳从东方升起”和“如果2+3=6，则太阳从西方升起”的真值都为真。

这两个命题的假设和结论之间没有什么联系，在自然语言中，我们不会使用这样的条件句。在数学推理中，条件语句作为一个数学概念不依赖于假设和结论之间的语义关系。

定义1.1.8 设 p 、 q 为任意两个命题， p ↔ q 可表示命题“ p 当且仅当 q ”。“↔”称为 等价 联结词，命题 p ↔ q 称为等值式。当且仅当 p 和 q 同时为真或同时为假时， p ↔ q 为真。真值表见表1.1.5。

等值式 p ↔ q 表示 p 与 q 互为充分必要条件的逻辑关系，也就是表示形如“ p 当且仅当 q ”“如果 p ，那么 q ，反之亦然”等的命题。

例如， p 表示“两个三角形是全等的”， q 表示“两个三角形的三条对应边相等”，则 p ↔ q 表示“两个三角形是全等的当且仅当它们的三条对应边相等”。

也可以用一个英文字母来表示复合命题，但在推理问题的研究中有时是不适合的。对于一个复合命题，通常先分析出其中包含的简单命题及它们之间的关系，分别用英文字母表示每一个简单命题，选用合适的联结词表示命题间的关系，然后用联结词联结表示简单命题的字母，组成复合命题的表示式。

例1.1.3 将下列命题符号化。

1）虽然天气很冷，老王还是来了。

2）小王和小李是好朋友。

3）小王和小李是好学生。

4）小王或小李中的一个人是游泳冠军。

5）只有学过微积分或数学系的学生，才可以选修这门课。

6）如果明天早晨6点不下雨，我就去跑步。

7）今天下雨与3+3=6。

8）登录服务器必须输入一个有效的口令。

9）2+3=5的充要条件是加拿大位于亚洲。

解 1）设 p 表示“天气很冷”， q 表示“老王来了”，则1）可符号化为 p ∧ q 。

2）这句虽然有连词“和”，但是一个简单句，可用 p 表示“小王和小李是好朋友”。

3）这句中的连词“和”连接两个简单句“小王是好学生”和“小李是好学生”，分别用 p 和 q 表示这两个简单命题，则可符号化为 p ∧ q 。

4）这句中的“或”是不兼容性或，因此应符号化为 ，其中 p 表示“小王是游泳冠军”， q 表示“小李是游泳冠军”。

5）这句含有3个简单命题，可分别用 p 、 q 、 r 来表示，设 p 表示“学过微积分的学生”， q 表示“数学系的学生”， r 表示“你可以选修这门课”。这句中含有的“或”是兼容性或，“只有……才……”的表达方式表示“你学过微积分或是数学系的学生”是“你可以选修这门课”的必要条件，所以，这个命题可以符号化为 r →（ p ∨ q ）。

6）设 p 表示“明天早晨6点下雨”， q 表示“我去跑步”，则6）可符号化为 ，或者也可以符号化为 。

7）设 p 表示“今天下雨”， q 表示“3+3=6”，则7）可符号化为 p ∧ q 。

8）设 p 表示“登录服务器”， q 表示“输入一个有效的口令”，则8）可符号化为 p → q 。

9）设 p 表示“2+3=5”， q 表示“加拿大位于亚洲”，则9）可符号化为 p ↔ q 。

◀

有些命题在自然语言中可能是没有意义的，如上例中的命题7），其中包含的两个简单句语义上没有联系，逻辑上是合取关系。在数理逻辑中， p ∧ q 、 p ∨ q 、 p → q 、 p ↔ q 中的 p 和 q 可以没有语义上的联系。

这里定义了5个主要联结词： ，∧，∨，→，↔。其中 是一元联结词，∧、∨、→、↔是二元联结词。与普通运算符一样，可以规定运算的优先级，优先顺序为 、∧、∨、→、↔。例如， p ∨ q → r 等同于（ p ∨ q ）→ r 。若有括号，先进行括号中内容的运算。括号有时被省略，如 是 和 q 的合取，这里是省略了 的括号，即 ，而不是 p 和 q 的合取的否定，即 。合取运算符的优先级高于析取运算符，但这个规则不好记，所以可使用括号来区别合取运算符和析取运算符的顺序。对于条件运算符和双条件运算符，也可使用括号区分它们的运算顺序。

例1.1.4 将下列命题符号化，并指出它们的真值。

1）1+1=2和2+3=6。

2）1+1=2或猴子是飞禽。

3）若2+3=6，则猴子是飞禽。

4）若猴子不是飞禽，则1+1=2和2+3=6。

5）若2+3=6或猴子是飞禽，则1+1=2。

6）2+3=6当且仅当猴子不是飞禽。

解 设 p 表示“1+1=2”， q 表示“2+3=6”， r 表示“猴子是飞禽”，则 p 表示的命题真值为1， q 表示的命题真值为0， r 表示的命题真值也为0。因而命题符号化为：

1） p ∧ q ，真值为0，因为 p 和 q 中有一个为0。

2） p ∨ q ，真值为1，因为 p 和 q 中有一个为1。

3） q → r ，真值为1，因为这个条件蕴涵式的前件为0，当条件蕴涵式的前件为0时，无论它的后件的真值为1还是0，这个条件蕴涵式的真值都为1。

4） ，真值为0，因为这个条件蕴涵式的前件为1，后件为0。

5） q ∨ r → p ，真值为1，原因同3）。

6） ，真值为0，因为 q 为0， 为1。

◀

除了这5个联结词外，还定义了一些表示其他逻辑关系的联结词。常用的有与非联结词、或非联结词和异或联结词等。下面给出它们的定义。

定义1.1.9 设 p 和 q 是任意两个命题， p ↑ q 可表示复合命题“ p 和 q 的与非”，“↑”称为 与非 联结词。命题 p ↑ q 称为 p 和 q 的 与非式 。当且仅当 p 和 q 同时为真时， p ↑ q 为假。真值表见表1.1.6。可以看出，与非式 p ↑ q 和 等值。

定义1.1.10 设 p 和 q 是任意两个命题， p ↓ q 可表示复合命题“ p 和 q 的或非”，“↓”称为 或非 联结词。命题 p ↓ q 称为 p 和 q 的 或非式 。当且仅当 p 和 q 同时为假时， p ↓ q 为真。真值表见表1.1.7。可以看出，或非式 p ↓ q 和 等值。

定义1.1.11 设 p 和 q 是任意两个命题， p ⊕ q 可表示复合命题“ p 、 q 之中恰有一个成立”，“⊕”称为 异或 （不兼容性或）联结词。命题 p ⊕ q 称为 p 和 q 的 异或式 。当且仅当 p 和 q 恰有一个为真时， p ⊕ q 为真。真值表见表1.1.8。可以看出，异或式 p ⊕ q 和 等值。

在计算机中，这些联结词表示的逻辑关系可以用数字电路中的门电路实现，例如，表示“非”逻辑关系的否定联结词 用数字电路中的“非门”实现，∧联结词用“与门”实现，∨联结词用“或门”实现，→和↔实际上可以用 、∧和∨三个联结词来表示，所以可以用非门、与门和或门组合的电路来实现。图1.1.1是非门、与门和或门的电路符号。

非门有一个输入端和一个输出端，与门和或门有两个或两个以上的输入端和一个输出端。与非、或非和异或逻辑关系可用与非门、或非门和异或门实现。在计算机电路中经常用到这些门电路。

例1.1.5 用逻辑电路实现命题公式 。

解 可以用图1.1.2所示的逻辑电路实现命题公式 。

◀

逻辑联结词广泛应用于信息检索中，例如，大部分网络搜索引擎支持布尔检索技术。在布尔检索中，联结词AND用于匹配同时包含两个检索项的记录，联结词OR用于匹配至少包含一个检索项的记录，而联结词NOT用于排除某个特定的检索项。采用布尔检索时，细心安排逻辑联结词的使用有助于有效找到特定主题的网页和信息。

使用逻辑运算符可以把自然语言表示的命题翻译成由命题变元和逻辑联结词组成的表达式，例如，在说明计算机硬件系统和软件系统时，将自然语言翻译成逻辑表达式是很重要的部分。对于一些逻辑难题，可以用逻辑表达式表示，然后推理求解。

例1.1.6 将下面的系统规范说明翻译成逻辑表达式，并确定这些系统规范说明是否一致。

“当且仅当系统正常操作时，系统处于多用户状态。”

“如果系统正常操作，则它的核心程序正在运行。”

“核心程序没有正常运行，或者系统处于中断模式。”

“系统不处于中断模式。”

解 令 p 表示“系统正常操作”， q 表示“系统处于多用户状态”， r 表示“核心程序正在运行”， s 表示“系统处于中断模式”，则上述规范说明可以表示为

系统和软件工程师从自然语言中提取需求，生成精确、无歧义性的规范说明，这些规范说明可作为软件开发的基础。系统规范说明应该是一致的，不应该包含有冲突的需求。当规范说明不一致时，无法开发出满足所有规范说明的系统。

若 为真，则 s 需为假。当 s 为假时， 为真则 r 必须为假，这时 p 必须为假，才能使 p → r 为真。当 p 为假时， q 必须为假，才有 p ↔ q 为真。因此，当 s 、 r 、 p 、 q 都为假时，上述规范说明的逻辑表达式的真值都为真，这4个规范说明是一致的。

如果在上述规范说明中增加“如果系统不处于多用户状态，它就处于中断状态”，表示为逻辑表达式 。当 q 和 s 都为假时， 为假。因此，这5个规范说明就是不一致的。

例1.1.7 三个客人坐在餐馆，服务生问：“每个人都要咖啡吗？”第一位客人回答：“我不知道。”接着第二位客人也回答：“我不知道。”最后，第三位客人回答：“不是每个人都要咖啡。”一会儿，服务生回来，将咖啡递给需要的客人。请问服务生是如何判断哪位客人需要咖啡的？

解 根据三位客人的回答，服务生给第一位客人和第二位客人送来咖啡。

设 p 、 q 、 r 分别表示第一、二、三位客人要咖啡。如果每个人都要咖啡，则 p ∧ q ∧ r 为真。如果第一位客人不要咖啡，则 p 为假，这时 p ∧ q ∧ r 为假，可以说“不是每个人都要咖啡”。第一个客人的回答是“我不知道”，服务生可以判断 p 不为假。根据第二个人的回答可以判断 q 为真，因为 q 为假时，第二个客人就知道“不是每个人都要咖啡”。第三位客人的回答说明 r 为假，因为这时已知 p 和 q 都为真，只有 r 为假， p ∧ q ∧ r 才为假，也就是“不是每个人都要咖啡”。因此，服务员可以断定第一位和第二位客人要咖啡，第三位客人不要咖啡。

◀ iq4gY8//MvqcTqJ5GlLy9eZfk6NEuc5i6EqVfADD6xvB/87jDFV9Jz3fregkqz8z