离散数学期末复习大纲.PPT

资源描述

《离散数学期末复习大纲.PPT》由会员分享，可在线阅读，更多相关《离散数学期末复习大纲.PPT（153页珍藏版）》请在金锄头文库上搜索。

1、离散数学期末总复习1.复习时注意准确掌握每个概念准确掌握每个概念灵活应用所学定理灵活应用所学定理注意解题思路清晰注意解题思路清晰证明问题时证明问题时, ,先用反向思维先用反向思维( (从结从结论入手论入手) )分析问题分析问题, ,再按正向思维再按正向思维写出证明过程写出证明过程.2.全书知识网络：全书知识网络：图图论论篇篇同构同构同构同构格与布尔代数格与布尔代数半群半群,独异点独异点,群群,环环,域域代数系统篇代数系统篇n 元运算元运算命题逻辑命题逻辑谓词逻辑谓词逻辑集合初步集合初步二元关系二元关系函函数数集合论篇集合论篇数理逻辑篇数理逻辑篇3.总复习复习重点复习

2、重点 (注注: 标有标有*的内容的内容,对网络学院学生不作要求对网络学院学生不作要求)第一章第一章命题逻辑命题逻辑1.联结词的定义联结词的定义(含义及真值表定义含义及真值表定义).2.会命题符号化会命题符号化.3.永真式的证明永真式的证明.4.永真蕴涵式的证明永真蕴涵式的证明,记住并能熟练应用常用公式记住并能熟练应用常用公式.5.等价公式的证明等价公式的证明,记住并能熟练应用常用公式记住并能熟练应用常用公式.6.会写命题公式的范式会写命题公式的范式, *能应用范式解决问题能应用范式解决问题.7.熟练掌握命题逻辑三种推理方法熟练掌握命题逻辑三种推理方法.4.第二章第二章谓词逻辑谓词逻辑1.准

3、确掌握有关概念准确掌握有关概念.2.会命题符号化会命题符号化.(如如P60题题(2)3.掌握常用的等价公式和永真蕴涵式掌握常用的等价公式和永真蕴涵式.包括包括: 带量词的公式在论域内展开式带量词的公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充, 量词分配公式量词分配公式.4.会用等价公式求谓词公式的真值会用等价公式求谓词公式的真值.(如如P66题题(3)*5.会写前束范式会写前束范式6.熟练掌握谓词逻辑推理熟练掌握谓词逻辑推理.第三章第三章集合论初步集合论初步1.集合的表示集合的表示,幂集幂集,全集全集,空集空集.2.集合的三种关系集合的三种关系(包含包含,相等相等,真包含真

4、包含)的定义及证明的定义及证明.3.集合的五种运算及相关性质集合的五种运算及相关性质.*4.应用包含排斥原理应用包含排斥原理.5.第四章第四章二元关系二元关系1.关系的概念关系的概念,表示方法表示方法.2.二元关系的二元关系的性质的定义性质的定义, 熟练掌握性质的判断及证明熟练掌握性质的判断及证明.3.掌握关系的复合掌握关系的复合,求逆及闭包运算求逆及闭包运算(计算方法及有关性质计算方法及有关性质)4.掌握等价关系的判断掌握等价关系的判断,证明证明,求等价类和商集求等价类和商集.*4.掌握相容关系定义掌握相容关系定义,简化图和简化矩阵简化图和简化矩阵,相容类相容类,最大相最大相容类容类,完

5、全覆盖完全覆盖.5.偏序关系的判断偏序关系的判断,会画会画Hasse图图,会求一个子集的极小会求一个子集的极小(大大) 元元,最小最小(大大)元元,上界与下界上界与下界,最小上界及最大下界最小上界及最大下界.第六章第六章函数函数1.函数的定义函数的定义.2.函数的类型函数的类型, 会判断会判断,会证明会证明.3.会计算函数的复合会计算函数的复合(左复合左复合),求逆函数求逆函数.知道有关性质知道有关性质.*4.了解集合的特征函数了解集合的特征函数,了解集合的基数了解集合的基数,可数集合可数集合.6.第六章第六章代数系统代数系统1.掌握运算的定义掌握运算的定义.2.熟练掌握二元运算的性质的判

6、断及证明熟练掌握二元运算的性质的判断及证明.3.掌握代数系统的同构定义掌握代数系统的同构定义,会证明会证明.了解同构性质的保持了解同构性质的保持.4.了解半群了解半群,独异点独异点,*环和环和*域的概念域的概念.5.熟练掌握群熟练掌握群,子群子群,交换群交换群(会证明会证明), 了解循环群了解循环群.*6,子群的陪集子群的陪集, Lagrange定理及其推论定理及其推论,(会应用会应用).*第七章第七章格与布尔代数格与布尔代数* 1.掌握格的定义掌握格的定义,了解格的性质了解格的性质.* 2.会判断格会判断格,分配格分配格,有补格和布尔格有补格和布尔格,* 3.重点掌握两个元素的布尔代数的性

7、质重点掌握两个元素的布尔代数的性质(10个个).* 4.会写两个元素的布尔表达式的范式会写两个元素的布尔表达式的范式.(实质是第一章的实质是第一章的主析取和主合取范式主析取和主合取范式).7.第八章第八章图论图论1.掌握图的基本概念掌握图的基本概念.(特别注意相似的概念特别注意相似的概念)2.熟练掌握图中关于结点度数的定理熟练掌握图中关于结点度数的定理. (会应用会应用)3.无向图的连通性的判定无向图的连通性的判定,连通分支及连通分支数的概念连通分支及连通分支数的概念.4.有向图的可达性有向图的可达性,强连通强连通,单侧连通和弱连通的判定单侧连通和弱连通的判定.求强求强分图分图,单侧分图和

8、弱分图单侧分图和弱分图.5.会求图的矩阵会求图的矩阵.6.会判定欧拉图和汉密尔顿图会判定欧拉图和汉密尔顿图.*7.会判定平面图会判定平面图, 掌握欧拉公式掌握欧拉公式.*8.了解对偶图了解对偶图.9.掌握树的基本定义掌握树的基本定义,v和和e间的关系式间的关系式.会画生成树会画生成树,会求会求最最小生成树小生成树.根树的概念根树的概念,完全完全m叉树的公式叉树的公式,会画最优树会画最优树,*会会设计前缀码设计前缀码.8.总复习复习重点复习重点第一章第一章命题逻辑命题逻辑1.联结词的定义联结词的定义(含义及真值表定义含义及真值表定义).2.会命题符号化会命题符号化.3.永真式的证明永真式的

9、证明.4.永真蕴涵式的证明永真蕴涵式的证明,记住并能熟练应用常用公式记住并能熟练应用常用公式.5.等价公式的证明等价公式的证明,记住并能熟练应用常用公式记住并能熟练应用常用公式.6.会写命题公式的范式会写命题公式的范式, *能应用范式解决问题能应用范式解决问题.7.熟练掌握命题逻辑三种推理方法熟练掌握命题逻辑三种推理方法.9.第一章第一章命题逻辑命题逻辑1.1.联结词联结词定义了六个逻辑联结词，分别是：定义了六个逻辑联结词，分别是： (1) 否定否定“ ” (2) 合取合取“” (3) 析取析取“” (4) 异或异或“ ” (5) 蕴涵蕴涵“” (6) 等价等价“”要熟练掌握这五个联结词在自

10、然语言中所表示的含义以要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。及它们的真值表的定义。：否定：否定表示表示“不不”：合取：合取表示表示“不但不但,而且而且.”“并且并且”：析取：析取表示表示“或者可兼取的或或者可兼取的或” ：异或：异或表示表示“或者不可兼取的或或者不可兼取的或”：蕴涵：蕴涵表示表示“如果如果,则则.” : 等价等价表示表示“当且仅当当且仅当”“充分且必要充分且必要”可以将这六个联结词看成六种可以将这六个联结词看成六种“运算运算”。10.联结词的定义联结词的定义(包括真值表和含义包括真值表和含义).特别要注意：特别要注意：“或者或者”的

11、二义性的二义性, 即要区分给定的即要区分给定的“或或”是是“可兼取的或可兼取的或”还是还是“不可兼取的或不可兼取的或 ”。“”的用法的用法，它既表示，它既表示“充分条件充分条件”也表示也表示“必要条件必要条件”,”,即要弄清哪个作为前件即要弄清哪个作为前件, ,哪个作为后件哪个作为后件. . P Q PQ PQ PQ PQ P Q F F F F T T F F T F T T F T T F F T F F TT T T T T T F 11.2.会命题符号化会命题符号化. 例如例如 P:我有时间我有时间. Q:我上街我上街. R:我在家我在家. 表示表示P是是Q的充分条件的充分条件: 如果

12、如果p,则则Q. 只要只要P,就就Q. PQ 表示表示P是是Q的必要条件的必要条件: 仅当仅当P,才才Q. 只有只有P,才才Q. QP 如果如果P,则则Q;否则否则R. (PQ) ( PR)3.永真式的证明永真式的证明. 方法方法1.列真值表列真值表. ( R (QR)(PQ)P 方法方法2.用公式的等价变换用公式的等价变换,化简成化简成T.例如证明例如证明( R (QR)(PQ)P是永真式是永真式.证证:上式上式( R ( Q R)(PQ)P(PQP Q)(R (QR) (PQ)P (公式的否定公公式的否定公式式)(R (QR) (PQ)P) (结合律结合律) (R Q) (RR) (PP)

13、 ( QP) (分配律分配律)(R Q) ( QP) R QQP T (互补互补,同一律同一律)12.4.永真蕴涵式的证明永真蕴涵式的证明, 记住常用的公式记住常用的公式. 永真蕴涵式永真蕴涵式: AB是永真式是永真式,则称则称A永真蕴涵永真蕴涵B. (AB) 方法方法1.列真值表列真值表. 方法方法2.假设前件真假设前件真,推出后件真推出后件真. (即直接推理即直接推理) 方法方法3.假设后件假假设后件假,推出前件假推出前件假.(即反证法即反证法)例证明例证明(P(QR)(PQ)(PR)是永真蕴涵式是永真蕴涵式.证证:假设后件假设后件(PQ)(PR)假假, 则则PQ为为T, PR为为F,于于

14、是是P为为T,R为为F, 进而又得进而又得Q为为T. 所以所以QR为为F, 所以前件所以前件P(QR)为为F. 所以所以(P(QR)(PQ)(PR)为为永真式永真式. 对于给定一个题对于给定一个题,究竟是用哪种方法究竟是用哪种方法,原则上哪种都可以原则上哪种都可以.但是哪个方法简单但是哪个方法简单,要根据具体题而定要根据具体题而定.A B A B F F T F T T T F F T T T13.5.等价公式的证明等价公式的证明,记住常用的公式记住常用的公式. 方法方法1.列真值表列真值表. 方法方法2.用公式的等价变换用公式的等价变换. 例如例如:证明证明 P(QR)(PQ)R P(QR)

15、P ( Q R) ( PQ) R (P Q)R (PQ)R注意注意:不论是证明永真蕴涵式不论是证明永真蕴涵式,还是证明等价公式以及后边还是证明等价公式以及后边的求公式的范式的求公式的范式,命题逻辑推理命题逻辑推理,都应用都应用43页的公式。页的公式。必须记忆一些常用的公式必须记忆一些常用的公式如如:P43表中的表中的永真蕴涵式永真蕴涵式: I1, I3, I9, I10, I11, I12, I13, 等等价价公公式式: E1 E16, E18, E19 , E20, E21, 14.6.命题公式的范式命题公式的范式1)析取范式析取范式:A1A2.An (n1) Ai (i=1,2.n

16、)是是合取式合取式. 2)合取范式合取范式:A1A2.An (n1) Ai (i=1,2.n)是是析取式析取式.3)析取范式与合取范式的写法析取范式与合取范式的写法.4)小项及小项的性质小项及小项的性质. m3 m2 m1 m0 P Q PQ P Q PQ P Q 00 F F F F F T 01 F T F F T F 10 T F F T F F 11 T T T F F F15.6)大项及其性质大项及其性质. M0 M1 M2 M3 P Q PQ P Q PQ P Q 00 F F F T T T 01 F T T F T T 10 T F T T F T 11 T T T T T F

17、7)主析取范式主析取范式: A1A2.An (n1) Ai (i=1,2.n)小项小项. 8)主合取范式主合取范式: A1A2.An (n1) Ai (i=1,2.n)大项大项.16.9).会写主析取范式和主合取范式会写主析取范式和主合取范式.求下面命题公式的范式求下面命题公式的范式:A(P,Q,R) (PQ)R方法方法1.列真值表列真值表.主析取范式主析取范式A(P,Q,R) (PQ)R ( P Q R )( P QR )( PQR) (P QR )(PQR )主合取范式主合取范式A(P,Q,R) (PQ)R (P QR )( PQR )( P QR)P Q R (PQ)RF F F TF

18、F T TF T F FF T T TT F F FT F T TT T F FT T T T17.方法方法2.用公式的等价变换用公式的等价变换. 主析取范式主析取范式;A(P,Q,R) (PQ)R (PQ)R ( P Q)R ( P Q(R R)(P P)(Q Q)R) ( P QR) ( P Q R)(PQR) (P QR)( PQR)( P QR)( P Q R )( P QR )( PQR) (P QR )(PQR )主合取范式主合取范式:A(P,Q,R) (PQ)R (PQ)R ( P Q)R ( PR )( QR) ( P(Q Q)R )(P P) QR) ( PQR )( P Q

19、R)(P QR )18.已知已知A(P,Q,R)的主析取范式中含有如下小项的主析取范式中含有如下小项: m0,m3, m4,m5,m7求它的主合取范式求它的主合取范式.解解:A(P,Q,R)的主合取范式中含有大项的主合取范式中含有大项:M1 ,M2, M6A(P,Q,R)(PQ R )(P QR)( P QR)* 范式的应用范式的应用如如P39习题习题(7),(8): 安排工作安排工作(排课表排课表), 判断比赛名次判断比赛名次,携带携带工具箱工具箱, 19.7.会用三种推理方法会用三种推理方法,进行逻辑推理进行逻辑推理. 会用三个推理规则会用三个推理规则:P,T,CP例如例如:证明证明 (

20、AB)C) D( CD) A B1.直接推理直接推理: D P CD P C T I10 Q, (PQ) P (AB)C P (AB) T I12 Q, PQ P A B T E8 (PQ)P Q 20.(AB)C) D( CD) A B2.条件论证条件论证:适用于结论是蕴涵式适用于结论是蕴涵式. A B ABA P(附加前提附加前提)(AB)C P A(BC) T E19 BC T I11 D P CD P C T I10 B T I12 AB CP 21.(AB)C) D( CD) A B3.反证法反证法: ( A B) P(假设前提假设前提)AB T E9(AB)C P C T I11

