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才为假，也就是“不是每个人都要咖啡”。因此，服务员可以断定第一位和第二位客人要咖啡，第三位客人不要咖啡。

◀