《离散数学》导学

开篇导学

课程导学视频：

导学一、导学二、导学三、导学四、导学五

读书须如蜂采蜜

说明：关于

离散数学的性质、内容

离散数学的学习目的

这两部分内容在绪论中已经讲过了，请同学们看课件和录相。这里只做几点补充。

一.离散数学的内容及其相互联系

内容：

1. 数理逻辑篇 （第1、2章）

讨论命题表达、演算、推理

2. 集合论篇 （第3、4、5章）

讨论集合基本知识、二元关系和函数的表达、性质和运算

3. 代数系统篇 （第6、7章）

讨论代数系统表达、性质。群、环、域、格、布尔代数

4. 图论篇 （第8章）

讨论图的基本理论，一些特殊图及其应用

各章之间的联系：

从上面这个图看出：

整本书各个章节之间是有机联系的。前面是后面的基础。

所以前面的基础一定要打好。否则后面的知识就学不好。另外学习时注意知识的相互联系，就使得学习的知识有系统性、完整性。而不是支离破碎的。就能全面掌握这些知识，为将来应用这知识打下坚实的理论基础。

二.离散数学中知识的结构

可见这是三层结构，内核层是基本概念，中间层是定理和公式，最后层是应用层，包括：计算、判断、证明、推理和用理论解决实际应用问题。

对这些知识点的要求：

概念：必须清楚(内涵、外延)。

定理、公式：最好能了解证明过程。对于重要定理、公式要记住。

应用：灵活应用上面知识，解决实际问题；

推理合乎逻辑；

证明思路清晰，论据充分；

计算正确；

判断准确。

三. 学习方法

此课特点：内容较杂，概念多，定理多，比较抽象，给学习带来一定难度。

学习方法：

1. 认清学习此课的重要性，提高学习自觉性。

2. 要有认真刻苦钻研、知难而进的学习精神。

3. 首先要仔细认真地阅读讲课录相和课件。

4. 准确掌握每个概念 (从概念的内涵及外延两个方面)。对抽象的概念，可以先从所熟悉的实例入手，这样便于理解这些抽象概念。

5.弄清各个知识点以及各个知识点之间的联系。同时要善于根据自己的学习体会，归纳总结各个知识点的要点,最好写学习笔记，使之变成自己的知识。

7. 在理解内容的基础上，一定要较多地做些习题。从而进一步加深理解所学内容。做习题时，一定不要先看答案，要独立完成。

8. 根据各个章节内容的不同，学习的方法各异，要不断总结自己的学习经验。

9. 学习时注意培养分析问题和解决问题的能力。

10. 最好有一个学习小组，同学们互相交流学习经验。互相启发、答疑解惑。

11. 在学习中遇到的问题，要及时向老师、同学请教，加以解决，不要等问题成堆了再解决，那样会增加学习困难，甚至失去学习信心。

四.参考学习流程：

五.学习进度

章 讲课 习题课 总学时 需要周数

第1章 命题逻辑 10 2 12 3

第2章 谓词逻辑 7 1 8 2

第3章 集合论基础 5 1 6 1.5

第4章 二元关系 12 2 14 3.5

第5章 函数 5 1 6 1.5

第6章 代数结构 10 2 12 3

第7章 格与布尔代数 7 1 8 2

第8章 图论 12 2 14 3.5

总 计 68 12 80 20

希望同学们按照学习进度学习。

对一件东西的爱好是由知识产生的，知识愈准确，爱好也愈强烈。要达到这准确，就须对所应爱好的事物全体所由组成的每一个部分都有透彻的知识。

——达 · 芬奇

你爱好计算机专业,就从学习好离散数学知识起步吧！

数理逻辑篇导学

(第一章、第二章)

学之乃知，不问不识

逻辑--是研究人的思维的科学。

逻辑包含：

1.辩证逻辑：是研究人的思维中的辩证法。

例如：用全面的和发展的观点观察事物；

具体问题具体分析；

实践是检查事物正误的唯一标准；等。

2.形式逻辑：是研究人的思维的形式和规律。

这里我们只关心形式逻辑。

一 . 形式逻辑

1． 人的思维过程：

概念 Þ 判断 Þ 推理

2． 正确的思维：

概念清楚，判断正确，推理合乎逻辑。

人们是通过各种各样的学习(理论学习和从实践中学习)来掌握许多概念和判断。

3． 而形式逻辑主要是研究推理的。

推理：是由若干个已知的判断(前提)，推出新的判断(结论)的思维过程。

4．推理方法：

类比推理：由个别事实推出个别结论。(个别Þ个别)

如：地球上有空气、水，地球上有生物。

火星上有空气、水。

Þ火星上有生物。（结论有待于验证）

归纳推理：由若干个别事实推出一般结论。 (个别Þ一般)

如：铜能导电。铁能导电。锡能导电。铅能导电。……

Þ一切金属都导电。 （结论有待于验证）

演绎推理：由一般规律推出个别事实。 (一般Þ个别)

形式逻辑主要是研究演绎推理的。

二. 数理逻辑

数理逻辑是用数学的方法研究形式逻辑。

所谓“数学方法”：是建立一套有严格定义的符号，即建立一套形式语言，来研究形式逻辑。所以数理逻辑也称为“符号逻辑”。

即用符号表达命题并进行推理。

请看下面两个推理的例子：

例1 请根据下面事实，找出凶手：

1. 清洁工或者秘书谋害了经理。

2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。

3.如果秘书的证词是正确的，则谋害发生在午夜前。

4.如果秘书的证词不正确，则午夜时屋里灯光未灭。

5. 如果清洁工富裕，则他不会谋害经理。

6.经理有钱且清洁工不富裕。

7.午夜时屋里灯灭了。

令A:清洁工谋害了经理。 B:秘书谋害了经理。

C:谋害发生在午夜前。 D:秘书的证词是正确的。

E:午夜时屋里灯光灭了。 H:清洁工富裕。

G:经理有钱。

命题符号为：

A∨B，A®ØC，D®C，ØD®ØE，H®ØA，G∧ØH，E Þ?

⑴ E P

⑵ ØD®ØE P

⑶ ØØD T ⑴⑵ I

⑷ D T ⑶ E

⑸ D®C P

⑹ C T ⑷⑸ I

⑺ A®ØC P

⑻ ØA T ⑹⑺ I

⑼ A∨B P

⑽ B T⑻⑼ I

结果是秘书谋害了经理。

例2 小杨、小刘和小林为高山俱乐部成员，该俱乐部的每个成员是个滑雪者或登山者。没有一个登山者喜欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个是登山者而不是滑雪者的成员。如果有，他是谁？

设：M(x):x是高山俱乐部成员。H(x):x是滑雪者。

D(x):x是登山者。 L(x,y):x喜欢y。

a:小杨；b:小刘；c:小林；d:雨；e:雪。

命题符号化为：

M(a), M(b), M(c), "x(M(x)→(H(x)∨D(x))), Ø$x(D(x)∧L(x,d)),