21、D P CD P C T I10C C T I922. 第二章第二章谓词逻辑谓词逻辑1.准确掌握有关概念准确掌握有关概念.2.会命题符号化会命题符号化.(如如P60题题(2)3.掌握常用的等价公式和永真蕴涵式掌握常用的等价公式和永真蕴涵式.包括包括: 带量词的公式在论域内展开式带量词的公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充, 量词分配公式量词分配公式.4.会用等价公式求谓词公式的真值会用等价公式求谓词公式的真值.(如如P66题题(3)*5.会写前束范式会写前束范式6.熟练掌握谓词逻辑推理熟练掌握谓词逻辑推理.23. 第二章第二章谓词逻辑谓词逻辑1.准确掌握有关概念准

22、确掌握有关概念. 客体客体: 客体变元客体变元, 谓词谓词, 量词量词, 量词后的指导变元量词后的指导变元, 量词的辖域量词的辖域, 约束变元与自由变元约束变元与自由变元, 论域论域, 全总个体域全总个体域, 谓词公式谓词公式(WFF), 命题函数命题函数, 前束范式前束范式, 24.2.会命题符号化会命题符号化.(如如P60题题(2) 命题的符号表达式与论域有关。命题的符号表达式与论域有关。当论域扩大时，需要当论域扩大时，需要添加用来表示客体特性的谓词，称此谓词为添加用来表示客体特性的谓词，称此谓词为特性谓词特性谓词。特性谓词往往就是给定命题中量词后边的那个名词。特性谓词往往就是给定命题中量

23、词后边的那个名词。如如“所有所有自然数自然数.” .” 、“有些有些大学生大学生.”.”。如何添加特性谓词，这是个十分重要的问题如何添加特性谓词，这是个十分重要的问题，这与前这与前边的量词有关边的量词有关。如果如果前边是前边是全称量词全称量词，特性谓词后边是特性谓词后边是蕴含联结词蕴含联结词“”“”；如果如果前边是前边是存在量词存在量词，特性谓词后边是特性谓词后边是合取联结词合取联结词“”“”。另外有些命题里有的客体在句中没有明确的量词另外有些命题里有的客体在句中没有明确的量词 ,而在而在写它的符号表达式时写它的符号表达式时,必须把隐含的量词明确的写出来必须把隐含的量词明确的写出来.25

24、.例如例如金子闪光金子闪光,但闪光的不一定都是金子但闪光的不一定都是金子.设设: G(x):x是金子是金子. F(x):x闪光闪光. x(G(x)F(x)x(F(x)G(x) x(G(x)F(x)x(F(x)G(x) 没有大学生不懂外语没有大学生不懂外语. S(x):x是大学生是大学生. F(x):x外语外语. K(x,y):x懂得懂得y. x(S(x)y(F(y)K(x,y) x(S(x)y(F(y) K(x,y)有些液体可以溶解所有固体有些液体可以溶解所有固体. F(x):x是液体是液体.S(x):x是固体是固体.D(x,y):x可溶解可溶解y. x(F(x)y(S(y)D(x,y)每个大

25、学生都爱好一些文体活动。每个大学生都爱好一些文体活动。S(x):x x是大学生是大学生, ,L(x,y):x x爱好爱好y, y, C(x):x x是文娱活动，是文娱活动，P(x):x x是体育活动是体育活动. .) x(S(x)y(C(y)P(y) L(x,y) 26.3.掌握常用的等价公式和永真蕴涵式掌握常用的等价公式和永真蕴涵式.包括包括: 带量词的公式在论域内展开式带量词的公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充, 量词分配公式量词分配公式. 设论域为设论域为aa1 1,a,a2 2,.,a,.,an n ，则，则 1). 1). xA(x)xA(x)A(aA(a

26、1 1)A(a)A(a2 2).A(a).A(an n) ) 2). 2). xB(x)xB(x)B(aB(a1 1)B(a)B(a2 2).B(a).B(an n) ) 1). 1). xA(x)xA(x)x x A(x)A(x) 2). 2). xA(x)xA(x)x x A(x)A(x) 1). 1). xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 2). 2). xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 3). 3). xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 4). 4). xA(x)BxA(x)Bx(x(x)B)(x)B) 5). B 5

27、). B xA(x)xA(x)x(BA(x) x(BA(x) 27.6). B6). B xA(x)xA(x)x(BA(x)x(BA(x)7)7). . xA(x)BxA(x)B x(A(x)B)x(A(x)B)8)8). . xA(x)BxA(x)B x(A(x)B)x(A(x)B)1). 1). x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xB(x)xB(x)2). 2). x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xB(x)xB(x)3). 3). x(A(x)B(x)x(A(x)B(x) xA(x)xA(x) xB(x)xB(x)4). 4). x

28、A(x)xA(x) xB(x)xB(x) x(A(x)B(x)x(A(x)B(x)4.会用等价公式求谓词公式的真值会用等价公式求谓词公式的真值.(如如P66题题(3)例例设论域为设论域为1,2,A(x,y):x+y=xy, 求求x yA(x,y)的真值的真值.x yA(x,y) x y A(x,y)y A(1,y)y A(2,y)( A(1,1)A(1,2) ( A(2,1)A(2,2)(T T) (T F) T28.*5.将下面谓词公式写成前束范式将下面谓词公式写成前束范式( xF(x,y)yG(y)xH(x,y) (xF(x,y)yG(y)xH(x,y) (去去)xF(x,y) yG(y)

29、 xH(x,y) (摩根摩根)xF(x,y) y G(y) xH(x,y) (量词否定量词否定)xF(x,z) y G(y) tH(t,z) (变元换名变元换名)x y t(F(x,z) G(y) H(t,z) (辖域扩充辖域扩充)29.6.熟练掌握谓词逻辑推理熟练掌握谓词逻辑推理.1).注意使用注意使用ES、US、EG、UG的限制条件的限制条件,特别是特别是ES,UG2).对于同一个客体变元，既有带对于同一个客体变元，既有带也有带也有带的前提，去量的前提，去量词时，词时，应先去应先去后去后去，这样，这样才可以特指同一个客体才可以特指同一个客体 c.3).去量词时，该量词必须是公式的最

30、左边的量词，且此去量词时，该量词必须是公式的最左边的量词，且此量词的前边量词的前边无任何符号无任何符号，它的辖域作用到公式末尾。，它的辖域作用到公式末尾。下面的作法是错误的：下面的作法是错误的：正确作法正确作法: x xP P(x x) x xQ(x) P x xP P(x x) x xQ(x) P P P(c c) x xQ(x) US x xP P(x x) x xQ(x) T E或或 x xP P(x x)Q(c)ES x x P P(x x) x xQ(x) T E实际上实际上 x x的辖域扩充后的辖域扩充后 x( P P(x x)Q(x) T E 量词改成为量词改成为 x x P

31、 P(c c)Q(c) ES P P(c c)Q(c) TE30.下面的作法是错误的：下面的作法是错误的：正确作法正确作法: x xP(x) P P(x) P x xP(x) PP(x) P P(c) US P(c) US x P(x) T E实际上实际上中量词不是中量词不是 P(c) ESP(c) ES x x而是而是 x x x x y yP(x,y) P P(x,y) P x x y yP(x,y) PP(x,y) P x xP(x,c) ES P(x,c) ES y yP(c,y) USP(c,y) US令令P(x,y):yP(x,y):y是是x x的的生母，生母，显然显然是个假命题

32、是个假命题4).添加量词时，也要加在公式的最左边，添加量词时，也要加在公式的最左边，(即新加的量词即新加的量词前也无任何符号前也无任何符号！)且其辖域作用到公式的末尾。且其辖域作用到公式的末尾。例如下面作法是错误的例如下面作法是错误的: x xP P(x x)Q(c) P x xP P(x x) y yQ(y) EG31.例如例如.证明下面推理的有效性证明下面推理的有效性.证明证明: x(A(x)x(A(x) D(x)D(x) P P A(a) A(a) D(a)D(a) ES ES A(a) A(a) T T I I D(a)D(a) T T I I x(x(A(x)(B(x)A(x)(B

33、(x) C(x)C(x) P) P A(a)(B(a) A(a)(B(a) C(a)C(a) US ) US B(a) B(a) C(a)C(a) T ) T I I x(x(A(x)(C(x)D(x)A(x)(C(x)D(x) P ) P A(a)(C(a)D(a) A(a)(C(a)D(a) US) US C(a)D(a) T I C(a)D(a) T I C(a) T I C(a) T I B(a) T IB(a) T I A(a) A(a) B(a) T IB(a) T I x(A(x)x(A(x) B(x) EG B(x) EG 32.第三章第三章集合论初步集合论初步1.集合的表示

34、集合的表示,幂集幂集,全集全集,空集空集.2.集合的三种关系集合的三种关系(包含包含,相等相等,真包含真包含)的定义及证明的定义及证明.3.集合的五种运算及相关性质集合的五种运算及相关性质.*4.应用包含排斥原理应用包含排斥原理.33.第三章第三章集合论初步集合论初步基本概念基本概念:集合与元素集合与元素,子集与真子集子集与真子集, 空集空集, 全集全集, 幂集幂集, 并集并集, 交集交集, 相对补集相对补集(差集差集), 绝对补集绝对补集(补集补集)1.集合的表示集合的表示,元素与集合的属于关系元素与集合的属于关系. 集合的三种表示方法集合的三种表示方法: 枚举法枚举法:一一列出集合中的元

35、素一一列出集合中的元素. 谓词描述法谓词描述法:用谓词描述集合中元素的性质用谓词描述集合中元素的性质. 文氏图文氏图:用一个平面区域表示用一个平面区域表示. 2.集合的三种关系集合的三种关系(被包含被包含,相等相等,被真包含被真包含)的定义及证明的定义及证明. A B x(xAxB) A=B A B B Ax(xAxB) A BA B ABx(xAxB)x(xB x A) 34.3空集空集,全集全集, 幂集幂集空集空集:无元素的集合无元素的集合. x是矛盾式是矛盾式. (空集是唯一的空集是唯一的) 全集全集E:包含所讨论所有集合的集合包含所讨论所有集合的集合. (全集不唯一全集不唯一) xE

37、P()=( )解解:a) 因为任何集合因为任何集合A, 都有都有 A A= 所以所以 P() P()= b) 因为因为 A A , 即即P(A) P(A) 所以所以 P(A)P(A)= c) P(E)=, = P()=P( )= , P(E)-P() )=,-, =,36.例例2 证明各式彼此等价。证明各式彼此等价。 PQ ( PQ)(P Q) c)AB=B, AB=A, A B, B A.证明证明. AB=B x(xAB xB) x(x AB xB) (xAB x B)x(x A x B) xB) (xA xB) x B)x(x A x B) xB)x(x A xB) (x B xB)x(x

38、 A xB)x(xAxB) A Bx(xAxB)x(x Bx A)x(xBxA) B A 由由 AB=B 得得 A (AB)=A B A=A B 类似由类似由AB=A, 可以推出可以推出AB=B 所以所以 AB=B AB=A 从而证得从而证得AB=B, AB=A, A B, B A 彼此等价。彼此等价。 T37.例例3 证明证明: (A-B)-C=A-(BC)方法方法1. (A-B)-C=(A B) C=A( B C)=A (BC)=A-(BC)方法方法2.任取任取x(A-B)-C(xAx B)x CxA( x Bx C) xA ( xBxC)xA ( xBC) xAx BC xA-(BC)

39、所以所以(A-B)-C=A-(BC)例例4. 令全集令全集E为信息学院的学生的集合为信息学院的学生的集合, C表示计算机专表示计算机专业学生的集合业学生的集合,M表示学习了离散数学的学生的集合表示学习了离散数学的学生的集合,D表表示学习了数据结构课学生的集合示学习了数据结构课学生的集合,F表示一年级的学生的表示一年级的学生的集合集合.用集合的关系式表达下面句子用集合的关系式表达下面句子. “学习了离散数学和数据结构课的学生学习了离散数学和数据结构课的学生,一定是计算机一定是计算机专业的非一年级的学生专业的非一年级的学生”. 解解. (MD) (CF)38.例例4 .在什么条件下，下面命题为真

40、？在什么条件下，下面命题为真？a) (A-B)(A-C)=A解解.(A-B)(A-C)= (AB)(AC)=A(BC)= A(BC)=A-(BC)=A 所以满足此式的所以满足此式的充要条件充要条件是：是：ABC= b) (A-B)(A-C)=解解.(A-B)(A-C)= A-(BC)= 充要条件充要条件是：是：A BCc) (A-B)(A-C)=解解.(A-B)(A-C)= (AB)(AC)=A(BC)= A(BC)=A-(BC)= 充要条件充要条件是是: A BCd) (A-B) (A-C)=解解. 因为因为当且仅当当且仅当A=B ，才有，才有A B=所以满足此式的所以满足此式的充要条件充

41、要条件是是: A-B=A-C39.*例例5. 用谓词逻辑推理证明用谓词逻辑推理证明对任何集合对任何集合A、B、C，如果有，如果有A B且且 B C ，则，则A C。证明证明: x(xAxB)x(xB x A), x(xBxC)x(xC x B)x(xAxC) x(xC x A) x(xAxB)x(xB x A) P x(xAxB) T I x(xB x A) T I x(xBxC)x(xC x B) P x(xBxC) T I xAxB US xBxC US xAxC T I x(xAxC) UG xB x A ES xB T I x A T I xC T I xC x A T I x(xC

42、x A) EG x(xAxC) x(xC x A) T I40.*有有14位学生参加考试位学生参加考试,9位同学数学得了优位同学数学得了优;5位同学物理位同学物理得了优得了优;4位同学化学得了优位同学化学得了优;其中物理和数学都得优的同其中物理和数学都得优的同学有学有4人人;数学和化学都得优的同学有数学和化学都得优的同学有3人人;物理和化学都得物理和化学都得优的同学有优的同学有3人人;三门都得优的同学有三门都得优的同学有2人人;问没有得到优的问没有得到优的有多少人有多少人?恰有两门得优的同学有多少人恰有两门得优的同学有多少人?解解.令令A、B、C分别表示数学、物理、化学得优同学集合分别表示数学

43、、物理、化学得优同学集合.全集为全集为E. 于是有于是有 |E|=14 |A|=9 |B|=5 |C|=4 |AB|=4 |AC|=3 |BC|=3 |ABC|=2 |ABC|=|A|+|B|+|C|-|AB|-|BC|-|BC|+ |ABC|=9+5+4-4-3-3+2=10 于是得到优的人数是于是得到优的人数是10人人. 没有得到优的人数是没有得到优的人数是: 14-10=4 人人恰有两门得优的人数恰有两门得优的人数: (|AB|-|ABC|)+(|BC|-|ABC|)+(|BC|-|ABC|)=4-2+3-2+3-2=441. 第四章第四章二元关系二元关系1.关系的概念关系的概念,表示

44、方法表示方法.2.二元关系的二元关系的性质的定义性质的定义, 熟练掌握性质的判断及证明熟练掌握性质的判断及证明.3.掌握关系的复合掌握关系的复合,求逆及闭包运算求逆及闭包运算(计算方法及有关性质计算方法及有关性质)4.掌握等价关系的判断掌握等价关系的判断,证明证明,求等价类和商集求等价类和商集.*5.掌握相容关系的概念掌握相容关系的概念,关系图和矩阵的简化关系图和矩阵的简化,求相容类求相容类,最大相容类和完全覆盖最大相容类和完全覆盖.6.偏序关系的判断偏序关系的判断,会画会画Hasse图图,会求一个子集的极小会求一个子集的极小(大大) 元元,最小最小(大大)元元,上界与下界上界与下界,最小上

45、界及最大下界最小上界及最大下界. 注意本章证明题的证明过程的思路注意本章证明题的证明过程的思路42.一一. .关系的概念关系的概念, ,表示方法表示方法, ,三个特殊关系三个特殊关系. .1.集合的笛卡集合的笛卡尔尔积积 AB=|xAyB |A|=m,|B|=n |A |A|=m,|B|=n |AB|=mnB|=mn 设设A=0,1，B=a,b，求，求A B 。 A B=,2.二元关系的概念二元关系的概念定义定义1:设设A、是集合、是集合,如果如果 AB,则称则称R是一个从是一个从A到到 B的二元关系。如果的二元关系。如果 R AA,则称则称R是是A上上的二元关系的二元关系. 如果如果|A

46、|=m |B|=n 则可以确定则可以确定2mn个从个从A到到B的不同关系的不同关系.定义定义2:任何任何序偶的集合序偶的集合，都称之为一个二元关系。，都称之为一个二元关系。43.3.3.关系的表示方法关系的表示方法1). 1). 枚举法枚举法: : 即将关系中所有序偶一一列举出，写在大括号内即将关系中所有序偶一一列举出，写在大括号内. 如如:R=,2).(2).(描述法描述法) )谓词公式法谓词公式法：即用谓词公式描述序偶中元素的关系。例如即用谓词公式描述序偶中元素的关系。例如 R=|xy3).3).有向图法有向图法：1。2。 3。 4。ABabcR1 :1。4。23R2 :44.4).矩阵

