这篇文章上次修改于 1123 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

离散数学

笔者按：本文为笔者本科课程所作课堂笔记。学知所限，或有谬误，万望不吝斧正。

另，本文中10.1一节用到mermaid代码，本页不能正常渲染。

参考书：《离散数学及其应用》（第三版）

离散量

离散量：从一种程度开始，只要经过有限多种程度的逐次更替就能变化到另一种程度。

一、集合论

1.1 什么是集合

集合：一组对象

集合是由指定范围内的满足给定条件的所有对象聚集在一起构成，每一个对象成为这个集合的元素。

ZFC公理化集合论：外延公理 + 空集存在公理 + 无序对公理 + 并集公理 + 幂集公理 + 无穷公理 + 替换公理 + 正则公理 + 选择公理

用带或不带下标的大写英文字母表示集合：

用带或不带下标的小写英文字母表示元素：

若是中元素，记作，否则记作。
表示方法

枚举法：或

叙述法： $是英文字母中的元音字母$ 或

文氏图：图解方法。一般使用平面上的方形或圆形表示一个集合，用平面上的一个点表示集合的元素。（即韦恩图。）
基数

集合A中的元素个数称为集合的基数，记作。

若一个集合的基数是有限的，则该集合称为有限集。

若一个集合的基数是无限的，则该集合称为无限集。

$则$ $则$

1.2 特殊集合和集合间关系

空集

不含任何元素的集合叫做空集，记作。

空集可以符号化为。

空集是绝对唯一的。
全集

针对一个具体范围，我们考虑的所有对象的集合叫做全集，记作或。

在文氏图中一般使用方形表示全集。

全集是相对唯一的。
集合的相等关系
- 元素的基本特性
  - 集合中的元素是无序的。
  - 集合中的元素是不同的。
- 外延性原理
  
  两个集合和相等，当且仅当它们的元素完全相同，记为，否则和不相等，记为。
子集和真子集

设是任意两个集合。
- 如果的每个元素都是中的元素，则称是的子集，也称作被包含或包含，记作，否则记作。
- 如果并且，则称是的真子集，也称作被真包含或真包含，记作，否则记作。
“”关系的数学语言描述是： $若则$ 。

由子集定义可有
证明集合相等

设为任意两个集合，则

$且$
元集的子集

对于任意元集合，它的元子集个数为个，所以不同的子集个数为。
幂集

设为任意集合，把的所有不同子集构成的集合叫做A的幂集，也叫集族或集合的集合，记作，即

1.3 集合的基本运算

并集

设是两个集合，则集合与的并集定义为

$或$
交集

设是两个集合，则集合与的交集定义为

$且$
补集

设是全集，则集合的补集定义为
差集

设是两个集合，则集合与的差集定义为

$且$
对称差集

设是两个集合，则集合与的对称差集定义为

$且或且$
并集和交集的扩展

设是任意个集合，则这个集合的并集是包含那些至少是这组集合中一个集合成员的元素的集合，即

$或或或$

设是任意个集合，则这个集合的交集是包含那些属于这组聚合中所有集合成员的元素的集合，即

$且且且$

1.4 集合的运算定律

集合运算的基本等式

设为全集，为任意集合。 $幂等律$

$交换律$

$结合律$

$同一律$

$零律$

$分配律$

$吸收律$

$矛盾律和排中律$

$双重否定律$

$德摩根律$

集合相等的证明

如需证明集合A和B相等，则证明两个集合的相互包含关系，即 $并且$

或者尝试反证：如果 $且$ ，以及对称的情况，得出矛盾；

或者尝试改变A的写法，使其包含给定条件，然后代入条件，得出B。

1.5 可数集合与不可数集合

：可数集合

：不可数集合

自然数集的定义

皮亚诺公理

是自然数；
每个自然数都有一个后继，这个后继也是一个自然数，记为；
两个自然数相等，当且仅当它们有相同的后继，即：，当且仅当；
没有任何自然数的后继是0；
（归纳公理）若是关于一个自然数的预测，如果：为真，且当为真，则有为真，则对任意自然数都成立。

冯·诺依曼的自然数定义

若，则

从而，这个集合序列的基数就可以来定义自然数：

如何比较集合的大小

对于无限集合，通过判断两个无限集合之间是否存在一一对应关系来判断大小。

等势：设为两个集合，若在之间存在一种一一对应的关系：则称与是等势的，记作。

若，则。反之不成立。

可数集合

凡与自然数集合等势的集合，称为可数集合，可数集合的基数记为。

不可数集合

开区间称为不可数集合。

凡与开区间等势的集合，称为不可数集合，不可数集合的基数记为。

第二章计数问题

2.1 加法原理和乘法原理

乘法原理：如果一些工作需要步完成，第步有种不同的选择，则完成这项工作所有可能的选择种数为 加法原理：假定均为集合，第个集合有个元素。如为两两不相交的集合，则可以从中选出的元素总数为即集合的元素数目。

2.2 排列与组合

排列：从含各不同元素的集合种有序选取的个元素叫做的一个-排列。不同的排列总数记为。如果，则称这个排列为S的一个全排列，简称为的排列。推论：个不同元素的排列共有种。

环形排列：含个不同元素的集合的环形-排列数是组合：从含有个不同元素的集合中无序选取的个元素叫做的一个 -组合，不同的组合总数记为。规定。

2.3 容斥原理和鸽笼原理

容斥原理：设和是任意有限集合，有设，和是任意有限集合，有 鸽笼原理：若有只鸽子住进个鸽笼，则（存在性）有一个鸽笼至少住进只鸽子。

第三章命题逻辑

3.1 什么是命题

命题是推理的前提和结论。命题是推理的基本单位。

命题：具有确切真值的陈述句。该命题可以取一个“值”，称为真值。真值只有“真”和“假”两种，分别用“T”（或“1”）和“F”（或“0”）表示。

一切没有判断内容的句子，如命令句（祈使句）、感叹句、疑问句、二义性的陈述句等都不能作为命题。

我们无法判断真假的句子和句子本身是否有真假是两回事。例如：“今天是晴天。”

命题带变量如，但却不对变量作任何限制，因为变量可以取甚至不是数，导致了二义性，因此不是命题。例如：“”不是命题。

原子命题（简单命题）：不能再分解为更为简单命题的命题。
复合命题：可以分解为更为简单命题的命题。

约定：通常用大写的、带或不带下标的英文字母表示命题。

3.2 命题联结词

否定联结词

设是任意一个命题，复合命题“非”或“的否定”称为的否定式，记作，“”为否定联结词。为真，当且仅当为假。

合取联结词

设、是任意两个命题，复合命题“并且”或“和”称为与的合取式，记作，“”为合取联结词。为真，当且仅当同为真。

虽然……但是……

析取联结词

设、是任意两个命题，复合命题“或”称为与的析取式，记作，“”为析取联结词。为真，当且仅当至少一个为真。

异或用单独的异或联结词或。

和不能同时为真，称为不可兼或。

蕴涵联结词

设、是任意两个命题，复合命题“如果，则”称为与的蕴涵式，记作，“”为蕴涵联结词。为假，当且仅当为真且为假。一般把蕴涵式中的称为该蕴涵式的前件，称为蕴涵式的后件。

如果，则
因为，所以
只要，就
，仅当
只有，才
除非，才
除非，否则

善意推定：当前件为假时，不管的真假，都为真。

逆否命题：

等价联结词

设、是任意两个命题，复合命题“，当且仅当”称为与的等价式，记作，“”为等价联结词（也称双条件联结词）。为假，当且仅当同真假。

3.3 命题符号化及其应用

命题联结词的真值表

命题联结词的优先级

否定 > 合取 > 析取 > 蕴涵 > 等价

同级的联结词从左到右；括号提升为最高优先级。

复合命题符号化

例：

：你陪伴我

：你代我叫车子

：我将出去

除非你陪伴我或代我叫车子，否则我将不出去。

或

命题联结词与开关电路

串联：

并联：

断开：

命题联结词与逻辑电路

与门：

或门：

非门：

命题联结词与网页检索

命题联结词与位运算

按位与
按位或
按位取反

3.4 命题公式和真值表

命题变元

一个特定的命题是一个常值命题，它要么具有值（或1），要么具有值（或0）。

一个任意的没有赋予具体内容的原子命题是一个变量命题，称为命题变量或命题变元。该命题变量无具体的真值，它的变域是集合（或）。

一个复合命题的原子命题是命题变元时，该复合命题是命题公式。

命题公式

命题演算的合式公式，又称命题公式，简称公式。

生成规则：

命题变元本身是一个公式；
如是公式，则也是公式；
如是公式，则也是公式；
仅由有限步使用1. 2. 3. 后所得到的包含命题变元、联结词和括号的符号串才是命题公式。

如果公式含有个命题变元，可记为。

原子命题变元是最简单的合式公式，称为原子合式公式，简称原子公式。

命题公式没有真值，只有对其命题变元进行真值指派后，命题公式的真值才能确定。

整个公式的最外层括号可以省略；公式中不影响运算次序的括号也可以省略。

命题公式常用二元树的方式来表达。

公式的解释

设是出现在公式G中的所有命题变元，指定一组真值，则这组真值称为的一个解释，常记为。