"x(H(x)→L(x,e))，"y(L(a,y)→ØL(b,y)), L(a,d)∧L(a,e)

⑴ L(a,d)∧L(a,e) P

⑵ L(a,e) T ⑴

⑶ "y(L(a,y)→ØL(b,y)) P

⑷ L(a,e)→ØL(b,e)) US ⑶

⑸ ØL(b,e)) T ⑵ ⑷ I₁₁

⑹"x(H(x)→L(x,e)) P

⑺ H(b)→L(b,e)) US ⑹

⑻ ØH(b) T ⑸ ⑺ I₁₂

⑼ "x(M(x)→(H(x)∨D(x))) P

⑽ M(b)→(H(b)∨D(b)) US ⑼

⑾ M(b) P

⑿ H(b)∨D(b) T ⑽ ⑾ I₁₁

⒀ D(b) T ⑻ ⑿ I₁₀

⒁ D(b)∧ØH(b) T ⑻ ⒀ I₉

所以小刘是登山者而不是滑雪者。

上面两个例子涉及到的问题：

1.如何表示命题，即表达式怎么写出来的？

2.用到的那些公式怎么得出的？

3.推理的过程如何描述的？

按照命题的表达形式划分为：

命题逻辑（第一章）

谓词逻辑（第二章）

两章所研究的共性问题：

命题的表达

公式

范式

推理

第一章.命题逻辑

本章要求：

1.掌握联结词的定义(含义及真值表定义)。

2.会命题符号化。

3.永真式的证明。

4.永真蕴涵式的证明,记住并能熟练应用常用公式。

5.等价公式的证明,记住并能熟练应用常用公式。

6.会写命题公式的范式, 能应用范式解决问题。

7.熟练掌握命题逻辑三种推理方法。

首先看看这一章的各个知识点之间的联系图

1－1.命题与命题的真值

注意学习以下知识点：

1.什么是命题？

2.什么是命题的真值？为什么定义两个真值？都用什么表示？

3.什么是简单命题与复合命题？

如何表示简单命题 (原子命题) ？用一个大写字母

如何表示复合命题 (分子命题)？用联结词

1－2 联结词 (这节是重点)

定义了六个逻辑联结词，分别是：

(1) 否定“Ø” (2) 合取“∧”

(3) 析取“∨” (4) 异或“ ”

(5) 蕴涵“®” (6) 等价“«”

要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义，会正确使用这些联结词。

Ø ：否定 表示“不”

∧：合取 表示“不但…,而且...”“并且”

∨：析取 表示“或者－可兼取的或”

：异或 表示“或者－不可兼取的或”

®：蕴涵 表示“如果…,则...”

«: 等价 表示“当且仅当”“充分且必要”

联结词的定义(包括真值表和含义).深入理解并记住下表

P	Q	P∧Q	P∨Q	P®Q	P«Q	P Q
F	F	F	F	T	T	F
F	T	F	T	T	F	T
T	F	F	T	F	F	T
T	T	T	T	T	T	F

特别要注意：

“或者”的二义性, 即要区分给定的“或”是“可兼取的或∨”还是“不可兼取的或 ”。

“®”的用法,它既表示“充分条件”也表示“必要条件”, 即要弄清哪个作为前件,哪个作为后件。

1-3 命题公式及命题符号化

注意学习以下知识点：

1.什么是常值命题？

2.什么是命题变元？如何表示？

3.什么是对命题变元作指派(给命题变元一个解释)？

4.什么叫合式公式？(递归定义)

5.会列命题公式的真值表。看下页真值表：

6.命题的符号化(这是难点)。

例如，列出P®(Q®R)的真值表

	P	Q	R	Q®R	P®(Q®R)
000	F	F	F	T	T
001	F	F	T	T	T
010	F	T	F	F	T
011	F	T	T	T	T
100	T	F	F	T	T
101	T	F	T	T	T
110	T	T	F	F	F
111	T	T	T	T	T

命题的符号化(这是难点)。

方法：先分析句子，看有哪些联结词，用联结词断句，找出原子命题，给原子命题设符号，用联结词联结原子命题。

注意以下几个句型的翻译：

例如 P:我有时间。 Q:我上街。 R:我在家。

P是Q的充分条件: 如果p,则Q。只要P,就Q。写成 P®Q

P是Q的必要条件: 仅当P,才Q。只有P,才Q。写成 Q®P

如果P,则Q;否则R. 写成 (P®Q)Ù(ØP®R)

或者我在家，或者我上街。写成 P Q

1-4 重言式与重言蕴涵式

注意学习以下知识点：

1.了解什么是重言式与重言蕴涵式？

2.会证明重言式与重言蕴涵式。

真值表方法

由前件真推出后件真

由后件假推出前件假

3.在理解基础上记住P43常用的重言蕴涵式。

重言蕴涵式是重点。

重言蕴涵式的应用：判断、证明、命题逻辑推理

重要的重言蕴涵式(如教材第43页所示)

I₁.P∧QÞP I₂. P∧QÞQ

I₃. PÞP∨Q I₄. QÞP∨Q

I₅. ØPÞP®Q I_6. QÞP®Q

I₇. Ø(P®Q)ÞP I₈. Ø(P®Q)ØÞQ

I₉. P,Q ÞP∧Q I₁₀. ØP∧(P∨Q)ÞQ

I₁₁. P∧(P®Q)ÞQ I_12. ØQ∧(P®Q)ØÞP

I_13. (P®Q)∧(Q®R)ÞP®R

I₁₄. (P∨Q)∧(P®R)∧(Q®R)ÞR

I_15. A®B Þ(A∨C)®(B∨C)

I_16. A®B Þ(A∧C)®(B∧C)

记住主要公式有I₁-I₁₃ 。

1-5 等价公式

等价公式是重点

注意学习以下知识点：

1.了解什么是等价公式？

2.会证明等价公式。

真值表方法

等价变换方法

3.在理解基础上记住P₄₃常用的等价公式。

等价公式在以下方面应用：

两个公式的相等的证明——等价变换

公式的化简

命题逻辑推理

重要的等价公式 记住下面公式

⑴对合律 E1 ØØPÛP

⑵交换律 E2 P∧QÛQ∧P E3 P∨QÛQ∨P

⑶结合律 E4 P∧(Q∧R)Û(P∧Q)∧R

E5 P∨(Q∨R)Û(P∨Q)∨R

⑷分配律 E6 P∧(Q∨R)Û(P∧Q)∨(P∧R)

E7 P∨(Q∧R)Û(P∨Q)∧(P∨R)

⑸底-摩根定律 E8 Ø(P∧Q) ÛØP∨ØQ E9 Ø(P∨Q) ÛØP∧ØQ

⑹幂等律 E10 P∨PÛP E11 P∧PÛP

⑺吸收律 P∨(P∧Q)ÛP P∧(P∨Q)ÛP

⑻ 同一律 P∨FÛP P∧TÛP

⑼ 零律 P∨TÛT P∧FÛF