47、表示法：(实际上就是图论中的邻接矩阵实际上就是图论中的邻接矩阵) 设设A=a1, a2, , am，B=b1, b2, , bn是个有限集，是个有限集， R AB，定义，定义R的的mn阶矩阵阶矩阵 MR=(rij)mn，其中，其中4.三个特殊关系三个特殊关系1).空关系空关系： AB，(或或 AA)，即无任何元素的关系，即无任何元素的关系. 它的关系图中只有结点它的关系图中只有结点,无任何边；它的矩阵中全是无任何边；它的矩阵中全是0。2).完全关系完全关系(全域关系全域关系) ： AB(或或AA)本身是一个从本身是一个从A到到B(或或A上上)的完全关系的完全关系. 即含有全部序偶的关系。它的矩

48、阵中全是即含有全部序偶的关系。它的矩阵中全是1。 1 若若R 0 若若R(1im,1jn)rij=45.3). 恒等关系恒等关系IA： IA AA,且且IA =|xA称之为称之为A 上的恒等关系。上的恒等关系。例如例如A=1,2,3, 则则IA =, A上的上的、完全关系、完全关系AA及及IA的关系图及矩阵如下：的关系图及矩阵如下：MIA =1 0 00 1 00 0 1331。2。31。2。31 1 11 1 11 1 1331。2。30 0 00 0 00 0 033M=MAA=AAIA46.二二. .关系的性质关系的性质: : 熟练掌握性质的判断及证明熟练掌握性质的判断及证明. .1.自

49、反性自反性定义定义:设设R是集合是集合A中的关系，如果对于任意中的关系，如果对于任意xA都有都有 R (xRx)，则称，则称R是是A中自反关系。即中自反关系。即 R是是A中自反的中自反的x(x AxRx)2.反自反性反自反性定义定义：设：设R是集合是集合A中的关系，如果对于任意的中的关系，如果对于任意的xA都有都有 R ，则称，则称R为为A中的反自反关系。即中的反自反关系。即 R是是A中反自反的中反自反的x(x A R)3.对称性对称性定义定义:R是集合是集合A中关系中关系,若对任何若对任何x, yA,如果有如果有xRy,必有必有 yRx,则称则称R为为A中的对称关系。中的对称关系。 R是是A

50、上对称的上对称的x y(x A y A xRy) yRx)47.4.反对称性反对称性定义定义:设设R为集合为集合A中关系中关系,若对任何若对任何x, yA,如果有如果有xRy,和和 yRx,就有就有x=y,则称则称R为为A中反对称关系中反对称关系。R是是A上反对称的上反对称的x y(x A y A xRy yRx) x=y) x y(x A y A x y R) R)5. 传递性传递性定义定义:R是是A中关系，对任何中关系，对任何x,y,zA,如果有如果有xRy,和和yRz,就就有有xRz,则称则称R为为A中传递关系。中传递关系。即即R在在A上传递上传递 x y z(x A y A z

51、A xRy yRz)xRz)这些性质要求会判断这些性质要求会判断,会证明会证明.这里特别要注意的是这里特别要注意的是, 这些定义都是蕴涵式这些定义都是蕴涵式, 所以当蕴涵所以当蕴涵式当前件为假时式当前件为假时 ,此蕴涵式为真此蕴涵式为真,即此性质即此性质成立成立!48.自反性自反性反自反性反自反性对称性对称性传递性传递性反对称性反对称性每个结点都有环每个结点都有环主对角线全是主对角线全是1每个结点都无环每个结点都无环主对角线全是主对角线全是0不同结点间如果有边不同结点间如果有边,则有方向相反的两条则有方向相反的两条边边.是以对角线为对称是以对角线为对称的矩阵的矩阵不同结点间不同结点间,

52、最多有一最多有一条边条边.以主对角线为对称以主对角线为对称的位置不会同时为的位置不会同时为1如果有边如果有边,则也有边则也有边. 或者使得前件为假或者使得前件为假. 如果如果aij=1,且且ajk=1,则则aik=1从关系的矩阵从关系的矩阵从关系的有向图从关系的有向图性质判定性质判定:49.判断下面关系的性质判断下面关系的性质:1。2。1。2。1。2。1。2。3333R2R1R3R4自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性 R1 Y N N Y Y R2 N Y N Y N R3 Y N Y N Y R4 Y N Y Y Y 50.1。2。1。2。1。2。

53、1。2。3333R5R6R7R8自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性 R5 N Y N Y Y R6 N N Y N N R7 N N N N N R8 N Y Y Y Y 51.关系性质当证明方法归纳关系性质当证明方法归纳: 设设R是是A上关系，上关系，1.1.证明证明R R的的自反性自反性：方法方法1 用自反定义证：任取用自反定义证：任取 xA,证出证出R.方法方法2 用恒等关系用恒等关系IA证：证：证出证出IA R. (见教材见教材P119(2)方法方法3 用自反闭包证：用自反闭包证：证出证出r(R)=R, 即即RIA=R.2.2.证明证明R R的

54、的反自反性反自反性：方法方法1 用反自反定义证：任取用反自反定义证：任取 xA,证出证出 R.3.3.证明证明R R的的对称性对称性：方法方法1 用对称定义证：用对称定义证：任取任取 x,yA,设设R, 证出证出 R.方法方法2 用求逆关系证：用求逆关系证：证出证出 Rc=R.方法方法3 用对称闭包证：用对称闭包证：证出证出 s(R)=R, 即即RRc =R.52.4.4.证明证明R R的的反对称性反对称性：方法方法1 用定义用定义1证：证：任取任取 x,yA,设设R, R.证出证出 x=y。方法方法2用定义用定义2证：证：任取任取 x,yA,xy, 设设R,证出证出 R. 方法方法3

55、用定理证：用定理证：证出证出 RRc IA . (见见教材教材P118)5.5.证明证明R R的的传递性传递性：方法方法1 用传递定义证：用传递定义证：任取任取 x,y,zA,设设R,R, 证出证出 R.方法方法2 用传递闭包证：用传递闭包证：证出证出 t(R)=R, 即即 RR2R3. =R.方法方法3用定理证：用定理证：证出证出 (见教材见教材P119(2)同学们可以根据具体情况,选用相应方法证明.其中必须掌握的是用基本定义证明.R RRo53.三三. .掌握关系复合掌握关系复合, ,求逆及闭包运算求逆及闭包运算( (计算方法及性质计算方法及性质) )( (一一) )关系的复合关系的复合

56、 1.定义定义 :设设R XY，S YZ，则，则 RS XZ。 RS=|x X z Zy(y Y R S) 2. 2.计算方法计算方法(俗称过河拆桥法俗称过河拆桥法) 枚举法枚举法 R=, S=, RS=, 有向图有向图a。b。 c。X。YabcRS。Zabc。Zabca。b。 c。X54. 矩阵矩阵3.3.性质性质1).1).满足结合律满足结合律: :R AB S BC T CD 则则 R(ST)=(RS)T2). R AB S BC T BC R (ST)=(RS)(RT) R (ST) (RS)(RT)3). R是从是从A到到B的关系，则的关系，则 R IB=IA R=R 推论推论: R

57、 AA, 则则 R IA=IA R=R (IA是运算是运算的的幺幺元元)4).关系的乘幂关系的乘幂 R0 =IA， R AA, Rm Rn = Rm+n (Rm)n =Rmn (m,n为非负整数为非负整数)MR S=010001100010011100=01110001055.( (二二). ). 逆关系逆关系1.定义定义 :设设R XY，R的逆关系的逆关系 RC=| R R RC R2. 计算方法计算方法 1). R=, RC =, 2). RC的有向图的有向图:是将是将R的有向图的所有边的方向颠倒的有向图的所有边的方向颠倒. 3). RC的矩阵的矩阵 MRC =(MR)T 即为即为R R矩

58、阵的转置矩阵的转置3.性质性质令令R、S都是从都是从X到到Y的关系，则的关系，则 1). (RC)C = R 2). (RS)C = RCSC 。 3). (RS)C = RCSC 。 4). (RS)C = RCSC 。56. 5). R S RC SC 。 6). (R)C=RC 7).令令R是从是从X到到Y的关系，的关系，S是是Y到到 Z的关系，则的关系，则 (R S)C= SC RC 。 8). R是是A上关系，则上关系，则 R是对称的，当且仅当是对称的，当且仅当 RC =R R是反对称的，当且仅当是反对称的，当且仅当 RRC IA。 57.( (三三).).闭包运算闭包运算1.1.

59、定义定义：给定：给定 A中关系中关系R,若若A上另一个关系上另一个关系R，满足：，满足：R R； R是自反的是自反的(对称的、传递的对称的、传递的)； R是是“最小的最小的”，即对于任何，即对于任何A上自反上自反(对称、传递对称、传递)的关系的关系R”, 如果如果R R”, 就有就有R R”。则称。则称R是是R的自反的自反(对称、传递对称、传递)闭包。记作闭包。记作r(R)、(s(R) 、t(R) (reflexive、 symmetric、transitive)2.2.计算方法计算方法给定给定 A中关系中关系R r(R)=RIA。 s(R)=RRC 。 t(R)=RR2R3. 。 t(R)

60、=RR2.Rn *求求t(R)矩阵的矩阵的Warshall算法算法.58.闭包的运算有三种形式闭包的运算有三种形式: 如如A=a.b.c R AA R=, a).集合形式集合形式. r(R)=RIA =, , =, s(R)=RRC =, , =, R2=, R3=, t(R)=RR2R3 =, , =,. , , 59.b)有向图形式有向图形式 .bacR3RbacbacIA=r(R)bacRbacbR2act(R)bac=cRbac=bRCas(R)bac60.c)矩阵形式矩阵形式.Mr(R)=MRMIA=010001100100010001=111110011Ms(R)=MRMRC=01

61、0001100001100010=011101110Mt(R)=M M M =010001100001100010=111111111R2R3R10001000161.3.3.性质性质1). R是是A上关系，则上关系，则 R是自反的，当且仅当是自反的，当且仅当 r(R)=R. R是对称的，当且仅当是对称的，当且仅当 s(R)=R. R是传递的，当且仅当是传递的，当且仅当 t(R)=R. 2). R是是A上关系，则上关系，则 R是自反的，则是自反的，则s(R)和和t(R)也自反。也自反。 R是对称的，则是对称的，则r(R)和和t(R)也对称。也对称。 R是传递的，则是传递的，则r(R)也传递。也

62、传递。 * 3).设设R是是A上关系，则上关系，则 sr(R)=rs(R) tr(R)=rt(R) st(R) ts(R)62.四四. .等价关系等价关系掌握等价关系的判断掌握等价关系的判断, ,证明证明, ,求等价类和商集求等价类和商集. . 1.了解集合的划分与覆盖的概念了解集合的划分与覆盖的概念. 例例 X=1,2,3, A1=1,2,3, A2=1,2,3, A3=1,2,3, A4=1,2,2,3, A5=1,3 A1, A2 ,A3 ,A4 是覆盖。是覆盖。 A1, A2 ,A3也是划分。也是划分。 2.等价关系定义等价关系定义 :设设R是是A上关系上关系,若若R是自反的、对称的

63、是自反的、对称的和传递和传递的，则称的，则称R是是A中的等价关系。中的等价关系。 3.等价关系等价关系R的有向图的有向图:可能由若干个独立子图构成的，可能由若干个独立子图构成的，每个独立子图都是完全关系图每个独立子图都是完全关系图。1。2。3R11。2。3R21。2。R363.4.4.等价类等价类：1).1).定义定义:R:R是是A A上的等价关系上的等价关系,aA,aA,由由a a确定的集合确定的集合aaR R a aR R=x|xAR=x|xAR 称集合称集合aaR R为由为由a a形成的形成的R R等价类。等价类。2).由等价关系图求等价类由等价关系图求等价类：R图中每个独立子图上的结

