离散数学教学课件

离散数学第1章绪论重点

1.离散对象

2.数学模型

3.学习方法：精准地掌握基本概念、基本理论，熟悉解决具体问题的基本方法讲述要点

1.了解离散数学的内容和研究对象。

2.数学模型的概念和建立数学模型与解决实际问题的关系。

3.以基本概念为基础，以基本理论为工具，学习解决特定问题的基本方法。1.11.21.3离散数学的研究对象、内容和方法第2章数理逻辑重点

1.命题

2.命题的真值（真假值）

3.命题和命题变量的表示——标识符

4.原子命题和复合命题讲述要点

1.数理逻辑只关心命题之间真假值的逻辑关系，忽略其语义。恰恰是这一特点，使得数理逻辑在各个领域内具有普遍的适用性。

2.标识符在不同的上下语境中，具有不同的含义：作为某一确定的命题，或者是一个命题变量；在后一种情形下，它不是一个命题，所以也就无所谓真假值。但是，可以为它“指派”一个具体的命题。所以说，标识符是一种逻辑框架，可以容纳任何确定的命题（原子的或复合的）。

3.注意提醒学习者，描述一个具体命题的环境——时间、空间或范围。因为世间现实存在的是相对真理，而绝对真理则是相对真理企及的最终标准。相关习题

2.12.22.1命题2.2命题联结词重点

1.命题联结词

2.联结词的最小集讲述要点

1.用符号定义联结词以消除日常用语中的二义性。

[例2.1]

P：“今天下午，小王打过球和上过阅览室”。

Q：“今天下午，小王先打了一会儿球，而后又去过阅览室”。

语句P一个复合语句；而语句Q只是一个原子语句。并且，按照联结词“”的定义，小王究竟是先打球还是先上阅览室是不确定的。

2.强调命题联结词“与”和“或”的可交换性，也即被这两个联结词中任何一个连接的两个命题相互是独立的。

3.条件命题“”在前件为“假”的情况下，无论后件是“真”或者“假”，该条件命题均为“真”。教材里所举的一个例子，只是帮助读者理解所谓的“善意推定”，我们宁愿把它视为逻辑的一个公理。

4.“联结词的最小集”可以一般地介绍，在学习完本章2.5.1命题公式的等价之后，读者自会有彻底的了解。2.3命题的合式公式重点

1.命题的合式公式

2.语句的符号化讲述要点

1.合式公式是一种规范的命题公式。仅当对一个合式公式实行指派时，公式转化为命题。

2.合式公式的结构是递归的。所以，当需要判断一个公式是否合式时，要从最里层的括号开始。渐次向外层“解构”。

[例2.2]

3.正确地将自然语言翻译成命题公式。注意“都不”和“不都”等等的细微区别。相关习题

2.32.42.52.72.4真值表、永真式和永假式重点

1.真值表的结构和生成

2.永真式和永假式

3.公式的置换例式讲述要点

1.构造真值表的方法

有n个变元的公式将有2n行。

在变元数较多时，真值表的局限性。

2.永真的公式可以理解为是一种包容任何命题指派的特殊公式。所以，它被任何公式蕴涵。

3.永假的公式可以理解为是一种排斥任何命题指派的特殊公式。所以，它蕴涵任何公式。

4.在教材的表2.14和2.15中，把等价符号“”和蕴涵符号“”两边的公式加上必要的括号，然后再将这两个符号分别换成“”和“”。我们就可得到同样数目的

永真式了。

6.构造置换例式时应强调的两方面：

（1）必须穷尽相同变元的所有置换。

（2）必须同时进行所有变元的置换。相关习题

2.62.82.92.10重点

1.公式的等价关系

2.公式的蕴涵关系

3.常用的等价关系和蕴涵关系

4.逆换式、反换式和逆反式讲述要点

1.注意区分两个公式的等价关系和以两等价的公式构成的永真双条件公式。

2.注意区分两个公式的蕴涵关系和以两蕴涵的公式构成的永真条件公式。

3.一个公式和它的逆反式等价：

4.一个公式的反换式和它的逆换式等价：

5.因为永真是的置换例式还是永真的，所以

（1）对等价的两个公式中相同的变元做相同的置换后，所得的两个置换例式仍然是等价的。

（2）对蕴涵的两个公式中相同的变元做相同的置换后，所得的两个置换例式仍然保持原有的蕴涵关系。相关习题

2.112.122.132.142.152.162.172.5公式的等价和蕴涵2.6公式的主范式（1）重点

1.初等积、小项和小项的编码

2.析取范式和主析取范式

3.初等和、大项和大项的编码

4.合取范式和主合取范式

5.化公式为范式的步骤讲述要点

1.引进范式的理论意义在于统一所有形式看似不同，但实际上是等价的公式的结构。为进一步研究自由布尔代数的结构给出理论基础。而其实际意义在于提供了一种化简逻辑电路的方法，验证公式的等价等等。

2.初等积和小项的区别是：小项是一种特殊的初等积，可以对小项编码。

3.在约定的编码方式下，一个小项在且仅在用与其编码对应的一组真值去指派它时，它是“真的”。

4.化公式为主范式的主要步骤是用等价的公式取代“上一步骤”的公式，而每一次变化要使“新的”公式更加接近主范式——若干初等积（初等和）或小项（大项）的合取（析取）。以求主析取范式为例：

（1）化公式为析取范式；

（2）化公式为主析取范式。

初学者难以理解的是化初等积为小项的步骤。在这个过程中，往往由于他们感觉上的“随意性”，导致他们的“盲目性”。鉴于这一点，建议做以下类比：2.6公式的主范式（2）

重要的是以上两式都是在各自运算下的恒等变换。

5.主合取范式有和主析取范式对偶的结构。

将关于主析取范式的论述中的“析取”与“合取”对换，“T”和“F”对换，“初等积”换成“初等和”，“小项”换成“大项”。这样做了以后，就是关于主合取范式的论述。相关习题

2.182.192.202.212.7命题演算的推理理论（1）重点

1.有效推理的概念

2.推理的T规则和CP规则

3.有效推理的方法

4.相容的前提和不相容的前提讲述要点

1.有效推理是保证推理获得正确结论的必要而非充分手段。只有对正确前提（真而非永真）使用有效推理所得的结论是正确的（真而非永真）。假的前提可以有效推理出任何真的或假的命题，这时无论结论是真或假，都是有效结论。

2.推理方法

（1）直接推理——只用T规则和CP规则。要充分应用表2.14和表2.15各公式。特别是一些十分有用而又常被忽略的公式。如

其实，这个蕴涵式表达的逻辑意义是：如果两个前提（P，Q）至少有一个是真的，并且又知道它们每一个都蕴涵另一个命题（R），那么最后这个命题是真的。我们提倡读者通过理解公式的逻辑含义来记住它，而不是硬记。

类似的还有表2.15的公式（12‘）、（13’）和（14‘）。

（2）条件证明。它是一种很有用的推理方法。适用于待证明的是一个条件命题。2.7命题演算的推理理论（2）

（3）间接证明（反证法）。反证法的要点是证明原有的前提加上待证结论的否定是一组不相容的前提。

