离散数学总复习.ppt

离 散 数 学,期 末 总 复 习,复 习 时 注 意准确掌握每个概念灵活应用所学定理注意解题思路清晰证明问题时,先用反向思维(从结论入手)分析问题,再按正向思维写出证明过程.,全书知识网络：,总 复 习 要 求,复习重点第一章 命题逻辑1.联结词的定义(含义及真值表定义).2.会命题符号化.3.永真式的证明.4.永真蕴涵式的证明,记住并能熟练应用常用公式.5.等价公式的证明,记住并能熟练应用常用公式.6.会写命题公式的范式,*能应用范式解决问题.7.熟练掌握命题逻辑三种推理方法.,第二章 谓词逻辑1.准确掌握有关概念.2.会命题符号化.(如P60题(2)3.掌握常用的等价公式和永真蕴涵式.包括:带量词的公式在论域内展开式,量词否定,量词辖域扩充,量词分配公式.4.会用等价公式求谓词公式的真值.(如P66题(3)5.会写前束范式6.熟练掌握谓词逻辑推理.第三章 集合论初步1.幂集,全集,空集.2.集合的五种运算及相关性质(特别是差集，对称差.）3.应用包含排斥原理.,第四章 二元关系1.关系的概念,表示方法.2.二元关系的 性质的定义,熟练掌握性质的判断及证明.3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质)4.掌握等价关系的判断,证明,求等价类和商集.5.掌握相容关系定义,简化图和简化矩阵,相容类,最大相容类,完全覆盖.6.偏序关系的判断,会画Hasse图,会求一个子集的极小(大)元,最小(大)元,上界与下界,最小上界及最大下界.,第六章 代数系统1.掌握运算的定义.2.熟练掌握二元运算的性质的判断及证明.3.掌握代数系统的同构定义,会证明.了解同构性质的保持.4.了解半群,独异点,环和域的概念.5.熟练掌握群,子群,交换群(会证明),了解循环群.6,子群的陪集,Lagrange定理及其推论,(会应用).第七章 格与布尔代数1.掌握格的定义,了解格的性质.2.会判断格,分配格,有补格和布尔格,3.重点掌握两个元素的布尔代数的性质(10个).4.会写两个元素的布尔表达式的范式.(实质是第一章的主析取和主合取范式).,第八章 图论1.掌握图的基本概念.(特别注意相似的概念)2.熟练掌握图中关于结点度数的定理.(会应用)3.无向图的连通性的判定,连通分支及连通分支数的概念.4.有向图的可达性,强连通,单侧连通和弱连通的判定.求强 分图,单侧分图和弱分图.5.会求图的矩阵.6.会判定欧拉图和汉密尔顿图.7.会判定平面图,掌握欧拉公式.8.了解对偶图.9.掌握树的基本定义,v和e间的关系式.会画生成树,会求最小生成树.根树的概念,完全m叉树的公式,会画最优树,会设计前缀码.,总 复 习,复习重点第一章 命题逻辑1.联结词的定义(含义及真值表定义).2.会命题符号化.3.永真式的证明.4.永真蕴涵式的证明,记住并能熟练应用常用公式.5.等价公式的证明,记住并能熟练应用常用公式.6.会写命题公式的范式,能应用范式解决问题.7.熟练掌握命题逻辑三种推理方法.,第一章 命题逻辑1.联结词定义了六个逻辑联结词，分别是：(1)否定“”(2)合取“”(3)析取“”(4)异或“”(5)蕴涵“”(6)等价“”要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。：否定 表示“不”：合取 表示“不但,而且.”“并且”：析取 表示“或者可兼取的或”：异或 表示“或者不可兼取的或”：蕴涵 表示“如果,则.”:等价 表示“当且仅当”“充分且必要”可以将这六个联结词看成六种“运算”。,联结词的定义(包括真值表和含义).特别要注意：“或者”的二义性,即要区分给定的“或”是“可兼取的或”还是“不可兼取的或”。“”的用法，它既表示“充分条件”也表示“必要条件”,即要弄清哪个作为前件,哪个作为后件.,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 T,T T T T T T F,2.会命题符号化.例如 P:我有时间.Q:我上街.R:我在家.表示P是Q的充分条件:如果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(QR)(PQ)P(PQPQ)(R(QR)(PQ)P(公式的否定公式)(R(QR)(PQ)P)(结合律)(RQ)(RR)(PP)(QP)(分配律)(RQ)(QP)RQQP T(互补,同一律),4.永真蕴涵式的证明,记住常用的公式.永真蕴涵式:AB是永真式,则称A永真蕴涵B.(AB)方法1.列真值表.方法2.假设前件真,推出后件真.(即直接推理)方法3.假设后件假,推出前件假.(即反证法)例证明(P(QR)(PQ)(PR)是永真蕴涵式.证:假设后件(PQ)(PR)假,则PQ为T,PR为F,于是P为T,R为F,进而又得Q为T.所以QR为F,所以前件P(QR)为F.所以(P(QR)(PQ)(PR)为永真式.对于给定一个题,究竟是用哪种方法,原则上哪种都可以.但是哪个方法简单,要根据具体题而定.,5.等价公式的证明,记住常用的公式.方法1.列真值表.方法2.用公式的等价变换.例如:证明 P(QR)(PQ)R P(QR)P(QR)(PQ)R(PQ)R(PQ)R注意:不论是证明永真蕴涵式,还是证明等价公式以及后边的求公式的范式,命题逻辑推理,都应用43页的公式。必须记忆一些常用的公式 如:P43表中的永真蕴涵式:I1,I3,I9,I10,I11,I12,I13,等 价 公 式:E1 E16,E18,E19,E20,E21,6.命题公式的范式1)析取范式:A1A2.An(n1)Ai(i=1,2.n)是合取式.2)合取范式:A1A2.An(n1)Ai(i=1,2.n)是析取式.3)析取范式与合取范式的写法.4)小项及小项的性质.m3 m2 m1 m0 P Q PQ PQ PQ PQ 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 F,6)大项及其性质.M0 M1 M2 M3 P Q PQ PQ PQ PQ 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 F7)主析取范式:A1A2.An(n1)Ai(i=1,2.n)小项.8)主合取范式:A1A2.An(n1)Ai(i=1,2.n)大项.,9).会写主析取范式和主合取范式.求下面命题公式的范式:A(P,Q,R)(PQ)R方法1.列真值表.主析取范式A(P,Q,R)(PQ)R(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式A(P,Q,R)(PQ)R(PQR)(PQR)(PQR),方法2.用公式的等价变换.主析取范式;A(P,Q,R)(PQ)R(PQ)R(PQ)R(PQ(RR)(PP)(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式:A(P,Q,R)(PQ)R(PQ)R(PQ)R(PR)(QR)(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR),已知A(P,Q,R)的主析取范式中含有如下小项:m0,m3,m4,m5,m7求它的主合取范式.解:A(P,Q,R)的主合取范式中含有大项:M1,M2,M6A(P,Q,R)(PQR)(PQR)(PQR)范式的应用 如P39习题(7),(8):安排工作(排课表),判断比赛名次,携带工具箱,7.会用三种推理方法,进行逻辑推理.会用三个推理规则:P,T,CP例如:证明(AB)C)D(CD)AB1.直接推理:D P CD P C T I10 Q,(PQ)P(AB)C P(AB)T I12 Q,PQ P AB T E8(PQ)PQ,(AB)C)D(CD)AB2.条件论证:适用于结论是蕴涵式.AB ABA P(附加前提)(AB)C P A(BC)T E19 BC T I11D PCD PC T I10 B T I12 AB CP,(AB)C)D(CD)AB3.反证法:(AB)P(假设前提)AB T E9(AB)C P C T I11 D PCD PC T I10CC T I9,第二章 谓词逻辑1.准确掌握有关概念.2.会命题符号化.(如P60题(2)3.掌握常用的等价公式和永真蕴涵式.包括:带量词的公式在论域内展开式,量词否定,量词辖域扩充,量词分配公式.4.会用等价公式求谓词公式的真值.(如P66题(3)5.会写前束范式6.熟练掌握谓词逻辑推理.,第二章 谓词逻辑1.准确掌握有关概念.客体:客体变元,谓词,量词,量词后的指导变元,量词的辖域,约束变元与自由变元,论域,全总个体域,谓词公式(WFF),命题函数,前束范式,2.会命题符号化.(如P60题(2)命题的符号表达式与论域有关。当论域扩大时，需要添加用来表示客体特性的谓词，称此谓词为特性谓词。特性谓词往往就是给定命题中量词后边的那个名词。如“所有自然数.”、“有些大学生.”。如何添加特性谓词，这是个十分重要的问题，这与前边的量词有关。如果前边是全称量词，特性谓词后边是蕴含联结词“”；如果前边是存在量词，特性谓词后边是合取联结词“”。另外有些命题里有的客体在句中没有明确的量词,而在写它的符号表达式时,必须把隐含的量词明确的写出来.,例如金子闪光,但闪光的不一定都是金子.设: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)每个大学生都爱好一些文体活动。S(x):x是大学生,L(x,y):x爱好y,C(x):x是文娱活动，P(x):x是体育活动.)x(S(x)y(C(y)P(y)L(x,y),3.掌握常用的等价公式和永真蕴涵式.包括:带量词的公式在论域内展开式,量词否定,量词辖域扩充,量词分配公式.设论域为a1,a2,.,an，则 1).xA(x)A(a1)A(a2).A(an)2).xB(x)B(a1)B(a2).B(an)1).xA(x)xA(x)2).xA(x)xA(x)1).xA(x)Bx(A(x)B)2).xA(x)Bx(A(x)B)3).xA(x)Bx(A(x)B)4).xA(x)Bx(x)B)5).BxA(x)x(BA(x),6).BxA(x)x(BA(x)7).xA(x)Bx(A(x)B)8).xA(x)Bx(A(x)B)1).x(A(x)B(x)xA(x)xB(x)2).x(A(x)B(x)xA(x)xB(x)3).x(A(x)B(x)xA(x)xB(x)4).xA(x)xB(x)x(A(x)B(x)4.会用等价公式求谓词公式的真值.(如P66题(3)例设论域为1,2,A(x,y):x+y=xy,求xyA(x,y)的真值.xyA(x,y)xyA(x,y)yA(1,y)yA(2,y)(A(1,1)A(1,2)(A(2,1)A(2,2)(TT)(TF)T,*5.将下面谓词公式写成前束范式(xF(x,y)yG(y)xH(x,y)(xF(x,y)yG(y)xH(x,y)(去)xF(x,y)yG(y)xH(x,y)(摩根)xF(x,y)yG(y)xH(x,y)(量词否定)xF(x,z)yG(y)tH(t,z)(变元换名)xyt(F(x,z)G(y)H(t,z)(辖域扩充),6.熟练掌握谓词逻辑推理.1).注意使用ES、US、EG、UG的限制条件,特别是ES,UG2).对于同一个客体变元，既有带也有带的前提，去量词时，应先去后去，这样才可以特指同一个客体 c.3).去量词时，该量词必须是公式的最左边的量词，且此量词的前边无任何符号，它的辖域作用到公式末尾。下面的作法是错误的：正确作法:xP(x)xQ(x)P xP(x)xQ(x)P P(c)xQ(x)US xP(x)xQ(x)T E或xP(x)Q(c)ES xP(x)xQ(x)T E实际上x的辖域扩充后 x(P(x)Q(x)T E 量词改成为x P(c)Q(c)ES P(c)Q(c)TE,下面的作法是错误的：正确作法:xP(x)P xP(x)P P(c)US xP(x)T E实际上中量词不是 P(c)ES x而是x xyP(x,y)P xyP(x,y)PxP(x,c)ES yP(c,y)US令P(x,y):y是x的生母，显然是个假命题4).添加量词时，也要加在公式的最左边，(即新加的量词前也无任何符号！)且其辖域作用到公式的末尾。例如下面作法是错误的:xP(x)Q(c)P xP(x)yQ(y)EG,例如.证明下面推理的有效性.证明:x(A(x)D(x)P A(a)D(a)ES A(a)T I D(a)T I x(A(x)(B(x)C(x)P A(a)(B(a)C(a)US B(a)C(a)T I x(A(x)(C(x)D(x)P A(a)(C(a)D(a)US C(a)D(a)T I C(a)T I B(a)T I A(a)B(a)T I x(A(x)B(x)EG,第三章 集合论初步1.幂集,全集,空集.2.集合的五种运算及相关性质(特别是差集，对称差.）3.应用包含排斥原理.,第三章 集合论初步基本概念:集合与元素,子集与真子集,空集,全集,幂集,并集,交集,相对补集(差集),绝对补集(补集),1空集,全集,幂集 空集:无元素的集合.x是矛盾式.(空集是唯一的)全集E:包含所讨论所有集合的集合.(全集不唯一)xE是永真式 幂 集:由A的所有子集构成的集合.P(A)=X|XA|P(A)|=2|A|2.掌握集合的五种运算及相关性质.AB=x|xAxB xAB xAxB AB=x|xAxB xAB xAxB A-B=x|xAx B xA-B xAxB A=E-A=x|xExA=x|xA xAxA A-B=A BAB=(A-B)(B-A)=x|(xAxB)(xBxA)AB=(AB)-(AB),例1.已知全集E=,AE,计算:a)P()P()=()b)P(A)P(A)=()c)P(E)-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()=,-,=,例2.令全集E为信息学院的学生的集合,C表示计算机专 业学生的集合,M表示学习了离散数学的学生的集合,D表示学习了数据结构课学生的集合,F表示一年级的学生的集合.用集合的关系式表达下面句子.“学习了离散数学和数据结构课的学生,一定是计算机专业的非一年级的学生”.解.(MD)(CF)例4.在什么条件下，下面命题为真？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，才有AB=所以满足此式的充要条件是:A-B=A-C,*有14位学生参加考试,9位同学数学得了优;5位同学物理得了优;4位同学化学得了优;其中物理和数学都得优的同学有4人;数学和化学都得优的同学有3人;物理和化学都得优的同学有3人;三门都得优的同学有2人;问没有得到优的有多少人?恰有两门得优的同学有多少人?解.令A、B、C分别表示数学、物理、化学得优同学集合.全集为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=4,第四章 二元关系1.关系的概念,表示方法.2.二元关系的 性质的定义,熟练掌握性质的判断及证明.3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质)4.掌握等价关系的判断,证明,求等价类和商集.*5.掌握相容关系的概念,关系图和矩阵的简化,求相容类,最大相容类和完全覆盖.6.偏序关系的判断,会画Hasse图,会求一个子集的极小(大)元,最小(大)元,上界与下界,最小上界及最大下界.注意本章证明题的证明过程的思路,一.关系的概念,表示方法,三个特殊关系.1.集合的笛卡 尔 积 AB=|xAyB|A|=m,|B|=n|AB|=mn 设A=0,1，B=a,b，求AB。AB=,2.二元关系的概念定义1:设A、是集合,如果AB,则称R是一个从A到 B的二元关系。如果 RAA,则称R是A上的二元关系.如果|A|=m|B|=n 则可以确定2mn个从A到B的不同关系.定义2:任何序偶的集合，都称之为一个二元关系。,3.关系的表示方法1).枚举法:即将关系中所有序偶一一列举出，写在大括号内.如:R=,2).(描述法)谓词公式法：即用谓词公式描述序偶中元素的关系。例如 R=|xy3).有向图法：,4).矩阵表示法：(实际上就是图论中的邻接矩阵)设A=a1,a2,am，B=b1,b2,bn是个有限集，RAB，定义R的mn阶矩阵 MR=(rij)mn，其中4.三个特殊关系1).空关系：AB，(或AA)，即无任何元素的关系.它的关系图中只有结点,无任何边；它的矩阵中全是0。2).完全关系(全域关系)：AB(或AA)本身是一个从A到B(或A上)的完全关系.即含有全部序偶的关系。它的矩阵中全是1。,3).恒等关系IA：IAAA,且IA=|xA称之为A 上的恒等关系。例如A=1,2,3,则IA=,A上的、完全关系AA及IA的关系图及矩阵如下：,二.关系的性质:熟练掌握性质的判断及证明.1.自反性定义:设R是集合A中的关系，如果对于任意xA都有 R(xRx)，则称R是A中自反关系。即 R是A中自反的x(xAxRx)2.反自反性定义：设R是集合A中的关系，如果对于任意的xA都有 R，则称R为A中的反自反关系。即 R是A中反自反的x(xAR)3.对称性定义:R是集合A中关系,若对任何x,yA,如果有xRy,必有 yRx,则称R为A中的对称关系。R是A上对称的xy(xAyAxRy)yRx),4.反对称性定义:设R为集合A中关系,若对任何x,yA,如果有xRy,和 yRx,就有x=y,则称R为A中反对称关系。R是A上反对称的xy(xAyAxRyyRx)x=y)xy(xAyAxyR)R)5.传递性定义:R是A中关系，对任何x,y,zA,如果有xRy,和yRz,就 有xRz,则称R为A中传递关系。即R在A上传递 xyz(xAyAzAxRyyRz)xRz)这些性质要求会判断,会证明.这里特别要注意的是,这些定义都是蕴涵式,所以当蕴涵式当前件为假时,此蕴涵式为真,即此性质 成立!,从关系的矩阵,从关系的有向图,性质判定:,判断下面关系的性质:,关系性质当证明方法归纳:设R是A上关系，1.证明R的自反性：方法1 用自反定义证：任取 xA,证出R.方法2 用恒等关系IA证：证出IA R.(见教材P119(2)方法3 用自反闭包证：证出r(R)=R,即RIA=R.2.证明R的反自反性：方法1 用反自反定义证：任取 xA,证出R.3.证明R的对称性：方法1 用对称定义证：任取 x,yA,设R,证出 R.方法2 用求逆关系证：证出 Rc=R.方法3 用对称闭包证：证出 s(R)=R,即RRc=R.,4.证明R的反对称性：方法1 用定义1证：任取 x,yA,设R,R.证出 x=y。方法2用定义2证：任取 x,yA,xy,设R,证出R.方法3 用定理证：证出 RRc IA.(见教材P118)5.证明R的传递性：方法1 用传递定义证：任取 x,y,zA,设R,R,证出 R.方法2 用传递闭包证：证出 t(R)=R,即 RR2R3.=R.方法3用定理证：证出(见教材P119(2)同学们可以根据具体情况,选用相应方法证明.其中必须掌握的是用基本定义证明.,三.掌握关系复合,求逆及闭包运算(计算方法及性质)(一)关系的复合 1.定义:设RXY，SYZ，则 RSXZ。RS=|xXzZy(yY RS)2.计算方法(俗称过河拆桥法)枚举法 R=,S=,RS=,有向图,矩阵3.性质1).满足结合律:RAB SBC TCD 则 R(ST)=(RS)T2).RAB SBC TBC R(ST)=(RS)(RT)R(ST)(RS)(RT)3).R是从A到B的关系，则 R IB=IA R=R 推论:RAA,则 R IA=IA R=R(IA是运算的幺元)4).关系的乘幂 R0=IA，RAA,Rm Rn=Rm+n(Rm)n=Rmn(m,n为非负整数),(二).逆关系1.定义:设RXY，R的逆关系 RC=|R RC R2.计算方法 1).R=,RC=,2).RC的有向图:是将R的有向图的所有边的方向颠倒.3).RC的矩阵 MRC=(MR)T 即为R矩阵的转置3.性质 令R、S都是从X到Y的关系，则 1).(RC)C=R 2).(RS)C=RCSC。3).(RS)C=RCSC。4).(RS)C=RCSC。,5).RS 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。,(三).闭包运算1.定义：给定 A中关系R,若A上另一个关系R，满足：RR；R是自反的(对称的、传递的)；R是“最小的”，即对于任何A上自反(对称、传递)的关系R”,如果RR”,就有RR”。则称R是R的自反(对称、传递)闭包。记作r(R)、(s(R)、t(R)(reflexive、symmetric、transitive)2.计算方法 给定 A中关系R r(R)=RIA。s(R)=RRC。t(R)=RR2R3.。t(R)=RR2.Rn*求t(R)矩阵的Warshall算法.,闭包的运算有三种形式:如A=a.b.c R AA R=,a).集合形式.r(R)=RIA=,=,s(R)=RRC=,=,R2=,R3=,t(R)=RR2R3=,=,.,b)有向图形式.,c)矩阵形式.,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)也传递。*3).设R是A上关系，则 sr(R)=rs(R)tr(R)=rt(R)st(R)ts(R),四.等价关系 掌握等价关系的判断,证明,求等价类和商集.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是自反的、对称的和传递 的，则称R是A中的等价关系。3.等价关系R的有向图:可能由若干个独立子图构成的，每个独立子图都是完全关系图。,4.等价类：1).定义:R是A上的等价关系,aA,由a确定的集合aR aR=x|xAR 称集合aR为由a形成的R等价类。2).由等价关系图求等价类：R图中每个独立子图上的结点构成一个等价类。不同的等价类个数=独立子图个数。3).等价类性质 R是A上等价关系，任意a,b,cA 同一个等价类中的元素，彼此有等价关系R。aRbR=，当且仅当 R。aR=bR 当且仅当 R。.A中任何元素a,a必属于且仅属于一个等价类。.任意两个等价类 aR,bR,要么aR=bR，要么aRbR=。R的所有等价类构成的集合是A的一个划分。,5.商集:定义：R是A上等价关系，由R的所有等价类构成的集合称之为A关于R的商集。记作A/R。即 A/R=aR|aA6.商集应用.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).无向图结点之间的连通关系是个等价关系.令G=是无向图,R是V上连通关系,即 R=|u和v是连通的例.给定图G如右上图所示:V/R=a,b,g,c,d,e,f,h,3).图的同构关系是个等价关系.令上述图构成的集合A=a,b,c,d,e,f,g,h,i,j,求商集A/.A/=a,h,b,i,c,e,d,f,g,j,练习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)不是.请看反例:,b)RS是等价关系.证明：1.证明RS的自反性方法1 用自反定义证：任取 xA,(证出RS)因R和S都自反，所以有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也自反。,2.证明RS的对称性：方法1 用对称定义证：任取 x,yA,设RS,(证出 RS.)则R，S，因为R和S对称，所以有R，S，于是RS。RS对称。方法2 用求逆关系证：(证出(RS)c=RS.)因为R和S对称，所以有Rc=R，Sc=S，而(RS)c=RcSc=RS，RS对称。方法3 用对称闭包证：(证出 s(RS)=RS,)因为R和S对称，所以s(R)=R,s(S)=Ss(RS)=(RS)(RS)c=(RS)(RcSc)=(RRc)(RSc)(SSc)(SRc)=(s(R)(RSc)(s(S)(SRc)=(R(RSc)(S(SRc)=RS(吸收律)RS对称。,3.证明RS的传递性：方法1 用传递定义证：任取 x,y,zA,设RS,RS,(证出RS)RSRS RSRS(RR)(S S)RS（因为R、S传递）RS 所以RS传递。所以RS是A上等价关系.,e)证明.R2是等价关系.方法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传递。最后得R2是等价关系。,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=(t(R)c=Rc 所以Rc传递。所以Rc是A上等价关系.,练习2.五.设X=1,2,3 Y=1,2,在X的幂集P(X)上定义二元关系R如下:对于任何A,BP(X),ARB 当且仅当 AY=BY1.画出关系R的有向图.2.R是等价关系吗?如果是,请写出商集P(X)/R.如果不是请说明原因解.1.关系R的有向图.2.从R有向图看出R有自反,对称和传递性,故是等价关系 P(X)/R=,1,2,1,2,3,1,3,2,3,1,2,3,*五.相容关系1.定义:给定集合X上的关系r,若r是自反的、对称的,则r是A上相容关系。2.图的简化：不画环；两条对称边用一条无向直线代替。3.矩阵的简化：因为r的矩阵是对称阵且主对角线全是1，用下三角矩阵(不含主对角线)代替r的矩阵。4.相容类：设r是集合X上的相容关系，CA,如果对于C 中任意两个元素x,y有r,称C是r的一个相容类.5.最大相容类:设r是集合X上的相容关系，C是r的一个相容类，如果C不能被其它相容类所真包含，则称C是一个最大相容类。-最大完全多边形.6.完全覆盖：r是中的相容关系，由r的所有最大相容类为元素构成的集合，称之为X的完全覆盖。记作Cr(X)。,练习.已知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,6,1,2,3,4,5,6,7,五.偏序关系判断,会画Hasse图,会求一个子集的极小(大)元,最小(大)元,上界与下界,最小上界及最大下界.1.定义：R是A上自反、反对称和传递的关系，则称R 是A上的偏序关系。并称是偏序集。2.x与y是可比较的：是偏序集，x,yA，如果要么xy,要么yx,则称x与y是可比较的。3.定义：是偏序集，任何x,yA，如果x与y都是可比较的，则称是全序关系(线序、链)。4.偏序集Hasse图的画法：令是偏序集，1).用“”表示A中元素。2).如果xy,且xy，则结点y要画在结点x的上方。3).如果xy,且y盖住x，x与y之间连一直线。4).从最下层结点(全是射出的边与之相连，逐层向上画，直到最上层结点(全是射入的边与之相连)。,例如,5.重要元素y是B的极小元y(yBx(xBxyxy)(在B中没有比y更小的元素了，y就是极小元)y是B的极大元y(yBx(xBxyyx)(在B中没有比y更大的元素了，y就是极大元)y是B的最小元y(yBx(xB yx)(最小元y是B中元素，该元素比B中所有元素都小)y是B的最大元y(yBx(xB xy)(最大元y是B中元素，该元素比B中所有元素都大)y是B的上界y(yAx(xB xy)(上界y是A中元素，该元素比B中所有元素都大)y是B的下界y(yAx(xB yx)(下界y是A中元素，该元素比B中所有元素都小),y是B的上界，并且对B的所有上界x,都有yx,则称y是B的最小上界(上确界)，记作LUB B=y。(即y是上界中最小的。如果B有上确界，则是唯一的)y是B的下界，并且对B的所有下界x,都有xy,则称y是B的最大下界(下确界)，记作GLB B=y。(即y是下界中最大的。如果B有上确界，则是唯一的)例如 B=2,3,6B的极小元:2,3 极大元:6 最小元:无 最大元:6 下界:1 上界:6,12,18 下确界:1 上确界:6,第八章 图论1.掌握图的基本概念.(特别注意相似的概念)2.熟练掌握图中关于结点度数的定理.(会应用)3.无向图的连通性的判定,连通分支及连通分支数的概念.4.有向图的可达性,强连通,单侧连通和弱连通的判定.求强分图,单侧分图和弱分图.5.会求图的矩阵.6.会判定欧拉图和汉密尔顿图.*7.会判定平面图,掌握欧拉公式.*8.了解对偶图.9.掌握树的基本定义,v和e间的关系式.会画生成树,会求最小生成树.根树的概念,完全m叉树的公式,会画最优树,*会设计前缀码.,一.图的概念 图的定义,有向边,无向边,平行边,环 邻接点,邻接边,孤立结点 有向图,无向图,简单图,混合图,零图,平凡图,多重图,完全图,子图,生成子图,补图,结点的度,结点的出度,结点的入度,图的最大度(G),最小度(G),图所有结点度数总和与边的关系,出度和与入度和关系 图的同构,二.路与回路 路,回路,迹,闭迹,通路,圈 无向图的连通性:连通图,连通分支,连通分支数W(G),点割集,割点,点连通度k(G),边割集,割边(桥),边连通度(G)结点间的距离,图的直径 有向图的连通性:可达性,强连通,单侧连通,弱连通,强分图,单侧分图,弱分图.(会求这些分图),三.图的矩阵 邻接矩阵A:结点与结点之间的邻接关系矩阵.根据邻接矩阵判断:各结点的度,有向图结点出,入度.由Ak可以求一个结点到另一个结点长度为k的路条数.可达矩阵P:结点u到结点v的可达性的矩阵.用P可以判定:各结点的度.有向图的强分图.关联矩阵M:是结点与边的关联关系矩阵.用M判定:各结点的度,四.欧拉图与汉密尔顿图(会判定)欧拉路,欧拉回路,欧拉图.判定:有欧拉路的充要条件:无或有两个奇数度的结点.有欧拉回路的充要条件:所有结点度数均为偶数.汉密尔顿路,汉密尔顿回路,汉密尔顿图 汉密尔顿图的判定:必要条件:V的任何非空子集S,有W(G-S)|S|充分条件:每对结点的度数和|V|=n*五.平面图 平面图的定义,平面的边界,欧拉公式:v-e+r=2 判定:必要条件:e3v-6*充要条件:G不含与K5或K3,3在2度结点内同构子图.,*六.对偶图与着色 会画对偶图,会对图正常着色.*七.二部图 作为一般了解,掌握K3.3八.树与生成树 树的定义:6个定义,其中最主要的是连通无回路,e=v-1 分支结点,叶结点 会求最小生成树九.根树 m叉树,完全 m叉树,(m-1)i=t-1 会画最优树,*会设计前缀码,