如果公式在解释下真，则称满足，此时是的成真赋值；

如果公式在解释下假，则称弄假于，此时是的成假赋值；

真值表

一般来说，若有个命题变元，则应有个不同的解释。

由公式G在其所有可能的解释下所取真值得到的表，称为真值表。

3.5 命题公式分类和等价

命题公式分类

公式称为永真公式（重言式），如果在它的所有解释之下都为真；

公式称为永假公式（矛盾式），如果在它的所有解释之下都为假；

公式称为可满足公式，如果它不是永假的。（因此，永真公式是一个可满足公式。）

是永真的，当且仅当是永假的。

是可满足的，当且仅当至少有一个解释，使在下为真。

若永真，则可满足；但反之不成立。

等价

设是两个命题公式，是出现在中所有的命题变元。如果对于的个解释，与的真值结果都相同，则称公式与是等价的，记作或。

对于任意两个公式G和H，的充分必要条件是是永真公式。

可判定性：能否给出一个可行方法，完成对任意公式的判定类问题。命题公式是可判定的。

3.6 命题等价公式及应用

命题等价公式

设为任意的命题公式。 $幂等律$

$交换律$

$结合律$

$同一律$

$零律$

$分配律$

$吸收律$

$矛盾律$

$排中律$

$双重否定律$

$德摩根律$

$蕴涵式$

$假言易位$

$等价式$

$等价否定等式$

$归谬论$

判断公式类型

开关电路化简

逻辑电路化简

3.7 范式

基本术语

文字：命题变元或命题变元的否定。例如：

简单析取式（子句）：有限个文字的析取。例如：；本身

简单合取式（短语）：有限个文字的合取。

析取范式：有限个短语（简单合取式）的析取式。例如：；；本身

合取范式：有限个子句（简单析取式）的合取式。

是一个文字、短语、子句、析取范式、合取范式；

是子句、合取范式、析取范式；

是子句、合取范式，但不是析取范式。

不是析取或合取范式，但去掉括号则是。

以框起的部分算作一个整体，不可拆分。

范式关注的是命题公式的当前书写形式。

单个的文字是子句、短语、析取范式、合取范式。

析取、合取范式只含有联结词集，且只能出现在命题变元前。

范式存在定理

定理任意公式都存在与其等价的析取范式和合取范式。

命题公式的范式表达并不唯一。

范式与真值

命题公式的析取范式可以指出公式何时为真；

命题公式的合取范式可以指出公式何时为假。

3.8 主范式

极小项和极大项

在含有个命题变元的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，并且出现的次序与一致，则称此短语或子句为关于的一个极小项或极大项。

极小项：短语。非记为0，记为1，记作或。

极大项：子句。非记为1，记为0，记作或。

性质

主析取范式和主合取范式

主析取范式：在给定的析取范式中，若每一个短语都是极小项，且按照编码从小到大的顺序排列，则称该范式为主析取范式。

主合取范式：在给定的析取范式中，若每一个子句都是极大项，且按照编码从小到大的顺序排列，则称该范式为主合取范式。

如果一个主析取范式不包含任何极小项，则称该主析取范式为“空”；

如果一个主合取范式不包含任何极大项，则称该主合取范式为“空”；

定理任何一个公式都有与之等价的主析取范式和主合取范式。

主范式求解定理

求出该公式所对应的析取范式和合取范式；
消去重复出现的命题变元，矛盾式或重言式；
若析取（合取）范式的某一个短语（子句）中缺少命题变元，则可用如下方式将补进去：

重复至所有短语或子句都是标准的极小项或极大项为止。
利用幂等律将重复的极小项和极大项合并，并利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。

真值表技术

考虑任意公式的主析取范式应该包含哪些极小项；

若某一种解释使得为真，则这个解释构成的极小项包含在其主析取范式中。将所有这样的极小项找到，它们的析取即为的主析取范式。

极大项反之。

主范式的应用

如果主析取范式包含所有的极小项，则该公式为永真公式；

如果主合取范式包含所有的极大项，则该公式为永假公式；

若两个公式具有相同的主析取范式或主合取范式，则两公式等价。

3.9 基本推理形式和蕴含公式

推理形式

推理：从一组前提合乎逻辑地推出结论的思维过程。

设和是公式。

称是的逻辑结果，当且仅当对任意解释，如果使得为真，则也会使为真。记为。

称为蕴含关系。此时称为有效的，否则称为无效的。

称为一组前提，有时用集合来表示，记为。

称为结论。此时也称是前提集合的逻辑结果，记为。

的优先级为。等价于。

推理的判定定理

定理公式是前提集合的逻辑结果，当且仅当永真。

推理定律——基本蕴含关系

设为任意的命题公式。 $简化规则$

$添加规则$

$合取引入规则$

$选言三段论$

$假言推理规则$

$否定后件式$

$假言三段论$

$二难推论$

3.10 自然演绎法推理

推理规则

前提引用规则（规则）：在推导的过程中，可随时引入前提集合中的任何一个前提

逻辑结果引用规则（规则）：在推导的过程中，可以随时引入公式，该公式是由其前的一个或多个公式推导出来的逻辑结果。

附加前提规则（规则）：如果能从给定的前提集合与公式推导出，则能从此前提集合推导出。

自然演绎法

从前提集合推出结论的一个演绎是构造命题公式的一个有限序列：，其中，或者是中的某个前提，或者是前面的某些的有效结论，并且就是，则称公式为该演绎的有效结论，或者称从前提能够演绎出结论来。

直接证明法

已知结论和条件，尝试倒推，“缺谁证谁”，即可写出证明。

例：前提，结论。证明。 $附加前提$

间接证明法

反证法
归谬法

要证明：，

根据判定定理：永真，

即，矛盾。

因此：。得证。

总可以不使用反证法而用规则代替。

也即，反证法是规则的一种变型。

反证法：，

根据规则：，

即，。

即：。

3.11 联结词的完备集〔扩展内容〕

联结词的扩充

联结词	复合命题	读法	真值
异或	不可兼或	异或	真值不同时为真
蕴涵否定	和的蕴涵否定	蕴涵否定	只有真假时为真
与非	和的与非	与非	只有均为真时才为假
或非	和的或非	或非	只有均为假时才为真


0	0	0	0	1	1
0	1	1	0	1	0
1	0	1	1	1	0
1	1	0	0	0	0

联结词的完备集

设是联结词集合，如果用中的联结词表示的等价公式，可以表示任何命题公式，则称是一个联结词完备集。

若是一个联结词完备集，而从中删除任何一个联结词而得到的新联结词集合，至少存在一个命题公式不能用中的联结词表示的等价公式表示出来，则称是一个极小完备的联结词集合。

第四章谓词逻辑

4.1 谓词的引入

谓词逻辑（一阶逻辑）：为了研究简单命题句子内部的逻辑关系，利用个体词、谓词和量词来描述简单命题，以对简单命题进行分解，并研究个体与总体的内在联系和数量关系。

个体词和谓词

命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和谓语两部分组成。

个体词：在原子命题中，可以独立存在的客体（句子中的主语、宾语等）。

谓词：用以刻画客体的性质或客体之间的关系。

个体词

个体常量：表示具体或特定的个体词。一般用带或不带下标的小写英文字母表示。
个体变量：表示抽象的或泛指的个体词。一般用带或不带下标的小写英文字母表示。
个体域（论域）：个体词的取值范围。常用表示。
全总个体域：宇宙间的所有个体域聚集在一起所构成的个体域。若无特别说明，均使用全总个体域。

谓词

设为非空的个体域，定义在（表示个个体都在个体域上取值）上取值于上的元函数，称为元命题函数或元谓词，记为。其中，个体变量。

谓词常量：表示具体性质或关系的谓词。
谓词变量：表示抽象的或泛指的性质或关系的谓词。

谓词均使用大写字母表示。

谓词中个体词的顺序不能随意变更。例，。

一元谓词用以描述某一个个体的某种特性，而元谓词则用以描述个个体之间的关系。

谓词包含了个体变量和谓词变量，本身不是命题。只有用谓词常量取代，用个体常量取代后，它才会成为命题。

一般将没有任何个体变量的谓词称为0元谓词，例如等。当为谓词常量时，0元谓词就成为了命题。此时，命题逻辑中的所有命题都可以表示为0元谓词。（即，0元谓词的谓词可以是常量或变量。当谓词是常量时，它同时也是命题。）

复合命题的谓词符号化

例：如果张三是一个三好学生，那么他的学习一定很好。

设：是一个三好学生，：学习成绩好，：张三

则该命题符号化为：

4.2 量词的引入

量词

全称量词：所有的、任意的、一切的、每一个……
存在量词：有些、至少有一个、某一些、存在……

其中的称为作用变量。一般将其量词加在其谓词之前，记为。此时，称为全称量词和存在量词的辖域。

更准确的表达

例：所有的老虎都要吃人。

不准确的符号化表达

：要吃人。

$老虎$

更准确的符号化表达

：是老虎，：要吃人。

例：有一些人登上过月球。

不准确的符号化表达

：登上过月球。

$人$

更准确的符号化表达

：是人，：登上过月球。