⑽ 互补律 P∨ØPÛT P∧ØPÛF

⑾ E16 P®QÛØP∨Q

⑿ E18 P®QÛØQ®ØP

⒀ E20 P«Q Û(P®Q)∧(Q®P)

⒁ P«Q Û(ØP∨Q)∧(P∨ØQ)

⒂ E21 P«Q Û(P∧Q)∨(ØP∧ØQ )

为便于记忆，将等价公式(前10个)与集合论的公式比较，请看集合公式：

⑴ 对合律 ~~AÛA ~A表示A的绝对补集

⑵ 幂等律 A∪AÛA A∩AÛA

⑶ 结合律 A∪(B∪C)Û(A∪B)∪C

A∩(B∩C)Û(A∩B)∩C

⑷交换律 A∪BÛB∪A A∩BÛB∩A

⑸分配律 A∪(B∩C)Û(A∪B)∩(A∪C)

A∩(B∪C)Û(A∩B)∪(A∩C)

⑹ 吸收律 A∪(A∩B)ÛA A∩(A∪B)ÛA

⑺底-摩根定律 ~(A∪B)Û~A∩~B

~(A∩B)Û~A∪~B

⑻ 同一律 A∪ΦÛA A∩EÛA E表示全集

⑼ 零律 A∪EÛE A∩ΦÛΦ

⑽ 互补律 A∪~AÛE A∩~AÛΦ

1-6.范式

命题公式的规范形式

注意学习以下知识点：

1.析取范式与合取范式形式与写法。

2.小项和大项的概念及性质要很好掌握。

3.熟练掌握主析取范式与主合取范式形式与写法。

真值表方法

等价变换方法

4.范式的应用。

1-7. 命题逻辑推理 (必须熟练掌握)

注意学习以下知识点：

1.推理的定义

H1∧H2∧....∧Hn Þ C

则称C是H1，H2，…Hn的有效结论，简称结论。

2.推理规则的形式，已经如何用这些规则

规则P(引入前提规则)：

规则T(引入结论规则)：

3.三种推理方法：

直接推理、条件论证及反证法

注意推理格式

熟练掌握三种推理方法,进行逻辑推理。

会用三个推理规则:P,T,CP

例如:证明 ((A∧B)®C)∧ØD∧(ØC∨D) Þ ØA∨ØB

1.直接推理:

⑴ ØD P

⑵ ØC∨D P

⑶ ØC T ⑴⑵ I₁₀ ØQ, (P∨Q) ÞP

⑷ (A∧B)®C P

⑸ Ø(A∧B) T ⑶⑷ I₁₂ ØQ, P®Q Þ ØP

⑹ ØA∨ØB T ⑸ E₈ Ø(P∧Q)ØÛP∨ØQ

2.条件论证:适用于结论是蕴涵式.

结论等价变换成： ØA∨ØB Û AØ®B

⑴A P(附加前提)

⑵(A∧B)®C P

⑶ A®(B®C) T⑵ E₁₉

⑷ B®C T⑴⑶ I₁₁

⑸ØD P

⑹ØC∨D P

⑺ØC T ⑸⑹ I₁₀

⑻ ØB T ⑷⑺ I₁₂

⑼ A®ØB CP

3.反证法:

⑴ Ø(ØA∨ØB) P(假设前提)

⑵A∧B T⑴ E₉

⑶(A∧B)®C P

⑷ C T ⑵ ⑸ I₁₁

⑸ ØD P

⑹ØC∨D P

⑺ØC T ⑻⑼ I₁₀

⑻C∧ØC T ⑷ ⑺ I₉

第二章 谓词逻辑

命题逻辑的局限性

在第一章, 一个原子命题只用一个字母表示，而不再对命题中的句子成分细分。这样有一些逻辑问题无法解决。请看下面的例子。

例1.令Ｐ：小张是大学生。

Ｑ：小李是大学生。

从符号Ｐ、Ｑ中不能归纳出他们都是大学生的共性。

我们希望从所使用的符号那里带给我们更多的信息，比如可以看出他们的共性。这种想法在第一章是无法实现的。

例2.令 Ａ：所有自然数都是整数。

Ｂ：８是自然数。

Ｃ：８是整数。

这是著名的三段论推理，A是大前提，B是小前提，C是结论。显然，由Ａ和Ｂ可以推出结论Ｃ。

这个推理是有效的，但是这个推理在第一章也是无法实现的。

解决这个问题的方法：

在表示命题时，既表示出主语(主词)，也表示出谓语(谓词)，就可以解决上述问题。这就提出了谓词的概念。

本章要求：

1.准确掌握有关概念。

2.会命题符号化。

3.掌握常用的等价公式和永真蕴涵式。包括:

带量词的公式在论域内展开式,量词否定,量词辖域扩充, 量词分配公式。

4.会用等价公式求谓词公式的真值。

5.会写前束范式。

6.熟练掌握谓词逻辑推理。

2-1 基本概念

客体与客体变元

谓词：

一元谓词P(x)：表示客体x的属性。

n元谓词 P(x1,x2,…xn)：表示n个客体之间的关系。

命题函数

论域(个体域)：

一般论域

全总个体域

量词：

存在量词－$x

全称量词－"x

2-2 谓词公式及命题符号化

客体函数

注意:客体函数与谓词是不同的,不可混淆。

原子谓词公式

谓词合式公式(WFF)

量词的作用域(辖域)

自由变元与约束变元—变元在公式中出现的形式

命题的符号化(难点)

命题符号化过程中特别注意：

特性谓词：用来表示客体特性的谓词。

往往就是给定命题中量词后边的那个名词。

如 “所有自然数…..”、“有些大学生….”。这里的自然数、大学生就是特性谓词。

如何添加特性谓词，这是个十分重要的问题，这与前边的量词有关：

如果前边是全称量词，特性谓词后边是蕴含联结词“→”；

如果前边是存在量词，特性谓词后边是合取联结词“∧”。

要从理论上了解这样做的原因---见课件。

2-3谓词演算的等价式与蕴涵式

对谓词公式赋值：对命题变元和客体变元作指派。

永真式

永真蕴含式

等价公式

重要公式：

了解公式的证明过程

会应用这些公式

公式：

1.由命题公式推广出的公式

2.带量词的公式在论域内的展开式。设论域为{a₁, a₂,…a_n,}

"xA(x)ÛA(a₁)∧A(a₂)∧......∧A(a_n)

$xB(x)ÛB(a₁)∨B(a₂)∨......∨B(a_n)

这两个公式是证明其它公式的基础。

3.量词否定公式(2个)

4.量词辖域的扩充公式(8个)特别注意下面两个：

第7. "xA(x)→BÛ$x(A(x)→B)

第8. $xA(x)→BÛ"x(A(x)→B)

5.量词分配公式(4个)特别注意下面两个：

第3. $x(A(x)∧B(x))Þ$xA(x)∧$xB(x)

第4. "xA(x)∨"xB(x)Þ"x(A(x)∨B(x))