在直接推理较难获得有效结论时，条件证明和反证法有时就很有效。相关习题

2.222.232.242.252.262.8命题逻辑和二值器件重点

1.逻辑运算“”、“”、“”和基本逻辑器件“与”、“或”、“非”的对应

2.用合式公式描述逻辑电路讲述要点

1.用二值逻辑器件搭建的有效的逻辑电路，可以用一个合式公式表达其输出端信号和输入端信号间的关系。

2.如何根据“用户要求”，正确写出对应的合式公式是命题逻辑的一个重要应用。是设计逻辑电路和化简电路的基础。

3.在化简一个逻辑电路时，熟练掌握“从输出端到输入端”逐步写出电路的合式公式是很重要的。2.9一阶谓词逻辑重点

1.谓词和个体

2.命题由个体和谓词组成

3.命题被拆分为个体和谓词的意义所在

4.谓词逻辑中，表达一个命题的形式符号讲述要点

1.正确识别命题的个体和谓词。特别是当存在多个个体并有联结词的情况。

[例2.3]

（1）小张和小李是表兄弟。

（2）小张或小李是三好生。

以上两个命题都有两个个体。但是，在谓词逻辑里，命题（1）只能表示成有两个个体的形式：B(z,w)。而命题（2）更合理地应表示为S(z)S(w)。在进行谓词逻辑的推理时尤其重要。相关习题

2.272.10命题函数和个体变量及量词（1）重点

1.个体变元

2.原子命题函数

3.个体域和量词讲述要点

1.一般情形下，一阶谓词逻辑中的谓词在讨论（或推理）时，总是事先已确定的。

2.用谓词表示的命题和函数的区别。前者的个体是已确定的，而后者的是待定的个体变元。

3.仅含有个体变元的谓词表达式叫原子命题函数。

4.个体域和全总个体域（全域）。

5.全称量词和存在量词。特别指出，存在量词定义的是“有一个”，即“至少有一个”的意思。而不是“恰有一个”。后者的含义是“有一个且仅有一个”。

6.使得一个命题函数转化为命题的两种途径：

（1）为命题函数里的每一个变元确定一个变元；

（2）为命题函数里的每一个变元用相应的量词加以限定（约束）。

7.举例说明同一个谓词公式在不同的个体域下是如何转化为真假截然不同的命题的。

8.存在多个量词时，要强调这些量词的次序不同时，所得的命题可能有不同的解释。如：2.10命题函数和个体变量及量词（2）相关习题

2.282.292.302.11谓词公式（1）重点

1.谓词合式公式（谓词表达式）

2.用公式正确表达“所有有属性A的个体都有属性B”（所有A的都是B），和“有一个（一些）有属性A的有属性B（有一些A是B）

3.自由变元和约束变元，量词的辖域

4.变元的替换

5.谓词公式的等价和蕴涵讲述要点

1.“项”的概念是对于个体定义的。它包含了个体常量、个体变量和定义在个体域上的函数。

2.原子命题函数是由谓词和若干项按照一定的规则组成的，是谓词合式公式的基础。在此基础上，我们递归地定义了谓词合式公式。

3.在表述“所有有属性A的个体都有属性B”这样的命题时，正确的是

因为我们是在讨论所有有属性A的个体共有的属性，所以该命题的真实性，不应该受到论域的影响。说得更明白些就是，如果有属性A的全部个体有属性B（即该命题是真的），那么它在任何个体域下都是真的；如果并非有属性A的全部个体有属性B（即该命题是假的），那么它不可能在所有个体域下都是真的。至少在一个论域下是假的。综上所述，一个如“所有有属性A的个体都有属性B”的真实性应该表述为与论域2.11谓词公式（2）

无关。为要做到这一点，唯一正确的表达方式是如上给出的条件命题的形式。

[例2.4]

显然，以上命题（1）是真命题。而（2）是假的。所以，（1）在任何论域下都是真的。至于命题（2），它可以在一个由左撇子组成的论域下是真的；但是不可能在任何论域下都是真的。所以（2）是虚假的命题。

4.在表述“有一个有属性A的个体有属性B”这样的命题时，正确的是

这一次我们是说个别（有一个）有属性A的个体有属性B。所以该命题的真实性必然与讨论的论域有关。明白地说，就是如果有一个具有属性A的个体果真有属性B（即该命题是真的），那么它仅在某一个（些）论域下是真的；而不必在所有论域下都是真的。反之，如果并非有一个具有属性A的个体有属性B（即该命题是假的），那么它必然在所有论域下都是假的。即后者的虚假性要表述成与论域无关。为要做到这一点，唯一正确的表达方式是如上给出的合取命题的形式。

[例2.5]沿袭例2.4中谓词的意义，并令P(x):x是植物。给出两个命题：

2.11谓词公式（3）

容易明白，命题（3）在某些论域下是真实的。而命题（4）在任何论域下都是虚假的。

以上讲述要点3，4是初学者的学习难点。但又是谓词逻辑非常重要的内容。建议教学者务必多举一些例子讲深讲透。

5.无论是自由变量的换名还是约束变量的换名，遵循同一原则。就是：公式的自由变量被换成自由的；公式的约束变量被换成约束的。且原来是同一个变量的，换成同一个变量。原来是不同的换名后也是不同的。

6.在讨论谓词公式的等价和蕴涵时，我们要对教师多说一些话，以澄清当前在一些教科书中关于这方面的某些含糊之处。一种说法是，因为我们讨论的是一阶谓词逻辑，即谓词公式里所有出现的谓词都是事先确定的。所以，在对公式A(x,y)，B(x,y)进行“解释”时，不应包括对谓词A，B的指派。唯一可以进行解释的是用指定的论域D上的个体去指派每一个个体变元。在这样的理解下，定义A(x,y)与B(x,y)等价，实际上就是在个体域D上：

而谓词A和B都是确定的。另一种观点的不同之处是把“解释”涵盖至谓词符号上。这时，不仅要对公式里的个体变元给予指派，还要以所有可能的谓词去指派公式里的谓词符号。于是，我们看到后者关于等价的定义狭义得多。以上的说明对蕴涵一样也是有效的。

最后，我们要指出的是，教材的公式2.3至2.25是在以上关于等价和蕴涵的后一种意义2.11谓词公式（4）

下成立的。当然，它们在一阶谓词逻辑中成立。所有这些等价和蕴涵公式都是谓词逻辑推理的基础，是教学的一个重点。限于篇幅，在此不一一列出。以下仅对较难理解的做一些说明。

7.关于某些等价式和蕴涵式的说明。

（1） 这个公式否定了在某个论域上的全部个体都有属性P。但是，它并不否定论域中的个别个体可以有属性P。也即“不是所有的有”在逻辑上等同于“有一些没有”。逻辑上正确的是：“全体都有的”属性就是“每一个也有”。“全体都没有的”属性就是“每一个都没有”。要着重区别的是“并非全部有”和“全部没有”。前者被表示为 ，而后者表示为。这也是为什么在证明一个虚假的命题时，企图论证“所有情况下”都虚假的是徒劳的原因。

（2）

