离散数学自学笔记联结词
时间：
未知2
公共课
1.1.2 联结词 今后“联结词”一词均指逻辑联结词及其符号表示。重要的联结词有5个，它们已在例1.2中出现。
否定词（negation）“并非”（not），用符号┐表示。设p表示一命题，那么┐p表示命题p的否定。p真时┐p假，而p假时┐p真。┐p读作“并非p”或“非p”。今后我们用1表示真值“真”，用0表示真值“假”，用类似表1.1的所谓真值表来规定联结值的意义，描述复合命题的真值状况。表1.1规定了否定词┐的意义，表示┐p的真值状况。
表1.1
例1.3 如果p表示命题“雪是白的”，那么“并非雪是白的”、“雪不是白的”应表示为┐p，此时┐p为假，因为p为真。
当用否定词“并非”代替自然语言中的“不”时（或者反过来），应注意保持原语句的意义。例如p 表示“我们都是好学生”时，┐p表示“并非我们都是好学生”或“我们不都是好学生”，而不是“我们都不是好学生”。
合取词（conjunction）“并且”（and），用符号∧表示。设p，q表示两命题，那么p∧q表示合取p和q所得的命题，即p和q同时为真时p∧q真，否则p∧q为假。p∧q读作“p并且q”或“p且q”。
合取词∧的意义和命题p∧q的真值状况可由表1.2来刻划。
表1.2
例1.4 如果p表示命题“你去了学校”q表示命题“我去了工厂”，那么p∧q表示命题“你去了学校并且我去了工厂”。p∧q为真，当且仅当你、我分别去了学校和工厂。
析取词（disjunction）“或”（or）用符号∨表示。设p，q表示两命题，那么p∨q表示p和q的析取，即当p和q有一为真时，p∨q为真，只有当p和q均假时p∨q为假。p∨q读作“p或者q”、“p或q”。
析取词∨的意义及复合命题p∨q的真值状况由表1.3描述。
表1.3
例1.5 如果p，q分别表示“今晚我看书”和“今晚我去看电影”，那么p∨q表示“今晚我看书或者去看电影”。当我于当晚看了书，或者看了电影，或者既看了书又看了电影时，p∨q为真，只是在我既不看书也不看电影时p∨q为假。
值得注意的是，这里的“或”是所谓可兼的，即当p和q均真时，确认p∨q为真。在日常生活中，“或”在有的场合下不同于上述意义。例如“人固有一死，或重于泰山，或轻于鸿毛”。其中的“或”是不可兼的，即当发现有人的死既重于泰山又轻于鸿毛时，上述论断被认为假。看来这里的“或”用∨表示不合适，可用表1.4规定的新联结词“不可兼或” 表示之。但是，像上述场合一样的许多场合下，两个析取命题事实上不可能同时为真，即表1.4的末行根本无需定义，这时用∨代替 就没有问题，并且能使语句的表示简化。例如“a>0或a=0或a<0”可表示为“a>0∨a=0∨a<0”，而不必多此一举地表示为“a>0 a=0 a<0”。
表1.4
蕴涵词（implication）“如果……，那么……”（if…then…），用符号→表示。设p，q表示两命题，那么p→q表示命题“如果p，那么q”。当p真而q假时，命题p→q为假，否则均认为p→q为真。p→q中的p称为蕴涵前件，q称为蕴涵后件。p→q的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p的必要条件”，“q当p”，“p仅当q”等等。数学中还常把q→p，┐p→┐q，┐q→┐p分别叫做p→q的逆命题，否命题，逆否命题。
蕴涵词→的意义及复合命题p→q的真值状况规定见表1.5.
表1.5
例1.6 如果用p表示“天气好”，q表示“我去接你”，那么p→q表示命题“如果天气好，那么我去接你”。当天气好时，我去接了你，这时诺言p→q真；我没去接你，则诺言p→q假。当天气不好时，我无论去或不去接你均未食言，此时认定p→q为真是适当的。
上述规定的蕴涵词称为实质蕴涵（substantive implication），因为它不要求p→q中的p，q有什么关系，只要p，q为命题，p→q就有意义。例如“如果2+2=5，那么雪是黑的”，就是一个有意义的命题，且据定义其真值为“真”。蕴涵词的这种规定形式，在讨论数学问题和逻辑问题时是正确的、充分的，但在某些情况下显得有些不足，为此不少人对其它规定形式的蕴涵词有兴趣，对此本书不予介绍。
双向蕴涵词（two-way implication）“当且仅当”（if and only if），用符号？表示之。设p，q为两命题，那么p？q表示命题“p当且仅当q”，“p与q等价”，即当p与q同真值时p？q为真，否则为假。p？q读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。由于“当且仅当”“等价”常在其它地方使用，因而用第一种读法更好些。
双向蕴涵词的意义及p？q的真值状况由表1.6给出。
表1.6
例1.7 如果p表示命题“△ABC@△A'B'C'”，q表示命题“△ABC与△A'B'C'的三边对应相等”，那么p？q表示平面几何中的一个真命题，因为p真时q显然真，p假时q亦必然假，故p与q同真值。若q表示命题“△ABC与△A'B'C'的三内角对应相等”，那么p？q不再是恒真的了，因p假时q未必为假。
以上介绍的是五个最常用、最重要的联结词，自然语言中还有其它联结词，有的可以直接用它们中的一个来表示，例如“也”等同于“且”，“除非”等同于“当且仅当”；有的则可以用它们中的若干个来表示，例如“不可兼或”可用∨，∧与┐来表示。
否定词（negation）“并非”（not），用符号┐表示。设p表示一命题，那么┐p表示命题p的否定。p真时┐p假，而p假时┐p真。┐p读作“并非p”或“非p”。今后我们用1表示真值“真”，用0表示真值“假”，用类似表1.1的所谓真值表来规定联结值的意义，描述复合命题的真值状况。表1.1规定了否定词┐的意义，表示┐p的真值状况。
表1.1
| p | ┐p |
| 0 1 | 1 0 |
例1.3 如果p表示命题“雪是白的”，那么“并非雪是白的”、“雪不是白的”应表示为┐p，此时┐p为假，因为p为真。
当用否定词“并非”代替自然语言中的“不”时（或者反过来），应注意保持原语句的意义。例如p 表示“我们都是好学生”时，┐p表示“并非我们都是好学生”或“我们不都是好学生”，而不是“我们都不是好学生”。
合取词（conjunction）“并且”（and），用符号∧表示。设p，q表示两命题，那么p∧q表示合取p和q所得的命题，即p和q同时为真时p∧q真，否则p∧q为假。p∧q读作“p并且q”或“p且q”。
合取词∧的意义和命题p∧q的真值状况可由表1.2来刻划。
表1.2
| p | q | p∧q |
| 0 0 1 1 | 0 1 0 1 | 0 0 0 1 |
例1.4 如果p表示命题“你去了学校”q表示命题“我去了工厂”，那么p∧q表示命题“你去了学校并且我去了工厂”。p∧q为真，当且仅当你、我分别去了学校和工厂。
析取词（disjunction）“或”（or）用符号∨表示。设p，q表示两命题，那么p∨q表示p和q的析取，即当p和q有一为真时，p∨q为真，只有当p和q均假时p∨q为假。p∨q读作“p或者q”、“p或q”。
析取词∨的意义及复合命题p∨q的真值状况由表1.3描述。
表1.3
| p | q | p∨q |
| 0 0 1 1 | 0 1 0 1 | 0 1 1 1 |
例1.5 如果p，q分别表示“今晚我看书”和“今晚我去看电影”，那么p∨q表示“今晚我看书或者去看电影”。当我于当晚看了书，或者看了电影，或者既看了书又看了电影时，p∨q为真，只是在我既不看书也不看电影时p∨q为假。
值得注意的是，这里的“或”是所谓可兼的，即当p和q均真时，确认p∨q为真。在日常生活中，“或”在有的场合下不同于上述意义。例如“人固有一死，或重于泰山，或轻于鸿毛”。其中的“或”是不可兼的，即当发现有人的死既重于泰山又轻于鸿毛时，上述论断被认为假。看来这里的“或”用∨表示不合适，可用表1.4规定的新联结词“不可兼或” 表示之。但是，像上述场合一样的许多场合下，两个析取命题事实上不可能同时为真，即表1.4的末行根本无需定义，这时用∨代替 就没有问题，并且能使语句的表示简化。例如“a>0或a=0或a<0”可表示为“a>0∨a=0∨a<0”，而不必多此一举地表示为“a>0 a=0 a<0”。
表1.4
| p | q | p q |
| 0 0 1 1 | 0 1 0 1 | 0 1 1 0 |
蕴涵词（implication）“如果……，那么……”（if…then…），用符号→表示。设p，q表示两命题，那么p→q表示命题“如果p，那么q”。当p真而q假时，命题p→q为假，否则均认为p→q为真。p→q中的p称为蕴涵前件，q称为蕴涵后件。p→q的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p的必要条件”，“q当p”，“p仅当q”等等。数学中还常把q→p，┐p→┐q，┐q→┐p分别叫做p→q的逆命题，否命题，逆否命题。
蕴涵词→的意义及复合命题p→q的真值状况规定见表1.5.
表1.5
| p | q | p→q |
| 0 0 1 1 | 0 1 0 1 | 1 1 0 1 |
例1.6 如果用p表示“天气好”，q表示“我去接你”，那么p→q表示命题“如果天气好，那么我去接你”。当天气好时，我去接了你，这时诺言p→q真；我没去接你，则诺言p→q假。当天气不好时，我无论去或不去接你均未食言，此时认定p→q为真是适当的。
上述规定的蕴涵词称为实质蕴涵（substantive implication），因为它不要求p→q中的p，q有什么关系，只要p，q为命题，p→q就有意义。例如“如果2+2=5，那么雪是黑的”，就是一个有意义的命题，且据定义其真值为“真”。蕴涵词的这种规定形式，在讨论数学问题和逻辑问题时是正确的、充分的，但在某些情况下显得有些不足，为此不少人对其它规定形式的蕴涵词有兴趣，对此本书不予介绍。
双向蕴涵词（two-way implication）“当且仅当”（if and only if），用符号？表示之。设p，q为两命题，那么p？q表示命题“p当且仅当q”，“p与q等价”，即当p与q同真值时p？q为真，否则为假。p？q读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。由于“当且仅当”“等价”常在其它地方使用，因而用第一种读法更好些。
双向蕴涵词的意义及p？q的真值状况由表1.6给出。
表1.6
| p | q | p«q |
| 0 0 1 1 | 0 1 0 1 | 1 0 0 1 |
例1.7 如果p表示命题“△ABC@△A'B'C'”，q表示命题“△ABC与△A'B'C'的三边对应相等”，那么p？q表示平面几何中的一个真命题，因为p真时q显然真，p假时q亦必然假，故p与q同真值。若q表示命题“△ABC与△A'B'C'的三内角对应相等”，那么p？q不再是恒真的了，因p假时q未必为假。
以上介绍的是五个最常用、最重要的联结词，自然语言中还有其它联结词，有的可以直接用它们中的一个来表示，例如“也”等同于“且”，“除非”等同于“当且仅当”；有的则可以用它们中的若干个来表示，例如“不可兼或”可用∨，∧与┐来表示。