64、点图中每个独立子图上的结点构成一个等价类。不同的等价类个数构成一个等价类。不同的等价类个数=独立子图个数。独立子图个数。3).等价类性质等价类性质 R是是A上等价关系，任意上等价关系，任意a,b,cA 同一个等价类中的元素，彼此有等价关系同一个等价类中的元素，彼此有等价关系R。 aaR RbbR R=，当且当且仅当仅当 R R。 aaR R=bbR R 当且当且仅当仅当 R R。 .A.A中任何元素中任何元素a,aa,a必属于且仅属于一个等价类。必属于且仅属于一个等价类。 . .任意两个等价类任意两个等价类 aaR R,bbR R, 要么要么aaR R=bbR R ，要么，要么aaR Rbb

65、R R= 。 R的所有等价类构成的集合是的所有等价类构成的集合是A的一个划分。的一个划分。64.5.商集商集:定义定义：R是是A上等价关系，由上等价关系，由R的所有等价类构成的所有等价类构成的集合称之为的集合称之为A关于关于R的商集。记作的商集。记作A/R。即。即 A/R=aaR R |aA6.6.商集应用商集应用. .1)按照集合的等势关系按照集合的等势关系(是等价关系是等价关系)“”对集合族对集合族S进行进行划分，得到商集划分，得到商集S/，进而得到基数类的概念。，进而得到基数类的概念。S=0,1,1,a,2,0,1,a,b,3,0,1,2,N,I,R,.S/=0,1,2,3,N,R,.2

66、).无向图结点之间的连通关系是个等价关系无向图结点之间的连通关系是个等价关系. 令令G=是无向图是无向图, R是是V上连通关系上连通关系, 即即 R=|u和和v是连通的是连通的例例. 给定图给定图G如右上图所示如右上图所示: V/R=a,b,g,c,d,e,f,h无元素无元素1个元素个元素2个元素个元素3个元素个元素可数集可数集不可数集不可数集.ghabefcd65.3).3).图的同构关系图的同构关系是个等价关系是个等价关系. . 令上述图构成的集合令上述图构成的集合A=a,b,c,d,e,f,g,h,i,j,求商集求商集A/ .A/ =a,h,b,i,c,e,d,f,g,jabcdefg

67、hij66.练习练习1.R和和S都是都是A上等价关系上等价关系,下面哪个是下面哪个是A上等价关系上等价关系?证明或举反例说明证明或举反例说明. a) RS b) RS c) R (即即AA-R) d) R-S e)R2 f) r(R-S) e) Rc解解.a) c) d) f)不是不是. 请看反例请看反例:R。a。cb。a。cb。a。cb。SRS。a。cb。R。a。cb。R。a。cb。R-S。a。cb。r(R-S)67.b) R RS是等价关系是等价关系.证明证明：1. 1. 证明证明R RS的自反性的自反性方法方法1 用自反定义证：任取用自反定义证：任取 xA, (证出证出RS)因因R和和S

68、都自反，所以有都自反，所以有R，S，于是有，于是有RS，所以，所以RS也自反。也自反。方法方法2 用恒等关系用恒等关系IA证：证：(证出证出IA R)因因R和和S都自反，所以都自反，所以 IA R ，IA S，所以，所以IA RS所以所以RS也自反。也自反。方法方法3 用自反闭包证：用自反闭包证： (证出证出r(RS)=RS, 即即 (RS)IA= RS)因因R和和S都自反，所以都自反，所以r(R)=R, r(S)=S, r(RS)=(RS)IA= (RIA)(SIA) =r(R)r(S)=RS 所以所以RS也自反。也自反。68.2.2.证明证明RSRS的对称性：的对称性：方法方法1 用对称定

69、义证：用对称定义证：任取任取 x,yA,设设RSS, (证出证出 RSS.)则则R，S S，因为因为R R和和S S对称，所以有对称，所以有R，S S，于是于是RSS。RSS对称。对称。方法方法2 用求逆关系证：用求逆关系证：(证出证出 (RSS)c=RSS.)因为因为R R和和S S对称，所以有对称，所以有Rc=R， S Sc=S S，而而(RSS)c=RcSSc= RSS ， RSS对称。对称。方法方法3 用对称闭包证：用对称闭包证： (证出证出 s(RSS)=RSS, )因为因为R R和和S S对称，所以对称，所以s(R)=R,s(S)=Ss(R)=R,s(S)=Ss(RSS)= (R

70、SS)(RSS)c =(RSS)(RcSSc) =(RRc)(RS Sc)(SS Sc)(S SRc) =(s(R)(RS Sc)(s s(S)(S SRc) =(R(RS Sc)(S(S SRc)=RS (吸收律吸收律) RSS对称。对称。69.3.3.证明证明RSS的传递性：的传递性：方法方法1 用传递定义证：任取用传递定义证：任取 x,y,zA, 设设RSS,RSS, (证出证出RSS)RSSRSS RS SRS S (RR)(S S S)S) RS S （因为（因为R、S传递）传递） RS S 所以所以RSS传递传递。所以RSS是A上等价关系.70.e)证明证明. R2是等价关系是等

71、价关系.方法方法1.由由P119习题习题(3)得得:如果如果R自反和传递自反和传递,则则R2 =R, 所所以以R2也是等价关系也是等价关系.方法方法2.证证R2自反自反:任取任取aA,因为因为R自反自反,所以所以R,根据关系的复合得根据关系的复合得, R R, 即即R2,所以所以R2自反。自反。证证R2对称对称: (R2)c=(Rc)2=R2 (由由R对称得对称得Rc=R) R2对称对称证证R2传递传递:任取任取a,b,cA,设有设有R2,R2, 根据关系的复合得根据关系的复合得,( dARR)( eARR) ,由于由于R传递传递,所以有所以有R,R, R2所以所以R2传递。传递。最后得最后

72、得R2是等价关系。是等价关系。71.g). R是是A上等价关系上等价关系,则则Rc也是也是A上等价关系上等价关系.证明证明1) 证证Rc自反。自反。因为任取因为任取xA,因因R自反，所以自反，所以R, Rc2) R对称，证对称，证Rc也对称。也对称。因为因为R对称，所以对称，所以Rc =R Rc也对称。也对称。3) R传递，证传递，证Rc也传递。也传递。方法方法1 .任取任取x,y,zA, 且有且有Rc ,Rc, 于是于是R ,R，因，因R传递，传递，R,于是有于是有Rc， Rc传递。传递。方法方法2. t(Rc)=Rc(Rc)2(Rc)3 = Rc(R2)c(R3)c= (RR2R3)c

73、 = (t(R)c=Rc 所以所以Rc传递。传递。所以所以Rc是是A上等价关系上等价关系.72.练习练习2.五五.设设X=1,2,3 Y=1,2, 在在X的幂集的幂集P(X)上定义二上定义二元关系元关系R如下如下: 对于任何对于任何A,BP(X), ARB 当且仅当当且仅当 A Y=B Y1.画出关系画出关系R的有向图的有向图.2.R是等价关系吗是等价关系吗?如果是如果是,请写出商集请写出商集P(X)/R. 如果不是请如果不是请说明原因说明原因解解.1.关系关系R的有向图的有向图.2. 从从R有向图看出有向图看出R有自反有自反,对称和传递性对称和传递性,故是等价关系故是等价关系 P(X)/R=

74、 ,1,2,1,2,3,1,3,2,3,1,2,31,31,31,2,31,2,32,32,333 11221,21,273.* *五五. .相容关系相容关系1.1.定义定义:给定集合给定集合X上的关系上的关系r, 若若r是自反的、对称的是自反的、对称的,则则r是是A上相容关系上相容关系。2.图的简化图的简化：不画环；不画环；两条对称边用一条无向直线代替。两条对称边用一条无向直线代替。3.矩阵的简化矩阵的简化：因为：因为r的矩阵是对称阵且主对角线全是的矩阵是对称阵且主对角线全是1，用下三角矩阵用下三角矩阵(不含主对角线不含主对角线)代替代替r的矩阵。的矩阵。4.相容类相容类：设：设r是集合是

75、集合X上的相容关系，上的相容关系，C A,如果对于如果对于C 中任意两个元素中任意两个元素x,y有有r ,称称C是是r的一个的一个相容类相容类.5. 最大相容类最大相容类:设设r是集合是集合X上的相容关系，上的相容关系，C是是r的一个相的一个相容类，如果容类，如果C不能被其它不能被其它相容类所真包含，则称相容类所真包含，则称C是一是一个最大相容类。个最大相容类。-最大完全多边形最大完全多边形.6.6.完全覆盖完全覆盖：r是中的相容关系，由是中的相容关系，由r的所有最大相容类的所有最大相容类为元素构成的集合，称之为为元素构成的集合，称之为X的完全覆盖。记作的完全覆盖。记作Cr(X)。74.练习练

76、习.已知已知X=1,2,3,4,5,6,7上的相容关系上的相容关系r的交换矩阵为的交换矩阵为: 求完全覆盖求完全覆盖Cr(X)解解.先画出先画出r的简化图的简化图, 如右上图所示如右上图所示.于是得完全覆盖为于是得完全覆盖为:Cr(X)=1,2,4,5,1,3,7,1,3,4,7,611 01 1 11 1 0 10 0 0 0 01 0 1 0 0 1123 4 5 6775.五五. .偏序关系偏序关系判断判断, ,会画会画HasseHasse图图, ,会求一个子集的极小会求一个子集的极小( (大大) )元元, ,最小最小( (大大) )元元, ,上界与下界上界与下界, ,最小上界及最大下界

77、最小上界及最大下界. .1. 定义定义：R是是A上自反、反对称和传递的关系，则称上自反、反对称和传递的关系，则称R 是是A上的偏序关系。并称上的偏序关系。并称是偏序集。是偏序集。2. x与与y是可比较的是可比较的：是偏序集，是偏序集，x,yA，如果要如果要么么xy,要么要么yx, 则称则称x与与y是可比较的。是可比较的。3.定义定义：是偏序集，任何是偏序集，任何x,yA，如果，如果x与与y都是可都是可比较的，则称比较的，则称是是全序全序关系关系(线序、链线序、链)。4.偏序集偏序集Hasse图的画法图的画法：令令是偏序集，是偏序集， 1).用用“ ”表示表示A中元素。中元素。 2).如果如果

78、xy,且且xy，则结点，则结点y要画在结点要画在结点x的上方。的上方。 3). 如果如果xy,且且y盖住盖住x，x与与y之间连一直线。之间连一直线。 4). 从最下层结点从最下层结点(全是射出的边与之相连，逐层向上画，全是射出的边与之相连，逐层向上画，直到最上层结点直到最上层结点(全是射入的边与之相连全是射入的边与之相连)。76.例如2。1。642。1。84。77.5. 重要元素重要元素y是是B的的极小元极小元y(yBx(xBxyxy) ( (在在B B中没有比中没有比y y更小的元素了，更小的元素了，y y就是就是极小元极小元) )y是是B的的极大元极大元y(yBx(xBxyyx) ( (在

79、在B B中没有比中没有比y y更大的元素了，更大的元素了，y y就是就是极大元极大元) )y是是B的的最小元最小元y(yB x(xB yx) ( (最小元最小元y y是是B B中元素，该元素比中元素，该元素比B B中所有元素都小中所有元素都小) ) y是是B的的最大元最大元y(yB x(xB xy) (最大元最大元y y是是B B中元素，该元素比中元素，该元素比B B中所有元素都大中所有元素都大) )y是是B的的上界上界y(yA x(xB xy) ( (上界上界y y是是A A中元素，该元素比中元素，该元素比B B中所有元素都大中所有元素都大) )y是是B的的下界下界y(yA x(xB yx)

80、 ( (下界下界y y是是A A中元素，该元素比中元素，该元素比B B中所有元素都小中所有元素都小) )78. y是是B的上界，并且对的上界，并且对B的所有上界的所有上界x,都有都有yx,则则称称y是是B的的最小上界最小上界( (上确界上确界) )，记作，记作LUB B=y 。 ( (即即y y是上界中最小的。如果是上界中最小的。如果B B有上确界，则是唯一的有上确界，则是唯一的) )y是是B的下界，并且对的下界，并且对B的所有下界的所有下界x,都有都有xy,则则称称y是是B的的最大下界最大下界( (下确界下确界) )，记作，记作GLB B=y 。 ( (即即y y是下界中最大的。如果是下界中

81、最大的。如果B B有上确界，则是唯一的有上确界，则是唯一的) )例如例如 B=2,3,6B的极小元的极小元:2,3 极大元极大元: 6 最小元最小元:无无最大元最大元:6 下界下界:1 上界上界:6,12,18 下确界下确界:1 上确界上确界:6。6。18。12。2。379. 第六章第六章函数函数1.函数的定义函数的定义.2.函数的类型函数的类型, 会判断会判断,会证明会证明.3.会计算函数的复合会计算函数的复合(左复合左复合),求逆函数求逆函数.知道有关性质知道有关性质.*4.了解集合特征函数和模糊子集的表示及计算了解集合特征函数和模糊子集的表示及计算.*5.了解自然数的定义了解自然数的

82、定义, 集合的等势定义集合的等势定义, 集合基数的定集合基数的定义义, 可数集定义可数集定义,可数集的基数可数集的基数, 连续统基数连续统基数, 基数的比较基数的比较.80.一一. .概念概念1.定义定义：X与与Y集合，集合，f是从是从X到到Y的关系，如果的关系，如果任何任何xX，都存在都存在唯一唯一yY，使得使得f,则称则称f是是从从X到到Y的函数的函数，(变换、映射变换、映射)，记作，记作f:XY. 如果如果f:XX是函数是函数, 也称也称f是是X上的函数上的函数. 要求会判断要求会判断某些给定关系是否是函数某些给定关系是否是函数.2.函数相等函数相等: f:AB, g:CD,f=gA=C

83、 B=D f(x)=g(x)3.3.从从X X到到Y Y函数的集合函数的集合Y YX X： YX =f| f:XY YX ：它是由它是由所有所有的从的从X到到Y函数函数构成的集合构成的集合.4.4.特殊函数特殊函数 1). 常值函数常值函数：函数：函数f:XY ，如果，如果 y0Y, 使得对使得对 xX, 有有f(x)=y0 , 即即ran f=y0 ,称称f是常值函数。是常值函数。 2).恒等函数恒等函数：恒等关系：恒等关系IX是是X到到X函数，即函数，即IX:XX,称称之为恒等函数。显然对于之为恒等函数。显然对于 xX，有，有 IX(x)=x 。81.5.函数的类型函数的类型, 会判断会判

84、断,会证明会证明.1).满射的满射的：f:XY是函数，如果是函数，如果 Rf=Y,则称则称f 是是满射的满射的。证明方法证明方法:任取任取yY, 看是否能够找到对应的自变元看是否能够找到对应的自变元 xX, 使得使得 y=f(x).2).映内的映内的：f:XY是函数，如果是函数，如果 Rf Y 则称则称f 是是映内的映内的。3).入射的入射的：f:XY是函数，如果对于任何是函数，如果对于任何x1,x2X, 如果如果 x1x2 有有f(x1)f(x2),(或者若或者若f(x1)=f(x2),则则x1=x2),则称则称f 是是入射的入射的，也称，也称f 是是单射的单射的，也称，也称f 是是一对一

85、的一对一的。证明的方法证明的方法:如定义中所说如定义中所说.4).双射的双射的：f:XY是函数，如果是函数，如果 f 既是满射的，又是既是满射的，又是入射的，则称入射的，则称 f 是是双射的双射的，也称，也称f 是是一一对应的一一对应的。双射是个重要概念双射是个重要概念, 我们用双射定义了如下概念我们用双射定义了如下概念: 集合的等势关系集合的等势关系“”; 代数系统的同构关系代数系统的同构关系“ ” 图的同构关系图的同构关系“ ”82.练习题练习题:R:R是实数集合，给定是实数集合，给定R R上的五个关系如下上的五个关系如下: : R R1 1=|x=y=|x=y2 2 R R2 2=|