这个蕴涵式再次提醒我们注意“全体”属性和“个体”属性之间的区别。左边表示“全体一致地有P或Q属性之一”。而右边表示的是“每一个有P或Q属性之一”。所以，后者不能蕴涵前者就明显了。相关习题

2.282.292.302.312.322.332.342.352.362.372.12谓词演算的推理理论（1）重点

1.谓词逻辑的推理规则

2.引用某些推理规则时必要的限制讲述要点

1.谓词逻辑的推理可以无条件地引用命题逻辑的P、T、CP规则和反证法。在引用谓词逻辑的UG、US、EG、ES规则时，一概要求以下公式中的变元x对y是自由的。

（1）全称特指规则US：

（2）存在推广规则EG：

（3）全称推广规则UG：

（4）存在特指规则ES

：

在此前提下，可以无条件引用US规则和EG规则。但是，对于以上规则（3）、（4）有以下限制：

规则UG的限制：变元x

在任何一个前提中都不是自由出现的；如果A(x) 是一个先前由规则ES引入的公式，那么要求变元x

一定不是被ES规则消除了量词约束后特指的变元（该特指的变元仅仅在形式上是自由的）。

规则ES的限制：被ES引入的变元y一定不可以在任一前提中是自由出现的，也不可以在先前引入的公式里自由出现。

所有这一切要求都基于一个很简单的理由，一个在公式A(x)里自由出现的变元x，并非

2.12谓词演算的推理理论（2）

在被任何个体取代后都是一个真命题。再则，前提中不包含自由变元的要求通常在推理中是自然满足的。因为我们有的前提一般总是以命题的形式给出的，而不是以一种没有真假值的公式给出的。我们知道，含有自由变元的只可能是谓词公式，而不可能是命题。

2.注意讲述推理过程的次序。举一个例子。

[2.6]试由前提

，

可以有效推出

证明 （1）

（2）

（3）

（4）

（5）

试想，如果将以上推理的次序改变为（3），（4），（1），（2）就是错误的。因为先在（4）引入一个自由变元y

，而后又在（2）引入同一变元，这是违背ES规则的。相关习题

2.382.392.402.412.422.432.44

第2章部分习题答案和提示（1）

2.1(a),(d),(e),(f)是命题；(b),(c)不是。

2.3

2.5(a)天气热。

天气下雨。（b）小王进城。小李进城。（c）你去。我去。

2.6(a),(c),(e)是合式公式，(b),(d)不是。其中(a),(e)是永真式，(c)是永假式。

注：(b),(d)两题有印刷错误，正确的题目是： （b）

（d）

2.10(a)；(b)

2.13我们甚至不必做出完整的真值表。而只要留意那些前件是真的行，观察这些行上的后件都是真的。否则，蕴涵就是不成立。例如，对于(a)只要观察P,Q都取1的这一行，这时是真的，所以这个蕴涵式是成立的。

2.14对较为简单的蕴涵关系如(a)，可以用分析法。复杂一些的可以通过证明相应的条件命题是永真式来完成。所说的条件命题就是把待证的蕴涵式里的蕴涵关系的符号“

”换成“”得到的命题。

2.15(c)参考教材第2章，2.9节中所举的选举器的例子。

2.16因为，当C为真时，A,B可以有不同的真值。至于

第2章部分习题答案和提示（2） 2.18(a) ；(b)；

(c)

2.19(a)；(b)

(c)

2.20(a)主析取范式是T,主合取范式是

(b)主析取范式是；主合取范式是

(d)主析取范式是；主合取范式是

2.21(a)主析取范式是；主合取范式是

(b)主析取范式是

主合取范式是

2.22(d)第2章部分习题答案和提示（3）

2.23(c)

2.25(c)证明前提不相容。就是可以从前提中推论出矛盾。

2.26令

即，要从推理如下。第2章部分习题答案和提示（4）

2.28(c)令

则语句可以表述为：

(d)令

2.30令

于是有第2章部分习题答案和提示（5）

(a)（所有）能被2整除的数都是偶数。

(b)有一个偶数可以整除6。

(c)（所有）不是偶数的数不能被2整除。

(d)对于任何一个偶数，都有一个偶数可以整除它。

(e)（所有）质数都不可以被（任何）偶数整除。

注：以上命题并非都是真的。并且，以后在论述某类对象时，只要不指明是对个别而言，一概是对所有该类对象所言。这时，可以免除“所有”、“任何一个”等修辞。另外，“有一个”的含义要理解成“至少有一个”，而不是“有且仅有一个”。

请问，语句“对每一个偶数，都有另一个不等于它的偶数可以整除它”应该如何表示成谓词逻辑的形式？

2.31

(a)令

(b)令

第2章部分习题答案和提示（6）

(c)令

(d)令

2.34

(a)

(b)

(c)

2.36

(a)

(b)

(c)第2章部分习题答案和提示（7）

2.37

(a)

(b)

(c)

2.39

(a)

(b)

(c)

2.40

(a)第2章部分习题答案和提示（8）

请注意证明中引入两前提的次序。

2.41

(b)为要用CP规则，先将结论转化为条件命题的形式：

于是，

2.42

(a) 第2章部分习题答案和提示（9）

(b)如果在步骤(2)之后标上“ES;(1)”，就正确了。但是标“US;(1)”就是错误

的(参考本题(a)，并且注意参考本文件前面的勘误表，更正本题的错误)。

(c)

(d)

2.43令第2章部分习题答案和提示（10）

2.44第4步骤上发生了错误。违背了使用ES规则的限制。如果将推理的次序改变为：

（3）、（4）、（1）、（2）、（5）、（6），推理就是有效的。读者在多次遭遇类似问题以后，应该能总结出这样的规律：当我们在一个推理中先后需要使用规则US和ES

的时候，通常是先利用ES

引入一个“自由变量”，如y。然后再在适当的时候用US引入变量y。因为使用规则US对引入的变量是无限制（当然，要求公式里被量词限制的变量对引入变量是自由的，这一点总是不变的）。第3章集合和关系3.1集合和集合的运算（1）重点

1.集合的一般涵义

2.集合的数学表达方式

3.一个对象“属于”某集合和一个对象”包含于“某集合的确切涵义

4.“包含于“的等价性、反对称性和传递性

5.”子集“、”幂集“的定义

6.集合的“并”、“交”、“差”、“补”的定义

7.“并”的初等性质和“差”的初等性质

8.集合运算的恒等式

9.序偶和笛卡儿积讲述要点

1.明确集合也可以是另一个集合的“元素”。但是集合是一些对象聚集在一起的一种“无序的数学结构”。它可以不包含任何对象，这就是所谓“空集”；空集也是一种有结构的对象，一种存在。又是不存在。说存在是结构的存在，说不存在是不包容任何元素。但是元素本身可以是无结构的对象。无结构的元素要么存在要么不存在。打个比喻说，集合是一种“容器”；而元素是可盛入这种容器的对象。在数学上，当我们讨论一类对象时，常常把它们“装入”一个“集合中。根据我们的需要，可以将不同的对象装入不同的集合中。在讨论集合问题时，会遇到这样的问题：元素，而后者又属于另一集合。初学者常犯的错误是不当地引用”传递性“，得出的错误结论。下面是一个这方面的例子。

