离散数学期末复习大纲课件

离 散 数 学期 末 总 复 习1精选ppt复 习 时 注 意准确掌握每个概念准确掌握每个概念灵活灵活应应用所学定理用所学定理注意解注意解题题思路清晰思路清晰证证明明问题时问题时,先用反向思先用反向思维维(从从结结论论入手入手)分析分析问题问题,再按正向思再按正向思维维写出写出证证明明过过程程.2精选ppt全全书书知知识识网网络络：图图论论篇篇同构同构同构同构格与布格与布尔尔代数代数半群半群,独异点独异点,群群,环环,域域代数系代数系统统篇篇n 元运算元运算命命题逻辑题逻辑谓词逻辑谓词逻辑集合初步集合初步二元关系二元关系函函 数数集合集合论论篇篇数理数理逻辑逻辑篇篇3精选ppt总 复 习复复习习重点重点(注注:标标有有*的内容的内容,对对网网络络学院学生不作要求学院学生不作要求)第一章第一章 命命题逻辑题逻辑1.联结词联结词的定的定义义(含含义义及真及真值值表定表定义义).2.会命会命题题符号化符号化.3.永真式的永真式的证证明明.4.永真永真蕴蕴涵式的涵式的证证明明,记记住并能熟住并能熟练应练应用常用公式用常用公式.5.等价公式的等价公式的证证明明,记记住并能熟住并能熟练应练应用常用公式用常用公式.6.会写命会写命题题公式的范式公式的范式,*能能应应用范式解决用范式解决问题问题.7.熟熟练练掌握命掌握命题逻辑题逻辑三种推理方法三种推理方法.4精选ppt第二章第二章 谓词逻辑谓词逻辑1.准确掌握有关概念准确掌握有关概念.2.会命会命题题符号化符号化.(如如P60题题(2)3.掌握常用的等价公式和永真掌握常用的等价公式和永真蕴蕴涵式涵式.包括包括:带带量量词词的公式在的公式在论论域内展开式域内展开式,量量词词否定否定,量量词辖词辖域域扩扩充充,量量词词分配公式分配公式.4.会用等价公式求会用等价公式求谓词谓词公式的真公式的真值值.(如如P66题题(3)*5.会写前束范式会写前束范式6.熟熟练练掌握掌握谓词逻辑谓词逻辑推理推理.第三章第三章 集合集合论论初步初步1.集合的表示集合的表示,幂幂集集,全集全集,空集空集.2.集合的三种关系集合的三种关系(包含包含,相等相等,真包含真包含)的定的定义义及及证证明明.3.集合的五种运算及相关性集合的五种运算及相关性质质.*4.应应用包含排斥原理用包含排斥原理.5精选ppt第四章第四章 二元关系二元关系1.关系的概念关系的概念,表示方法表示方法.2.二元关系的二元关系的 性性质质的定的定义义,熟熟练练掌握性掌握性质质的判断及的判断及证证明明.3.掌握关系的复合掌握关系的复合,求逆及求逆及闭闭包运算包运算(计计算方法及有关性算方法及有关性质质)4.掌握等价关系的判断掌握等价关系的判断,证证明明,求等价求等价类类和商集和商集.*4.掌握相容关系定掌握相容关系定义义,简简化化图图和和简简化矩化矩阵阵,相容相容类类,最大相最大相容容类类,完全覆盖完全覆盖.5.偏序关系的判断偏序关系的判断,会画会画Hasse图,会求一个子集的极小会求一个子集的极小(大大)元元,最小最小(大大)元元,上界与下界上界与下界,最小上界及最大下界最小上界及最大下界.第六章第六章 函数函数1.函数的定函数的定义.2.函数的函数的类型型,会判断会判断,会会证明明.3.会会计算函数的复合算函数的复合(左复合左复合),求逆函数求逆函数.知道有关性知道有关性质.*4.了解集合的特征函数了解集合的特征函数,了解集合的基数了解集合的基数,可数集合可数集合.6精选ppt第六章第六章 代数系代数系统统1.掌握运算的定掌握运算的定义义.2.熟熟练练掌握二元运算的性掌握二元运算的性质质的判断及的判断及证证明明.3.掌握代数系掌握代数系统统的同构定的同构定义义,会会证证明明.了解同构性了解同构性质质的保持的保持.4.了解半群了解半群,独异点独异点,*环环和和*域的概念域的概念.5.熟熟练练掌握群掌握群,子群子群,交交换换群群(会会证证明明),了解循了解循环环群群.*6,子群的陪集子群的陪集,Lagrange定理及其推定理及其推论论,(会会应应用用).*第七章第七章 格与布格与布尔尔代数代数*1.掌握格的定掌握格的定义义,了解格的性了解格的性质质.*2.会判断格会判断格,分配格分配格,有有补补格和布格和布尔尔格格,*3.重点掌握两个元素的布重点掌握两个元素的布尔尔代数的性代数的性质质(10个个).*4.会写两个元素的布会写两个元素的布尔尔表达式的范式表达式的范式.(实质实质是第一章的是第一章的主析取和主合取范式主析取和主合取范式).7精选ppt第八章第八章 图论图论1.掌握掌握图图的基本概念的基本概念.(特特别别注意相似的概念注意相似的概念)2.熟熟练练掌握掌握图图中关于中关于结结点度数的定理点度数的定理.(会会应应用用)3.无向无向图图的的连连通性的判定通性的判定,连连通分支及通分支及连连通分支数的概念通分支数的概念.4.有向有向图图的可达性的可达性,强强连连通通,单侧连单侧连通和弱通和弱连连通的判定通的判定.求求强强 分分图图,单侧单侧分分图图和弱分和弱分图图.5.会求会求图图的矩的矩阵阵.6.会判定欧拉会判定欧拉图图和和汉汉密密尔尔顿图顿图.*7.会判定平面会判定平面图图,掌握欧拉公式掌握欧拉公式.*8.了解了解对对偶偶图图.9.掌握掌握树树的基本定的基本定义义,v和和e间的关系式的关系式.会画生成会画生成树,会求会求最最小生成小生成树.根根树的概念的概念,完全完全m叉叉树的公式的公式,会画最会画最优树,*会会设计前前缀码.8精选ppt总 复 习复复习习重点重点第一章第一章 命命题逻辑题逻辑1.联结词联结词的定的定义义(含含义义及真及真值值表定表定义义).2.会命会命题题符号化符号化.3.永真式的永真式的证证明明.4.永真永真蕴蕴涵式的涵式的证证明明,记记住并能熟住并能熟练应练应用常用公式用常用公式.5.等价公式的等价公式的证证明明,记记住并能熟住并能熟练应练应用常用公式用常用公式.6.会写命会写命题题公式的范式公式的范式,*能能应应用范式解决用范式解决问题问题.7.熟熟练练掌握命掌握命题逻辑题逻辑三种推理方法三种推理方法.9精选ppt第一章第一章 命命题逻辑题逻辑1.1.联结词联结词定定义义了六个了六个逻辑联结词逻辑联结词，分，分别别是：是：(1)否定否定“”(2)合取合取“”(3)析取析取“”(4)异或异或“”(5)蕴蕴涵涵“”(6)等价等价“”要熟要熟练练掌握掌握这这五个五个联结词联结词在自然在自然语语言中所表示的含言中所表示的含义义以以及它及它们们的真的真值值表的定表的定义义。：否定：否定 表示表示“不不”：合取：合取 表示表示“不但不但,而且而且.”“并且并且”：析取：析取 表示表示“或者可兼取的或或者可兼取的或”：异或：异或 表示表示“或者不可兼取的或或者不可兼取的或”：蕴蕴涵涵 表示表示“如果如果,则则.”:等价等价 表示表示“当且当且仅仅当当”“充分且必要充分且必要”可以将可以将这这六个六个联结词联结词看成六种看成六种“运算运算”。10精选ppt联结词联结词的定的定义义(包括真包括真值值表和含表和含义义).特特别别要注意：要注意：“或者或者”的二的二义义性性,即要区分即要区分给给定的定的“或或”是是“可兼取的或可兼取的或”还还是是“不可兼取的或不可兼取的或 ”。“”的用法的用法，它既表示，它既表示“充分条件充分条件”也表示也表示“必要条件必要条件”,”,即要弄清哪个作即要弄清哪个作为为前件前件,哪个作哪个作为为后件后件.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精选ppt2.会命会命题题符号化符号化.例如例如 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(Q R)(PQ)P(PQP Q)(R(QR)(PQ)P (公式的否定公公式的否定公式式)(R(QR)(PQ)P)(结结合律合律)(R Q)(RR)(PP)(QP)(分配律分配律)(R Q)(QP)R QQP T(互互补补,同一律同一律)12精选ppt4.永真永真蕴蕴涵式的涵式的证证明明,记记住常用的公式住常用的公式.永真永真蕴蕴涵式涵式: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)为为永真式永真式.对对于于给给定一个定一个题题,究竟是用哪种方法究竟是用哪种方法,原原则则上哪种都可以上哪种都可以.但是哪个方法但是哪个方法简单简单,要根据具体要根据具体题题而定而定.A B A B F F T F T T T F F T T T13精选ppt5.等价公式的等价公式的证证明明,记记住常用的公式住常用的公式.方法方法1.列真列真值值表表.方法方法2.用公式的等价用公式的等价变换变换.例如例如:证证明明 P(QR)(PQ)R P(QR)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精选ppt6.命命题题公式的范式公式的范式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 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精选ppt6)大大项项及其性及其性质质.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 F7)主析取范式主析取范式:A1A2.An (n1)Ai(i=1,2.n)小小项项.8)主合取范式主合取范式:A1A2.An (n1)Ai(i=1,2.n)大大项项.16精选ppt9).会写主析取范式和主合取范式会写主析取范式和主合取范式.求下面命求下面命题题公式的范式公式的范式: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 F T TF T F FF T T TT F F FT F T TT T F FT T T T17精选ppt方法方法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 QR)(P QR)18精选ppt已知已知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精选ppt7.会用三种推理方法会用三种推理方法,进进行行逻辑逻辑推理推理.会用三个推理会用三个推理规则规则:P,T,CP例如例如:证证明明 (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精选ppt(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精选ppt(AB)C)D(CD)A B3.反反证证法法:(A B)P(假假设设前提前提)AB T E9(AB)C P C T I11 D P CD P C T I10C C T I922精选ppt 第二章第二章 谓词逻辑谓词逻辑1.准确掌握有关概念准确掌握有关概念.2.会命会命题题符号化符号化.(如如P60题题(2)3.掌握常用的等价公式和永真掌握常用的等价公式和永真蕴蕴涵式涵式.包括包括:带带量量词词的公式在的公式在论论域内展开式域内展开式,量量词词否定否定,量量词辖词辖域域扩扩充充,量量词词分配公式分配公式.4.会用等价公式求会用等价公式求谓词谓词公式的真公式的真值值.(如如P66题题(3)*5.会写前束范式会写前束范式6.熟熟练练掌握掌握谓词逻辑谓词逻辑推理推理.23精选ppt 第二章第二章 谓词逻辑谓词逻辑1.准确掌握有关概念准确掌握有关概念.客体客体:客体客体变变元元,谓词谓词,量量词词,量量词词后的指后的指导变导变元元,量量词词的的辖辖域域,约约束束变变元与自由元与自由变变元元,论论域域,全全总总个体域个体域,谓词谓词公式公式(WFF),命命题题函数函数,前束范式前束范式,24精选ppt2.会命会命题题符号化符号化.(如如P60题题(2)命命题题的符号表达式与的符号表达式与论论域有关。域有关。当当论论域域扩扩大大时时，需要，需要添加用来表示客体特性的添加用来表示客体特性的谓词谓词，称此，称此谓词为谓词为特性特性谓词谓词。特性特性谓词谓词往往就是往往就是给给定命定命题题中量中量词词后后边边的那个名的那个名词词。如如“所有所有自然数自然数.”.”、“有些有些大学生大学生.”.”。如何添加特性如何添加特性谓词谓词，这这是个十分重要的是个十分重要的问题问题，这这与前与前边边的量的量词词有关有关。如果如果前前边边是是全称量全称量词词，特性特性谓词谓词后后边边是是蕴蕴含含联结词联结词“”“”；如果如果前前边边是是存在量存在量词词，特性特性谓词谓词后后边边是是合取合取联结词联结词“”“”。另外有些命另外有些命题题里有的客体在句中没有明确的量里有的客体在句中没有明确的量词词 ,而在而在写它的符号表达式写它的符号表达式时时,必必须须把把隐隐含的量含的量词词明确的写出来明确的写出来.25精选ppt例如例如金子金子闪闪光光,但但闪闪光的不一定都是金子光的不一定都是金子.设设: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 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精选ppt3.掌握常用的等价公式和永真掌握常用的等价公式和永真蕴蕴涵式涵式.包括包括:带带量量词词的公式在的公式在论论域内展开式域内展开式,量量词词否定否定,量量词辖词辖域域扩扩充充,量量词词分配公式分配公式.设论设论域域为为aa1 1,a,a2 2,.,a,.,an n，则则 1).1).xA(x)xA(x)A(aA(a1 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).B xA(x)xA(x)x(BA(x)x(BA(x)27精选ppt6).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).xA(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精选ppt*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)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精选ppt6.熟熟练练掌握掌握谓词逻辑谓词逻辑推理推理.1).注意使用注意使用ES、US、EG、UG的限制条件的限制条件,特特别别是是ES,UG2).对对于同一个客体于同一个客体变变元，既有元，既有带带 也有也有带带 的前提，去量的前提，去量词时词时，应应先去先去 后去后去，这样这样才可以特指同一个客体才可以特指同一个客体 c.3).去量去量词时词时，该该量量词词必必须须是公式的最左是公式的最左边边的量的量词词，且此，且此量量词词的前的前边边无任何符号无任何符号，它的，它的辖辖域作用到公式末尾。域作用到公式末尾。下面的作法是下面的作法是错误错误的：的：正确作法正确作法: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 P(c c)Q(c)ES P P(c c)Q(c)TE30精选ppt下面的作法是下面的作法是错误错误的：的：正确作法正确作法: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的的生母，生母，显显然然是个假命是个假命题题4).添加量添加量词时词时，也要加在公式的最左，也要加在公式的最左边边，(即新加的量即新加的量词词前也无任何符号前也无任何符号！)且其且其辖辖域作用到公式的末尾。域作用到公式的末尾。例如下面作法是例如下面作法是错误错误的的:x xP P(x x)Q(c)P x xP P(x x)y yQ(y)EG31精选ppt例如例如.证证明下面推理的有效性明下面推理的有效性.证证明明: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(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精选ppt第三章第三章 集合集合论论初步初步1.集合的表示集合的表示,幂幂集集,全集全集,空集空集.2.集合的三种关系集合的三种关系(包含包含,相等相等,真包含真包含)的定的定义义及及证证明明.3.集合的五种运算及相关性集合的五种运算及相关性质质.*4.应应用包含排斥原理用包含排斥原理.33精选ppt第三章第三章 集合集合论论初步初步基本概念基本概念:集合与元素集合与元素,子集与真子集子集与真子集,空集空集,全集全集,幂幂集集,并集并集,交集交集,相相对补对补集集(差集差集),绝对补绝对补集集(补补集集)1.集合的表示集合的表示,元素与集合的属于关系元素与集合的属于关系.集合的三种表示方法集合的三种表示方法:枚枚举举法法:一一列出集合中的元素一一列出集合中的元素.谓词谓词描述法描述法:用用谓词谓词描述集合中元素的性描述集合中元素的性质质.文氏文氏图图:用一个平面区域表示用一个平面区域表示.2.集合的三种关系集合的三种关系(被包含被包含,相等相等,被真包含被真包含)的定的定义义及及证证明明.A B x(xAxB)A=B A B B Ax(xAxB)A BA B ABx(xAxB)x(xB x A)34精选ppt3空集空集,全集全集,幂幂集集 空集空集:无元素的集合无元素的集合.x是矛盾式是矛盾式.(空集是唯一的空集是唯一的)全集全集E:包含所包含所讨论讨论所有集合的集合所有集合的集合.(全集不唯一全集不唯一)xE是永真式是永真式 幂 集集:由由A的所有子集构成的集合的所有子集构成的集合.P(A)=X|X A|P(A)|=2|A|4.掌握集合的五种运算及相关性掌握集合的五种运算及相关性质质.AB=x|xAxB xAB xAxB AB=x|xAxB xAB xAxB A-B=x|xAx B xA-B xAx B A=E-A=x|xEx A=x|x A xAx A A-B=A BA B=(A-B)(B-A)=x|(xAx B)(xBx A)A B=(AB)-(AB)35精选ppt例例1.已知全集已知全集E=,A E,计计算算: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()=,-,=,36精选ppt例例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 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精选ppt例例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)所以所以(A-B)-C=A-(BC)例例4.令全集令全集E为信息学院的学生的集合信息学院的学生的集合,C表示表示计算机算机专 业学生的集合学生的集合,M表示学表示学习了离散数学的学生的集合了离散数学的学生的集合,D表表示学示学习了数据了数据结构构课学生的集合学生的集合,F表示一年表示一年级的学生的的学生的集合集合.用集合的关系式表达下面句子用集合的关系式表达下面句子.“学学习了离散数学和数据了离散数学和数据结构构课的学生的学生,一定是一定是计算机算机专业的非一年的非一年级的学生的学生”.解解.(MD)(CF)38精选ppt例例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，才有，才有A B=所以所以满足此式的足此式的充要条件充要条件是是:A-B=A-C39精选ppt*例例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 x A)EG x(xAxC)x(xC x A)T I40精选ppt*有有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=441精选ppt 第四章第四章 二元关系二元关系1.关系的概念关系的概念,表示方法表示方法.2.二元关系的二元关系的 性性质质的定的定义义,熟熟练练掌握性掌握性质质的判断及的判断及证证明明.3.掌握关系的复合掌握关系的复合,求逆及求逆及闭闭包运算包运算(计计算方法及有关性算方法及有关性质质)4.掌握等价关系的判断掌握等价关系的判断,证证明明,求等价求等价类类和商集和商集.*5.掌握相容关系的概念掌握相容关系的概念,关系关系图图和矩和矩阵阵的的简简化化,求相容求相容类类,最大相容最大相容类类和完全覆盖和完全覆盖.6.偏序关系的判断偏序关系的判断,会画会画Hasse图,会求一个子集的极小会求一个子集的极小(大大)元元,最小最小(大大)元元,上界与下界上界与下界,最小上界及最大下界最小上界及最大下界.注意本章注意本章证证明明题题的的证证明明过过程的思路程的思路42精选ppt一一.关系的概念关系的概念,表示方法表示方法,三个特殊关系三个特殊关系.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|=m|B|=n 则可以确定可以确定2mn个从个从A到到B的不同关系的不同关系.定定义义2:任何任何序偶的集合序偶的集合，都称之，都称之为为一个二元关系。一个二元关系。43精选ppt3.3.关系的表示方法关系的表示方法1).1).枚枚举举法法:即将关系中所有序偶一一列即将关系中所有序偶一一列举举出，写在大括号内出，写在大括号内.如如:R=,2).(2).(描述法描述法)谓词谓词公式法公式法：即用即用谓词谓词公式描述序偶中元素的关系。例如公式描述序偶中元素的关系。例如 R=|xy3).3).有向有向图图法法：1。2。3。4。ABabcR1:1。4。23R2:44精选ppt4).矩阵表示法：(实际实际上就是上就是图论图论中的中的邻邻接矩接矩阵阵)设设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上上)的完全关系的完全关系.即含有全部序偶的关系。它的矩即含有全部序偶的关系。它的矩阵中全是中全是1。1 若若R 0 若若R(1im,1jn)rij=45精选ppt3).恒等关系恒等关系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精选ppt二二.关系的性关系的性质质:熟熟练练掌握性掌握性质质的判断及的判断及证证明明.1.自反性自反性定定义义:设设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上上对对称的称的x y(x A y A xRy)yRx)47精选ppt4.反反对对称性称性定定义义:设设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 A xRy yRz)xRz)这这些性些性质质要求会判断要求会判断,会会证证明明.这这里特里特别别要注意的是要注意的是,这这些定些定义义都是都是蕴蕴涵式涵式,所以当所以当蕴蕴涵涵式当前件式当前件为为假假时时,此此蕴蕴涵式涵式为为真真,即此性即此性质质 成立成立!48精选ppt自反性自反性反自反性反自反性对对称性称性传递传递性性反反对对称性称性每个每个结结点都有点都有环环 主主对对角角线线全是全是1每个每个结结点都无点都无环环 主主对对角角线线全是全是0不同不同结结点点间间如果有如果有边边,则则有方向相反的两条有方向相反的两条边边.是以是以对对角角线为对线为对称称 的矩的矩阵阵不同不同结结点点间间,最多有一最多有一条条边边.以主以主对对角角线为对线为对称称的位置不会同的位置不会同时为时为1如果有如果有边边,则也有也有边.或者使得前件或者使得前件为假假.如果如果aij=1,且且ajk=1,则aik=1从关系的矩从关系的矩阵阵从关系的有向从关系的有向图图 性性质质判定判定:49精选ppt判断下面关系的性判断下面关系的性质质: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精选ppt1。2。1。2。1。2。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精选ppt关系性关系性质质当当证证明方法明方法归纳归纳:设设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的的反自反性反自反性：方法方法1 用反自反定用反自反定义证义证：任取：任取 xA,证出出 R.3.3.证证明明R R的的对对称性称性：方法方法1 用用对对称定称定义证义证：任取任取 x,yA,设R,证出出 R.方法方法2 用求逆关系用求逆关系证证：证出出 Rc=R.方法方法3 用用对对称称闭闭包包证证：证出出 s(R)=R,即即RRc=R.52精选ppt4.4.证证明明R R的的反反对对称性称性：方法方法1 用定用定义义1证证：任取任取 x,yA,设R,R.证出出 x=y。方法方法2用定用定义义2证证：任取任取 x,yA,xy,设R,证出出 R.方法方法3 用定理用定理证证：证出出 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精选ppt三三.掌握关系复合掌握关系复合,求逆及求逆及闭闭包运算包运算(计计算方法及性算方法及性质质)(一一)关系的复合关系的复合 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精选ppt 矩矩阵阵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 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精选ppt(二二).).逆关系逆关系1.定定义义:设设R XY，R的逆关系的逆关系 RC=|R R RC R2.计计算方法算方法 1).R=,RC=,2).RC的有向的有向图:是将是将R的有向的有向图的所有的所有边的方向的方向颠倒倒.3).RC的矩的矩阵 MRC=(MR)T 即即为为R R矩矩阵阵的的转转置置3.性性质质 令令R、S都是从都是从X到到Y的关系，的关系，则则 1).(RC)C=R 2).(RS)C=RCSC。3).(RS)C=RCSC。4).(RS)C=RCSC。56精选ppt 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精选ppt(三三).).闭闭包运算包运算1.1.定定义义：给给定定 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)=RR2.Rn*求求t(R)矩矩阵的的Warshall算法算法.58精选ppt闭闭包的运算有三种形式包的运算有三种形式:如如A=a.b.c R AA R=,a).集合形式集合形式.r(R)=RIA=,=,s(R)=RRC=,=,R2=,R3=,t(R)=RR2R3 =,=,.,59精选pptb)有向有向图形式形式.bacR3RbacbacIA=r(R)bacRbacbR2act(R)bac=cRbac=bRCas(R)bac60精选pptc)矩矩阵形式形式.Mr(R)=MRMIA=010001100100010001=111110011Ms(R)=MRMRC=010001100001100010=011101110Mt(R)=M M M =010001100001100010=111111111R2R3R10001000161精选ppt3.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)62精选ppt四四.等价关系等价关系 掌握等价关系的判断掌握等价关系的判断,证证明明,求等价求等价类类和商集和商集.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的有向的有向图图:可能由若干个独立子可能由若干个独立子图图构成的，构成的，每个独立子每个独立子图图都是完全关系都是完全关系图图。1。2。3R11。2。3R21。2。R363精选ppt4.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图图中每个独立子中每个独立子图图上的上的结结点点构成一个等价构成一个等价类类。不同的等价。不同的等价类类个数个数=独立子独立子图图个数。个数。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 RbbR R=。R的所有等价的所有等价类类构成的集合是构成的集合是A的一个划分。的一个划分。64精选ppt5.商集商集:定定义义：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).无向无向图结图结点之点之间间的的连连通关系是个等价关系通关系是个等价关系.令令G=是无向是无向图图,R是是V上上连连通关系通关系,即即 R=|u和和v是是连通的通的例例.给定定图G如右上如右上图所示所示:V/R=a,b,g,c,d,e,f,h无元素无元素1个元素个元素2个元素个元素3个元素个元素可数集可数集 不可数集不可数集.ghabefcd65精选ppt3).3).图的同构关系的同构关系是个等价关系是个等价关系.令上述令上述图构成的集合构成的集合A=a,b,c,d,e,f,g,h,i,j,求商集求商集A/.A/=a,h,b,i,c,e,d,f,g,jabcdefghij66精选ppt练习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精选pptb)R RS是等价关系是等价关系.证明明：1.1.证证明明R 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也自反。也自反。68精选ppt2.2.证证明明RSRS的的对对称性：称性：方法方法1 用用对对称定称定义证义证：任取任取 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)=(RSS)(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