86、y=x+6=|y=x+6 R R3 3=|y=(x-1)=|y=(x-1)-1-1 R R4 4=|y=2=|y=2x x R R5 5=|x=|x2 2+y+y2 2=4 =4 上述五个关系中，哪些上述五个关系中，哪些是从是从R R到到R R的函数。如果是函数，的函数。如果是函数，说明它是属于什么类型的（指满射、入射、双射）。说明它是属于什么类型的（指满射、入射、双射）。如果不是函数，说明理由如果不是函数，说明理由。解解.R.R1 1不不是从是从R R到到R R的函数的函数, x, x是负数时是负数时无定义无定义, ,另外当另外当x0x0时时, ,有两个有两个y y值与之对应值与之对应.

87、. R R2 2是从是从R R到到R R的函数的函数, ,是双射的是双射的. . R R3 3不不是从是从R R到到R R的函数的函数, ,因为因为x=1x=1时时, ,无定义无定义. . R R4 4是从是从R R到到R R的函数的函数, ,是入射的是入射的, ,不是满射的不是满射的. . R R5 5不不是从是从R R到到R R的函数的函数, ,因为因为|x|2|x|2时时, ,无定义无定义.|x|2.|x|2时时对应的函数值不唯一对应的函数值不唯一. .xy83.二二. .会计算函数复合会计算函数复合( (左复合左复合),),求逆函数求逆函数. .知道有关性质知道有关性质. .1.1.函

88、数的复合函数的复合1)1)定义定义: f:XY, g:YZ是函数是函数,则定义则定义 g f =|x X z Zy(y Y f g) 则称则称 g f 为为f与与g的复合函数的复合函数(左复合左复合). 注意注意:这里把这里把g写在写在f的左边了的左边了.所以叫左复合所以叫左复合. g f :XZ,即即 g f 是是X到到Z的函数的函数.这样写是为了这样写是为了照顾数学习惯照顾数学习惯: g f(x)=g(f(x) xX2).2).复合函数的计算复合函数的计算计算方法同复合关系的计算计算方法同复合关系的计算. 但要注意是左复合但要注意是左复合.3).3).函数复合的性质函数复合的性质 (1

89、).满足可结合性满足可结合性。 f:XY, g:YZ, h:ZW 是函数是函数,则则 (h g)f=h(g f)84.(2).定理定理5-2.2 f:XY, g:YZ是两个函数是两个函数, 则则 a).如果如果f和和g是是满满射的，则射的，则 g f 也是也是满满射的；射的； b).如果如果f和和g是是入入射的，则射的，则 g f 也是也是入入射的；射的； c).如果如果f和和g是是双双射的，则射的，则 g f 也是也是双双射的。射的。(3).如果如果gf是是满满射的，则射的，则g是是满满射的；射的；如果如果gf是是入入射的，则射的，则 f 是是入入射的；射的；如果如果gf 是是双双射

90、的，则射的，则f是是入入射的射的和和g是是满满射的。射的。(4). f:XY是函数是函数, 则则 f IX = f 且且 IY f = f 。 f:XX是函数是函数, 则则 f IX=IX f=f 。IX是运算是运算“”的的幺元幺元. 85.2.逆函数逆函数1).定义定义：设：设f:Xy是双射的函数，是双射的函数，fC:YX 也是函数也是函数, 称称之为之为 f 的逆函数。并用的逆函数。并用f-1代替代替fC 。 f-1存在，也称存在，也称f 可逆。可逆。2).性质性质(1). 设设f:Xy是双射的函数，则是双射的函数，则(f-1)-1= f 。(2). 设设f:XY是双射的函数，则有是双射

91、的函数，则有f-1 f= IX 且且 f f-1 = IY。(3).令令 f:XY, g:YX是两个函数是两个函数, 如果如果 gf= IX 且且 fg = IY , 则则 g= f-1 。(4).令令 f:XY, g:YX是两个是两个双射双射函数函数,则则 (gf)-1=f-1 g-1 86.*证明题证明题给定函数给定函数f:AB g:CD ，已知，已知 f g 并且并且ram g ran f , 其中其中 ran g 是函数是函数g的值域的值域求证：如果求证：如果g是入射的，则是入射的，则. 证明证明：先证：先证A C 任取任取 x A, 因为因为f:AB 是函数，必存是函数，必存在在唯

92、一唯一y B，使得，使得 f, 又因为又因为f g ，所以，所以 g, 而而g:CD是函数，所以是函数，所以x C, 所以所以A C 。再证再证C A ，任取任取 x C, 因为因为 g:CD 是函数，必存在是函数，必存在唯一唯一y D，使得，使得 g, 所以所以y ran g, 又又ram g ran f , 所以所以y ran f, 而而f:AB，所以所以必存在必存在x A, 使得使得 f, 因为因为f g ，所以，所以 g, 可是前边已得可是前边已得 g, 而而 g是是入射的，所以入射的，所以x=x, 即得即得x A, 所以所以C A 。最后得最后得A=C。87.第六章第六章代数系统

93、代数系统1.掌握运算的定义掌握运算的定义.2.熟练掌握二元运算的性质的判断及证明熟练掌握二元运算的性质的判断及证明.3.掌握代数系统的同构定义掌握代数系统的同构定义,会证明会证明.了解同构性质的保持了解同构性质的保持.4.了解半群了解半群,独异点独异点, *环和域的概念环和域的概念.5.熟练掌握群熟练掌握群,子群子群,交换群交换群(会证明会证明), 6.了解循环群了解循环群.*6. 掌握循环群定义掌握循环群定义, 循环群的循环周期以及循环群的同循环群的循环周期以及循环群的同构构.7.了解了解Lagrange定理及其推论定理及其推论,(会应用会应用).*7. 掌握掌握Lagrange定理及其推论

94、定理及其推论(会应用会应用).*8.了解环的运算法则了解环的运算法则. 注意本章证明题的思路和技巧注意本章证明题的思路和技巧88.一一. .掌握运算和代数系统的概念掌握运算和代数系统的概念. .1.运算定义运算定义：设：设X是个集合，是个集合，f:XnY是个映射，则称是个映射，则称f是是 X上的上的n元运元运.(Xn =XX.X -n个个X的笛卡尔积的笛卡尔积)2代数系统定义代数系统定义：X是非空集合，是非空集合，X上的上的m个运算个运算 f1,f2,fm, 构成代数系统构成代数系统U,记作记作U= ( m1)二二. .熟练掌握二元运算的性质的判断及证明熟练掌握二元运算的性质的判断及证明：和和

95、是代数系统是代数系统, , 是二元运算：是二元运算：1.封闭性：封闭性： x,yX, 有有 xyX。2.可交换性：可交换性： x,yX, 有有 xy=y x。3.幂等性：幂等性： xX, 有有 xx=x。4. 有幺元：有幺元： eX, xX，有，有 ex=xe=x.5.有零元有零元: x, xX，有，有x=x=.6.可结合性：可结合性： x,y,zX, 有有 (xy)z =x(yz)。.89.7.有逆元：有逆元： xX, 有有x-1X，使得，使得 x-1x=xx-1=e8.可消去性：可消去性： aX， x, yX,有有 (ax=ay)(xa=ya) x=y. 9.分配律：分配律：对对可分配：

96、可分配： x,y,zX，有，有 x(yz)=(xy)(xz) 或或 (xy)z =(xz)(yz) 10.吸收律：吸收律： x,yX，有，有 x(xy)=x 和和 x(xy)=x 对这些性质要求会判断、会证明。对这些性质要求会判断、会证明。三三. .掌握代数系统同构定义掌握代数系统同构定义, ,会证明会证明. .了解同构性质的保持了解同构性质的保持1.定义设定义设,是两个代数系统，是两个代数系统，和和都都是二是二元元运算，如果存在映射运算，如果存在映射f:XY,使得对任何使得对任何x1 ,x2X，有，有 f(x1x2)=f(x1)f(x2) -此式此式叫同态叫同态(同构同构)关系式关系式则

97、称则称 f是从是从到到的同态映射，简称这两个代数的同态映射，简称这两个代数系统系统同态同态。记作。记作XY。并称并称为为的的同态像同态像。90.如果如果f是满射的，称此同态是满射的，称此同态f是是满同态满同态。如果如果f是入射的，称此同态是入射的，称此同态f是是单一同态单一同态。如果如果f是双射的，称是双射的，称与与同构同构，记作，记作X Y。f是是到到的同态的同态(同构同构),称之为称之为自同态自同态(自同构自同构)。2.代数系统代数系统同构性质的保持同构性质的保持代数系统代数系统, , X Y, f:XY是同构映射是同构映射, 如果如果中中满足交换、结合、有幺元、有零元、每个元满足交换、

98、结合、有幺元、有零元、每个元素可逆素可逆, 则则中中也满足上述性质。反之亦然也满足上述性质。反之亦然.*3.同态核同态核定义定义：f是从是从到到的同态映射的同态映射, (XY),e和和 e 分别是分别是X、Y中幺元。定义中幺元。定义集合集合ker (f)为：为： ker (f)=x|xXf(x)= e 称称ker (f)为为 f的同态核。的同态核。91.四四. .掌握半群掌握半群, ,独异点独异点, ,群群, ,环和域的概念环和域的概念. .半群半群:封闭封闭结合结合独异点独异点:有幺元有幺元群群可逆可逆环环: 是交换群是交换群是半群是半群对对+可分配可分配整环整环是可交换独异点是可交换

99、独异点无零因子无零因子(ab=0则则a=0或或b=0)域域是交换群是交换群是交换群是交换群对对+可分配可分配是交换群是交换群对对+可分配可分配92.五五. .熟练掌握群的阶和元素的阶的概念及群的性质熟练掌握群的阶和元素的阶的概念及群的性质. . 1.群的阶群的阶:是群是群 ,如果如果KG=n (n是正整数是正整数), 则则G是是n阶群阶群.否则否则G是无限阶群是无限阶群. 2.元素的阶元素的阶:设设是个群，是个群，aG，如果存在如果存在正整数正整数k，使得使得ak=e,则称则称a的阶是有限的。如果存在的阶是有限的。如果存在最小的正整数最小的正整数n，使得使得an=e,则称则称a的阶是的阶

100、是n。否则就称。否则就称a的阶是无限的。的阶是无限的。定理定理6-5.7：是群是群, aG, 如果如果a的阶为的阶为n ,则则 ak=e 当且仅当当且仅当 k=mn (mI)(即即k是是n的整数倍的整数倍)定理定理6-5.8. 群中的元素与其逆元群中的元素与其逆元具有相同的阶。具有相同的阶。定理定理6-5.9 有限群中，每个元素的阶都是有限的。有限群中，每个元素的阶都是有限的。 93. 3.群的性质群的性质 1).群满足可消去性群满足可消去性定理定理6-5.1设设是个群，则对任何是个群，则对任何a,b,cG, 如果如果有有 ab=ac 则则 b=c 。 ba= ca 则则 b=c 。 2).

101、群方程可解性群方程可解性定理定理6-5.2 设设是个群，则对任何是个群，则对任何a,bG, 存在唯一元素存在唯一元素 xG, 使得使得 ax=b . 存在唯一元素存在唯一元素 yG, 使得使得 ya=b . 3). 群中无零元群中无零元。定理定理6-5.3 设设是个群是个群,如果如果KG 2,则则G中无零元中无零元. 4). 群中除幺元外，无其它幂等元群中除幺元外，无其它幂等元。 5).定理定理6-5.5 是个群，对任何是个群，对任何a,bG,有有 (a-1)-1 =a (ab)-1=b-1a-194. 6). 有限群的运算表的特征有限群的运算表的特征定理定理6-5.6 是个有限群，则是个有

102、限群，则G中中每个元素每个元素在在运算运算表中的每一行表中的每一行(列列)必出现且仅出现一次必出现且仅出现一次。练习题练习题: :给定群给定群,*,*的运算表如的运算表如右图所示右图所示. .求解下面群的方程求解下面群的方程: : b*db*d-1-1*x*c=d*c*x*c=d*c-1-1解解: : b*db*d-1-1*x*c=d*c*x*c=d*c-1 -1 d d-1-1=b =b c c-1-1=c=c b*b*x*c=d*c b*b=c c*x*c=d*c b*b*x*c=d*c b*b=c c*x*c=d*c 消去消去c c得得 c*x=d c*x=d 解得解得: : x=cx=

103、c-1-1*d=c*d=b*d=c*d=b* a b c da a b c db b c d ac c d a bd d a b c95.六六. .掌握交换群掌握交换群( (会证明会证明) )练习题练习题1 1. .给定集合给定集合x|xx|x是有理数且是有理数且x1x1，在上定，在上定义二元运算义二元运算* *如下：任何如下：任何a a，bb a*b=a+b-ab a*b=a+b-ab求证求证 *是个交换群。是个交换群。证明证明: :1 1. .证封闭性证封闭性. .任取任取a,ba,b G,a1,b1, G,a1,b1, a*b=a+b-ab a*b=a+b-ab 若若a+b-ab=1,a