3.1集合和集合的运算（2）

[例3.1]设。试问有

解如果我们改变一下集合B的写法：。就看得很清楚，。

集合B里含有的是有结构的集合A，只有”打开“此结构，才能发现元素a。显然，A和a是有区别的。一定要把日常生活中的”属于“和集合论的”属于”（）的含义区别开来。

2.要区别“属于”和“包含于”。前者讨论一个对象是否存在于某一集合（容器）里。而后者讨论的是两个集合（容器）里是否有相同的对象。

3.在搞清楚以上这些概念后，对正确求解一个集合的幂集就会容易得多了。

4.文氏图可以帮助理解集合里的很多概念。但是也可能引起一些概念的混淆。如图3.1。就可能引发上面讨论过的错误。所以，我们建

议在论述集合论的时候，只要有可能就使用符号逻辑

的表示方法或推理。

5.理解地记忆常用的集合恒等式。

6.序偶和笛卡儿积是“关系”理论的基础。要强调笛卡儿

积和它的子集都是由序偶作为它们的元素的。相关习题

3.13.23.33.43.53.63.73.83.93.103.113.12

3.133.143.163.173.183.19BAa

图3.13.2关系（1）重点

1.关系的定义

2.关系的数学表示

3.关系和二维表

4.关系图和关系矩阵

5.自反、对称、反对称和传递关系

6.关系的运算

（1）关系的并、交、差、补

（2）关系的复合

（3）关系的逆

（4）关系的闭包运算讲述要点

1.“关系”揭示了集合所含有的元素之间的某种联系。所以它是研究事物间联系的基本数学模型。关系可以建立在一个或多个集合之上。建立在同一个集合上的关系具有普遍的理论和实际意义。

2.一个关系R是具有同一种联系的元素组（序偶、三元组、n元组等等）的全体或集合。而每一个元素组中的元素仅仅是具有此类联系的一个实例。关系的属性是该关系中的所有元素组共同具有的。但是，个别元素组的元素之间的特殊的属性不可视为整个关系的属性。

3.2关系（2）

2.一般说来，关系是有”指向性“的。意思是，一个元素a和另一个元素b有某种关系R，并不一定有b和a也要有关系R。所以，表示这种有指向性的关系时要用序偶。

3.关系矩阵是表达二元关系的重要工具。它给出了一个关系的所有属性。

4.在讲述四种特殊的关系时，首先要指出它们都是定义在一个集合上的关系。同时务必强调每一种特殊的属性是定义该关系的集合包含的所有元素普遍具有的。

[例3.2]设

5.另一种似乎相反的误解是看不出某一个关系是特殊关系。

[例3.3]

原因何在？持反对观点的人从字面上理解了”传递性“。他们试图找到三个——甚至是三个不同的元素，。当然，他们失望了。可是传递性的定义呢？被他们”自觉“地用想当然的理解取代了。在这个例子里，我们确实无法找到哪怕是有重复的三个元素x,y,z,并且使得

元素）。这不正是符合传递性定义的”善意推定“吗？

这个例子再一次让我们说，真正掌握一个概念是多么重要。也使我们相信，数理逻辑确实是理论学习的基础。我们赞同在”枯燥“的理论学习时类比生活里的事物。但这种类比必须是严谨的，或者至少在我们要类比的属性上本质是一致的。

3.2关系（3）

6.通过列举一些生活中的关系的实例，使学生加深了解关系的并、交、差、补、复合和闭包等运算的意义。

7.强调集合A到B的关系R与集合B到C的关系的复合，是一个在A到C的新关系。并通过写出复合关系矩阵的某一特定项的公式，来了解为什么矩阵的乘积就是复合关系的矩阵的道理。并且要把两个关系的复合与一个可传递关系之间的区别阐述清楚。

[例3.4]

8.本质上说，闭包运算是一种为关系新增”尽可能少“的序偶，以使原来的关系成为一个有某种特殊性质的运算。可通过”观察法“求闭包的方法来加深对闭包公式的理解。相关习题

3.153.203.213.223.233.243.253.263.273.283.293.303.313.323.33

3.3等价关系和集合的划分（1）重点

1.等价关系的定义

2.等价类和等价关系所诱导的商集

3.关于等价类和等价关系的定理

4.划分的定义

5.等价关系和划分的定理讲述要点

1.等价关系的三大性质：自反性、对称性和传递性。通过列举学生熟悉的一些例子，加深对等价关系的理解。等价关系实际上是一种”对等的关系。

2.等价类可以被看成是是等价关系的基本属性。即，一个等价关系的存在蕴涵着相应的一些等价类的存在。有关这一点，可从以上“重点”之5得到映证。

3.商集是等价关系诱导的等价类的全体。可以理解为“按等价关系的定义将一个集合‘除分’为若干互不相交的子集“的结果。

4.详细讲述教材中本节的例3.18。整数的”模k同余“关系是一种很有实用价值的等价关系。

5.等价与划分之间的联系让我们阐明了一个道理：等价类是等价关系的一个基本属性。于是，可以将等价关系定义为”可以定义一个等价关系R，即，"

3.3等价关系和集合的划分（2）相关习题

3.343.353.363.4序关系和哈斯图（1）重点

1.偏序关系和全序关系的定义

2.偏序关系的哈斯图

3.“盖住”的定义

4.偏序关系中子集的特殊元素：最大和最小、极大和极小、上界和下界、上确界和下确界

5.上（下）确界的唯一性定理讲述要点

1.偏序关系的三大基本性质：自反性、反对称性和传递性。通过列举学生熟悉的一些例子，加深对偏序关系的理解。实际上，偏序关系是一种不对等的单边关系。

2.偏序关系的元素不象等价关系中那样按属性“类聚”成一个个子集。它们是分层的。这种特殊的层次关系是偏序所特有的。

3.哈斯图是直观表达偏序的层次关系的有用工具。是偏序关系的一种特殊的关系图。可通过让学生从一个给出的哈斯图恢复其关系图的练习，来加深对偏序关系和哈斯图的理解。

4.极大和最大是一个初学者比较难于区别的概念。可通过与定义在区间

的极大与最大的类比来加强理解。同时强调其区别：因为任何两个实数都是可以比较大小的，但是偏序并不是简单的大小关系，它本质上是一种不对称的关系。3.4序关系和哈斯图（2）

它不保证任意两个元素都有这种不对称关系。所以，实函数的两个极大可以比较大小；但是偏序的两个元素不一定可以比较大小。本质上说，实数的大小关系是全序关系，而偏序关系不必是全序的。综上所述，“极值”是一种局部的概念，“最值”是一种全局的概念。在这一点上，偏序的子集的“极值”和“最值与实函数的”极值“和”最值“是完全可以类比的。

5.要特别提醒读者留意的是，一个子集的”极值“和”最值“一定属于该子集的一员，而子集的”界“可以属于或者不属于该子集。

6.留意确界的唯一性的表达：一子集如果有上（下）确界，则确界是唯一的。因为一个子集可能不存在确界。相关习题