谓词逻辑符号化的两条规则

统一个体域为全总个体域，而对于每一个句子中个体变量的变化范围用一元特性谓词刻画之。这种特性谓词在加入到命题函数中时必须遵循如下规则：

对于全称量词，刻画其对应个体域的特性谓词作为蕴涵式之前件加入；
对于存在量词，刻画其对应个体域的特性谓词作为合取式之合取项加入。

量词相关的真值确定

当个体域是有限集合时，和的真值可用与之等价的命题公式来进行表示。

4.3 谓词符号化举例

谓词符号化

例：没有人登上过木星。

令：是人，：登上过木星。

或

例：在美国留学的学生未必都是亚洲人。

令：是亚洲人，：是在美国留学的学生。

或

二元谓词

例：天下乌鸦一般黑。

令：是乌鸦，：与一般黑。

或

假定个体域

例：每个实数都存在比它大的另外的实数。

令：是实数，：小于。

$

若假定个体域为所有实数，则命题符号化为

多句话

例：所有狮子都是凶猛的；有些狮子不喝咖啡；有些凶猛的动物不喝咖啡。

令：是狮子；：是凶猛的；：喝咖啡。

假定所有动物的集合为个体域。

例：所有的蜂鸟都五彩斑斓；没有大鸟以蜜为生；不以蜜为生的鸟都色彩单调；蜂鸟都是小鸟。

令：是蜂鸟；：是大鸟；：是以蜜为生的鸟；：五彩斑斓。

假定所有鸟的集合为个体域。

常量的使用

例：只要是需要室外活动的课，郝亮都喜欢；所有的公共体育课都的需要室外活动的课；篮球是一门公共体育课；郝亮喜欢篮球这门课。

令：的需要室外活动的课；：喜欢；：是一门公共体育课；：郝亮；：篮球。

4.4 谓词公式

符号

常量符号：指所属个体域中的某个元素，用带或不带下表的小写英文字母表示。
变量符号：指所属个体域中的任意元素，用带或不带下表的小写英文字母表示。
函数符号：元函数符号可以是所属个体域集合的任意一个函数，用带或不带下标的小写英文字母表示。
谓词符号：元函数符号可以是所属个体域集合的任意一个谓词，用带或不带下标的大写英文字母表示。

项

任意的常量符号或任意的变量符号是项；
若是元函数符号，是项，则是项；
仅由有限次使用以上两个规则产生的符号串才是项。

合式公式

若是元谓词，是项，则称为原子谓词公式，简称原子公式。

合式公式（公式）

原子公式是合式公式；
若是合式公式，则也是合式公式；
由有限次使用以上三个规则产生的表达式才是合式公式。

公式的最外层括号可省略。

量词后面的括号省略方式为：一个量词的辖域中仅出现一个原子公式，则此辖域的外层括号可省略，否则不能省略。

一个个体词只能受一个量词的约束，否则就是没有意义的。

4.5 自由变元和约束变元

自由变元和约束变元

给定一个合式公式，若变元出现在使用变元的量词的辖域之内，则称变元的出现为约束出现，此时的变元称为约束变元。若的出现不是约束出现，则称它为自由出现，此时的变元称为自由变元。

辖域

若量词后有括号，则括号内的子公式就是该量词的辖域；
若量词后有括号，则与量词邻接的子公式就是该量词的辖域。

变元改名规则

约束变元的改名规则
- 将量词中的变元以及该量词辖域中此变量之所有约束出现都用新的个体变元替换；
- 新的变元一定要有别于改名辖域中的所有其他变量。
自由变元的代入规则
- 将公式中出现该自由变元的每一处都用新的个体变元替换；
- 新的变元不允许在原公式中以任何约束形式出现。也可用个体常量代入。

闭式

设是任意一个公式。若中无自由出现的个体变元，则称为封闭的合式公式，简称闭式。

显然，闭式是一个命题。

4.6 谓词公式的解释和分类

公式的解释

谓词逻辑中公式的每一个解释由如下四部分组成：

非空的个体域集合；
中的每个常量符号，指定中的某个特定的元素；
中的每个元函数符号，指定到中的某个特定的函数；
中的每个元谓词符号，指定到中的某个特定的谓词；

规定：公式中无自由变元，或将自由变元看成是常量符号。

公式的分类

有效公式：公式在它所有的解释下都取值为真。

矛盾公式：公式在它所有的解释下都取值为假。

可满足公式：至少有一种解释使得公式取值为真。

公式的判定问题

谓词逻辑是不可判定的；

只含有一元谓词变项的公式是可判定的；

如下形式的公式：若中无量词和其他自由变元时，也是可判定的；

个体域有穷时的谓词公式是可判定的。

4.7 谓词公式的等价关系

等价

如果公式是有效公式，则公式称为等价的，记为。

设是命题演算中的命题公式，是出现在中的命题变元，当用任意的谓词公式分别代入后，得到的新谓词公式称为原公式的代入实例。

定理 永真公式的任意一个代入实例必为有效公式。

谓词演算中的基本等价公式

命题公式中的基本等价公式在谓词演算中依然成立。

假设是只含自由变元的公式，是不含的公式。则在全总个体域中有 $改名规则$

$量词转换律量词否定等价式$

下面四条公式~中的不能有。

$量词辖域的扩张与收缩律$

$量词分配律$

对不满足分配律；对不满足分配律。

对于多个量词的公式，设是含有自由变元的谓词公式，则有

4.8 前束范式〔扩展内容〕

前束范式

称公式是一个前束范式，如果中的一切量词都位于该公式的最前端（不含否定词）且这些量词的辖域都延伸至公式的末端。

其标准形式如下：其中为量词或，称作公式的母式（基式），中不再有量词。

前束范式的求解步骤

消去公式中的联结词（如果有的话）；
反复运用量词转换律、德摩根律和双重否定律，直到将所有的都内移到原子谓词公式的前端；
使用谓词的等价公式将所有量词提到公式的最前端并保证其辖域直到公式的末端。

4.9 推理形式和推理规则

推理形式

设是公式，称是的逻辑结果（或称共同蕴涵），当且仅当对任意解释，若同时满足，则满足，记为，此时称是有效的，否则称为无效的。称为一组前提，有时用集合来表示，记，称为结论，又称是前提集合的逻辑结果，记为。

定理设是公式，公式是前提集合的逻辑结果，当且仅当为有效公式。

推理规律

命题演算中的基本蕴涵公式~在谓词演算中仍然成立。

假设是只含自由变元的公式，则有全总个体域中，有

对于多个量词的公式，设是含有自由变元的谓词公式，则有

全称特指规则US

，不在中约束出现。

或：，为任意个体常量。

存在特指规则ES

，为使得为真的特定的个体常量。

当中还有除之外的自由变元（例如），则必须用关于这些变元的函数符号（例如）来取代。

全称推广规则UG

，中无变元。

存在推广规则EG

，为特定个体常量。

或：，中无变元。

4.10 综合推理方法

谓词的演绎推理

假定推导过程都是在相同的个体域内进行的（通常是全总个体域）。

综合推理方法

推导过程中可以引用命题演算中的规则P和规则T；
如果结论是以条件形式或析取形式给出，则可使用规则CP；
若需消去量词，可以引用规则US和规则ES；
当所求结论需定量时，可引用规则UG和规则EG引入量词；
证明时可采用如命题演算中的直接证明方法和间接证明方法；
在推导过程中，对消去量词的公式或公式中不含量词的子公式，可以引用命题演算中的基本等价公式和基本蕴涵公式；
在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。

例：证明

难点：

在推导过程中，如既要使用规则US又要使用规则ES消去量词，而且选用的个体是同一个符号，则必须先使用规则ES，再使用规则US。然后再使用命题演算中的推理规则，最后使用规则UG或规则EG引入量词，得到所求结论。
如一个变量是用规则ES消去量词，对该变量在添加量词时，则只能使用规则EG；如使用规则US消去量词，对该变量在添加量词时，则可使用规则EG和规则UG。
在用规则US和规则ES消去量词时，此量词必须位于整个公式的最前端，且辖域为其后的整个公式。
在添加量词和时，所选用的不能在公式或中出现。

例：反证法

证明 $附加前提$

如有两个含有存在量词的公式，当用规则ES消去量词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。

第五章证明技术

5.2 证明定理的方法

在定理证明中，如果将证明中的已知看成是命题逻辑中的前提，将证明的结果看成是命题逻辑中的结论，则大多数定理都是一个蕴涵关系。

要证明逻辑关系，只需证明蕴涵式为永真公式。

基本证明技术

直接证明

间接证明

因为等价于。

几种典型的证明技术

空证明：

平凡证明：

归谬法证明：反证法

分情形证明：

为了证明形如的蕴含式，可以用重言式来作为推理规则。这个推理规则说明，可以通过对分别证明每个蕴含式来证明由命题的析取式组成前件的原来的蕴含式。这种论证称为分情形证明。

等价性证明：

为了证明一个定理是双条件的，即形如的命题，其中和都是命题，可以使用重言式：即，如果证明了蕴含式“若则”和“若则”，那么就可以证明命题“，当且仅当”。

存在性证明

构造性证明

惟一性证明

