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

.1离 散 数 学期 末 总 复 习.2复 习 时 注 意准确掌握每个概念准确掌握每个概念灵活应用所学定理灵活应用所学定理注意解题思路清晰注意解题思路清晰证明问题时证明问题时,先用反向思维先用反向思维(从结从结论入手论入手)分析问题分析问题,再按正向思维再按正向思维写出证明过程写出证明过程.3全书知识网络：全书知识网络：图图论论篇篇同构同构同构同构格与布尔代数格与布尔代数半群半群,独异点独异点,群群,环环,域域代数系统篇代数系统篇n 元运算元运算命题逻辑命题逻辑谓词逻辑谓词逻辑集合初步集合初步二元关系二元关系函函 数数集合论篇集合论篇数理逻辑篇数理逻辑篇.4总 复 习复习重点复习重点(注注:标有标有*的内容的内容,对网络学院学生不作要求对网络学院学生不作要求)第一章第一章 命题逻辑命题逻辑1.联结词的定义联结词的定义(含义及真值表定义含义及真值表定义).2.会命题符号化会命题符号化.3.永真式的证明永真式的证明.4.永真蕴涵式的证明永真蕴涵式的证明,记住并能熟练应用常用公式记住并能熟练应用常用公式.5.等价公式的证明等价公式的证明,记住并能熟练应用常用公式记住并能熟练应用常用公式.6.会写命题公式的范式会写命题公式的范式,*能应用范式解决问题能应用范式解决问题.7.熟练掌握命题逻辑三种推理方法熟练掌握命题逻辑三种推理方法.5第二章第二章 谓词逻辑谓词逻辑1.准确掌握有关概念准确掌握有关概念.2.会命题符号化会命题符号化.(如如P60题题(2)3.掌握常用的等价公式和永真蕴涵式掌握常用的等价公式和永真蕴涵式.包括包括:带量词的公式在论域内展开式带量词的公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充,量词分配公式量词分配公式.4.会用等价公式求谓词公式的真值会用等价公式求谓词公式的真值.(如如P66题题(3)*5.会写前束范式会写前束范式6.熟练掌握谓词逻辑推理熟练掌握谓词逻辑推理.第三章第三章 集合论初步集合论初步1.集合的表示集合的表示,幂集幂集,全集全集,空集空集.2.集合的三种关系集合的三种关系(包含包含,相等相等,真包含真包含)的定义及证明的定义及证明.3.集合的五种运算及相关性质集合的五种运算及相关性质.*4.应用包含排斥原理应用包含排斥原理.6第四章第四章 二元关系二元关系1.关系的概念关系的概念,表示方法表示方法.2.二元关系的二元关系的 性质的定义性质的定义,熟练掌握性质的判断及证明熟练掌握性质的判断及证明.3.掌握关系的复合掌握关系的复合,求逆及闭包运算求逆及闭包运算(计算方法及有关性质计算方法及有关性质)4.掌握等价关系的判断掌握等价关系的判断,证明证明,求等价类和商集求等价类和商集.*4.掌握相容关系定义掌握相容关系定义,简化图和简化矩阵简化图和简化矩阵,相容类相容类,最大相最大相容类容类,完全覆盖完全覆盖.5.偏序关系的判断偏序关系的判断,会画会画Hasse图图,会求一个子集的极小会求一个子集的极小(大大)元元,最小最小(大大)元元,上界与下界上界与下界,最小上界及最大下界最小上界及最大下界.第六章第六章 函数函数1.函数的定义函数的定义.2.函数的类型函数的类型,会判断会判断,会证明会证明.3.会计算函数的复合会计算函数的复合(左复合左复合),求逆函数求逆函数.知道有关性质知道有关性质.*4.了解集合的特征函数了解集合的特征函数,了解集合的基数了解集合的基数,可数集合可数集合.7第六章第六章 代数系统代数系统1.掌握运算的定义掌握运算的定义.2.熟练掌握二元运算的性质的判断及证明熟练掌握二元运算的性质的判断及证明.3.掌握代数系统的同构定义掌握代数系统的同构定义,会证明会证明.了解同构性质的保持了解同构性质的保持.4.了解半群了解半群,独异点独异点,*环和环和*域的概念域的概念.5.熟练掌握群熟练掌握群,子群子群,交换群交换群(会证明会证明),了解循环群了解循环群.*6,子群的陪集子群的陪集,Lagrange定理及其推论定理及其推论,(会应用会应用).*第七章第七章 格与布尔代数格与布尔代数*1.掌握格的定义掌握格的定义,了解格的性质了解格的性质.*2.会判断格会判断格,分配格分配格,有补格和布尔格有补格和布尔格,*3.重点掌握两个元素的布尔代数的性质重点掌握两个元素的布尔代数的性质(10个个).*4.会写两个元素的布尔表达式的范式会写两个元素的布尔表达式的范式.(实质是第一章的实质是第一章的主析取和主合取范式主析取和主合取范式).8第八章第八章 图论图论1.掌握图的基本概念掌握图的基本概念.(特别注意相似的概念特别注意相似的概念)2.熟练掌握图中关于结点度数的定理熟练掌握图中关于结点度数的定理.(会应用会应用)3.无向图的连通性的判定无向图的连通性的判定,连通分支及连通分支数的概念连通分支及连通分支数的概念.4.有向图的可达性有向图的可达性,强连通强连通,单侧连通和弱连通的判定单侧连通和弱连通的判定.求强求强 分图分图,单侧分图和弱分图单侧分图和弱分图.5.会求图的矩阵会求图的矩阵.6.会判定欧拉图和汉密尔顿图会判定欧拉图和汉密尔顿图.*7.会判定平面图会判定平面图,掌握欧拉公式掌握欧拉公式.*8.了解对偶图了解对偶图.9.掌握树的基本定义掌握树的基本定义,v和和e间的关系式间的关系式.会画生成树会画生成树,会求最会求最小生成树小生成树.根树的概念根树的概念,完全完全m叉树的公式叉树的公式,会画最优树会画最优树,*会会设计前缀码设计前缀码.9总 复 习复习重点复习重点第一章第一章 命题逻辑命题逻辑1.联结词的定义联结词的定义(含义及真值表定义含义及真值表定义).2.会命题符号化会命题符号化.3.永真式的证明永真式的证明.4.永真蕴涵式的证明永真蕴涵式的证明,记住并能熟练应用常用公式记住并能熟练应用常用公式.5.等价公式的证明等价公式的证明,记住并能熟练应用常用公式记住并能熟练应用常用公式.6.会写命题公式的范式会写命题公式的范式,*能应用范式解决问题能应用范式解决问题.7.熟练掌握命题逻辑三种推理方法熟练掌握命题逻辑三种推理方法.10第一章第一章 命题逻辑命题逻辑1.1.联结词联结词定义了六个逻辑联结词，分别是：定义了六个逻辑联结词，分别是：(1)否定否定“”(2)合取合取“”(3)析取析取“”(4)异或异或“”(5)蕴涵蕴涵“”(6)等价等价“”要熟练掌握这五个联结词在自然语言中所表示的含义以要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。及它们的真值表的定义。：否定：否定 表示表示“不不”：合取：合取 表示表示“不但不但,而且而且.”“并且并且”：析取：析取 表示表示“或者可兼取的或或者可兼取的或”：异或：异或 表示表示“或者不可兼取的或或者不可兼取的或”：蕴涵：蕴涵 表示表示“如果如果,则则.”:等价等价 表示表示“当且仅当当且仅当”“”“充分且必要充分且必要”可以将这六个联结词看成六种可以将这六个联结词看成六种“运算运算”。.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.122.会命题符号化会命题符号化.例如例如 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(互补互补,同一律同一律).134.永真蕴涵式的证明永真蕴涵式的证明,记住常用的公式记住常用的公式.永真蕴涵式永真蕴涵式: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 T.145.等价公式的证明等价公式的证明,记住常用的公式记住常用的公式.方法方法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,.156.命题公式的范式命题公式的范式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 F.166)大项及其性质大项及其性质.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)大项大项.179).会写主析取范式和主合取范式会写主析取范式和主合取范式.求下面命题公式的范式求下面命题公式的范式: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 T.18方法方法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).19已知已知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):安排工作安排工作(排课表排课表),判断比赛名次判断比赛名次,携带携带工具箱工具箱,.207.会用三种推理方法会用三种推理方法,进行逻辑推理进行逻辑推理.会用三个推理规则会用三个推理规则: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.21(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 .22(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 I9.23 第二章第二章 谓词逻辑谓词逻辑1.准确掌握有关概念准确掌握有关概念.2.会命题符号化会命题符号化.(如如P60题题(2)3.掌握常用的等价公式和永真蕴涵式掌握常用的等价公式和永真蕴涵式.包括包括:带量词的公式在论域内展开式带量词的公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充,量词分配公式量词分配公式.4.会用等价公式求谓词公式的真值会用等价公式求谓词公式的真值.(如如P66题题(3)*5.会写前束范式会写前束范式6.熟练掌握谓词逻辑推理熟练掌握谓词逻辑推理.24 第二章第二章 谓词逻辑谓词逻辑1.准确掌握有关概念准确掌握有关概念.客体客体:客体变元客体变元,谓词谓词,量词量词,量词后的指导变元量词后的指导变元,量词的辖域量词的辖域,约束变元与自由变元约束变元与自由变元,论域论域,全总个体域全总个体域,谓词公式谓词公式(WFF),命题函数命题函数,前束范式前束范式,.252.会命题符号化会命题符号化.(如如P60题题(2)命题的符号表达式与论域有关。命题的符号表达式与论域有关。当论域扩大时，需要当论域扩大时，需要添加用来表示客体特性的谓词，称此谓词为添加用来表示客体特性的谓词，称此谓词为特性谓词特性谓词。特性谓词往往就是给定命题中量词后边的那个名词。特性谓词往往就是给定命题中量词后边的那个名词。如如“所有所有自然数自然数.”.”、“有些有些大学生大学生.”.”。如何添加特性谓词，这是个十分重要的问题如何添加特性谓词，这是个十分重要的问题，这与前这与前边的量词有关边的量词有关。如果如果前边是前边是全称量词全称量词，特性谓词后边是特性谓词后边是蕴含联结词蕴含联结词“”；如果如果前边是前边是存在量词存在量词，特性谓词后边是特性谓词后边是合取联结词合取联结词“”。另外有些命题里有的客体在句中没有明确的量词另外有些命题里有的客体在句中没有明确的量词 ,而在而在写它的符号表达式时写它的符号表达式时,必须把隐含的量词明确的写出来必须把隐含的量词明确的写出来.26例如例如金子闪光金子闪光,但闪光的不一定都是金子但闪光的不一定都是金子.设设: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).273.掌握常用的等价公式和永真蕴涵式掌握常用的等价公式和永真蕴涵式.包括包括:带量词的公式在论域内展开式带量词的公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充,量词分配公式量词分配公式.设论域为设论域为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).286).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)T.29*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)(辖域扩充辖域扩充).306.熟练掌握谓词逻辑推理熟练掌握谓词逻辑推理.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)TE.31下面的作法是错误的：下面的作法是错误的：正确作法正确作法:x xP(x)P P(x)P x xP(x)PP(x)P P(c)USP(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)ESP(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)EG.32例如例如.证明下面推理的有效性证明下面推理的有效性.证明证明: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 C(a)D(a)T I I C(a)T C(a)T I I B(a)T B(a)T I I A(a)A(a)B(a)T B(a)T I I x(A(x)x(A(x)B(x)EG B(x)EG”表示否定其中“)()()()(),()()(),()()(xBxAxxDxAxxDxCxAxxCxBxAx.33第三章第三章 集合论初步集合论初步1.集合的表示集合的表示,幂集幂集,全集全集,空集空集.2.集合的三种关系集合的三种关系(包含包含,相等相等,真包含真包含)的定义及证明的定义及证明.3.集合的五种运算及相关性质集合的五种运算及相关性质.*4.应用包含排斥原理应用包含排斥原理.34第三章第三章 集合论初步集合论初步基本概念基本概念:集合与元素集合与元素,子集与真子集子集与真子集,空集空集,全集全集,幂集幂集,并集并集,交集交集,相对补集相对补集(差集差集),绝对补集绝对补集(补集补集)1.集合的表示集合的表示,元素与集合的属于关系元素与集合的属于关系.集合的三种表示方法集合的三种表示方法:枚举法枚举法:一一列出集合中的元素一一列出集合中的元素.谓词描述法谓词描述法:用谓词描述集合中元素的性质用谓词描述集合中元素的性质.文氏图文氏图:用一个平面区域表示用一个平面区域表示.2.集合的三种关系集合的三种关系(被包含被包含,相等相等,被真包含被真包含)的定义及证明的定义及证明.A B x(xAxB)A=B A B B Ax(xAxB)A BA B ABx(xAxB)x(xB x A).353空集空集,全集全集,幂集幂集 空集空集:无元素的集合无元素的集合.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).36例例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()=,-,=,.37例例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 彼此等价。彼此等价。T.38例例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).39例例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-C.40*例例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 I.41*有有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.42 第四章第四章 二元关系二元关系1.关系的概念关系的概念,表示方法表示方法.2.二元关系的二元关系的 性质的定义性质的定义,熟练掌握性质的判断及证明熟练掌握性质的判断及证明.3.掌握关系的复合掌握关系的复合,求逆及闭包运算求逆及闭包运算(计算方法及有关性质计算方法及有关性质)4.掌握等价关系的判断掌握等价关系的判断,证明证明,求等价类和商集求等价类和商集.*5.掌握相容关系的概念掌握相容关系的概念,关系图和矩阵的简化关系图和矩阵的简化,求相容类求相容类,最大相容类和完全覆盖最大相容类和完全覆盖.6.偏序关系的判断偏序关系的判断,会画会画Hasse图图,会求一个子集的极小会求一个子集的极小(大大)元元,最小最小(大大)元元,上界与下界上界与下界,最小上界及最大下界最小上界及最大下界.注意本章证明题的证明过程的思路注意本章证明题的证明过程的思路.43一一.关系的概念关系的概念,表示方法表示方法,三个特殊关系三个特殊关系.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:任何任何序偶的集合序偶的集合，都称之为一个二元关系。，都称之为一个二元关系。.443.3.关系的表示方法关系的表示方法1).1).枚举法枚举法:即将关系中所有序偶一一列举出，写在大括号内即将关系中所有序偶一一列举出，写在大括号内.如如:R=,2).(2).(描述法描述法)谓词公式法谓词公式法：即用谓词公式描述序偶中元素的关系。例如即用谓词公式描述序偶中元素的关系。例如 R=|xy3).3).有向图法有向图法：1。2。3。4。ABabcR1:1。4。23R2:.454).矩阵表示法：(实际上就是图论中的邻接矩阵实际上就是图论中的邻接矩阵)设设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=.463).恒等关系恒等关系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=AAIA.47二二.关系的性质关系的性质:熟练掌握性质的判断及证明熟练掌握性质的判断及证明.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).484.反对称性反对称性定义定义:设设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)这些性质要求会判断这些性质要求会判断,会证明会证明.这里特别要注意的是这里特别要注意的是,这些定义都是蕴涵式这些定义都是蕴涵式,所以当蕴涵所以当蕴涵式当前件为假时式当前件为假时,此蕴涵式为真此蕴涵式为真,即此性质即此性质 成立成立!.49自反性自反性反自反性反自反性对称性对称性传递性传递性反对称性反对称性每个结点都有环每个结点都有环 主对角线全是主对角线全是1每个结点都无环每个结点都无环 主对角线全是主对角线全是0不同结点间如果有边不同结点间如果有边,则有方向相反的两条则有方向相反的两条边边.是以对角线为对称是以对角线为对称 的矩阵的矩阵不同结点间不同结点间,最多有一最多有一条边条边.以主对角线为对称以主对角线为对称的位置不会同时为的位置不会同时为1如果有边如果有边,则也有边则也有边.或者使得前件为假或者使得前件为假.如果如果aij=1,且且ajk=1,则则aik=1从关系的矩阵从关系的矩阵从关系的有向图从关系的有向图 性质判定性质判定:.50判断下面关系的性质判断下面关系的性质: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 .511。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 .52关系性质当证明方法归纳关系性质当证明方法归纳:设设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.534.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 RRo.54三三.掌握关系复合掌握关系复合,求逆及闭包运算求逆及闭包运算(计算方法及性质计算方法及性质)(一一)关系的复合关系的复合 1.定义定义:设设R XY，S YZ，则，则 R S XZ。R S=|x X z Zy(y Y R S)2.2.计算方法计算方法(俗称过河拆桥法俗称过河拆桥法)枚举法枚举法 R=,S=,R S=,有向图有向图a。b。c。X。YabcRS。Zabc。Zabca。b。c。XSR.55 矩阵矩阵3.3.性质性质1).1).满足结合律满足结合律:R AB S BC T CD 则则 R(S T)=(R S)T2).R AB S BC T BC R (ST)=(R S)(R T)R (ST)(R S)(R T)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=011100010.56(二二).).逆关系逆关系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。.57 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。.58(三三).).闭包运算闭包运算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算法算法.59闭包的运算有三种形式闭包的运算有三种形式:如如A=a.b.c R AA R=,a).集合形式集合形式.r(R)=RIA=,=,s(R)=RRC=,=,R2=,R3=,t(R)=RR2R3 =,=,.,.60b)有向图形式有向图形式.b a cR3Rb a cb a cIA=r(R)b a cRb a cb R2a ct(R)b a c=cRb a c=b RCa s(R)b a c.61c)矩阵形式矩阵形式.Mr(R)=MRMIA=010001100100010001=111110011Ms(R)=MRMRC=010001100001100010=011101110Mt(R)=M M M =010001100001100010=111111111R2R3R100010001.623.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).63四四.等价关系等价关系 掌握等价关系的判断掌握等价关系的判断,证明证明,求等价类和商集求等价类和商集.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。R3.644.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的一个划分。的一个划分。.655.商集商集:定义定义：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个元素个元素可数集可数集 不可数集不可数集.gh a b ef c d.663).3).图的同构关系图的同构关系是个等价关系是个等价关系.令上述图构成的集合令上述图构成的集合A=a,b,c,d,e,f,g,h,i,j,求商集求商集A/.A/=a,h,b,i,c,e,d,f,g,j abcdefghij.67练习练习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).68b)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也自反。也自反。.692.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 (吸收律吸收律