104、+b-ab=1,则则b= =1, b= =1, 产生矛盾产生矛盾. . 所以所以 a+b-ab1 a a+b-ab1 a*b*b G G2 2. .证可结合性证可结合性, ,任取任取a,b,ca,b,c G,a1,b1,c1,G,a1,b1,c1,a*(b*c)=a+(b+c-bc)-a(b+c-bc)a*(b*c)=a+(b+c-bc)-a(b+c-bc)=a+b+c-bc-ab-ac+abc=(a+b-ab)+c-(a+b-ab)c=(a*b)*c=a+b+c-bc-ab-ac+abc=(a+b-ab)+c-(a+b-ab)c=(a*b)*c3 3. .证有幺元证有幺元0,0,任取任取a

105、a G,G, a a*0=a+0-a0=a 0*a=0+a-0a=a *0=a+0-a0=a 0*a=0+a-0a=a 所以所以0 0是幺元是幺元. ._1-a1-a96.4 4. .证可逆性证可逆性. .任取任取a a G,a1,G,a1,设有设有b,b,使得使得 a a*b=a+b-ab=0 *b=a+b-ab=0 a+(1-a)b=0, b= a+(1-a)b=0, b= 1 b1 b G G a*b=0 a*b=0 且且b*a= *a= +a- a= =0b*a= *a= +a- a= =0所以所以a a有逆元有逆元b.b.即即a a-1-1= =5 5. .证交换性证交换性. .任取

106、任取a,ba,b G,G, a a*b=a+b-ab=b+a-ba=b*a*b=a+b-ab=b+a-ba=b*a 综上所述综上所述是个交换群是个交换群. ._aa-1_aa-1_aa-1_aa-1a-1a+a(a-1)-aa_aa-197.七七. . 了解循环群了解循环群. . 1.循环群的定义循环群的定义:设设是群是群,如果存在一个元素如果存在一个元素gG, 使得对每个使得对每个 xG, 都存在整数都存在整数i, 有有x=gi, 则称则称是是个个循环群循环群. 并称并称g是是G的的生成元生成元. 2.循环群的循环周期循环群的循环周期: 周期有限周期有限:为为k; 周期无限周期无限: 3.两

107、种循环群两种循环群: : 周期为周期为k; : 周期无限周期无限.98.八八. .会证明子群会证明子群, ,会应用会应用LagrangeLagrange定理及其推论定理及其推论. . 1. 1.子群的证明方法子群的证明方法: :方法方法1.用子群的定义，即证明运算在子集上满足封闭、用子群的定义，即证明运算在子集上满足封闭、有幺元、可逆。有幺元、可逆。方法方法2. 设设是群是群, S是是G的非空子集，如果的非空子集，如果满足：满足：封闭性和封闭性和可逆性可逆性,则则是是的子群。的子群。方法方法3.设设是群是群, B是是G的的有限子集有限子集,如果如果在在B上满足上满足封闭性封闭性，则，则是是的子

108、群。的子群。方法方法4. 设设是群是群, S是是G的非空子集，如果的非空子集，如果任何任何a,bS 有有ab-1S, 则则是是的子群。的子群。99.练习题练习题2:设设f和和g都是群都是群到到的同态，证明的同态，证明是是的一个子群，其中的一个子群，其中 C=x| xG1且且f(x)=g(x)证明证明：方法方法1，用子群定义证明，用子群定义证明满足：满足：a)封闭性封闭性.任取任取x1, x2C,(推出推出x1x2Cf(x1x2)=g(x1x2) f(x1)=g(x1) f(x2)=g(x2) f(x1x2) =f(x1) f(x2) =g(x1) g(x2)=g(x1x2) x1x2Cb)证

109、幺元证幺元e1C, (推出推出f(e1)= g(e1) 设设e1和和e2分别是分别是G1和和G2中的幺元中的幺元, 因因 f(e1)= e2= g(e1) e1C。c)可逆性：任取可逆性：任取xC, (推出推出x-1C 即即 f(x-1)= g(x-1) f(x)=g(x) x-1G1, f (x-1)= (f(x)-1= (g(x)-1 =g(x-1) x-1C。综上所述，综上所述，是是的一个子群。的一个子群。100.方法方法4,任取任取x1, x2C, (推出推出x1x2-1 C 即即 f(x1x2 -1)=g(x1x2 -1) f(x1)=g(x1) f(x2)=g(x2) x2-1

110、G1 f(x1x2-1 ) =f(x1) f(x2-1) =f(x1)(f(x2)-1 = g(x1) (g(x2)-1 = g(x1) g(x2-1) = g(x1x2-1) x1x2-1C 所以所以是是的一个子群。的一个子群。101.综合练习题综合练习题:设设是群，定义是群，定义G上关系上关系R如下；如下； R= | zG,使得使得 y=zxz-1 1.证明证明R是是G上等价关系。上等价关系。*2.令上述令上述为为时时, 求商集求商集N6/R.证明证明1.a) 证证R自反自反：任取：任取xG, 幺元幺元eG, 因为因为 x=exe-1 由由R定义得定义得R，所以，所以R自反。自反。b)证证

111、R对称对称：任取：任取x,yG, 设有设有R, 由由R定义得定义得 zG,使得使得 y=zxz-1 , 于是有：于是有： z-1yz= z-1(zxz-1)z , z-1yz= (z-1z)x(z-1z) , 所以所以 z-1y(z-1) -1 =x因因z-1G，所以有，所以有 R, 所以所以R对称。对称。c)证明证明R传递传递：任取：任取x,y,zG, 设有设有R, R由由R定义得定义得 z1,z2G,使得使得 y=z1xz1-1 , z=z2yz2-1 ,于是有于是有z=z2yz2-1 = z2(z1xz1-1)z2-1 = (z2z1)x(z1-1z2-1)=(z2z1)x(z2z1)-

112、1 因因z2z1R ,R, R传递。传递。R是是G上等价关系。上等价关系。102.*2.令上述令上述为为时时, 求商集求商集N6/R. N6=0,1,2,3,4,5 R= | zN6,使得使得 y=zxz-1 , R z(y=zxz-1) z(yz=zx)按照上述表达式得关系按照上述表达式得关系R图如下图如下:因此商集因此商集 N6/R=0,1,2,3,4,5210354103. * 第七章第七章格与布尔代数格与布尔代数1.掌握格的定义掌握格的定义,了解格的性质了解格的性质.2.会判断格会判断格,分配格分配格,有补格和布尔格有补格和布尔格,3.重点掌握两个元素的布尔代数的性质重点掌握两个元素

113、的布尔代数的性质(10个个).4.会写两个元素的布尔表达式的范式会写两个元素的布尔表达式的范式.(实质是第一章的主实质是第一章的主析取和主合取范式析取和主合取范式).104.一一. .掌握格的定义掌握格的定义1. 格的定义格的定义是偏序集，如果任何是偏序集，如果任何a,bA,使得使得a,b都有最大都有最大下界和最小上界，则称下界和最小上界，则称是格。是格。 2. 由格诱导的代数系统由格诱导的代数系统设设是格是格,在在A上定义二元运算上定义二元运算和和为为: a,bA ab=LUB a,b a,b的最小上界的最小上界.Least Upper Bound ab=GLB a,b a,b的最大下界

114、的最大下界.Greatest Lower Bound称称是由格是由格诱导的代数系统诱导的代数系统. (-并并,-交交)二二. .格的性质格的性质是由格是由格诱导的代数系统。诱导的代数系统。 a,b,c,dA1. aab bab aba abb2.如果如果ab，cd，则，则 acbd，acbd。105.推论推论：在一个格中，任何：在一个格中，任何 a,b,cA，如果，如果bc，则，则 abac，abac。此性质称为此性质称为格的保序性格的保序性。3. 和和都满足都满足交换律交换律。即。即 ab=ba，ab=ba。4. 和和都满足都满足幂等律幂等律。即。即 aa=a aa=a 5. 和和都满足

115、都满足结合律结合律。即。即 (ab)c =a(bc) ， (ab)c =a(bc) 。6. 和和都满足都满足吸收律吸收律。即。即a( ab) =a, a(ab) =a。7. 是代数系统，如果是代数系统，如果和和是是满足吸收律满足吸收律的二的二元运算，则元运算，则和和必满足幂等律必满足幂等律。8. 和和不不满足满足分配律分配律。但有分配。但有分配不等式不等式： a(bc) (ab)(ac) ， (ab)(ac) a(bc) 。9. ab ab=b ab=a106.三三. .格的同态格的同态, ,同构同构1.设设和和是两个格，由它们诱导的代数系是两个格，由它们诱导的代数系统分别是统分别是和和，

116、如果存在映射，如果存在映射f:A1A2 使得对任何使得对任何a,bA1, f(a1b)=f(a)2f(b) f(a1b)=f(a)2f(b)则称则称f是是到到的同态映射。的同态映射。也称也称是是的同态像。的同态像。如果如果 f 是双射的，就称是双射的，就称f是是到到，的格同构，也称格的格同构，也称格和和同构。同构。两个格同构两个格同构:两个格的图同构两个格的图同构.2.格同态和同构的保序性格同态和同构的保序性107.四四. .分配格分配格1.定义定义是由格是由格诱导的代数系统。如果诱导的代数系统。如果对对 a,b,cA，有，有 a(bc) =(ab)(ac) ， a(bc)= (ab

117、)(ac)则称则称是是分配格。分配格。2. 二个重要的五元素非分配格二个重要的五元素非分配格：3.分配格的判定分配格的判定：一个格是分配格的一个格是分配格的充分且必要条件充分且必要条件是在该格中没有任何是在该格中没有任何子格与上述两个五元素非分配格之一同构子格与上述两个五元素非分配格之一同构.4. 分配格的性质分配格的性质 1). 定理定理7-2.1. 在格中，如果在格中，如果对对可分配，则可分配，则对对也也可分配可分配.反之亦然。反之亦然。 2). 定理定理7-2.2. 所有链均为所有链均为分配格。分配格。 3 1 30 2 5 d e a b c108.3). 设设是分配格，对任何是分配

118、格，对任何a,b,cA, 如果有如果有 ab=ac 及及 ab=ac 则必有则必有 b=c .五五. .有界格有界格有界格定义有界格定义：如果一个格存在：如果一个格存在全上界全上界1与全下界与全下界0，则，则称此格为有界格称此格为有界格.六六. .有补格有补格1. 元素的补元元素的补元：设设是个有界格，是个有界格，aA, 如果存在如果存在 bA, 使得使得 ab=1 ab=0 则称则称a与与b互为补元。互为补元。2. 有补格的定义有补格的定义：一个有界格中，如果每个元素都有补：一个有界格中，如果每个元素都有补元，则称之为有补格。元，则称之为有补格。3.在有界分配格中，如果元素有补元，则补元

119、是唯一的。在有界分配格中，如果元素有补元，则补元是唯一的。七七. . 布尔格布尔格如果一个格既是分配格又是有补格，则称如果一个格既是分配格又是有补格，则称之为布尔格。布尔格中每个元素都有唯一补元。之为布尔格。布尔格中每个元素都有唯一补元。109.练习题练习题. .给定集合如下：给定集合如下：A A1 1=1,2,4,8,16 A=1,2,4,8,16 A2 2=1,2,3,5,6,10,15,30=1,2,3,5,6,10,15,30A A3 3=1,2,3,5,30 A=1,2,3,5,30 A4 4=1,2,3,5,10,15,30=1,2,3,5,10,15,30A A5 5=1,2,

120、3,4,9,36 =1,2,3,4,9,36 令令是上述集合上的整除关系。是上述集合上的整除关系。1.请分别画出各个偏序集请分别画出各个偏序集A,的哈斯图的哈斯图(i=1,2,3,4,5)(i=1,2,3,4,5)1。2。4。8。16。2 9364 1 330。3。2。5 。10。15 。6。3。5。30。30。3。2。5。10。5。110.2.2.用用“Y”“Y”表示表示“是是”，用，用“N”“N”表示表示“否否”填下表。填下表。 A ,分配格分配格有补格有补格布尔格布尔格 Y Y N N N N Y Y N Y N Y N N N1。2。4。8。16。2 9364 1 330。3。2。5

121、。10。15 。6。3。5。30。30。3。2。5。10。5。111.八八. 布尔代数布尔代数1.定义定义由布尔格由布尔格诱导的代数系统诱导的代数系统称之称之为布尔代数。其中为布尔代数。其中是取补元运算。是取补元运算。如果如果A是有限集合，则称它是有限布尔代数。是有限集合，则称它是有限布尔代数。2.布尔代数性质布尔代数性质设设布尔代数布尔代数, 任意任意x,y,zB, 有有交换律交换律 xy=yx xy=yx结合律结合律 x(yz)=(xy)z x(yz)=(xy)z 幂等律幂等律 xx=x xx=x 吸收律吸收律 x(xy)=x x(xy)=x分配律分配律 x(yz)=(xy)(xz

122、) x(yz)=(xy)(xz)112.同一律同一律 x0=x x1=x 零律零律 x1=1 x0=0 互补律互补律 x =1 x =0 对合律对合律底摩根定律底摩根定律3.布尔代数的同构布尔代数的同构1). 定义定义：令：令和和是两个布尔是两个布尔代数，如果存在映射代数，如果存在映射f:B1B2 ,对任何对任何a,bB1 , 有有 f(a1b)=f(a)2f(b) f(a1b)=f(a)2f(b) f( )=则称则称f是是到到的同态映射。的同态映射。 f(a)113.2). 原子原子定义定义1: 设设设设布尔代数布尔代数, 元素元素aB, a0, 对对任何元素任何元素xB, 有有xa=

123、a, 或或 xa=0, 则称则称a是原子。是原子。定义定义2:是布尔格是布尔格,在在的的哈斯图中称盖住全哈斯图中称盖住全下界下界0的元素为原子。的元素为原子。1。e。0。d。f。b。c。a。0。1。 01a b114.3). 有关引理有关引理定理定理7-3.2 设设a,b是布尔代数是布尔代数中的原子中的原子，如果，如果ab, 则则ab=0, (如果如果ab0, 则则 a=b) 定理定理7-3.3 设设a,b1,b2 bn是是布尔代数布尔代数中的原中的原子子，则，则ab1b2bn的的充分且必要条件为充分且必要条件为对于某个对于某个i(1in), 有有a=bi.定理定理7-3.4 设设b是有