5.3 数学归纳法

数学归纳法原理

假设要证明的命题能写成形式： $有$ 其中是某个固定的整数。

即：希望证明对所有的整数都有为真。

假设

归纳基础：验证，有为真；
归纳假设：假设对于，有为真；
归纳结论：证明，有为真。

结论对所有的整数，都有为真。

强形式数学归纳法原理

假设

归纳基础：验证，有为真；
归纳假设：假设对于，有为真；
归纳结论：证明，有为真。

结论对所有的整数，都有为真。

第六章二元关系

6.1 序偶和笛卡尔积

有序组的定义

由两个元素按照一定的次序组成的二元组称为序偶，记作。其中是第一元素，是第二元素。

两个序偶，当且仅当且。

笛卡儿积

设是两个集合，称集合为集合与的笛卡儿积。

性质

设是任意两个集合，则不一定有，即笛卡儿积不满足交换律；
，当且仅当或者；
设是任意三个集合，则不一定有，即笛卡儿积不满足结合律；
当集合都是有限集时，；
笛卡儿积对并运算和交运算满足分配律。

推广

由个元素按照一定次序组成的元组称为重有序组，记作，其中是第一个元素，是第二个元素，……，是第个元素。

设是个集合，称集合为集合的笛卡儿积。当时，可记。

性质

两个重有序组，当且仅当；
当集合都是有限集时，。

6.2 关系的定义

二元关系

设为两个非空集合，称的任意子集为从到的一个二元关系，简称关系。

其中，称为关系的前域，称为关系的后域。如果，则称为上的一个二元关系。

数学符号

若序偶，通常把这一事实记为，读作“对有关系”；
若序偶，通常把这一事实记为，读作“对没有关系”。

几种重要关系

当时，称为从到的空关系；
当时，称为从到的全关系；上的全关系通常记为。
当时，称为上的恒等关系。

有限集合的二元关系数量

当集合都是有限集时，共有个不同的元素，这些元素将会产生个不同的子集。即，从到的不同关系共有个。

定义域和值域

设是从到的二元关系，则为关系的前域，为关系的后域。令。

称为的定义域，记为；

为的值域，记为；

为的域。

二元关系概念的推广

设为个非空集合，称的任意子集为中的一个元关系。

在元关系中，最常用的是二元关系，因而，在不引起混淆的情况下，提到的关系均指二元关系。

6.3 关系的表示

关系的集合表示

关系是一种特殊的集合，因此集合的两种基本表示法（枚举法和叙述法），可以用到关系的表示中。

关系的图形表示

设，是从到的一个关系。

集合中的元素和分别作为图中的结点，用“”表示；
如果，则从到可用一有向边相连。

如果，则从到可用一带箭头的小圆圈表示，即画一个自环。

关系的矩阵表示

设，是从到的一个二元关系，称矩阵为关系的关系矩阵，其中又称为的邻接矩阵。

例：上面选课关系的邻接矩阵

布尔矩阵的并和交运算

如果和是两个矩阵，则和的并也是一个矩阵，记为。其中：

如果和是两个矩阵，则和的交也是一个矩阵，记为。其中：

布尔矩阵的积运算

如果是矩阵，是矩阵，则和的积是一个矩阵，记为。其中：

6.4 关系的运算

关系的并交差补运算

关系是一种特殊的集合，因此集合的所有基本运算（并、交、差、补），都可以应用到关系中，并且同样满足集合的所有运算定律。

设是从到的两个关系，则 $（即全集为）$

关系的复合运算

设是三个集合，是从到的关系，是从到的关系（即），则与的复合关系（合成关系）是从到的关系，并且：。运算“”称为复合运算。

用三种关系表示法进行复合运算

集合表示法：寻找所有满足且，从而得到；
关系图表示法：将关系的关系图画在一起，然后寻找所有首尾相接的两条有向边，再去掉中间相接的结点，可得到的关系图；
关系矩阵表示法：将关系和的关系矩阵做布尔积运算，即得的关系矩阵。

关系的逆运算

设是两个集合，是到的关系，则从到的关系称为的逆关系，运算""称为逆运算。

用三种关系表示法求逆

集合表示法
关系图表示法：将的关系图中有向边的方向改变成相反方向即得的关系图，反之亦然；
关系矩阵表示法：将关系的关系矩阵转置即得的关系矩阵，即和的关系矩阵互为转置矩阵；
的定义域和值域正好是的值域和定义域，即；
。

6.5 关系的运算定律

结合律与同一律

设是任意四个集合，分别是从到、到、到的二元关系，分别是上的恒等关系，则 二元关系相等的证明方法

目标：证明两个关系相等。

也即证明两个集合相等。从而，

分配律

设是任意四个集合，是从到的关系，是从到的关系，是从到的关系，则分配律==反之不成立==。

逆运算性质定律

设是三个集合，分别是从到、从到的关系，则

$分配性$

$可换性$

$单调性$

6.6 关系的幂运算

关系的幂运算

设是集合上的关系，则的次幂记为，定义如下：

;
；
。

仍然是上的关系，表示多次自我复合的结果；

；

。

幂运算的性质

的基数并非随着的增加而增加，而是呈递减趋势。

当时，则。

定理设是有限集合，且，是上的关系，则

6.7 关系的性质（一）

自反性与反自反性

设是集合上的关系。

如果对任意的，都有，那么称在上是自反的，或称具有自反性；
如果对任意的，都有，那么称在上是反自反的，或称具有反自反性。

存在既不是自反的也不是反自反的关系；

关系是自反的，当且仅当的关系图中每个结点都有自环；关系是反自反的，当且仅当的关系图中每个结点都无自环；

关系是自反的，当且仅当的关系矩阵的主对角线上全为1；关系是反自反的，当且仅当的关系矩阵的主对角线上全为0。

对称性与反对称性

设是集合上的关系。

如果对任意的，如果，那么，则称是对称的，或称具有对称性；
如果对任意的，如果且，那么，则称是反对称的，或称具有反对称性。

存在既不是对称的也不是反对称的关系，也存在既是对称又是反对称的关系；

既是对称的，又是反对称的。

因为，反对称要求在时没有对称关系；在时，没有要求。

关系是对称的，当且仅当的关系图中，任何一对结点之间，要么有方向相反的两条边，要么无边；关系是反对称的，当且仅当的关系图中，任何一对结点之间至多只有一条边；

关系是对称的，当且仅当的关系矩阵为对称矩阵；关系是反对称的，当且仅当的关系矩阵满足时，或。

传递性

设是集合上的关系。对任意的，如果且，那么，则称是传递的，或称具有传递性。

一个特殊例子：是传递的。

关系是传递的，当且仅当在的关系图中，任何三个不同结点之间，若从到有一条边存在，从到有一条边存在，则从到一定有一条边存在；

关系是传递的，当且仅当在的关系矩阵中，对任意，若且，必有。

6.8 关系的性质（二）

关系性质的判定定理

设是集合上的关系，则

是自反的；
是反自反的；
是对称的；
是反对称的；
是传递的。

关系性质判定

	自反性	反自反性	对称性	反对称性	传递性
定义	，有	，有	，若，则	，若且，则	，若且，则
关系运算
关系图	每个结点都有环	每个结点都无环	任两结点间，要么没有边，要么有方向相反的两条边	任两结点间，至多有一条边	如果从到有边，从到有边，则从到一定有边
关系矩阵	主对角线上全为1	主对角线上全为0	对称矩阵	或	，若且，必有

一个关系可能满足多种性质，如：

非空集合上的全关系：自反，对称，传递

非空集合上的空关系：反自反，对称，反对称，传递

非空集合上的恒等关系：自反，对称，反对称，传递

实数集上的等于关系：自反，对称，反对称，传递

幂集上的真包含关系：反自反，反对称，传递

关系性质的保守性

设是集合上的关系，则

若是自反的，则也是自反的；（不是自反的）
若是反自反的，则也是反自反的；（不是反自反的）
若是对称的，则也是对称的；（不是反自反的）
若是反对称的，则也是反对称的；（不是反自反的）
若是传递的，则也是传递的。（不是传递的）


自反	√	√	√		√
反自反	√	√	√	√
对称	√	√	√	√
反对称	√	√		√
传递	√	√

第七章特殊关系

7.1 等价关系

等价关系定义

设是非空集合上的关系。如果是自反的、对称的、传递的，则称为上的等价关系。

等价关系的关系图类似下图：

即，等价关系是多个“小集合”的全关系组合而成。

要证明一个等价关系，就要证明该关系是自反的、对称的、传递的。

等价类

设是非空集合上的等价关系，对任意，称集合为关于的等价类，或叫做由生成的一个等价类，其中称为的生成元（代表元或典型元）。

定理设是非空集合上的等价关系，则

对任意；
对任意，如果，则有，否则；
。

商集

设是非空集合上的等价关系，由确定的一切等价类的集合，称为集合上关于的商集，记为，即。

计算商集的通用过程

任选中一个元素，计算；
如果，任选一个元素，计算；
如果，任选一个元素，计算；
以此类推，直到中所有元素都包含在计算出的等价类中。

7.2 集合的划分

定义

给定一个非空集合，设有集合。如果满足：

