离散数学期末复习大纲课件.ppt_163文库

资源描述

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

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

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

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

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

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

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

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

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

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 2.会命题符号化会命题符号化.例如例如 P:我有时间我有时间.Q:我上街我上街.R:我在家我在家.表示表示P是是Q的充分条件的充分条件:如果如果p,则则Q.只要只要P,就就Q.PQ 表示表示P是是Q的必要条件的必要条件:仅当仅当P,才才Q.只有只有P,才才Q.QP 如果如果P,则则Q;否则否则R.

12、(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(互补互补,同一律同一律)4.永真蕴涵式的证明永真蕴涵式的证明,记住常用的公式记住常用的公式.永真蕴涵式永真蕴涵式:AB是永真式是永真式,则称则称A永真

13、蕴涵永真蕴涵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)为为永真式永真式.对于给定一个题对于给定一个题,究竟是用哪种方法究竟是用哪种方法,原则上哪种都可以原则上哪种

14、都可以.但是哪个方法简单但是哪个方法简单,要根据具体题而定要根据具体题而定.A B A B F F T F T T T F F T T T5.等价公式的证明等价公式的证明,记住常用的公式记住常用的公式.方法方法1.列真值表列真值表.方法方法2.用公式的等价变换用公式的等价变换.例如例如:证明证明 P(QR)(PQ)R P(QR)P(Q R)(PQ)R (P Q)R(PQ)R注意注意:不论是证明永真蕴涵式不论是证明永真蕴涵式,还是证明等价公式以及后边还是证明等价公式以及后边的求公式的范式的求公式的范式,命题逻辑推理命题逻辑推理,都应用都应用43页的公式。页的公式。必须记忆一些常用的公式必须记忆一

15、些常用的公式如如: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 P Q PQ P Q 00 F F F F F T 01 F T F F T F 10

16、 T F F T F F 11 T T T F F F6)大项及其性质大项及其性质.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)大项大项.9).会写主析取范式和主合取范式会写主析取范式和主合取范式.求下面命题公式的范式求下面命题公式的范式:A(P,Q,R)(PQ)R方法方法1.列真值表列真值表.主析取范式主析取

17、范式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方法方法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)主合取

18、范式主合取范式: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)已知已知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):安排工作安排工作(排课表排课表),判断比赛名次判断比赛名次,携带携带工具箱工具箱,7.会用三种推理方法会用三种推理

19、方法,进行逻辑推理进行逻辑推理.会用三个推理规则会用三个推理规则: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(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 (AB)C)D(CD)A B3.反证法反证法:(A B)P(假设前提假设前提)

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

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

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

23、闪光,但闪光的不一定都是金子但闪光的不一定都是金子.设设: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)每个大学生都爱好一些文体活动。每个大学生都爱好一些文体

24、活动。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)3.掌握常用的等价公式和永真蕴涵式掌握常用的等价公式和永真蕴涵式.包括包括:带量词的公式在论域内展开式带量词的公式在论域内展开式,量词否定量词否定,量词辖域扩充量词辖域扩充,量词分配公式量词分配公式.设论域为设论域为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(

25、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)6).B6).B xA(x)xA(x)x(BA(x)x(BA(x)7)7).xA(

26、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,

27、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*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)(辖域扩充辖域扩充)6.熟练掌握

28、谓词逻辑推理熟练掌握谓词逻辑推理.1).注意使用注意使用ES、US、EG、UG的限制条件的限制条件,特别是特别是ES,UG2).对于同一个客体变元，既有带对于同一个客体变元，既有带也有带也有带的前提，去量的前提，去量词时，词时，应先去应先去后去后去，这样，这样才可以特指同一个客体才可以特指同一个客体 c.3).去量词时，该量词必须是公式的最左边的量词，且此去量词时，该量词必须是公式的最左边的量词，且此量词的前边量词的前边无任何符号无任何符号，它的辖域作用到公式末尾。，它的辖域作用到公式末尾。下面的作法是错误的：下面的作法是错误的：正确作法正确作法:x xP P(x x)x xQ(x)P

29、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下面的作法是错误的：下面的作法是错误的：正确作法正确作法: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

30、而是而是 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例如例如.证明下面推理的

31、有效性证明下面推理的有效性.证明证明: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