124、限布尔代数是有限布尔代数中的中的非非0元素，元素，则必存在原子则必存在原子a，使得使得ab.定理定理7-3.5 有限布尔代数中，有限布尔代数中，b =0，当且仅当当且仅当 bc。定理定理7-3.6 设设是有限布尔代数，是有限布尔代数，b非非0元素，元素，a1,a2 ak是是B中满足中满足ajb的所有原子的所有原子(j=1,2,k), 则则 ba1a2 ak且除原子次序不同外，且除原子次序不同外，上述表达式是唯一的。上述表达式是唯一的。115.定理定理7-3.7 在布尔代数在布尔代数中中，对，对B中任何原子中任何原子a和任何非和任何非0元素元素b, ab和和a 两式中有且仅有一个成立。两式中有

125、且仅有一个成立。定理定理7-3.8 (Stone定理定理)设设是有限布尔代数，是有限布尔代数，M是是B中所有原子构成的集合，则中所有原子构成的集合，则与与同构。同构。推论推论1. 任何有限布尔代数的元素个数为任何有限布尔代数的元素个数为2n (n=1,2,3,) 因为因为|P(M)|= 2n推论推论2. 两个有限布尔代数同构的充分且必要条件是元素两个有限布尔代数同构的充分且必要条件是元素个数相同。个数相同。116.4. 4. 布尔表达式概念布尔表达式概念1).定义定义：设：设是布尔代数，其上的布尔表达式是布尔代数，其上的布尔表达式递归定义如下：递归定义如下：(1)B中任何元素是个布尔表达式。

126、中任何元素是个布尔表达式。(2)任何变元任何变元x是个布尔表达式是个布尔表达式.(3)如果如果E1 ,E2是个布尔表达式是个布尔表达式, 则则 ,(E1E2),(E1E2)也也是布尔表达式。是布尔表达式。(4)有限次地应用规则有限次地应用规则1)-3),得到的符号串都是布尔表达得到的符号串都是布尔表达式。式。117.2). 布尔表达式的范式布尔表达式的范式 1. 有两个元素的布尔代数的布尔表达式的范式有两个元素的布尔代数的布尔表达式的范式: 是两个元素的布尔代数是两个元素的布尔代数 1). 析取范式析取范式 (1).小项小项: 含有含有n个变元的小项形式为个变元的小项形式为:其中其中例如例如

127、都是小项都是小项. (2).布尔表达式的析取范式布尔表达式的析取范式:含有变元含有变元 x1,x2,xn 的布尔表达式的布尔表达式E(x1,x2,xn),如果写成如果写成如下形式如下形式: A1A2.Am (m1)其中每个其中每个Ai (1im)都是有都是有n个变元的小项个变元的小项. 则称此式是则称此式是E(x1,x2,xn)的析取范式的析取范式. 118.2). 合取范式合取范式 (1). 大项大项:含有含有n个变元的大项形式为个变元的大项形式为:其中其中例如例如都是大项都是大项. (2).布尔表达式的合取范式布尔表达式的合取范式:含有变元含有变元 x1,x2,xn 的布尔表达式的布尔

128、表达式E(x1,x2,xn),如果写成如果写成如下形式如下形式: A1A2. Am (m1)其中每个其中每个Ai (1im)都是有都是有n个变元的大项个变元的大项. 则称此式是则称此式是E(x1,x2,xn)的合取范式的合取范式. 例如例如:3). 析取范式与合取范式的写法析取范式与合取范式的写法: 方法方法1:列真值表列真值表方法方法2:表达式的等价变换表达式的等价变换.119.方法方法1. 用真值表求析取范式用真值表求析取范式: 先介绍小项的性质先介绍小项的性质, 以两个变元以两个变元x1,x2为例为例每一组赋值每一组赋值,有且仅有一个小项为有且仅有一个小项为1.根据一组赋值根据一组赋

129、值,求值为求值为1的小项的小项: 如果变元如果变元x,被赋值为被赋值为0,则则在此小项中在此小项中, x以以形式出现形式出现; 如果变元如果变元x,被赋值为被赋值为1,则在则在此小项中此小项中, x以原形以原形x形式出现形式出现. 求求E(x1,x2,xn)的析取范式的析取范式:先列出它的真值表先列出它的真值表,找出表中找出表中每个每个1对应的小项对应的小项,然后用然后用连接上述小项连接上述小项. 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1120.例如例如,求求布尔代数布尔代数上上的布尔表达式的布尔表达式 E(x1,x2,x3)=x1(x2

130、 ) 的析取范式的析取范式.E(x1,x2,x3)=(x1 )(x1 x2 )(x1 x2x3)x3 x1 x2 x3 E (x1, x2 , x3) 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 1 1 1x3x3x2121.方法方法1. 用真值表求合取范式用真值表求合取范式: 先介绍大项的性质先介绍大项的性质, 以两个变元以两个变元x1,x2为例为例每一组赋值每一组赋值,有且仅有一个大项为有且仅有一个大项为0.根据一组赋值根据一组赋值,求值为求值为0的大项的大项: 如果变元如果变元x,被赋值为被赋值为1,则则在此小项中

131、在此小项中, x以以形式出现形式出现; 如果变元如果变元x,被赋值为被赋值为0,则在则在此小项中此小项中, x以原形以原形x形式出现形式出现. 求求E(x1,x2,xn)的合取范式的合取范式:先列出它的真值表先列出它的真值表,找出表中找出表中每个每个0对应的大项对应的大项,然后用然后用连接上述大项连接上述大项. 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0122.例如例如,求求布尔代数布尔代数上上的布尔表达式的布尔表达式 E(x1,x2,x3)=x1(x2 ) 的合取范式的合取范式.E(x1,x2,x3)=(x1x2x3)(x1x2 ) (x

132、1 x3) (x1 ) ( x2 ) x3 x1 x2 x3 E (x1, x2 , x3) 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 1 1 1x3x2x3x1x2x3123.方法方法2. 用表达式的等价变换求析取范式用表达式的等价变换求析取范式:E(x1,x2,x3)=x1(x2 ) =(x1x2)(x1 )=(x1x2(x3 ) (x1(x2 ) )=(x1x2x3)(x1x2 )(x1x2 )(x1 )=(x1x2x3)(x1x2 )(x1 )结果与前相同结果与前相同.用表达式的等价变换求合取范式用表达式的等价变

133、换求合取范式:E(x1,x2,x3)=x1(x2 )=(x1(x2 )(x3 )(x1 )x2 )=(x1x2 x3 )(x1x2 )(x1 x3 )(x1 ) (x1x2 ) ( x2 )=(x1x2 x3 )(x1x2 )(x1 x3 )(x1 ) ( x2 )x3x3x2x2x3x3x3x3x3x3x2x3x3x3x2x1x3x3x2x1x3x3x2x3x3x2x1x3x3x2124.*2. 一般的布尔代数的布尔表达式的范式一般的布尔代数的布尔表达式的范式: 是布尔代数是布尔代数,含有变元含有变元 x1,x2,xn 的布尔表的布尔表达式达式E(x1,x2,xn), 1). 小项小项: 是

134、由是由n个变元和个变元和B中元素构成的如下形式中元素构成的如下形式,称为小称为小项项.其中其中 C12.n为为B中元素中元素, 我们称之为小项的系数我们称之为小项的系数. 例如例如B=0,1,a,b, 下面就是下面就是E(x1,x2,x3)中的小项中的小项:2). 布尔表达式布尔表达式E(x1,x2,.xn)的析取范式的析取范式:含有变元含有变元 x1,x2,xn 的布尔表达式的布尔表达式E(x1,x2,xn),如果写成如果写成如下形式如下形式: A1A2.Am (m1)其中每个其中每个Ai (1im)都是有都是有n个变元的小项个变元的小项. 则称此式是则称此式是E(x1,x2,xn)的析取范