则集合称作集合的一个划分，而叫做这个划分的块或类。

等价划分

定理设是非空集合上的等价关系，则对的商集是的一个划分，称为由所导出的等价划分。

等价关系导出

定理给定集合的一个划分，则由该划分确定的关系是上的等价关系。称该关系为由划分所导出的等价关系。

7.3 偏序关系定义

定义

设是非空集合上的关系，如果是自反的、反对称的、传递的，则称为上的偏序关系，记为，读作小于等于，并将记为。序偶称为偏序集。

不是经典的“小于等于”。

当且时，可写作。

可写作；可写作。

可比与覆盖

设是非空集合上的偏序关系，，若：

或，则称与可比；
且不存在使得，则称覆盖。

例：对于整除关系，有4和6覆盖2：

2可以整除4，2可以整除6，但4不可以整除6。即，对于6，。

7.4 哈斯图及特殊元素

哈斯图

设是非空集合上的偏序关系，使用如下方法对的关系图进行简化：

取消每个结点的自环；
取消所有由于传递性出现的边。即若，则去掉这条边；
重新排列每条边，使得边的箭头方向全部向上，然后去掉这些箭头。

以上步骤可以得到一个包含足够偏序信息的图，这个图称为偏序关系的哈斯图。

设，是上的整除关系。

特殊元素

最大元和最小元

设是偏序集，是的任何一个子集。若存在元素，使得

对任意，都有，则称为的最大元；
对任意，都有，则称为的最小元。

如果不可比，则不存在最大元、最小元。

极大元和极小元

设是偏序集，是的任何一个子集。若存在元素，使得

对任意，都有，则称为的极大元；
对任意，都有，则称为的极小元。

如果不可比，则都是极大元、极小元。

总结

的最大元、最小元、极大元和极小元如果存在，一定在中；
是的最大元中所有的元素都比小；

是的最小元中所有的元素都比大；

是的极大元中没有比大的元素；

是的极小元中没有比小的元素；

上界和上确界

设是偏序集，是的任何一个子集。若存在元素，使得

对任意，都有，则称为的上界；
若元素是的上界，元素是的任何一个上界，若均有，则称为的最小上界或上确界。

下界和下确界

设是偏序集，是的任何一个子集。若存在元素，使得

对任意，都有，则称为的下界；
若元素是的上界，元素是的任何一个上界，若均有，则称为的最大下界或下确界。

总结

子集的上、下界和上、下确界可在集合中寻找；
子集的上、下界不一定存在，如果存在可能多个；
子集的上、下确界不一定存在，如果存在一定唯一；
若子集有上（下）确界，则一定有上（下）界。反之不然。

因为上（下）界中的元素不一定都可比。

总结

若是的最大元，则是的极大元、上界之一、上确界；
若是的最小元，则是的极小元、下界之一、下确界；
若是的上确界，且，则是的最大元；
若是的下确界，且，则是的最小元；
集合的最大（小）元，上（下）确界若存在，则唯一；
集合若无最大（小）元，必然存在多个极大（小）元。

7.5 其它次序关系

拟序关系

设是非空集合上的关系，如果是反自反的和传递的，则称为上的拟序关系，记为，读作小于，并将记为。序偶称为拟序集。

定理设是集合上的拟序关系，则是反对称的。

若是集合上的偏序关系，则是上的拟序关系；

若是集合上的拟序关系，则是上的偏序关系。

全序关系

设是一个偏序关系，若对任意，与都是可比的，则称关系为全序关系或线序关系。称为全序集，或线序集，或链。

全序关系的哈斯图将集合中的元素排成一条线，像一条链子，这充分体现了全序集可以称作线序集或链的原因。

良序关系

设是全序集，若的任何一个非空子集都有最小元素，则称为良序关系，此时称为良序集。

良序关系一定是全序关系，而有限全序集一定是良序集。

总结

偏序关系、全序关系和良序关系之间的关系如下图：

第八章函数

8.1 函数基本定义

定义

设是集合到的关系，如果对每个，都存在唯一的，使得，则称关系为到的函数或映射，记为。为函数的定义域，记为；为函数的值域，记为。

当时，通常记为。这时称为函数的自变量（原像），为在下的函数值（像）。注意区分和，二者是不同的。

如果关系具备下列两种情况之一，那么就不是函数：

存在元素，在中没有像；
存在元素，有两个及两个以上的像。

所有从到的一切函数构成的集合记为：

函数的数量

设函数，对中的每个元素而言，其序偶的第二元素都有种可能的选择，因而总共有种选法，也就是有个不同的函数。

关系与函数的差别

当和都是有限集合时，函数和一般关系具有如下差别：

关系和函数的数量不同：从到的不同关系有个，从到的不同函数却仅有个；
关系和函数的基数不同：每一个关系的基数可以从零一直到，每一个函数的基数都为个；
关系和函数的第一元素存在差别：关系的第一个元素可以相同，函数的第一元素一定是互不相同的。

8.2 函数的类型

函数的类型

设是从集合到的函数。

对任意，如果，都有，则称为从到的单射；
如果，则称为从到的满射；
如果既是单射又是满射，则称为从到的双射。

必要条件

若是从有限集到有限集的函数，则有

是单射的必要条件为；
是满射的必要条件为；
是双射的必要条件为。

函数类型的数学化描述

是单射，当且仅当对，若，则；

是满射，当且仅当对，一定存在，使得；

是双射，当且仅当满足以上两点。

典型（自然）映射

设是集合上的一个等价关系，称为对商集的典型（自然）映射，其定义为。它是一个满射。

函数类型证明

根据数学化描述证明。

证明单射可以考虑反证。例如：对任意，假设。

证明满射可以考虑包含关系。例如：有，证明。

8.3 函数的运算

函数的复合

设是两个函数，则与的复合关系 $使得且$ 是从到的函数，称为函数与的复合函数，记为。

函数和可以复合的前提条件是；

；

对任意，有；

复合运算的保守性

设和分别是从到和从到的函数，则

设是满射，则也是从到的满射；
设是单射，则也是从到的单射；
设是双射，则也是从到的双射。

如是从到的满射，则是从到的满射；

如是从到的单射，则是从到的单射；

如是从到的双射，则是从到的单射，是从到的满射。

函数的逆

设是函数，如果是从到的函数，则称为函数的逆函数。

函数存在，当且仅当是双射，此时也是双射。

第九章图论基础

9.1 图的引入

不同类型的图

无序对和无序积

设为任意集合，称集合为与的无序积，称为无序对。

与序偶不同，对。

图的定义

一个图是一个序偶，记为，其中：

是有限非空集合，称为结点，称为结点集。
是有限集合，称为边集。中的每个元素都有中的结点对与之对应，称之为边。

与边对应的结点对既可以是无序的，也可以是有序的。

若边与无序结点对相对应，则称为无向边，记为，这时称是边的两个端点。

若边与有序结点对相对应，则称为有向边或弧，记为，这时称为的始点或弧尾，为的终点或弧头，统称为的端点。

9.2 图的表示

集合表示和图形表示

图的集合表示：对于一个图，如果将其记为，并写出和的集合表示，这称为图的集合表示。

图的图形表示：用小圆圈表示中的结点，用由指向的有向线段或曲线表示有向边，无向线段或曲线表示无向边。

邻接矩阵

设图，其中，并假定结点已经有了从到的次序，则阶方阵称为的邻接矩阵，其中 $或否则$ 。

邻接点与邻接边

在图中，若两个结点和是边的端点，则称与互为邻接点，否则与称为不邻接的；具有公共结点的两条边称为邻接边；两个端点相同的边称为环或自回路；图中不与任何结点相邻接的结点称为孤立结点。

一些简单的特殊图

零图：仅由孤立结点组成的图；
平凡图：仅含一个结点的零图；
图：含有个结点条边的图。

环的存在与否不会导致图论定理的重大变化，很多场合下都会被忽略；

零图没有任何边，邻接矩阵为全0；

图的各边如何分布，不说明则不清楚。

9.3 图的分类

按边有无方向分类

每条边都是无向边的图称为无向图；

每条边都是有向边的图称为有向图；

有些边是无向边，而另一些边是有向边的图称为混合图。

按有无平行边分类

在有向图中，两结点间（包括结点自身间）若有同始点和同终点的几条边，则这几条边称为平行边；

在无向图中，两结点间（包括结点自身间）若有几条边，则这几条边称为平行边。

两结点间相互平行的边的条数称为边或的重数。

含有平行边的图称为多重图；

非多重图称为线图；

无环的线图称为简单图。

按有无权值分类

赋权图是一个三重组或四重组，其中是结点集合，是边的集合，是从到非负实数集合的函数（即结点的权值函数），是从到非负实数集合的函数（即边的权值函数）。

相应的，边或结点均无权值的图称为无权图。

9.4 子图和补图

各类子图

设有图和图。

若，，则称是的子图，记为。
若，且（即或），则称是的真子图，记为。
若，则称是的生成子图。

生成子图：相对于原图，全部的结点都在。
设且，以为结点集，以两个端点均在中的边的全体为边集的的子图，称为导出的的子图，简称的导出子图。

导出子图：相对于原图，只要结点还在，其对应的全部的边都在。