6.两个量词的公式(8个)

2-4 前束范式

1.前束范式定义：

2.前束范式的写法

2-5 谓词演算的推理理论 (这是本章重点内容)

本章的推理是在命题推理基础上实现的。

推理方法，推理规则(P、T、CP)同第一章。

所用公式：43页和70页的I₁~I₁₉，E₁~E₃₃

增加处理量词的规则：US、ES、EG、UG

注意这四个规则的形式、含义、作用和使用时的注意事项。特别是ES、UG。

推理时往往先去量词，使之没有客体变元了，就变成了命题逻辑推理。最后添加量词。

因此要特别注意：如何去量词？如何添加量词？

后面集合论将以数理逻辑作为工具、方法进行研究，所以它是集合论的基础。

集合论篇导学

（第三章、第四章、第五章）

勤能补拙是良训一分辛劳一分才

集合论是现代数学的基础。

现代集合论的观点已经渗透到数学分析、泛函分析、概率、函数论以及信息

论、排队论等现代数学各个领域。

集合的概念在全书中都要用到。

在计算机的理论与应用中，也都能找到集合的身影。

第三章 集合论基础

这一章的绝大部分内容同学们都熟悉，很多内容在高中都学习过。对于这部分内容，如果同学们在高中学得比较好,这里只是做个复习。

高中没有学习的内容：

集合的幂集

集合的对称差运算

包含排斥原理

研究的方法不同：这里以谓词演算为工具，研究集合理论。

本章要求：

1.掌握集合间三种关系的定义、谓词定义、证明方法。

2.掌握三个特殊集合，会求集合的幂集。

3.掌握集合的五种运算定义、计算方法及性质。

4.会用包含排斥原理解决集合计数问题。

3-1 基本概念

“集合”是最基本的概念。

本节涉及以下内容：

1.集合与元素

2.有限集合与无限集合

3.集合的表示方法：

枚举法:枚举出集合中的各个元素。

谓词描述法：用谓词描述集合中元素的特征。

3-2 集合间的关系

注意它们的谓词定义：

1. AÍBÛ"x(x∈A®x∈B)

2. A＝BÛ"x(x∈A«x∈B)

3. AÌBÛ"x(x∈A®x∈B)Ù$x(x∈BÙxÏA)

要求会判断，会证明这些关系。

3-3 特殊集合

1.全集 E

2.空集 Φ

3.集合的幂集(Power Set)

A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2^A。

P(A)={X|XÍA}

P(A)是集合，元素是A的所有子集。

3-4 集合的运算

五种运算：∩、∪、-、~、Å 。

A∩B={x|x∈A∧x∈B}

A∪B ={x|x∈A∨x∈B}

A-B ={x|x∈A∧xÏB}

~A =E-A={x|x∈E∧xÏA}={x|xÏA}

AÅB=(A-B)∪(B-A)={x|(x∈A∧xÏB)∨(x∈B∧xÏA)}

AÅB=(A∪B)-(A∩B)

掌握这五个运算的定义、计算、相关性质。

公式的证明可以用谓词演算，也可以用集合公式。

3-5. 包含排斥原理

有限集合的计数问题

|A∪B|=|A|＋|B|－|A∩B|

|A∪B∪C|=|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C|

第四章 二元关系

二元关系是一个很重要的概念。它在很多数学领域中都有应用。

计算机科学的如下理论都离不开关系 ：逻辑设计、数据结构、编译原理、软件工程、数据库理论、 计算理论、 算法分析、 操作系统等。

本章主要介绍：

关系的概念及表示方法

关系的性质

关系的运算：

关系的复合

逆关系

关系的闭包

三种重要关系:

等价关系

相容关系

次序关系

4-1 序偶与集合的笛卡尔积

这是这章的基础－－比较简单。

1.序偶与有序n元组

2.集合的笛卡尔积

要求掌握上面概念，会求集合的笛卡尔积。

4-2 关系及其表示法

一.基本概念

1.二元关系定义——就是特殊的集合——元素是序偶。

2.关系的定义域与值域

二. 关系的表示方法 (要求熟练掌握)

1.枚举法

2.谓词公式法

3.有向图法

4.矩阵表示法

三.特殊关系(掌握这些关系的各种表达形式的特点)

空关系Φ

完全关系(全域关系)

A上的恒等关系I_A

4-3 关系的性质

本节是这章的重点，因为后面经常都涉及到这些性质。

要求掌握定义,会判断(在有向图、矩阵上),会证明这些性质。

1.自反性 （reflexive）

R是A中自反的Û"x(xÎA®xRx)

2.反自反性 (irreflexive)

R是A中反自反的Û"x(xÎA®<x,x>ÏR)

3.对称性 (symmetric)

R是A上对称的Û"x"y((xÎAÙyÎAÙxRy) ®yRx)

4.反对称性 (antisymmetric)

R是A上反对称的Û"x"y((xÎAÙyÎAÙxRyÙyRx) ®x=y)

Û"x"y((xÎAÙyÎAÙx¹yÙ<x,y>ÎR)®<y,x>ÏR)

5. 传递性 (transitive)

R在A上传递Û"x"y"z((xÎAÙyÎAÙzÎAÙxRyÙyRz)®xRz)

注意：

上述性质的定义表达式都是蕴涵式,所以判断关系R性质时要特别注意使得性质定义表达式的前件为F的时候此表达式为T，即R是满足此性质的。 (自反和反自反性除外)

性质证明：都要从定义的蕴涵的前件入手，推出后件。

要多做一些例题，熟悉判断、证明过程。

4-4 关系的复合

这是由两个关系生成一种新的关系，即关系的复合运算。例如

这里a和c间就是舅舅和外甥的关系,记作 RoS, 称它是R和S的复合关系。

本节主要掌握：

复合关系定义

计算方法 (过河拆桥)和相关性质

4-5 逆关系

这节内容比较好理解。逆关系就是我们常说的反关系。

本节主要掌握：

逆关系定义

计算方法 (序偶元素前后次序颠倒)

相关性质

4-6 关系的闭包

本节内容比前两节稍微难理解一些。关键是对定义有比较深刻的理解。

学习时，对讲课时开始讲的那个例子好好体会一下—— 关系闭包的本质。

本节要求重点掌握：

闭包的定义(三个条件)

计算方法

性质

4-7 集合的划分与覆盖
本节内容与后面两节“等价关系”和“相容关系”有联系。

1.覆盖与划分定义

2.最小划分与最大划分

3.交叉划分

4.划分的加细

重点是划分的概念，会判断划分，会求划分。

4-8 等价关系与等价类
本节是本章的重点。是用得最多的关系。

要求熟练掌握：

一.等价关系

1.概念

2.等价关系的有向图的特点

二. 等价类

1.定义

2. 由等价关系图求等价类

3. 等价类性质

三. 商集

掌握：判断证明等价关系、会求等价类（商集）。

4-9 相容关系

相容关系与覆盖有联系

本节要求：

1.掌握定义