135、式的析取范式. 125.E(x1,x2,xn)写析取范式形式写析取范式形式.126.类似地类似地, E(x1,x2,xn)的合取范式为的合取范式为:E(x1,x2,xn)=(x1x2. xn E(0,0,0) (x1x2.xn-1 E(0,0,0,1). ( . xnE(1,1,1,0) ( . E(1,1,1)其中其中E(0,0,0),E(0,0,0,1),E(1,1,1,0)和和E(1,1,1)就是所谓的就是所谓的“系数系数”.实际上实际上, 求求E(x1,x2,xn)的析取或者合取范式时的析取或者合取范式时, 就是求这就是求这些些“系数系数”.xnx1x2xnx1x2xn-1127.已知

136、已知是布尔代数是布尔代数, 其中其中B=0,a,b,1分别求出下面布尔表达式的析取范式和合取范式分别求出下面布尔表达式的析取范式和合取范式.解解. 先求四个系数先求四个系数:析取范式为析取范式为:128.合取范式为合取范式为:129. 第八章第八章图论图论1.掌握图的基本概念掌握图的基本概念.(特别注意相似的概念特别注意相似的概念)2.熟练掌握图中关于结点度数的定理熟练掌握图中关于结点度数的定理. (会应用会应用)3.无向图的连通性的判定无向图的连通性的判定,连通分支及连通分支数的概念连通分支及连通分支数的概念.4.有向图的可达性有向图的可达性,强连通强连通,单侧连通和弱连通的判定单侧连通和

137、弱连通的判定. 求强求强分图分图,单侧分图和弱分图单侧分图和弱分图.5.会求图的矩阵会求图的矩阵.6.会判定欧拉图和汉密尔顿图会判定欧拉图和汉密尔顿图.*7.会判定平面图会判定平面图, 掌握欧拉公式掌握欧拉公式.*8.了解对偶图了解对偶图.9.掌握树的基本定义掌握树的基本定义,v和和e间的关系式间的关系式.会画生成树会画生成树,会求会求最最小生成树小生成树.根树的概念根树的概念,完全完全m叉树的公式叉树的公式,会画最优树会画最优树,*会设计前缀码会设计前缀码.130.一一.图的概念图的概念图的定义图的定义, 有向边有向边,无向边无向边,平行边平行边,环环邻接点邻接点,邻接边邻接边, 孤立结

138、点孤立结点有向图有向图, 无向图无向图,简单图简单图,混合图混合图,零图零图,平凡图平凡图,多重图多重图, 完全图完全图,子图子图, 生成子图生成子图,补图补图, 结点的度结点的度, 结点的出度结点的出度, 结点的入度结点的入度, 图的最大度图的最大度(G),最小度最小度(G), 图所有结点度数总和与边的关系图所有结点度数总和与边的关系, 出度和与入度和关系出度和与入度和关系图的同构图的同构131.二二.路与回路路与回路路路,回路回路,迹迹,闭迹闭迹,通路通路,圈圈无向图的连通性无向图的连通性:连通图连通图,连通分支连通分支,连通分支数连通分支数W(G), 点割集点割集,割点割点,点连

139、通度点连通度k(G), 边割集边割集,割边割边(桥桥),边连通度边连通度(G) 结点间的距离结点间的距离, 图的直径图的直径有向图的连通性有向图的连通性:可达性可达性, 强连通强连通,单侧连通单侧连通,弱连通弱连通, 强分图强分图,单侧分图单侧分图,弱分图弱分图.(会会求这些分图求这些分图)132.三三.图的矩阵图的矩阵邻接矩阵邻接矩阵A:结点与结点之间的邻接关系矩阵结点与结点之间的邻接关系矩阵. 根据邻接矩阵判断根据邻接矩阵判断:各结点的度各结点的度, 有向图结点出有向图结点出,入度入度. 由由Ak可以求一个结点到另一个结点长度为可以求一个结点到另一个结点长度为k的路条数的路条数. 可达

140、矩阵可达矩阵P:结点结点u到结点到结点v的可达性的矩阵的可达性的矩阵. 用用P可以判定可以判定:各结点的度各结点的度. 有向图的强分图有向图的强分图. 关联矩阵关联矩阵M:是结点与边的关联关系矩阵是结点与边的关联关系矩阵. 用用M判定判定:各结点的度各结点的度133.四四.欧拉图与汉密尔顿图欧拉图与汉密尔顿图(会判定会判定) 欧拉路欧拉路,欧拉回路欧拉回路,欧拉图欧拉图. 判定判定:有欧拉路的充要条件有欧拉路的充要条件:无或有两个奇数度的结点无或有两个奇数度的结点. 有欧拉回路的充要条件有欧拉回路的充要条件:所有结点度数均为偶数所有结点度数均为偶数. 汉密尔顿路汉密尔顿路,汉密尔顿回路汉密尔顿

141、回路,汉密尔顿图汉密尔顿图汉密尔顿图的判定汉密尔顿图的判定: 必要条件必要条件:V的任何非空子集的任何非空子集S,有有W(G-S)|S| 充分条件充分条件:每对结点的度数和每对结点的度数和|V| =n*五五.平面图平面图平面图的定义平面图的定义,平面的边界平面的边界, 欧拉公式欧拉公式: v-e+r=2 判定判定:必要条件必要条件: e3v-6 *充要条件充要条件:G不含与不含与K5或或K3,3在在2度结点内同构子图度结点内同构子图.134.*六六.对偶图与着色对偶图与着色会画对偶图会画对偶图, 会对图正常着色会对图正常着色.*七七. 二部图二部图作为一般了解作为一般了解, 掌握掌握K

142、3.3八八.树与生成树树与生成树树的定义树的定义:6个定义个定义,其中最主要的是连通无回路其中最主要的是连通无回路, e=v-1 分支结点分支结点, 叶结点叶结点会求最小生成树会求最小生成树九九. 根树根树 m叉树叉树,完全完全 m叉树叉树, (m-1)i=t-1 会画最优树会画最优树, *会设计前缀码会设计前缀码135.练习题练习题1.请画出请画出K K5 5 的所有不同构的生成树。的所有不同构的生成树。解解. K. K5 5的生成树的生成树T T边数为边数为4, T4, T的度数和为的度数和为8 82 2. .一棵完全二叉树有一棵完全二叉树有e e条边，条边，t t个叶结点，请推导出个

143、叶结点，请推导出e e与与t t的关系式。的关系式。解解. .根据完全根据完全m m叉树的公式叉树的公式:(m-1)i=t-1 :(m-1)i=t-1 得分支结点数得分支结点数 i=t-1 i=t-1 又根据树中又根据树中 e=v-1 v e=v-1 v是结点数是结点数. .所以所以 e=(i+t)-1=t-1+t-1=2t-2 e=(i+t)-1=t-1+t-1=2t-2(11114)(11123)(11222)136.3 3. .今有今有a,b,c,d,e,f,ga,b,c,d,e,f,g七个人七个人, ,已知下列事实已知下列事实: : a: a:会讲英语会讲英语. b:. b:会讲英语和

144、汉语会讲英语和汉语. . c: c:会讲英语会讲英语, ,意大利语和俄语意大利语和俄语 d: d:会讲日语和汉语会讲日语和汉语. . e: e:会讲德语和意大利语会讲德语和意大利语 f: f:会讲法语会讲法语, ,日语日语, ,俄语俄语 g: g:会讲法语和德语会讲法语和德语. .试问能否将这七个人适当安排座位试问能否将这七个人适当安排座位, ,使得每个人都能和他使得每个人都能和他两边的人两边的人直接交谈直接交谈? ?若能若能, ,请给予安排请给予安排. .若不能若不能, ,说明理由说明理由. .解解. 以以a,b,c,d,e,f,g为结点为结点,如果两个如果两个人之间讲同一种语言人之间讲同一

145、种语言,则它们之间则它们之间连一条直线连一条直线.得到右图得到右图. 从此图中找到从此图中找到H回路回路: abdfgeca按照此回路坐成一个圆圈按照此回路坐成一个圆圈,就可以就可以使得每个人都可以和它两边的人直接交谈使得每个人都可以和它两边的人直接交谈.e ea ab bc cd dg gf f137.4. 下面序列哪些可以构成一个无向连通图的结点度数序下面序列哪些可以构成一个无向连通图的结点度数序列列?哪些不能哪些不能?哪些可以构成连通简单图哪些可以构成连通简单图?哪些可能构成哪些可能构成欧拉图欧拉图?哪些可能构成汉密尔顿图哪些可能构成汉密尔顿图?哪些可能是完全图哪些可能是完全图?哪些可能

146、是树哪些可能是树?如果能如果能.请画出一个那样的图请画出一个那样的图. 如果不能如果不能请说明原因请说明原因. a.(1,2,3,3) b.(3,3,3,3) c.(1,1,1,1,2,4) d.(2,3,3,4,4) e.(2,3,4,4,5) f.(2,2,2,2,4)解解.a.(1,2,3,3) .a.(1,2,3,3) 不能构成不能构成无向连通图的结点度数序列无向连通图的结点度数序列,因为此序列中有三个奇数因为此序列中有三个奇数,不附和握手定理不附和握手定理.b.(3,3,3,3) 可以是个完全图可以是个完全图K3,是个是个H图图.c.(1,1,1,1,2,4) 可以是棵树可以是棵树.

147、 .d.(2,3,3,4,4) 构成构成无向连通图的无向连通图的结点度数序列结点度数序列,是个是个H图图. 138.e.(2,3,4,4,5)可构成连通图的结点序列可构成连通图的结点序列.但不是简单图但不是简单图,5个个结点中有一个结点度为结点中有一个结点度为5, 所以不是有环所以不是有环,就是有平行边就是有平行边.f.(2,2,2,2,4)是个欧拉图是个欧拉图,139.模拟试题 (信息学院) 2002.1 离离散散数数学学试试卷卷班级班级: : 学号学号姓名姓名: :总分总分 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10一一.(12

148、.(12分分) )试将下面命题符号化。试将下面命题符号化。1.仅当天不下雨且我有时间，才上街。仅当天不下雨且我有时间，才上街。2.如果小张出差，那么小王和小李两人中要有一个出差。如果小张出差，那么小王和小李两人中要有一个出差。3.3.每个大学生都爱好一些文体活动。每个大学生都爱好一些文体活动。(S(x):x(S(x):x是大学生，是大学生，L(x,y):xL(x,y):x爱好爱好y y，C(x):xC(x):x是文娱活动，是文娱活动，P(x):xP(x):x是体育活动。是体育活动。) ) 140.4.4.没有大学生不懂外语。没有大学生不懂外语。( S(x):x( S(x):x是大学生，是大学生

149、，K(x,y):xK(x,y):x懂得懂得y y， F(x):x F(x):x是外语。是外语。) )二二.(6.(6分分) )写出下面命题公式写出下面命题公式 (PQ)P (PQ)P 的主合取范式。的主合取范式。三三.(6.(6分分) )求下面谓词公式的真值。要求有解题的过程。求下面谓词公式的真值。要求有解题的过程。 x(PQ(x)R(a), 其中其中 P:21, Q(x):x3, R(x):x5, a:5, 论论域为域为 -2,6.四四.(6分分)令全集令全集E=, P(A)表示表示A的幂集的幂集, 分别计算分别计算: 1. P() P() 2. P(A) P(A) 3. P(E)-P()

150、141.五五.(12.(12分分) )用谓词逻辑推理证明下面推理的有效性。用谓词逻辑推理证明下面推理的有效性。（要求按照谓词逻辑推理格式，书写推理过程。）（要求按照谓词逻辑推理格式，书写推理过程。）六六.(16.(16分分) )已知已知 R R1 1、R R2 2是集合上的等价关系，问是集合上的等价关系，问R R1 1RR2 2、R R1 1RR2 2 、R R1 1-R-R2 2 、r(AA)-Rr(AA)-R1 1) )中哪些是中哪些是A A上的等价关系上的等价关系？如果不是说明理由？如果不是说明理由, ,或举反例。如果是请给予证明或举反例。如果是请给予证明七七.(10.(10分）分）R

151、 R是实数集合，给定是实数集合，给定R R上的五个关系如下上的五个关系如下: : R R1 1=|x=y=|x=y2 2 R R2 2=|y=x+6=|y=x+6 R R3 3=|y=(x-1)=|y=(x-1)-1-1 R R4 4=|y=2=|y=2x x R R5 5=|x=|x2 2+y+y2 2=4 =4 上述五个关系中，哪些是从上述五个关系中，哪些是从R R到到R R的函数。如果是函数，的函数。如果是函数，说明它是属于什么类型的（指满射、入射、双射）。说明它是属于什么类型的（指满射、入射、双射）。如果不是函数，说明理由如果不是函数，说明理由。142.八八.(12.(12分分) )给

152、定集合给定集合x|xx|x是有理数且是有理数且x1x1，在上，在上定义二元运算定义二元运算* *如下：如下：对任何对任何a a，bb a*b=a+b-ab a*b=a+b-ab求证求证 *是个交换群。是个交换群。九九.(12.(12分分) )1.请画出请画出K K5 5 的所有不同构的生成树。的所有不同构的生成树。2.2.一棵完全二叉树有一棵完全二叉树有e e条边，条边，t t个叶结点，请推导出个叶结点，请推导出e e与与t t的关系式。的关系式。*3.*3.今有今有a,b,c,d,e,f,ga,b,c,d,e,f,g七个人七个人, ,已知下列事实已知下列事实: : a: a:会讲英语会讲英

153、语. b:. b:会讲英语和汉语会讲英语和汉语. . c: c:会讲英语会讲英语, ,意大利语和俄语意大利语和俄语 d: d:会讲日语和汉语会讲日语和汉语. . e: e:会讲德语和意大利语会讲德语和意大利语 f: f:会讲法语会讲法语, ,日语日语, ,俄语俄语 g: g:会讲法语和德语会讲法语和德语. .143.试问能否将这七个人适当安排座位试问能否将这七个人适当安排座位, ,使得每个人都能和他使得每个人都能和他两边的人两边的人直接交谈直接交谈? ?如果能如果能, ,请给予安排请给予安排. .如果不能如果不能, ,说明说明理由理由. .*4. 下面序列哪些可以构成一个无向连通图的结点度数序

154、下面序列哪些可以构成一个无向连通图的结点度数序列列?哪些不能哪些不能?哪些可以构成连通简单图哪些可以构成连通简单图?哪些可能构成哪些可能构成欧拉图欧拉图?哪些可能构成汉密尔顿图哪些可能构成汉密尔顿图?哪些可能是完全图哪些可能是完全图?哪些可能是树哪些可能是树?如果能如果能.请画出一个那样的图请画出一个那样的图. 如果不能如果不能请说明原因请说明原因. a.(1,2,3,3) b.(3,3,3,3) c.(1,1,1,1,2,4) d.(2,3,3,4,4) e.(2,3,4,4,5) f.(2,2,2,2,4)*5 *5 给定一组权值，给定一组权值，1,3,5,2,7,1,8,6,9,2,1,

155、3,5,2,7,1,8,6,9,2,画最优树。画最优树。144.十十.(10.(10分分) )给定集合如下：给定集合如下：A A1 1=1,2,4,8,16 A=1,2,4,8,16 A2 2=1,2,3,5,6,10,15,30=1,2,3,5,6,10,15,30A A3 3=1,2,3,5,30 A=1,2,3,5,30 A4 4=1,2,3,5,10,15,30=1,2,3,5,10,15,30A A5 5=1,2,3,4,9,36 =1,2,3,4,9,36 令令是上述集合上的整除关系。是上述集合上的整除关系。1.请分别画出各个偏序集请分别画出各个偏序集A,的哈斯图的哈斯图(i=1,

156、2,3,4,5)(i=1,2,3,4,5)2.2.用用“”“”表示表示“是是”，用，用“”“”表示表示“否否”填下表。填下表。 A ,分配格分配格有补格有补格布尔格布尔格145.补充题型补充题型一一.填空填空1.设设A,B是集合是集合, 且且|A|=m,|B|=n,则则|AB|=( ). 可以构造可以构造( )个从个从A到到B的二元关系的二元关系. 其中有其中有( )个是从个是从A到到B的的函数函数. 在在( )条件下条件下, 有从有从A到到B的入射函数的入射函数,有有( )个入射函数个入射函数; 在在( )条件下条件下, 有从有从A到到B的双射函数的双射函数,有有( )个双射函数个双射函数.

157、2.A(P,Q,R)是个永真的命题公式是个永真的命题公式, 则则A(P,Q,R)的主析取范的主析取范式中有式中有( )个小项个小项.3.A(P,Q,R)是个命题公式是个命题公式, 如果如果A(P,Q,R)的主析取范式中的主析取范式中有有k个小项个小项, 则它的主合取范式中有则它的主合取范式中有( )个大项个大项.4.一个图是欧拉图一个图是欧拉图,当且仅当它的所有结点的度当且仅当它的所有结点的度( ).5.一棵完全一棵完全m叉树叉树, 有有t个叶结点个叶结点,则它有则它有( )分支结点分支结点.146.二二.判断下面命题的真值判断下面命题的真值, 并说明理由并说明理由, 或举反例或举反例.1.

158、R和和S都是都是A上关系，上关系， a) R和和S都自反，则都自反，则RS也也自反。自反。 b) R和和S都反自反，则都反自反，则RS也反自反。也反自反。 c) R和和S都对称，则都对称，则RS也对称。也对称。 d) R和和S都传递，则都传递，则RS也传递。也传递。2.如果如果AB，B C，则，则 A C 。 3. (A-B)(A-C)=A 当且仅当当且仅当 B=C=.4. 含有三个以上元素的链含有三个以上元素的链,不是有补格不是有补格.5. 所有链都是分配格所有链都是分配格.6.不是所有格都是有界格不是所有格都是有界格.7.任何两个结点都有边相关联的无向图是完全图任何两个结点都有边相关联的

159、无向图是完全图.8.圈就是回路圈就是回路,回路也是圈回路也是圈.147.三三. .给定集合给定集合A=1,2,3A=1,2,3，在，在A A上定义五个关系如下：上定义五个关系如下： M MR1R1= R= R2 2： R R3 3 =,=, R R4 4 =AA =AA （完全关系）（完全关系） R R5 5= = （空关系）（空关系）1求复合关系求复合关系R R1 1 R R2 2c c， 2. 2.求求R R2 2的传递闭包的传递闭包t(Rt(R2 2).).3.3.用用“”“”表示表示“是是”，用用“”“”表示表示“否否”，填，填下表：下表：自反的自反的反自反的反自反的对称的对称

160、的反对称的反对称的传递的传递的R R1 1 R R2 2R R3 3R R4 4R R5 5123111011001148.4.4.上述五个关系中，哪些是等价关系？哪些是偏序关系上述五个关系中，哪些是等价关系？哪些是偏序关系？哪些是哪些是A A到到A A的函数的函数? ?如果是等价关系如果是等价关系, ,请写出它对请写出它对A A的商集。如果是偏序关系的商集。如果是偏序关系, ,请画出它的哈斯图。如果是函数请画出它的哈斯图。如果是函数, ,请指出它的类型请指出它的类型. .四四. 名词解释名词解释 n元谓词元谓词, 原子谓词公式原子谓词公式, 论域论域 , 群中元素的阶群中元素的阶, 循环

161、群循环群,布尔格布尔格, 拉格朗日定理拉格朗日定理. 迹迹,圈圈, 通路通路, 生成子图生成子图, 图图G的的(G), (G), k(G), (G), W(G), 平面图的欧拉公式平面图的欧拉公式, 零图零图, 平凡图平凡图, 简单图简单图, 149.*五五.设设X=1,2,3 Y=1,2, 在在X的幂集的幂集P(X)上定义二元关系上定义二元关系R如下如下: 对于任何对于任何A,BP(X), ARB 当且仅当当且仅当 A Y=B Y1.画出关系画出关系R的有向图的有向图.2.R是等价关系吗是等价关系吗?如果是如果是,请写出商集请写出商集P(X)/R. 如果不是请如果不是请说明原因说明原因.15

162、0.重点掌握的习题重点掌握的习题:(网络学院网络学院)1.P8(3), P12(5)(7),P19(7)d)g),(8)c),P23(8)ef,P39(4)d,2.P60(2),P66(3)b, P78(3),3.P86(4)(7),P94(5)(7)(9),4.P109(2),P113(1)(3)(4),P118(1)(2)(3)(5),P127(1),P134(1) (2)(4)(7),P145(1)(6)(7),5.P151(1)(3)(5)(6),P156(3),6.P184(1),P190(3)(5),P197(3),P200(1),P211(3)P221(2)(11)7.P242(1)(2),P248(2),P252(1),P269(1)(3)8.P279(2)(5),P287(3)(7),P300(3),P311(1)(2)(3)(6),P317(5) P321(1)(3),P327(2)(3)(6),P337(1)(2)(3)(5)(8)9.前边的前边的模拟题以及补充题模拟题以及补充题.151. 谢谢同学们一个学期的合作！152. 预祝同学们取得优异成绩鸡年大吉！考试顺利！153.

展开阅读全文

离散数学期末复习大纲.PPT

最新文档