完全图

设为一个具有个结点的无向简单图，如果中任意两个结点间都有边相连，则称为无向完全图，简称为完全图，记为。

设为一个具有个结点的有向简单图，如果中任意两个结点间都有两条方向相反的有向边相连，则称为有向完全图，在不发生误解的情况下，也记为。

完全图的邻接矩阵除主对角线上的元素为0外，其余元素均为1；
无向完全图的边数为；
有向完全图的边数为.

补图

设为简单图，为完全图，则称为的补图，记为。

补图就是从完全图中删除图中的边；
补图就是以为结点集，以所有能使成为完全图的添加边组成的集合为边集的图；
图和它的补图有相同的结点，两个结点在里相邻，当且仅当它们在里不相邻。

邻接矩阵求补图的方法

若设简单图的邻接矩阵，则它的补图的邻接矩阵为：

9.5 握手定理

结点的度数

图中以结点为端点的次数之和称为结点的度数或度，记为。显然，有环时则需计算两次。

有向图中以结点为始点的次数称为的出度，记为；以结点为终点的次数称为的入度，记为。显然，。

图中，称为的最大度，称为的最小度。

有向图中，称为的最大出度，称为的最小出度；为的最大入度，称为的最小入度。

设图，的邻接矩阵为

若是无向图，则结点的度数或；
若是有向图，则结点的出度，入度.

握手定理

定理图中结点度数的总和等于边数的二倍，即设图，则有推论图中度数为奇数的结点个数为偶数。

常称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。

定理有向图中各结点的出度之和等于各结点的入度之和，等于边数，即设有向图，则有

设为图的结点集，称为的度数序列。若为有向图，还可分别定义出度序列和入度序列。

9.6 图的同构

引言

即，两个图本质上是同一个图。

定义

设两个图和，如果存在双射函数，使得对于任意的（或者）当且仅当（或者），并且与的重数相同，则称与同构，记为。

形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，一个图可以变形为另一个图，那么这两个图是同构的。

必要条件

结点数目相同
边数相同
度数相同的结点数相同

可以通过同构的必要条件不满足说明两个图不同构。

但不能作为充分条件使用。即使满足这三个条件，也不一定是同构。

9.7 通路和回路

通路和回路

给定图中结点和边相继交错出现的序列

若中边的两端点是和（有向图时与分别是的始点和终点），，则称为结点到结点的通路。和分别称为此通路的始点和终点，统称为通路的端点。通路中边的数目称为此通路的长度。当时，此通路称为回路。
若通路中的所有边互不相同，则称此通路为简单通路，否则称为复杂通路；若回路中的所有边互不相同，则称此回路为简单回路，否则称为复杂回路。
若通路中的所有结点互不相同，所有边也互不相同，则称此通路为基本通路或者初级通路；若回路中除外的所有结点互不相同，所有边也互不相同，则称此回路为基本回路或者初级回路。

回路是通路的特殊情况。

在不会引起误解的情况下，一条通路可以用边的序列来表示；

在简单图中，一条通路也可以用结点的序列来表示。

通路数量

定理设为线图，，为的邻接矩阵，。则：

为从结点到结点长度为的通路数目；
为结点到自身的长度为的回路数目；
是中长度为的通路（含回路）总数；
是中长度为的回路总数。

就是对矩阵求次幂。

推论设矩阵，则：

表示结点到长度不大于的通路数目；
表示图中长度不大于的通路总数；
表示图中所有长度不大于的回路总数。

9.8 可达性和最短通路

可达性

在图中，。如果从到存在通路，则称到是可达的，否则称到不可达。

规定任何结点到自己都是可达的。

定理在一个具有个结点的图中，如果从结点到结点（）存在一条通路，则从到存在一条长度不大于的通路。

推论在一个具有个结点的图中，如果从结点到结点（）存在一条通路，则从到存在一条长度不大于的基本通路。

定理在一个具有个结点的图中，如果存在一条经过结点的回路，则从到存在一条长度不大于的回路。

推论在一个具有个结点的图中，如果存在一条经过结点的回路，则从到存在一条长度不大于的基本回路。

定理设为线图，，为的邻接矩阵，，，。则有当时，如果，那么从到可达，否则不可达。

设是一个线图，其中，并假定结点已经有了从到的次序，称阶方阵为图的可达性矩阵，其中 $当到可达否则$ 。

定理设为线图，、分别是的邻接矩阵和可达性矩阵，则有，这里，表示做矩阵布尔乘法的次幂。

最短通路

如果到可达，则称长度最短的通路为从到的短程线，从到的短程线的长度称为从到的距离，记为。如果到不可达，则通常记为。

定理设为线图，，为的邻接矩阵，，，则 $如果所有均为$

9.9 无向图的连通性

无向图的连通性

若无向图中的两个结点都是可达的，则称是连通图，否则称是非连通图或分离图。

无向完全图（）都是连通图；
多于一个结点的零图都是非连通图；
非平凡无向线图是连通图，当且仅当它的可达性矩阵的所有元素均为1。

定理无向图中结点之间的可达关系 $到可达$ ，则是上的等价关系。

无向图中结点之间的可达关系的每个等价类导出的子图都称为的一个连通分支。用表示中的连通分支个数。

点割集与边割集

图的删除操作

对于一个无向图，

表示从图中删除边，表示从图中删除边的集合中所有边；
表示从图中删除结点及其关联的所有边，表示从图中删除结点集合中所有结点以及这些结点关联的所有的边。

点割集

设无向图，若存在结点子集，使得，而对于任意的，均有，则称为的一个点割集。特别地，若点割集中只有一个结点，则称为割点。

边割集

设无向图，若存在边的子集，使得，而对于任意的，均有，则称为的一个边割集。特别地，若边割集中只有一条边，则称为割边。

连通度

设无向连通图，

称 $为的点割集或为平凡图$ 为的点连通度，若，则称为-连通图。
称 $为的边割集$ 为的边连通度，若，则称为边-连通图。

若是平凡图，则，，所以；

若是完全图，则无点割集。当删除个结点后成为平凡图，因而。显然，；

若中存在割点，则。若中存在割边，则。

若是非连通图，因为不用删除结点或边就已经不连通了，所以规定非连通图的点连通度和边连通度均为0。

9.10 有向图的连通性

有向图的连通性

由于有向图中边都有方向性，因此有向图结点之间的可达关系仅仅具有自反性和传递性，而不具有对称性。因此，有向图中的可达关系不是等价关系。

设是一个有向图，

略去中所有有向边的方向得到的无向图是连通图，则称有向图是连通图或称为弱连通图。否则称是非连通图；
若中任何一对结点之间至少有一个结点到另一个结点是可达的，则称是单向连通图；
若中任何一对结点之间都是相互可达的，则称是强连通图。

显然，强连通图必是单向连通图；单向连通图必是连通图。但反之均不成立。

判定

有向图是强连通图的充分必要条件是中存在一条经过所有结点至少一次的回路。

有向图是单向连通图的充分必要条件是中存在一条经过所有结点至少一次的通路。

邻接矩阵判定

由邻接矩阵，求出可达性矩阵，

有向线图是强连通图，当且仅当它的可达性矩阵的所有元素均为1；
有向线图是单向连通图，当且仅当它的可达性矩阵及其转置矩阵经过布尔加运算后所得的矩阵中除主对角元外其余元素均为1；
有向线图是弱连通图，当且仅当它的邻接矩阵及其转置矩阵经布尔加运算所得的矩阵作为邻接矩阵而求得的可达性矩阵中所有元素均为1.

连通分支

在有向图中，设是的子图，如果

是强连通的（单向连通的、弱连通的）；
对任意，若，则不是强连通的（单向连通的、弱连通的）；

那么称为的强连通分支（单向连通分支、弱连通分支），或称为强分图（单向分图、弱分图）。

弱连通分支也就是忽略边的方向所对应的无向图的连通分支；

注意把握强（单向、弱）连通分支的极大性特点，即，任意增加一个结点或一条边就不是强（单向、弱）连通的了。

判定

在有向图中，它的每一个结点位于且仅位于一个强（弱）连通分支中，至少位于一个单向连通分支中。

在有向图中，它的每一条边至多在一个强连通分支中；至少在一个单向连通分支中；在且仅在一个弱连通分支中。

弱连通分支：图的不互连部分

强连通分支：出度为0或入度为0的结点，极大回路，……

单向连通分支：极大通路

9.11 最短通路问题

设是一个简单无向赋权图，

该图中一条通路上所有边的权值之和，称为这条通路的长度；
两个结点间长度最短的通路，称为这两个结点间的最短通路。

单源点的最短通路——Dijkstra算法

基本思想

将结点集合分为两部分：一部分称为具有（永久性）标号的集合，另一部分称为具有（暂时性）标号的集合；
所谓结点的标号是指从到的最短通路的长度；而结点的标号是指从到的某条通路的长度；
首先将取为标号，其余结点为标号，然后逐步将具有标号的结点改为标号。

初始化：将源结点置为标号，，将所有置为标号，即，且
找最小：寻找具有最小值的标号的结点。若为，则将的标号改为标号，且。
修改：修改与相邻的结点的标号值。
重复2-3，直到所有结点都改为标号。