3.373.383.393.403.413.5函数及其运算（1）重点

1.函数的定义及其与关系的差异

2.几类特殊的函数：满射、入射和双射

3.函数的运算：复合函数和逆函数讲述要点

1.函数是一种具有某些特殊性质的关系，这些特殊性质是：像的存在性和像的唯一性。即，对于定义域

对应。这在有限域上的函数来说，该函数的“关系矩阵”有这样的特征：矩阵每一行有且仅有一个元素等于1。

2.既然函数是一种特殊的关系，所以也具有一切关系所具有的普遍属性和研究方法。

3.满射是一类具有“原像存在性”的函数。即，

4.入射是一类具有“原像唯一性”的函数。即，

比较以下函数本身像的唯一性和入射原像的唯一性：

像的唯一性：

原像的唯一性：

我们看到，以上二者恰好互为逆命题。即，入射在存在的像和它们的原像之间是“一一3.5函数及其运算（2）

对应”的。容易明白，如果一个入射还是满射，那么这样的函数（双射）在集合X,Y之间一定是”一一对应“的。

一一对应的函数；而入射是在定义域

参考以下图3.2。

XY

XYf(X)入射双射图3.23.5函数及其运算（3）

5.和关系一样，适当定义的两个函数可以复合成一个新的函数。但是须注意函数复合的习惯写法，它把待复合的第二个函数写在第一个的左边，或称”左复合“。也即它们的复合次序是”从右至左“的。这是和关系在复合时采用”右复合“，或者”从左至右“的次序是不同的。当然，这仅仅是形式上的不同。复合运算的本质是一致的。

6.函数有逆函数则该函数一定是双射。反之，双射一定有是可逆的。因此，可逆的充要条件是双射。于是，任何逆函数一定是双射。相关习题

3.423.433.443.453.463.473.483.49第3章部分习题答案和提示(1)

3.1

(a)

(b)

(c)

(d)

3.2参考本文件3.1集合和集合的运算（2）[例3.1]

3.3其中(a),(c),(d),(e),(g)是真的,其余是价的。

3.4除(a)以外，均为假。

3.6

3.7

(a)

第3章部分习题答案和提示(2)

(b)

3.8

(a)

(b)

(c)

3.9

第3章部分习题答案和提示(3)

3.12

3.14

3.15 第3章部分习题答案和提示(4)

3.16

3.18建议读者用两种方式来证明本题.一是通过分析法,证明等号两端集合互为子集.另一种方法是用集合运算的定义和恒等式直接证明等号一端的集合可以恒等地变换为另一端的集合表达式.

3.19

(b)

3.20

3.23第3章部分习题答案和提示(5)

3.23

3.25

第3章部分习题答案和提示(6)

3.27

3.30

第3章部分习题答案和提示(7)

3.31

除（a）是真的以外，其余均为假。真命题要一般的证明，假命题只要举一个反例。

3.33

第3章部分习题答案和提示(8)

第3章部分习题答案和提示(9)

3.34

3.36

由于关系S是用两个等号定义的。而相等关系是自反、对称、传递的。所以关系S必定是等价关系。 由此等价关系诱导出的等价类由无限多个。等价类有两类，第一类都是由关于x轴对称的两个不同的点组成（不含y轴上的对称点）；第二类由除原点的x轴上的一个点组成。

3.38

第3章部分习题答案和提示(10)

3.40

第3章部分习题答案和提示(11)

3.43

（a）、（b）、（d）既不是满射也不是入射。

（c）是满射而非入射。

（e）是满射也是入射，所以是双射。

3.44第3章部分习题答案和提示(12)

3.46

3.48

第4章数函数和

递推关系4.1数函数概念重点

1.数函数的概念

2.数函数的一般表达方式讲述要点

1.数函数是定义在自然数集上的函数。通常，它的第一项

会有一些特殊的意义。或者纯属为计算方便而添加的辅助项。

2.理解数函数的自变量和函数值的离散性。避免讨论非自然数之处的数函数的值。特别如教材本节的例4.2，此数函数不会给出该交通工具在整分钟以外的任何性状。相关习题

4.14.24.2数函数的基本运算

4.3数函数的母函数（1）重点

1.数函数的和（差）、数量积、积和卷积的定义

2.数函数运算的一些初等性质

3.两个数函数相等的概念

4.数函数的母函数讲述要点

1.数函数的母函数与唯一一个幂级数对应。具体地说，就是数函数的第r项的值等于幂级数这一项的系数。所以，开始对母函数的幂级数表达，可以仅从这方面来理解。

2.那么，为什么要用幂级数来表达数函数呢？好处是数函数的许多运算可以通过幂级数的运算来实现。而幂级数有许多现成的运算可以应用。实际上，幂级数的和、对应项的积、数量乘积和积的每一项的系数恰与数函数的和、积、数量积和卷积相等。

3.对不熟悉数学分析的读者，建议跳过本章。对学习过数学分析或微积分的同学，建议复习一下函数的幂级数展开和常微分方程的有关内容。

4.4.2数函数的基本运算

4.3数函数的母函数（2）相关习题

4.34.44.54.4递推关系（1）重点

1.递推关系和初边条件

2.解递推关系

3.常系数线性递推关系及其相应的齐次方程

4.通解、特解、齐次解及其联系

5.特征方程和特征根

6.通过特征方程求数函数的通解

7.通过求母函数求数函数讲述要点

1.具备微分方程知识的读者对数函数的特征根解法不会有什么问题。建议他们在开始本章内容之前，复习一下微分方程的相关内容。

2.单独的递推关系并不能唯一确定一个数函数。譬如，递推关系，我们熟知的斐波那契数列满足该递推关系。而数函数这样的简单数函数也满足它。要得到唯一数函数解，不但要有递推关系，还需要给出数函数的初边条件。这一点是和解代数方程很不一样的。打个比方，微分方程所包含的信息是：从当前的地方你如何走可以到达下一步。而你可以从不同的地方开始，显然从不同的地点开始按相同的指示前行，你会到达不同的下一个地点。本质上说，递推关系和微分方程一样都与差分方程有关。后者给出函数在相邻两自变量处的函数值之差的方程。4.4递推关系（2）

例如，教材本节的递推关系

所以，我们也把k阶常系数线性递推公式叫做k阶常系数线性差分方程。

3.从齐次方程引导出差分方程的特征方程和特征根的概念。再由特征根表达的齐次解的线性组合与递推关系一个特解之和，通过初边条件找出数函数的通解。

4.注意，当存在m重特征根的情况出现时，由特征根表达的齐次解的线性组合中关于这m项要有不同一般的表达。例如，

5.用母函数求解数函数的通式需要一定的技巧。我们不提什么过高的要求。只要能看懂教材上的例子就可以了。相关习题

4.6第4章部分练习答案和提示（1）

4.1

(a)

(b)

4.2

其中，r表示每次测量的序号。

4.3

(a)

(b)

第4章部分练习答案和提示（2）

4.4

(a) 第4章部分练习答案和提示（3）

(b)

(c)

4.5

(a)第4章部分练习答案和提示（4）