2.会求简化图和简化矩阵

3.会求相容类及最大相容类

4.会求完全覆盖

4-10 次序关系

次序关系也是常遇到的重要关系，它在计算机理论有直接的应用，并且它与第七章的格与布尔代数有密切关系。

要求：

1.掌握偏序关系概念

2.掌握全序(线序、链)概念

3.会画偏序集的哈斯图(Hasse图)

4.会求偏序集中的各个重要元素

第五章 函数

函数是一个基本的数学概念，应用的范围很广。

在计算机科学的理论中，如计算理论 、开关理论、编译理论、数据库理论、软件工程、计算机安全保密，操作系统等都用到函数。

这里是讲离散函数，与高等数学中的函数是有区别的。

本章主要介绍：

函数的概念、函数的复合、逆函数，以及在集合的基数中的应用。

重点掌握内容：

函数的概念、类型的判断和证明

函数的复合、求逆会计算、性质证明

了解的内容：

集合的特征函数

集合的基数概念、可数集概念

5-1 函数的基本概念

1.有关概念——函数是个特殊的关系。

2.函数的表示方法——同关系。

3.从X到Y函数的集合Y^X

4.两个特殊函数

常值函数

恒等函数：恒等关系IX是X到X函数。

5.两个函数相等(三个条件)

6.函数的类型：满射的、入射的、双射的

重点是掌握函数概念、会判断和证明函数的类型.

5-2 函数的复合

注意与关系复合相比较：相同之处、不同之处(表示方法不同)

1.定义——左复合表示

关系复合：RÍX×Y SÍY×Z

RoSÍX×Z

函数复合：Z←Y:g Y←X:f

Z←X:gof –g在f的左边。

2. 会计算复合函数——过河拆桥

3. 掌握函数复合的性质

5-3 逆函数

1.定义：f:X®Y是双射的函数，才可逆。

2.求逆函数－－同求逆关系

3.性质

5-4 集合的特征函数与模糊子集

本节作为函数的一个应用，只作为一般了解内容.

一.集合的特征函数

1.定义

是用函数表示集合的子集的特征(元素的特征)

2.性质

用集合的特征函数可以进行集合的运算和表示集合间的关系。

二.模糊子集

定义及表示方法

5-5 集合的基数

本节作为函数的一个应用，只作为一般了解内容.

1.了解自然数及自然数集合N的定义

2.了解集合的等势

3.了解基数类和基数

4.了解有限集合与无限集合定义

5.了解可数集合及其基数、可数集的判定、 至多可数集

6.了解不可数集合及其基数

代数系统篇导学

(第六章、第七章)

人的知识愈广，人的本身也愈臻完善

第六章 代数系统

代数系统也称之为代数结构、抽象代数、近世代数。

代数的构成＝运算对象 ＋ 运算

熟悉的代数实例：

初等代数：整数上的 ＋、－、 ×等运算

线性代数：矩阵上的 转置、＋、×、变换等运算

命题代数：命题上的 Ø、 Ú 、 Ù 等运算

集合代数：集合上的 ~、 È、 Ç 等运算

抽象代数—研究抽象对象的抽象运算的代数的共性。

将代数的研究引导到更高的层次—即抛开具体对象的代数。

近世代数对现代数学的发展有显著的影响，不仅为全部数学提供了有力的工具，而且在物理、化学、计算机科学(例如编码理论、安全保密理论、数据库理论等等)、控制论等学科中都有广泛的应用。

抽象代数可以培养学生的抽象逻辑思维能力和计算能力。培养同学分析问题和解决问题的能力。

本章要讨论的主要内容：

主要讨论：

代数结构(系统)的概念

运算的性质

代数结构(系统)的同态与同构

介绍一些典型的代数系统：半群、独异点、群、环、域等。

本章内容比较抽象，学习时要结合我们熟悉的具体例子，理解这些抽象概念，就比较容易了。

重点掌握的内容：

1. 二元运算的性质的判断、证明。

2.半群、独异点、群、环、域的概念。

3. 群的性质和群的证明，群中元素的阶。

4.交换群、循环群概念。

5. 子群的证明方法。

6. 同态、同构概念和证明，同构性质。

一般了解的内容：

1.同余关系。

2.置换群的概念。

6-1 代数结构(系统)的概念

1．n元运算定义

f：Xⁿ®Y是个映射，则称f 是X上的n元运算。

要深刻理解这个定义。

例如：自然数集合N上的“＋、×”

注意从这两个例子，容易理解二元运算f:X²®Y是个映射。进而理解用映射

f：Xⁿ®Y定义n元运算f 。

2.二元运算的运算表

如令X={S,R,A,L}，其中

S表示开始时的位置； R表示“向右转”；

A表示“向后转”； L表示“向左转”；

“o”表示转动的复合运算；其运算表如下：

这个表可以反应运算的特征。

要求：会画二元运算表。

能根据运算表判断运算有哪些性质(后面介绍)。

3.代数系统的概念

U=<X, f₁,f₂,…f_m> ( m≥1)，这里有X上的m个运算f₁,f₂,…f_m。

一个代数系统由两部分构成的：

运算对象的集合

若干个运算

例如 <N,+,×>，<I, -,+,－,×>、<P(E),~,∪,∩,Å>就是是我们熟悉的代数系统。

要深入了解代数系统的概念。

6-2 二元运算的性质

这一节是重要的一节。因为就是根据运算的性质将代数系统分成半群、独异点、群、交换群、环、域、格、布尔代数等。

讨论下面性质：<X,«>和<X,«, o>是代数系统, «,o 是二元运算：

1.封闭性："x,y∈X, 有 x«y∈X。

2.可交换性："x,y∈X, 有 x«y=y«x。

3.幂等性： "x∈X, 有 x«x=x。

4.有幺元： e∈X, "x∈X，有 e«x=x«e=x.

例如 加法＋：幺元为0；乘法×：幺元为1。

5.有零元: θ∈X, "x∈X，有θ«x=x«θ=θ.

例如乘法×：零元为0。

6.可结合性："x,y,z∈X, 有 (x«y)«z =x«(y«z)。

7.有逆元： x∈X, 有x-1∈X，使得 x-1«x=x«x-1=e

例如：＋：x-1=-x ; ×：x-1=1/x (x¹0)

8.可消去性： a∈X，"x, y∈X,有

(a«x=a«y)∨(x«a=y«a) Þ x=y.

9.分配律： «对o可分配："x,y,z∈X，有

x«(yoz)=(x«y)o(x«z) 或 (xoy)«z =(x«z)o(y«z)

10.吸收律："x,y∈X，有 x«(xoy)=x 和 xo(x«y)=x

例如,集合A，B有AÇ(AÈB)=A AÈ(A ÇB) =A

对这些性质要求会判断、会证明。

如何从运算表看运算“o”的性质：

给定X={S,R,A,, L} <X, o>,从运算表

看出满足下面性质：

1.满足封闭性。

2.可以验证满足结合律。