任意两点间的最短通路——Floyd算法

基本思想

设为图中的结点个数，从矩阵（即图的长度矩阵）开始，依次构造出个矩阵，其中表示从结点到而中间结点仅属于集合的所有通路中的最短通路长度；
若已知，则的元素为：；
的元素就是从结点到的最短通路长度。

两种算法的比较

Dijkstra算法求指定结点到其它结点间的最短通路，Floyd算法求出任意两点间的最短通路；
在求解多源最短路径问题上，二者的时间复杂度相当，都是；
二者均能处理无向赋权图和有向赋权图；
Dijkstra算法不能求解有负权边的图，而Floyd算法可以求解带负权边的图。

第十章树

10.1 认识树

树的模型

graph TD
1 --> 2 --> 4 --> 7
1 --> 3 --> 5
3 --> 6 --> 9
4 --> 8

树的应用

二元搜索树
决策树
前缀码（配合哈夫曼算法）

10.2 无向树

定义

连通而不含回路的无向图称为无向树，简称树，常用表示树。

树中度数为1的结点称为叶；度数大于1的结点称为分支点或内部结点。

每个连通分支都是树的无向图称为森林。

平凡图称为平凡树。

容易看出，树中没有环和平行边，因此一定是简单图，并且在任何非平凡树中，都无度数为0的结点。

一棵树也可以叫做森林。

树的性质（等价定义）

定理设无向图，，，下列各命题是等价的：

连通而不含回路（即是树）；
中无回路，且；
是连通的，且；
中无回路，但在任二结点之间增加一条新边，就得到唯一的一条基本回路；
是连通的，但删除任一条边后，便不连通；
中每一对结点之间有唯一一条基本通路。

特点

在结点给定的无向图中，

树是边数最多的无回路图；
树是边数最少的连通图。

由此可知，在无向图中，

若，则是不连通的；
若，则必含回路。

性质应用

定理任意非平凡树都至少有两片叶。

10.3 生成树

定义

给定图，

若的某个生成子图是树，则称之为的生成树，记为。生成树中的边称为树枝。
中不在中的边称为弦，的所有弦的集合称为生成树的补。

生成树存在的条件

定理一个图存在生成树的充分必要条件是是连通的。

算法

求连通图的生成树的算法：

破圈法

循环找到图中的回路并删除回路中的一条边，直到删除的边的总数为.
避圈法

循环选取中一条与已选取的边不构成回路的边，直到选取的边的总数为.

生成树的广度优先搜索算法

连通图，

任选，将标记为0，令；
如果，则结束，为所求的生成树中包含的所有边。否则令；
依次对中所有标记为的结点，如果它与中的结点相邻接，则将标记为，指定为的前驱，令，转步骤⒉。

10.4 最小生成树

定义

设是连通的赋权图，是一棵生成树，的每个树枝所赋权值之和称为的权，记为。具有最小权的生成树称为的最小生成树。

一个无向图的生成树不是唯一的，同样地，一个赋权图的最小生成树也不一定是唯一的。

Kruskal算法

其要点是，在与已选取的边不构成回路的边中选取最小者。

在中选取最小权边，置，；
当时，结束，否则转步骤⒊；
在中选取不在中的边，使中无回路且是满足此条件的最小权边；
置，，转步骤⒉。

Prim算法

其要点是，从任意结点开始，每次增加一条最小权边构成一棵新树。

在中任意选取一个结点，置；
在中选取与某个邻接的结点，使得边的权最小，置；
重复步骤⒉，直到。

10.5 根树

定义

一个有向图，若略去所有有向边的方向所得到的无向图是一棵树，则这个有向图称为有向树。

一棵非平凡的有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称之为根树或外向树，出度为0的结点称为叶；入度为1，出度大于0 的结点称为内点；又将内点和根统称为分支点。

在根树中，从根到任一结点的通路长度，称为该结点的层数；称层数相同的结点在同一层上；所有结点的层数中最大的称为根树的高。

习惯上使用倒置法来画根树，即把根画在最上方，叶画在下方，有向边的方向均指向下方，这样就可以省去全部的箭头，不会发生误解。

家族关系

在根树中，若从结点到可达，则称是的祖先，是的后代；又若是根树中的有向边，则称是的父亲，是的儿子；如果两个结点是同一个结点的儿子，则称这两个结点是兄弟。

元树

如果在根树中规定了每一层上结点的次序，这样的根树称为有序树。

在根树中，

若每个分支点至多有个儿子，则称为元树；
若每个分支点都恰有个儿子，则称为满元树；
若元树是有序的，则称为元有序树；
若满元树是有序的，则称为满元有序树；
任一结点及其所有后代导出的子图称为的以为根的子树。

二元有序树

二元有序树的每个结点至多有两个儿子，分别称为的左儿子和右儿子。二元有序树的每个结点至多有两棵子树，分别称为的左子树和右子树。

满元树的性质

定理在满元树中，若叶数为，分支点数为，则有

10.6 根树的遍历

二元树的遍历

二元树的先根次序遍历算法

访问根；
按先根次序遍历根的左子树；
按先根次序遍历根的右子树。

二元树的中根次序遍历算法

按先根次序遍历根的左子树；
访问根；
按先根次序遍历根的右子树。

二元树的后根次序遍历算法

按先根次序遍历根的左子树；
按先根次序遍历根的右子树；
访问根。

表达式的记法

可以用二叉树表示一些复杂的表达式，如复合命题，集合的组合，以及算术表达式。

例：有如下二叉树表示表达式

中缀形式：

对表达式的二叉树进行中根遍历时，就得到了它的中缀形式。需要加括号规定运算顺序以防止二义性。

前缀形式：

对表达式的二叉树进行先根遍历时，就得到了它的前缀形式。前缀形式的最大优点是无二义性，所以不再需要括号。

写成前缀形式的表达式称为波兰符号法。表达式的求值方式是从右向左。

后缀形式：

对表达式的二叉树进行后根遍历时，就得到了它的后缀形式。后缀形式同样无二义性，所以也不再需要括号。

写成后缀形式的表达式称为逆波兰符号法。表达式的求值方式是从左向右。

根树的遍历

根树的先根次序遍历算法

访问根；
按先根次序从左向右遍历根的各子树。

根树的后根次序遍历算法

按先根次序从左向右遍历根的各子树；
访问根。

10.7 最优树与哈夫曼算法〔扩展内容〕

前缀码

设为长度为的符号串，称其子串分别为的长度为的前缀。

设是一个符号串集合，若对任意，不是的前缀，也不是的前缀，则称为前缀码。若符号串中，只出现0和1两个符号，则称为二元前缀码。

用二元树产生二元前缀码

给定一棵二元树，假设它有片树叶。设是任意一个分支点，则至少有一个儿子，至多有两个儿子。若有两个儿子，则在由引出的两条边上，左边的标上0，右边的标上1；若只有一个儿子，在引出的边上可标0也可标1。设为的任意一片树叶，从树根到的通路上各边的标号组成的符号串放在处，片树叶处的个符号串组成的集合为一个二元前缀码。

最优树

设有一棵二元树，若对其所有的片叶赋以权值，则称之为赋权二元树；若权为的叶的层数为，则称为该赋权二元树的权；而在所有赋权的二元树中，最小的二元树称为最优树。

哈夫曼算法

初始：令；
从中取出两个最小的权和，画结点和，分别带权和。画和的父亲，令带权；
令；
判断是否只含一个元素？若是，则停止，否则转⒉。

第十一章特殊图

11.1 欧拉图

哥尼斯堡七桥问题

定义

设是无孤立结点的图，若存在一条通路（回路），经过图中每边一次且仅一次，则称此通路（回路）为该图的一条欧拉通路（回路）。具有欧拉回路的图称为欧拉图。

规定平凡图为欧拉图。

欧拉通路是经过图中所有边的通路中长度最短的通路。

欧拉回路是经过图中所有边的回路中长度最短的回路。

判定

无向图具有一条欧拉通路，当且仅当是连通的，且仅有零个或两个奇度数结点。

无向图具有一条欧拉回路，当且仅当是连通的，并且所有结点的度数均为偶数。

有向图具有一条欧拉通路，当且仅当是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。

有向图具有一条欧拉回路，当且仅当是连通的，且所有结点的入度等于出度。

一笔画

所谓一笔画是指笔不离纸、不重复地画出图形。能否一笔画本质上就是求图中是否存在欧拉通路（或欧拉回路）的问题。

求无向图的欧拉回路——Fleury算法

依次选边，每选一条边就从图中删去。选取条件是：

与上一条已选取的边关联；
除非无别的边可选，否则不能选割边（桥）。

中国邮路问题

一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局。那么，应该按怎样的路线走，他所走的路程才会最短？

解首先转化为图论问题：在一个无向赋权连通图中求一条回路，使其总权值最小。

如果此无向图为欧拉图，则使用Fleury算法直接求欧拉回路即可。

否则，有些边必须重复经过，相当于在原图中添加了一些平行边。从而，只要保证这些平行边的权值最小就行了。

定义（中国邮路问题）在一个有奇度数结点的赋权连通图中，增加一些平行边，使得新图不含奇度数结点，并且增加的边的总权值最小。