(b)将母函数化成简单分式的形式：

最后一个式子的最后一项中求和号系母函数自乘的结果。因此，

(c)提示：分别写出、和的幂级数展开式，然后三式相乘并合并同幂次项，最后有结果：第4章部分练习答案和提示（5）

4.6

(a)通过观察，该数函数的递推公式是：

(b)第4章部分练习答案和提示（6）

含待定常数的通解是：

最后，通过初边条件解得。得出数函数的通解是

另一种解法如下。考虑到(a)给出的差分方程在是正确的。注意到母函数每一项的系数正是以该项指数为序号的数函数值。我们以乘本题中的递归关系式，并留意此关系式仅在有意义。得第4章部分练习答案和提示（7）

第5章图论5.1图的基本概念和术语（1）重点

1.图的定义

2.图的主要概念和术语

3.图的同构

4.图的最基本定理（有关边和度）

5.子图、支撑子图和补图的概念讲述要点

1.图是一种数学结构。有相当多的离散对象的问题可以用图来描述。对于初学者来说，要避免过分依赖图形来理解图这种数学结构。否则，将大大削弱图的应用范围。但是，完全脱离图形的讨论也不是我们提倡的。总之，在我们对着一个图形讨论图的种种属性时，我们的思想不要离开这些“点”和“边”在图这种数学结构里所表示的本质属性。

2.把图和第3章里讲述过的“关系”做一下对比，可以发现它们之间有许多雷同的地方。在“关系”那里，总是建立在一个（有时也讨论多个集合）集合上的；而从图的定义可以发现它建立在一个被称做“顶点”的元素的集合上。而关系中的每一对序偶，恰与图的有向边相应。一对元素如果是“对称”地有关系，那么对应在图里的一无向边。可以这么说，完全地表示了一个关系的关系图（形），实际上就是一种图的图形表示。即，“关系”实际上就是一种（有向）图。反过来说，我们有必要把图的“边”看成是其某两个5.1图的基本概念和术语（2） “顶点”之间有某种关系的抽象表达。从图的观点重新审视关系之后，使我们在随后的学习中会更为主动地类比图和关系的许多雷同的表现。特别是它们的矩阵表达。不过尽管图和关系在数学结构上有许多雷同之处，可是关系更注重研究集合的元素的联系以及这种联系的拓展（闭包，并，交，差，补和复合)等；而图则会在很多应用中为表示两个顶点之间联系的边赋予别的属性，如边权等。由此对所谓的加权图的种种讨论，有很多实际的应用。

3.完全图是一个重要的概念。特别强调有向完全图的不唯一性。相关习题

5.15.25.35.45.55.2路和回路重点

1.路和回路

2.有向图的简单路、简单回路和初等路、初等回路

3.有向图上的可达概念以及弱连通、大则单侧连通和强连通

4.将有向图的相关概念扩充到无向图讲述要点

1.一般来说，我们可将无向图的边用两条方向相反的有向边代替，并在这样替代后所得的有向图上来讨论无向图的路、回路和简单路、简单回路、初等路、初等回路等等。只是在以下两方面要做一些说明。一是无向图的一条边被两条方向相反的有向边代替后，是一个有向回路，并且还是一初等回路。但是，我们通常并不把一条无向边看成是一回路。约定，无向图具有的“最小”回路“（初等回路）应含有3条边。其二是无向图中两顶点的”可达“总是对称的，所以，无向图强调的仅有一种连通性，就是两顶点要么是连通的，要么是不连通的。不存在强连通、弱连通和单侧连通等。

2.连通分图是初学者比较难于理解的一个概念。要从”局部最大“，也即”极大“的含义来理解。相关习题

5.65.75.85.95.105.3图的矩阵表示重点

1.图的邻接矩阵

2.加权图的矩阵

3.邻接矩阵的幂矩阵及其意义

4.路径矩阵及其求法讲述要点

1.讲述邻接矩阵及其幂时，可通过与关系矩阵及其幂的类比来加深图和关系的理解。实际上，如果我们定义一个”相邻“关系，那么它的”关系图“就是我们这里讨论的图的图示。于是，刚刚定义的那个相邻关系的矩阵就是图的邻接矩阵。有时我们真的很难区分我们讨论的究竟是一个关系还是一个图。其实，做这样的区别往往是无意义的。譬如，我们有一个无向图。当我们做它的传递闭包时，就是在做一些矩阵的幂。而最后所得传递闭包的矩阵实际上正是相应图的路径矩阵。

2.鉴于求路径矩阵的方法与关系的传递闭包的方法没有什么不同，建议更多地关注邻接矩阵的幂的含义。相关习题

5.115.125.135.145.4树和生成树重点

1.无向树及其生成树的概念

2.无向连通图的秩

3.最小生成树及克鲁斯卡算法讲述要点

1.回忆5.2小节中讨论的无向图的回路概念。按照我们的约定，排除了一条无向边是初等回路的情况，于是可以这样来为无向树下一更为简单的定义：连通而无回路的无向图叫做无向树。

2.无向树的5个等价的定义（任一个都可以作为定义，其余作为初等性质）。

3.任一无向连通图均有生成树（可以不唯一），但无向连通图的秩是唯一的。

4.克鲁斯卡算法的关键在于两方面。一是用以构建生成树的边是按边权从小到大的次序加入到最终的生成树里去的。二是原无向图中还未加入到待求生成树里去的边中，具有最小边权的那条是否可以添加到生成树，取决于该边是否与待求生成树中已有边共同构成回路。如是，则这条边要从我们的算法中删去；否则，就将它加入到待求的生成树。

5.如可能，建议作为例题给出用一种程序设计语言写出的克鲁斯卡算法。相关习题

5.155.165.175.185.195.5有向树及其应用（1）重点

1.有向树概念

2.根树概念及相关术语

3.位置树概念

4.森林概念讲述要点

1.有向树中最为常用的是“根树”。根树是一种特殊的具有层次结构的有向图。

2.注意，因为习惯的原因，根树每一接点的“度”的含义有别与图的接点度的定义。前者在计算接点的度时，不计其入度。可以理解，因为有向树的接点除“根”之外，它们的入度都是1。所以，一个接点的度就和它的子树的数目相同。这样定义有向树的度会更有明显的意义。

3.强调二叉树的子树具有的位置特征。在绘制二叉树的图形时，要明显地表达出这样的特征。

4.前缀码是一种有广泛应用的编码。前缀码具有“任何代码都不是其他每一代码的前缀”的特点。这与它的构成方式有关。因为一组前缀码是且仅是某一特定的二叉树所有叶子编码。而这种编码是通过逐层因袭其双亲代码作为前缀形成的。这是前缀码的命名的由头。恰恰是这样的“继承——前缀”属性，使得它有有趣的特点：前缀码中无前缀。5.5有向树及其应用（2）相关习题

2.205.215.225.235.245.255.6欧拉图和哈密顿图（1）重点

1.七桥问题和欧拉图

2.欧拉路和欧拉回路

3.欧拉定理

4.哈密顿图

5.哈密顿图的一个必要性定理和一个充分性定理讲述要点