(RoL)oA=SoA=A

Ro(LoA)=RoR=A

(RoL)oA=Ro(LoA)

3.有幺元S.

4.每个元素可逆。

R^-1=L, L^-1=R, A^-1=A, S^-1=S.

6-3 代数系统的同态与同构

针对各种各样的代数系统，有些代数系统表面上看不同，实际它们运算的性质相似、或完全一样。

如何研究两个代数系统运算性质的相似性、相同性。这就是代数系统间的同态、同构问题。

本节稍微难理解一些，同学们要下点工夫。

1.同态、同构的定义

同态：设<X,«>,<Y, o>是代数系统，«和 o是二元运算，如果存在映射f:X®Y,使得对任何x₁ ,x₂∈X，有

f(x1«x2)=f(x1)of(x2) -----此式叫同态(同构)关系式

同构：如果f是双射的，称<X,«>与<Y, o>同构，记作X @ Y。

这个定义不太好理解。从两个方面理解这个定义：

首先理解同态和同构是两个代数系统之间有映射。

其次，该映射满足同态(同构)关系式。

另外对课件中同态例子、同构例子仔细捉摸一下。从而体会同态和同构的意义。

例1 <R⁺ ,×>： 是正实数R⁺上的乘法×；

<R, +> ： 是实数R上的加法+。

证明 <R⁺ ,×>与<R, +> 同构。

构造一个映射 f: R+®R

任何x∈R⁺, f(x)=lgx (是双射)

任何x,y∈R⁺, f(x×y)=lg(x×y)=lgx+lgy=f(x)+f(y)

所以<R⁺ ,×>与<R, +> 同构。

表面上看这两个代数系统完全不同，实际它们运算的性质却完全一样，都满足：可交换、可结合、有幺元、每个元素可逆。

2.代数系统间的同构关系@是等价关系(了解)

3.代数系统同构的性质(掌握)

通过本问题的讨论能够清楚了解同构的意义。

两个代数系统同构＝运算性质完全相同

4.同态性质的保持(了解)

两个代数系统同态 » 运算性质相似

5.同态核

本节要求：深入理解同态、同构的定义，会判断、证明两个代数系统同构。

6-4 同余关系

1.“置换性质”定义：

代数系统U＝<X,«>，«是X上的二元运算，设E是X上的等价关系，对任何x₁,x₂,y₁,y₂∈X,有

x₁Ex₂ Ù y₁Ey₂ Þ( x₁«y₁)E( x₂«y₂)

则称对于运算«，相对等价关系E, 具有置换性质。

例如：

2.同余关系

设U＝<X, «>是个代数系统, «是X上的二元运算,E是X中的等价关系，如果«相对E满足置换性质，则称E是代数系统U中的同余关系。

本节内容作为一般了解。

下面将要分别介绍几个典型的代数系统：

含有一个运算的：半群、独异点、群

含有二个运算的：环、域

含有三个运算的：布尔代数 (第七章介绍)

6-5 半群和独异点

一. 半群

1.定义：如果«在S上«满足封闭性、可结合性，则称<S,«>是半群。

例如：I是整数集合，R是实数集合。

<I,+>, <R,+>

<I,×>, <R,×>

<P(E),∩> ，<P(E), ∪> ， <P(E), Å>

2.交换半群

上面那些半群都是交换半群。

二. 独异点

1.独异点定义：设<M, «>是个半群,如果对«有幺元。则称<M, «>是个独异点，也称它是含幺半群。

<I,+>,<R,+>幺元是0 <I,×>,<R,×>幺元是1

<P(E),∩>,幺元是E <P(E), ∪>幺元是Φ

<P(E), Å>幺元是Φ 所以它们都是独异点。

2.交换独异点

上面那些独异点都是交换独异点。

本节主要掌握这几个概念、会证明半群和独异点。

下面将讨论群

6-6 群* Group

群是抽象代数中最重要的。

一. 概念

1.群的定义

2.有限群

二.群的性质

1.群满足可消去性

2. 群方程可解性

3. 群中无零元

4. 群中除幺元外，无其它幂等元。

5.定理6-6.5 <G,«>是个群，对任何a,b∈G,有

⑴ (a^-1)^-1 =a

⑵ (a«b)^-1=b^-1«a^-1

6. 有限群的运算表的特征(见下面表)

三.群的阶与群中元素的阶

注意：这两个“阶”是不同的概念。

1.群的阶：<G,«>是群,如果K[G]=n,

则称<G,«>是n阶群,如果K[G]是无限的,

则称<G,«>是无限阶群。

例如；<X, o>是4阶群：

R向右转，L向左转，

A向后转，S开始位置。

“o”是转动的复合运算。

例如，实数R上的加法+。

群<R, +>的阶是无限的。

2 .群中元素的阶

定义：设<G,«>是个群，a∈G，如果存在最小的正整数n，使得an=e, 则称a的阶是n。否则就称a的阶是无限的。

例：群<X, o>：R向右转，L向左转， A向后转，S开始位置。

“o”是转动的复合运算。

R⁴=S R⁸=S R¹²=S

L⁴=S L⁸=S

A²=S A⁴=S A⁶=S

R的阶是4，L的阶是4， A的阶是2， S的阶是1，

例，群<R, +>中除了幺元0以外，其它实数的阶是无限的。

本节要求掌握：

1.有关概念。

2.群的性质。

3.会证明群。

6-7. 特殊群

一.交换群 (阿贝尔群 、Abel群)

群<G, «>的运算«可交换。

二.循环群

例子:群<X, o>中：

A=R² L=R³ S=R⁴

所以 X={R,A,L,S}={R,R²,R³,R⁴} R⁵ =R 出现了循环。

1.定义：设<G,«>是群，如果存在一个元素g∈G，使得对每个x∈G， 都存在整数i，有x=gⁱ，则称<G,«>是个循环群.并称g是G的生成元。

2.循环周期:

就是生成元的阶。

3．两个重要的循环群：

<N₄,+₄> N₄ ={0,1,2,3}={1^4,1,1²,13} 1⁴ =0 循环周期是4.

<I,+> I={…-3,-2,-1,0,1,2, 3, ...}

I={… 1^-3,1^-2,1^-1,10,1¹ ,1²,1³ ...}循环周期是无限的.

定理：设<G,«>是个以g为生成元的循环群, 则

⑴若它的循环周期是无限的，则<G,«>与<I,+>同构。

⑵若它的循环周期是k(有限的),则<G,«>与<N_k,+_k>同构。

三.置换群

1.置换

定义:设S={x₁ ,x₂,... ,x_n}是个有限集合, 从S到S的一个双射称之为S上的一个置换. 称|S|为置换的元数. 并表示为:

这个p就是S上的一个 n元置换。

例. S={1,2,3}, 可以构成如下六个置换：

2. 置换的复合运算

既可以把置换看成是关系, 也可以看成是函数, 所以定义两个复合运算:¨ -- 右复合, o -- 左复合. 例如:

3. 置换群定义