32、(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第三章第三章集合论初步集合论初步1.集合的表示集合的表示,幂集幂集,全集全集,空集空集.2.集合的三种关系集合的三种关系(包含包含,相等相等,真包含真包含)的定义及证明的定义及证明.3.集合的五种运算及相关性质集合的五种运算及相关性质.*4.应用包含排斥原理应用包含排斥原理.第三章第三章集合论初步集合论初步基本概念基本概念:集合与元素集合与元素,子集与真子集子集与真子集

33、,空集空集,全集全集,幂集幂集,并集并集,交集交集,相对补集相对补集(差集差集),绝对补集绝对补集(补集补集)1.集合的表示集合的表示,元素与集合的属于关系元素与集合的属于关系.集合的三种表示方法集合的三种表示方法:枚举法枚举法:一一列出集合中的元素一一列出集合中的元素.谓词描述法谓词描述法:用谓词描述集合中元素的性质用谓词描述集合中元素的性质.文氏图文氏图:用一个平面区域表示用一个平面区域表示.2.集合的三种关系集合的三种关系(被包含被包含,相等相等,被真包含被真包含)的定义及证明的定义及证明.A B x(xAxB)A=B A B B Ax(xAxB)A BA B ABx(xAxB)x(xB

35、B)(B-A)=x|(xAx B)(xBx A)A B=(AB)-(AB)例例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()=,-,=,例例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

36、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例例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

37、)xA(xBxC)xA(xBC)xAx BC xA-(BC)所以所以(A-B)-C=A-(BC)例例4.令全集令全集E为信息学院的学生的集合为信息学院的学生的集合,C表示计算机专表示计算机专业学生的集合业学生的集合,M表示学习了离散数学的学生的集合表示学习了离散数学的学生的集合,D表表示学习了数据结构课学生的集合示学习了数据结构课学生的集合,F表示一年级的学生的表示一年级的学生的集合集合.用集合的关系式表达下面句子用集合的关系式表达下面句子.“学习了离散数学和数据结构课的学生学习了离散数学和数据结构课的学生,一定是计算机一定是计算机专业的非一年级的学生专业的非一年级的学生”.解解.(MD)(

38、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，才有，才有A B=所以满足此式的所以满足此式的充

39、要条件充要条件是是:A-B=A-C*例例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(xAx

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

41、为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.二元关系的二元关系的性质的定义性质的定义,熟练掌握

42、性质的判断及证明熟练掌握性质的判断及证明.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:任何任何序偶的集合

44、序偶的集合，都称之为一个二元关系。，都称之为一个二元关系。3.3.关系的表示方法关系的表示方法1).1).枚举法枚举法:即将关系中所有序偶一一列举出，写在大括号内即将关系中所有序偶一一列举出，写在大括号内.如如:R=,2).(2).(描述法描述法)谓词公式法谓词公式法：即用谓词公式描述序偶中元素的关系。例如即用谓词公式描述序偶中元素的关系。例如 R=|xy3).3).有向图法有向图法：1。2。3。4。ABabcR1:1。4。23R2:4).矩阵表示法：(实际上就是图论中的邻接矩阵实际上就是图论中的邻接矩阵)设设A=a1,a2,am，B=b1,b2,bn是个有限集，是个有限集，R AB，定义，定

45、义R的的mn阶矩阵阶矩阵 MR=(rij)mn，其中，其中4.三个特殊关系三个特殊关系1).空关系空关系：AB，(或或 AA)，即无任何元素的关系，即无任何元素的关系.它的关系图中只有结点它的关系图中只有结点,无任何边；它的矩阵中全是无任何边；它的矩阵中全是0。2).完全关系完全关系(全域关系全域关系)：AB(或或AA)本身是一个从本身是一个从A到到B(或或A上上)的完全关系的完全关系.即含有全部序偶的关系。它的矩阵中全是即含有全部序偶的关系。它的矩阵中全是1。1 若若R 0 若若R(1im,1jn)rij=3).恒等关系恒等关系IA：IA AA,且且IA=|xA称之为称之为A 上的恒等关系。

46、上的恒等关系。例如例如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二二.关系的性质关系的性质:熟练掌握性质的判断及证明熟练掌握性质的判断及证明.1.自反性自反性定义定义:设设R是集合是集合A中的关系，如果对于任意中的关系，如果对于任意xA都有都有 R(xRx)，则称，则称R是是A中自反关系。即中自反关系。即 R是是A中自反的中自反的x(x AxRx)2.反自反性反自反性定

47、义定义：设：设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)4.反对称性反对称性定义定义:设设R为集合为集合A中关系中关系,若对任何若对任何x,yA,如果有如果有xRy,和和 yRx,就有就有x=y,则称则称R为为A中反对称关系中反对称

48、关系。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 1。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 关系性质当证明方法归纳关系性质当证明方法归纳:设设R是是A上关系，上

展开阅读全文