1.欧拉定理有较明显的直观性。重点在于其应用。

2.哈密顿图没有严格意义下的充分必要条件。本教材给出了一个必要性定理和一个充分性定理。强调必要性定理可证明一个图不是哈密顿图（如果图不满足必要性条件）。而充分性定理可以用来证明图是哈密顿图（如果它满足充分性条件）。

3.有时，要证明一个图不是哈密顿图需要一些另外的技巧。因为它可能并不能直接看出不满足哈密顿图的必要条件。如教材的本小节图5.24之(b)。它被称为彼得森图。

[例5.1]证明彼得森图不是哈密顿图。

参照教材的图5.24(b)（或点击此地的图5.1）。可以看出彼得森图是由两个内外都是五边形的图按顶点交错相连组成（即一个五边形的相邻顶点分别与另一个五边形的不相邻顶点相邻）。它有15条边，10个顶点。如果它有哈密顿回路，该回路恰有10条边。并且，这个哈密顿回路至少包含连接内外两五边形的5条边（以下简称这些边为“连接边”）中的偶数条（2条或者4条）。我们简要地分析如下。因为如果哈密顿回路存在，5.6欧拉图和哈密顿图（2）

我们就能从该回路的任一顶点出发沿回路巡行并且通过每一个顶点一次且仅一次，最后返回上述起点。显然这样的巡行必定只能是偶数次、不重复地通过前述的“连接边”才能实现的。也就是说，可以删除1条或3条这样的连接边和两个五边形的4条或2条边，而剩余10条边的图恰好是一哈密顿回路。并且根据欧拉定理，该删除了5条边的哈密顿回路上每一点正好是2度的。我们来证明这两种情形都是不可能的。 首先，假设存在的哈密顿回路包含4条连接边（点击此地看图5.1(b)），不妨设删除的是(A,a)连接边。注意顶点a已是2度，所以(a,c)、(a,d)两边必存在于假设的哈密顿回路上。于是，为使顶点c，d是2度的，(b,d)、(c,e)必定不在回路上。而外五边形顶点A已是2度，所以它关联的两边(A,B)、(A,E)务必在回路上。这样，为保证顶点B,E是2度的，边(B,C)、(D,E)必不在上述回路中。最后，我们在哈密顿回路可能存在的第一种情形下（该回路含4条连接边）推论出这样的图在同时保证每一顶点是2度的必要条件下，只能是如图5.1(b)的结构。而它却由两个互不连通的回路组成。

其次，假设存在的哈密顿回路包含2条连接边。由此可以断定如果哈密顿回路存在，我们在沿此回路巡行时，只能有唯一一次进入内五边形的可能。因此，该回路必须一次连续通过内五边形的所有顶点。于是，在连接边(A,a)已假设存在的前提下，另一连接边只能是(c,C)或(d,D)两者之一。不妨设回路上的另一连接边是(d,D)（点击此地看图5.1(c)），为看得更加清楚，我们给出它的同构的图5.1(d)（点击此地看图）。删除最后这个图的顶点A,D及其与之关联的边后，根据教材5.6定理5.10可知，它也不是哈密5.6欧拉图和哈密顿图（3）

返回点击此地：返回5.6(1)

返回5.6(2)

顿图。

至此，我们已证明了彼得森图不是哈密顿图。相关习题

5.285.295.305.315.325.335.345.355.7最短路径与最长路径（1）重点

1.从加权图的某一顶点到其余各点的最短路

2.狄克斯特尔的最短路算法

3.评审图概念及有关术语

4.关键路径算法讲述要点

1.加权图的两顶点之间路的长度不是其边数而是组成该路上的边的边权之和。

2.狄克斯特尔算法中，“有效路”是一重要概念。在此算法中，将起点以及运算过程中那样一些顶点组成一集合U。从起点到这些点的最短路已在运算中求出。而其余各点组成另一个集合S=V-U（其中，V是图的所有顶点的集合）。任一有效路上的顶点除终点属于集S以外，其余所有顶点都属于集U。在运算的某一步上，属于集S的每一顶点都有一个所谓“指数”，指数等于起点到该点的一切有效路中长度最小的那条的边权之和。此其第一个“最小”。但是一般地说，此最小只是到该顶点的所有有效路中长度最小的；它不一定是最短路。而在每一步上，集合S里具有最小指数的那个顶点的最短路正是具有该最小指数的那一有效路。此其第二个“最小”。严格区别这两个“最小”是绝对必要的。总之，集合S每一点的所有有效路中边权最小的仅仅是该点的指数。而S的所有点的有效路中最短的那条才是当前步骤上的一条最短路。

3.理解算法的每一步上，对集合S的顶点的指数修改的必要性和计算方法。

5.7最短路径与最长路径（2）

4.注意，狄克斯特尔算法是逐个求得每一顶点最短路的。并且这些最短路的大小是递增的。也即，最小的最短路最先求出，顶点中最长的最短路最后求出。

5.用最长路径的算法求解顶点的最长路径时，要注意从发点开始，按所谓“拓扑序列”的次序逐一向收点求解。仅当一个顶点的所有前驱接点的最长路径都已经求出后，该顶点的最长路径才是可解的。最长路径对应一点的最早发生时间。

6.区分事件和工程这两个概念。它们分别对应着评审图的接点和边。前者对应一个时刻；后者对应一个过程（时间段）。

7.求顶点的最迟发生时间时，要从收点向发点按“反拓扑序列”的次序逐一求解。仅当一点的所有后继接点的最迟发生时间均已求出后，该接点的最迟发生时间才是可解的。

8.本质上说，顶点的最迟发生时间等于收点的最迟发生时间（整个工程完成的时间）减去该顶点到收点的最长路的长度的结果。所以，求一个顶点的最迟发生时间时，要做该顶点的所有后继的最迟发生时间与该顶点到后继的边的边权之差，再取这些差中最小（而不是最大）的一个作为该顶点的最迟发生时间。

9.活动的最早发生时间等于相应边的起点的最早发生时间。这容易理解。要注意的是活动的最迟发生时间等于相应边的终点与该边边权之差。一般它并不等于起点的最迟发生时间。

10.当存在唯一一条关键路径时，某些关键活动的边权的改变（增大或减小）可以影响总工期的相应改变；含有两条以上关键路径时，其不重合的并行部分所含边或重合5.7最短路径与最长路径（3）

部分边的边权的增大可影响总工期的同样增大，而其中一条关键路径上的并行但不重合部分所含边的边权的减小，并不能使总工期相应减小。相关习题

5.265.275.8平面图重点

1.平面图概念

2.关于平面图的术语面、有限面、无限面和度

3.平面图的欧拉定理和简单无回路平面图的边与接点数的不等式

4.库拉多夫斯基定理讲述要点

1.这一小节里，我们讨论了由几何的点和线构成的纯粹几何图形。而不为其点和线赋予任何非几何性质。

2.一个由点和线构成的图究竟是否为平面图，不因人们的绘图技巧而改变。它取决于图本身的拓扑性质。所以，当我们在保持原图的点线关系不变的情形下确实将它表达为一平面图后，它是一个平面图；但是，当这种尝试失败时，我们并不能肯定它不是平面图。非平面图是需要理论证明的。常用的证明工具就是本节给出的定理。