定义：S是有限集合, 令|S|=n, 由Sn中的若干个置换构成的群, 称之为S上的置换群. 并称它是n元置换群.

例1中，S3={p1 ,p2 ,p3, p4 ,p5 ,p3}时 , “¨”与“o”的运算表

<{p₁},¨>, <{p₁,p₂},¨>, <{p₁,p₃},¨>, <{p₁,p₄},¨>,<{p₁ ,p₅ ,p₆},¨>以及< S₃ , ¨>

和< S₂ , o >都是置换群.

本节要求：

掌握交换群的概念和证明。

掌握循环群的概念和证明，证明主要是指出它的生成元。

置换群作为一般了解。

6-8 子群及其陪集

一. 子群定义：

设<G,«>是群, S是G的非空子集，如果<S,«>满足：

⑴ 任何a,b∈S 有a«b∈S, (封闭)

⑵ 幺元 e∈S, (有幺元)

⑶ 任何a∈S 有a^-1∈S, (可逆)

则称<S,«>是<G,«>的子群。

子群就是群中之群。

例如<I,+>是<R,+>的子群。

要求会判断子群，会证明子群。

二.平凡子群与真子群

设<G,«>是群，<{e},«>和<G,«>也是<G,«>的子群。称之为平凡子群。其余真子集构成的子群称之为真子群。

三.证明子群的方法(四个)

方法1.用子群的定义，即证明运算在子集上满足封闭、有幺元、可逆。

方法2. 设<G,«>是群, S是G的非空子集，如果<S,«>满足：

⑴ 任何a,b∈S 有a«b∈S, (封闭)

⑵ 任何a∈S 有a-1∈S, (可逆)

则<S,«>是<G,«>的子群。

方法3. 设<G,«>是群, B是G的有限子集,如果«在B上满足封闭性，则<B,«>是<G,«>的子群。

方法4. 设<G,«>是群, S是G的非空子集，如果任何a,b∈S 有a«b-1∈S, 则<S,«>是<G,«>的子群。

最基本的是子群定义。要求同学至少会用子群定义证明子群。

四. 子群的陪集

在证明关于子群的阶数的Lagrange定理时，用到子群的陪集。

1.定义：设<H,«>是群<G,«>的子群，a∈G，定义集合:

aH={a«h| h∈H}

Ha={h«a| h∈H}

则称aH(Ha)为a确定的H在G中的左(右)陪集。

这里要求同学们知道这个概念。能看懂Lagrange定理证明过程即可。

五. 子群的阶数--拉格朗日定理(Lagrange定理)

设<G, «>是有限群，|G|=n, <H, «>是<G, «>的任意子群，且|H|=m, 则 n=km (k∈I)。

拉格朗日定理说明了n 阶群的子群的阶数是n的因子。

例 N₆={0,1,2,3,4,5}， 群<N₆,+₆>的运算表如图：

0 1 2 3 4 5

令H₁={0}

H₂={0,3}

H₃={0,2,4}

从<H₁,+₆>, <H₂,+₆ > ,<H₃ ,+₆>

的运算表看出它们是<N₆,+₆>

的子群。而且它们的阶分别

是1，2，3阶，阶数是6的因

子。

推论1.：<G,«>是n阶群，则任意a∈G，a的阶必是n的因子且aⁿ =e。

推论2.：<G, «>是素数阶群， 则它无非平凡子群，且它必是循环群。

要求同学会应用Lagrange定理及其推论。

6-9. 环与域

下面讨论有两个运算的代数系统。

一. 环 (Ring)

1.定义:给定代数系统<R,+, ·>, 若R上二元运算+和 ·满足:

⑴ <R,+>是交换群。

⑵ <R,·>是半群。

⑶ ·对+可分配。即对任何a,b,c∈R,有

a·(b+c)=(a·b)+(a·c)

(a+b)·c =(a·c)+(b·c)

称<R,+, ·>是个环。

注意：这里的R是Ring的字头，不一定是实数集合。

+ 也不一定是加法；·也不一定是乘法。

例如：<I,+, ·>, <R,+,·> 其中+和 · 分别是加法和乘法，是环。

2. 环的运算法则

这些运算法则与我们习惯的代数运算法则类似。好理解.

3. 可交换环和含幺环

设<R,+,·>是环, 若<R,·>是交换半群,则称它是可交换环。若<R,·>是含幺半群(独异点),则称它是含幺环。

例如：<I,+,·>, <R,+,·>分别是整数和实数上的加法+和乘法·构成的环, 它们是可交换环也是含幺环。

4. 整环；设<R,+,·> 满足：

⑴ <R,+>是交换群。

⑵ <R,·>是可交换独异点。

⑶ · 对+可分配。

⑷ 无零因子 (如果a·b=0 ，则要么a=0 要么b=0 )

例如：<I,+, ·>, <R,+,·>是整环。

二. 域 (Field)

定义：设<F,+, ·>是个代数系统，K[F]≥2，如果F上二元运算+和 ·满足：

⑴ <F,+>是交换群。

⑵ <F-{0},·>是交换群。

⑶ · 对+可分配。

称<F,+,·>是个域。

例如：<R,+,·>其中+和 · 分别是实数R上的加法和乘法,

是域。而<I,+,·>却不是域。

本节要求掌握这几个环和域的定义，理解这些概念。会判定即可。

第七章 格和布尔代数

布尔代数是计算机逻辑设计的基础。

7-1 格 (Lattice)

一.概念

1. 格的定义

<A,≤>是偏序集，如果任何a,b∈A，使得{a,b}都有最大下界和最小上界，则称<A,≤>是格。

下面两个偏序中，<B,≤> 不是格，<C,≤> 是格。

2. 由格诱导的代数系统

定义二元运算∨和∧：设<A, ≤>是格, "a,b∈A，

a∨b=LUB {a,b}, {a,b}的最小上界.Least Upper Bound (∨-并运算)

a∧b=GLB {a,b}, {a,b}的最大下界.Greatest Lower Bound (∧-交运算)

称<A,∨,∧>是由格<A,≤>诱导的代数系统.

3. 子格：设<A,≤>是格, <A,∨,∧>是由<A,≤>诱导的代数系统。B是A的非空子集，如果∧和∨在B上封闭，则称<B, ≤>是<A, ≤>的子格。

二. 格的对偶原理

格的对偶原理：设P是对任何格都为真的命题，如果将P中的≤换成≥，∧换成∨，∨换成∧，就得到命题P’ , 称P’为P的对偶命题，则P’对任何格也是为真的命题。

三. 格的性质

有9个性质。了解下面这些主要性质：

• ∨和∧都满足交换律。即 a∨b=b∨a，a∧b=b∧a.

• ∨和∧都满足幂等律。即 a∨a=a a∧a=a

• ∨和∧都满足结合律。即

(a∨b)∨c =a∨(b∨c) ， (a∧b)∧c =a∧(b∧c) .

• ∨和∧都满足吸收律。即 a∨( a∧b) =a， a∧(a∨b) =a .