算法

设为图中所有奇度数结点的集合。

使用Floyd算法计算图中任意两点间的最短通路长度；
构成一个的矩阵，这个矩阵给出了图中每两个奇度数结点间的最短通路长度；
将矩阵中的结点进行两两组合，找出一个最佳的组合情况，这种组合使得它们的最短通路长度之和最小；
根据这个最佳组合，求出各对组合的最短通路，并将最短通路上的每条边都加一条平行边。

11.2 哈密顿图

周游世界问题

要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。

定义

设是一个无向或有向图，若存在一条通路（回路），经过图中每个结点一次且仅一次，则称此通路（回路）为该图的一条哈密顿通路（回路）。具有哈密顿回路的图称为哈密顿图。

规定平凡图为哈密顿图。

哈密顿通路是经过图中所有结点的通路中长度最短的通路。

哈密顿回路是经过图中所有结点的回路中长度最短的回路。

必要条件

定理设无向图是哈密顿图，是的任意非空子集，则，其中是从中删除后所得到图的连通分支数。

推论设无向图中存在哈密顿通路，则对的任意非空子集，都有.

此定理是哈密顿图的必要条件，而不是~~充分条件~~。

此定理的主要应用是判断某些图不是哈密顿图，即：若存在的某个非空子集使得，则不是哈密顿图。

有割点的图一定不是哈密顿图。

充分条件

定理设是具有个结点的简单无向图。如果对任意两个不相邻的结点，均有，则中存在哈密顿通路。

定理设是具有个结点的简单无向图。如果对任意两个不相邻的结点，均有，则中存在哈密顿回路。

推论设是具有个结点的简单无向图，。如果对任意，均有，则是哈密顿图。

定理及其推论给出的是哈密顿图的充分条件，而不是~~必要条件~~。

TSP问题

巡回售货员问题也称为货郎担问题。有一个售货员，从他所在城市出发去访问个城市，要求经过每个城市恰好一次，然后返回原地。如何安排他的旅行路线才能保证最短？

问题设是个结点的赋权完全图。这里是城市的集合，是连接城市的道路集合，是从到正实数集合的一个函数（即是城市到之间的距离）。他们之间的距离需满足如下的三角不等式：试求出该赋权图上的最短哈密顿回路。

解找出所有可能的哈密顿回路并计算每条回路的总权值，得到最短通路。

当增大时，计算时间不可接受。TSP是NP难问题。

11.3 偶图

偶图

若无向图的结点集能够划分为两个子集，满足，且，使得中任意一条边的两个端点，一个属于，另一个属于，则称为偶图或二分图或二部图。和称为互补结点子集，偶图通常记为。

完全偶图

在偶图中，若中的每个结点与中的每个结点都有且仅有一条边相关联，则称偶图为完全偶图或完全二分图，记为，其中.

偶图的判定

定理无向图为偶图的充分必要条件是所有回路的长度均为偶数。

根据偶图的充分必要条件，我们可将平凡图和零图看成特殊的偶图。

常用其逆否命题来判断一个图不是偶图：无向图不是偶图的充分必要条件是中存在长度为奇数的回路。

偶图的匹配

在偶图中，，若存在的子集，其中是中的个不同的结点，则称的子图为从到的一个完全匹配，简称匹配。

匹配实际上就是在偶图中，寻找到的单射。显然，这样的单射有时并不存在。

匹配的判定条件

定理（霍尔定理）偶图中存在从到的匹配的充分必要条件是中任意个结点至少与中的个结点相邻，。这个条件通常称为相异性条件。

定理（条件）设是一个偶图。如果满足：

中每个结点至少关联条边；
中每个结点至多关联条边；

则中存在从到的匹配。其中为正整数。这个条件通常称为条件。

条件是充分条件。不满足条件仍可能存在匹配。

11.4 平面图

平面图

如果能够把一个无向图的所有结点和边画在平面上，使得任何两边都不会在非结点处交叉，则称为平面图，否则称为非平面图。

例：平面图

例：非平面图

平面图的面

在平面图的一个平面表示中，由边所包围的其内部不包含图的结点和边的区域，称为的一个面，包围该面的诸边所构成的回路称为这个面的边界，面的边界的长度称为该面的次数，记为。区域面积有限的面称为有限面，区域面积无限的面称为无限面。

例：

面的概念也可以用下面形象的说法加以描述：

假设我们把一个平面图的平面表示画在平面上，然后用一把小刀，沿着图的边切开，那么平面就被切成许多块，每一块就是图的一个面。更确切地说，平面图的一个面就是平面的一块，它用边作边界线，且不能再分成子块。

另外，对于同一平面图的不同平面表示（例如下图中，将放在里面），虽然面的数目相同，但写出的边界和对应的次数可以不同。

定理平面图的所有面的次数之和等于边数的二倍。

欧拉公式

1750年，欧拉发现，任何一个凸多面体，若有个顶点、条棱和个面，则有.这个公式可以推广到平面图上来（球极投影），称之为欧拉公式。

定理设是连通平面图，若它有个结点、条边和个面，则有

平面图的必要条件

推论设是一个简单连通平面图，若，则有

该推论是必要条件。即，一个简单连通图，若不满足，则一定是非平面图。

推论设是一个简单连通平面图，若每个面的次数至少为，则有

该推论是必要条件。即，一个简单连通图，若每个面的次数至少为，若不满足，则一定是非平面图。

库拉托夫斯基定理

同胚

如果两个图和同构，或经过反复插入或消去2度结点后同构，则称与同胚。

收缩

图中边的收缩是指从中删除，将的两个端点重合，用一个新的结点代替，使关联除外的和关联的一切边，称为边的收缩。一个图可以收缩为图，是指可以从经过若干次边的收缩而得到。

库拉托夫斯基定理

定理一个图是平面图的充分必要条件是它的任何子图都不与或同胚。

定理一个图是平面图的充分必要条件是它的任何子图都不能收缩为或。

复习要点

以下是笔者所参加课程之考纲要求。各院校专业与教授风格皆大相径庭，读者应审慎参考，不应盲从所述。

凡〔扩展内容〕一概不考。

集合

可数集合、不可数集合
包含
集合的定义

数理逻辑

自由变元、约束变元
推理规则（US等等）
主析取、合取范式（必考）
谓词逻辑推理（必考）
- 前置：命题逻辑推理
- 命题符号化
- 演绎法：后面的等标注必须正确
公式类型：重言式、可满足式、矛盾式等
基本等价关系

关系理论

二元关系
- 基本运算：复合运算、逆运算
- 性质：自反、传递等；保守性
- ~~闭包不考~~
特殊关系（常考）
- 等价
- 次序：拟序、良序、偏序（必考）等
函数
- ~~置换函数不考~~
概念
- 复合运算
- 性质

图论

图
- 最短通路（掌握 Dijkstra 和 Floyd 其一即可）
- ~~中国邮递员等两个问题不考~~
树
- 最小生成树（掌握其一即可）
特殊图
- 平面图：~~对偶、着色不考~~
- 欧拉图等图的概念
- 偶图、子图、完全图、补图等的概念（能判定）
  - 偶图：能判定其匹配

〔离散数学完〕

离散数学 - 课堂笔记

离散数学

离散量

一、集合论

1.1 什么是集合

1.2 特殊集合和集合间关系

1.3 集合的基本运算

1.4 集合的运算定律

集合运算的基本等式

集合相等的证明

1.5 可数集合与不可数集合

自然数集的定义

如何比较集合的大小

可数集合

不可数集合

第二章 计数问题

2.1 加法原理和乘法原理

2.2 排列与组合

2.3 容斥原理和鸽笼原理

第三章 命题逻辑

3.1 什么是命题

3.2 命题联结词

否定联结词

合取联结词

析取联结词

蕴涵联结词

等价联结词

3.3 命题符号化及其应用

命题联结词的真值表

命题联结词的优先级

复合命题符号化

命题联结词与开关电路

命题联结词与逻辑电路

命题联结词与网页检索

命题联结词与位运算

3.4 命题公式和真值表

命题变元

命题公式

公式的解释

真值表

3.5 命题公式分类和等价

命题公式分类

等价

3.6 命题等价公式及应用

命题等价公式

判断公式类型

开关电路化简

逻辑电路化简

3.7 范式

基本术语

范式存在定理

范式与真值

3.8 主范式

极小项和极大项

主析取范式和主合取范式

3.9 基本推理形式和蕴含公式

推理形式

3.10 自然演绎法推理

推理规则

自然演绎法

3.11 联结词的完备集〔扩展内容〕

联结词的扩充

联结词的完备集

第四章 谓词逻辑

4.1 谓词的引入

个体词和谓词

复合命题的谓词符号化

4.2 量词的引入

量词

谓词逻辑符号化的两条规则

量词相关的真值确定

4.3 谓词符号化举例

4.4 谓词公式

符号

项

合式公式

4.5 自由变元和约束变元

自由变元和约束变元

闭式

4.6 谓词公式的解释和分类

第二章计数问题

第三章命题逻辑

第四章谓词逻辑

第五章证明技术

第六章二元关系

第七章特殊关系