3.牢记两个著名的非平面图：K5和K3,3

是重要的。相关习题

5.365.375.385.395.405.41第5章部分习题答案和提示（1）

5.1

5.4

证明对图G，S做一如下的映射：第5章部分习题答案和提示（2）

5.6

证明

第5章部分习题答案和提示（3）

5.7（更正教材错误：题目5.7和5.8的图5.43与5.44应交换，并改正顶点标记）

5.8（见题5.7说明的更正。更正后的 图5.44如右所示）

所有的强分图是：第5章部分习题答案和提示（4）

5.10

证明无向图接点的连通性显然具有自反（总假定一个接点对自己是连通的）、对称性和传递性。所以，无向图接点的连通性是一种等价关系。

由连通性诱导的等价类是连通分图。

5.12

设图有n个顶点。求该图邻接矩阵的布尔幂。列出上述每一个矩阵中的

5.13邻接矩阵如下。第5章部分习题答案和提示（5）

5.14第5章部分习题答案和提示（6）

5.15设该无向树有t个一度接点。并以e和v分别表示它的边数和接点数。按题意

v-t=2+1+3=6

由无向树的性质，e=v-1。而2e等于树接点的度数之和。所以

2e=2v-2=t+2×2+3×1+4×3

整理后，有

2v-t=21

把最后这个方程与第一个联解，得t=9。

5.16提示：应用图和无向树的性质，通过反证法证明之。

5.17提示：本证明较为烦琐，可参考教材最后“参考文献”之三。

5.19克鲁斯卡解本题的过程可通过下表给出。第5章部分习题答案和提示（7）生成树的边权值当前边权之和已生成连同分支已生成连通分支数无无无[v1],[v2],[v3],[v4],[v5],[v6],[v7]7(v1,v6)11[v1,v6],[v2],[v3],[v4],[v5],[v7]6(v4,v5)23[v1,v6],[v2],[v3],[v4,v5],[v7]5(v1,v2)25[v1,v6,v2],[v3],[v4,v5],[v7]4(v5,v7)27[v1,v6,v2],[v3],[v4,v5,v7]3(v4,v7)*2-不变同上。此边的两端点同在一个已生成连通分支3(v5,v6)29[v3],[v1,v6,v2v4,v5,v7]2(v1,v7)*3-不变同上。此边的两端点同在一个已生成连通分支2(v3,v4)312[v1,v2v3v4,v5,v6,v7]1第5章部分习题答案和提示（8）

5.20以下的图5.2就是一例。

5.23请参考教材末尾的参考文献之三。

5.26请参考教材末尾的参考文献之三。

5.30可输出三位二进制码鼓轮对应的欧拉图如

右上的图5.3。于是，写出鼓轮的一种排列是

000，001，011，111，110，101，010，100

所以，鼓轮上槽片的分布应该是

00011101

5.31图5.2图5.3第5章部分习题答案和提示（9）

5.32答案给出如以下图5.4。

5.33答案是：(a)不是哈密顿图，(b)是哈密顿图。

5.34满足定理5.11的充分性条件，但因为它不是无回路的简单图。所以不是哈密顿图。图5.4图5.5第5章部分习题答案和提示（10）

5.35

(a)在一个欧拉图上找一个欧拉回路C。从任一顶点出发，沿此欧拉回路巡行，并为正在通过的边确定一个与此巡行方向相同的方向。所得的有向图即是强连通的。

(b)在一个哈密顿图上找一个哈密顿回路C。从任一顶点出发，沿此哈密顿回路巡行，并为正在通过的边确定一个与此巡行方向相同的方向。如果还有一些边不在此哈密顿回路C上，为这些边任意选定一个方向。所得的有向图即是强连通的。 （参考教材第5章5.2节末尾的一段话）

5.37图5.6第5章部分习题答案和提示（11）

5.38

证明设平面连通图G的每一面的度。按教材公式5.20就有

5.39

证明反证法。设边数小于30的无环简单平面图的每一接点的度均超过4。即，

第5章部分习题答案和提示（12）

5.40

证明按照题设平面图无环，也无平行边，所以它的所有面的最小度k大于等于3，即

5.41题目给出的三个图可以同构地表示为如以下图5.7给出的平面图。图5.7第6章代数系统6.1运算和代数系统（1）重点

1.简要了解“系统”的含义

2.运算即函数

3.封闭运算

4.最常见运算的初等性质

5.运算的幺元、零元和逆元

6.关于幺元和逆元的唯一性定理讲述要点

1.一般地说，系统是指相同或相类的事物按一定的秩序和内部联系组合而成的整体。对于代数系统来说，这种秩序和联系指的是运算规则。

2.运算是一个很广义的概念。实数或复数的运算只是其中的特例。要习惯运算符号的一般表示。理解算符就是函数符号。进而了解运算的前缀和中缀表达。

3.学习用复合表表达一个运算。

4.运算的结合律、交换率、吸收律是某些代数系统特有的规律，而非一般代数系统必须具有。

5.某些特殊代数系统具有的特殊元素，如幺元、零元、逆元。强调这些元素唯一性的条件。注意，逆元的唯一性更要求代数运算是可结合的。

6.初步熟悉抽象代数中的证明技巧。6.1运算和代数系统（2）

7.让学生自己尽量多地举例给出运算、代数系统、幺元等等的实例和反例。相关习题

6.16.26.36.46.2半群和独异点重点

1.半群和独异点的概念

2.集合代数上的独异点和整数上的“摸k同余”独异点

3.子半群概念及其判定定理

4.逆元的对称性讲述要点

1.半群是一种特殊的代数系统，独异点是特殊的半群。

2.记住几个典型半群和独异点的实例。

3.进一步熟悉抽象代数系统的证明技巧。相关习题

6.56.66.76.86.96.106.116.126.136.14

6.3群和子群（1）重点

1.群和子群的概念

2.群、独异点、半群和代数系统的递蕴涵关系

3.群的初等性质

4.初步理解群的同构概念

5.了解1至3阶群的唯一结构（复合表）

6.了解4阶群的两种结构（复合表）讲述要点

1.让学生利用群的初等性质（运算封闭、有唯一幺元，

除幺元之外无幂等元、复合表的每一行和每一列都是

其所有元素的一个全排列，且它们两两互不相同等）。

自己给出1至3阶群的复合表。通过这样的练习，将会

加深他们对群的性质的理解。

2.强调群的可约律的限制。即被约的元素必须在等号

两侧表达式的同一端。要讲清楚它不同于实数领域内

等式两边的可约律，原因是一般群的运算并不具有交换

律。

3.理解从代数系统到群的递蕴涵关系（参考图6.1）。

代数系统半群独异点群图6.16.3群和子群（2）

在此需要说明的是，群蕴涵独异点等等（意思是一个群必是独异点，一个独异点必是半群…等等），在图6.1中表示为被包含的集蕴涵包含它的集。这是正确的表达。因为蕴涵不同于包含。前者描述事物的属性关联，而后者描述的是外延的关联。从外