• a≤bÛ a∨b=b Û a∧b=a

四.格的同态与同构

同构格的哈斯图是同构的图。

具有一、二、三个元素的格分别同构于含有一、二、三个元素的链。

具有四个元素的格分别同构于下面两种格形式之一：

具有五个元素的格分别同构于下面五种格形式之一：

7-2 几个特殊格

一. 分配格

1. 定义： <A,∨,∧>是由格<A,≤>诱导的代数系统。如果对"a,b,c∈A，有

a∨(b∧c) =(a∨b)∧(a∨c) ，

a∧(b∨c)= (a∧b)∨(a∧c)

则称<A,≤>是分配格。

例 <P(E),∪,∩>是分配格。

2. 二个重要的有五个元素的非分配格：

其哈斯图如下：

3.分配格的判定：一个格是分配格的充分且必要条件是在该格中没有任何子格与上述两个五元素非分配格之一同构。

4. 分配格的性质

二. 有界格

1. 格的全上界1与全下界0

2. 有界格定义

三. 有补格

1. 元素的补元：设<A,≤>是个有界格，a∈A, 如果存在 b∈A, 使得

a∨b=1 a∧b=0 则称a与b互为补元。

例：下图中a的补元是b,c; b的补元是a,c;

c的补元是a,b。

2. 有补格：

一个有界格中，每个元素都有补元。

四. 布尔格

有补格又是分配格。

布尔格中每个元素都有唯一补元，元素a的补元记作 。

本节要求掌握：

这几个特殊格的定义；

了解它们的性质；

会判断这些格。

7－3 布尔代数

一. 定义

由布尔格<B, ≤>诱导的代数系统<B, ∨, ∧,¯>称之为布尔代数。

二. 布尔代数的性质(10个)

掌握这些性质。(与集合运算的性质对照记忆)

三. 布尔代数的同构

Stone钻石定理

推论1. 任何有限布尔代数的元素个数为2ⁿ (n=1,2,3,…)

因为|P(M)|= 2ⁿ 其中|M|=n

推论2. 两个有限布尔代数同构的充分且必要条件是元素个数相同。

要求理解并会应用这个定理和推论。

7-4.布尔表达式

1. 布尔表达式概念(类似命题公式的合式公式)

2. 布尔表达式的范式

重点掌握两个元素的布尔代数的布尔表达式的范式－－类似命题公式的主析取范式合主合取范式。

图论篇导学

(第八章)

读书而不能运用，则所读书等于费纸。

——华盛顿

第八章 图论

图论的起源可以追溯到1736年欧拉关于哥尼斯堡“七桥问题”的研究。本世纪三十年代以后，由于科学技术发展对离散数学模型提出了迫切的要求，图

论才成为一门独立的学科。现在它已经广泛地应用于物理、化学、电子学、通讯科学、计算机科学、经济学、语言学、心理学等各个领域。近年来，图论的发展迅速，并陆续出现拓扑图论、代数图论、极图理论、随机图论等新的研究方向。

本章内容特点:

概念很多, 而且有些概念很相近,容易弄错,要特别仔细。

内容直观，也不那么抽象，容易理解。

证明多属于构造型的，即把要证明的结论直接构造出来。

8-1.图的基本概念

1.准确掌握下面概念：

图的定义, 有向边,无向边,平行边,环；

邻接点,邻接边, 孤立结点；

有向图, 无向图,简单图,混合图,零图,平凡图,多重图；

完全图,子图, 生成子图,补图；

结点的度, 结点的出度, 结点的入度,结点度数序列；

图的最大度Δ(G),最小度δ(G)。

2.深入了解无向图所有结点度数总和与边数的关系,有向图出度和与入度

和的关系。

3.会画图的生成子图、补图。

4.掌握图的同构的概念，会判定同构的图。

8-2. 路与回路

1.准确掌握下面概念：路,回路,迹,闭迹,通路,圈。

2.掌握无向图的连通性:

连通图,连通分支,连通分支数W(G),

点割集,割点,点连通度k(G),

边割集,割边(桥),边连通度λ(G)

3.掌握有向图的连通性:

可达性, u到v的距离d<u,v> ，图的直径D

强连通,单侧连通,弱连通 .(会判断这些连通性)

强分图,单侧分图,弱分图.(会求这些分图)

8-3. 图的矩阵表示

1.邻接矩阵A:结点与结点之间的邻接关系矩阵.

由A判断:各结点的度, 有向图结点出,入度.

由Ak可求一个结点到另一结点长度为k的路条数.

2.可达矩阵P:结点u到结点v的可达性的矩阵.

用P可以判定:各结点的度. 有向图的强分图.

3.关联矩阵M:是结点与边的关联关系矩阵.

用M判定:各结点的度

要求会求这些矩阵，以及由这些矩阵判断图的特征。

8-4.带权图的最短路与关键路

本节内容是补充的，作为一般了解。不作为期末考核范围。

8-5. 欧拉图与汉密尔顿图

1. 概念：欧拉路,欧拉回路,欧拉图

2.判定:

有欧拉路的充要条件:无或有两个奇数度的结点.

有欧拉回路的充要条件:所有结点度数均为偶数.

3.概念：汉密尔顿路,汉密尔顿回路,汉密尔顿图

4.汉密尔顿图的判定:

必要条件:V的任何非空子集S,有W(G-S)≤|S|

充分条件:每对结点的度数和≥|V| =n

本节要求：会画、会判定以及简单应用欧拉图与汉密尔顿图。

8-6 二部图

本节内容是补充的，作为一般了解。知道K_3,3就可以了。

8-7 平面图

1.掌握概念：平面图的定义,平面的边界,

2.掌握平面图所有面的边界总长与边数的关系。

3.掌握欧拉公式: v-e+r=2

4.掌握两个重要的非平面图K₅或K_3,3。

5.掌握判定平面图的:

必要条件: e≤3v-6

充要条件:G不含与K₅或K_3,3在2度结点内同构子图。

8-8 对偶图与着色

1.了解对偶图、自对偶图的定义.

2.会画平面图的对偶图。

3.了解图G的正常着色、G的着色数χ(G) 。

4.掌握G着色方法:(韦尔奇.鲍威尔法)，会对图正常着色。

5.会应用着色解决一些实际问题——着色的应用。

8-9 树与生成树

树是图论中的重点内容

1.掌握树的基本定义、6个等价的定义、以及它们之间的相互证明。

其中最主要的结论是：树是连通无回路, e=v-1 。

2. 掌握分支结点, 叶结点的概念

3.会求图的生成树

4.会用Kruskal算法(避圈法)画带权图的最小生成树。

8-10. 根树及其应用

本节也是重点。

1.掌握概念：根树及相关概念, m叉树,完全 m叉树,有序树，带权二叉

树，最优树。

2. 重要公式：完全m叉树 (m-1)i=t-1 (会证明、会应用此公式)

3. 会将m叉树变成二叉树

4. 会画最优树

5. 会设计前缀码