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

《离散数学期末复习大纲课件.ppt》由会员分享，可在线阅读，更多相关《离散数学期末复习大纲课件.ppt（153页珍藏版）》请在三一办公上搜索。

1、离 散 数 学,期 末 总 复 习,离 散 数 学期 末 总 复 习,复 习 时 注 意准确掌握每个概念灵活应用所学定理注意解题思路清晰证明问题时,先用反向思维(从结论入手)分析问题,再按正向思维写出证明过程.,复 习 时 注 意,全书知识网络：,全书知识网络：图论篇同构同构T,F,总 复 习,复习重点 (注: 标有*的内容,对网络学院学生不作要求)第一章 命题逻辑1.联结词的定义(含义及真值表定义).2.会命题符号化.3.永真式的证明.4.永真蕴涵式的证明,记住并能熟练应用常用公式.5.等价公式的证明,记住并能熟练应用常用公式.6.会写命题公式的范式, *能应用范式解决问题.7.熟练掌握命题

2、逻辑三种推理方法.,总 复 习复习重点 (注: 标有*的内容,对网络学院学生,第二章 谓词逻辑1.准确掌握有关概念.2.会命题符号化.(如P60题(2)3.掌握常用的等价公式和永真蕴涵式.包括: 带量词的公式在论域内展开式,量词否定,量词辖域扩充, 量词分配公式.4.会用等价公式求谓词公式的真值.(如P66题(3)*5.会写前束范式6.熟练掌握谓词逻辑推理.第三章 集合论初步1.集合的表示,幂集,全集,空集.2.集合的三种关系(包含,相等,真包含)的定义及证明.3.集合的五种运算及相关性质.*4.应用包含排斥原理.,第二章 谓词逻辑,第四章 二元关系1.关系的概念,表示方法.2.二元关系的 性

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

4、代数系统的同构定义,会证明.了解同构性质的保持.4.了解半群,独异点,*环和*域的概念.5.熟练掌握群,子群,交换群(会证明), 了解循环群.*6,子群的陪集, Lagrange定理及其推论,(会应用).*第七章 格与布尔代数* 1.掌握格的定义,了解格的性质.* 2.会判断格,分配格,有补格和布尔格,* 3.重点掌握两个元素的布尔代数的性质(10个).* 4.会写两个元素的布尔表达式的范式.(实质是第一章的主析取和主合取范式).,第六章 代数系统,第八章 图论1.掌握图的基本概念.(特别注意相似的概念)2.熟练掌握图中关于结点度数的定理. (会应用)3.无向图的连通性的判定,连通分支及连通分

5、支数的概念.4.有向图的可达性,强连通,单侧连通和弱连通的判定.求强 分图,单侧分图和弱分图.5.会求图的矩阵.6.会判定欧拉图和汉密尔顿图.*7.会判定平面图, 掌握欧拉公式.*8.了解对偶图.9.掌握树的基本定义,v和e间的关系式.会画生成树,会求最小生成树.根树的概念,完全m叉树的公式,会画最优树,*会设计前缀码.,第八章 图论,总 复 习,复习重点第一章 命题逻辑1.联结词的定义(含义及真值表定义).2.会命题符号化.3.永真式的证明.4.永真蕴涵式的证明,记住并能熟练应用常用公式.5.等价公式的证明,记住并能熟练应用常用公式.6.会写命题公式的范式, *能应用范式解决问题.7.熟练掌

6、握命题逻辑三种推理方法.,总 复 习复习重点,第一章 命题逻辑1.联结词定义了六个逻辑联结词，分别是： (1) 否定“” (2) 合取“” (3) 析取“” (4) 异或“ ” (5) 蕴涵“” (6) 等价“”要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。 ：否定 表示“不”：合取 表示“不但,而且.”“并且”：析取 表示“或者可兼取的或” ：异或 表示“或者不可兼取的或”：蕴涵 表示“如果,则.” : 等价 表示“当且仅当”“充分且必要”可以将这六个联结词看成六种“运算”。,第一章 命题逻辑,联结词的定义(包括真值表和含义).特别要注意：“或者”的二义性, 即要区分

7、给定的“或”是“可兼取的或”还是“不可兼取的或 ”。“”的用法，它既表示“充分条件”也表示“必要条件”,即要弄清哪个作为前件,哪个作为后件.,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,联结词的定义(包括真值表和含义). P Q,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.

8、列真值表. (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 (互补,同一律),2.会命题符号化.,4.永真蕴涵式的证明, 记住常用的公式. 永真蕴涵式: AB是永真式,则称A永真蕴涵B. (AB) 方法1.列真值表. 方法2.假设前件真,推出后件真. (即直接推理) 方法3.假设后件假,推出前件假.(即反证法)例证明(P(QR)(PQ)(PR)

9、是永真蕴涵式.证:假设后件(PQ)(PR)假, 则PQ为T, PR为F,于是P为T,R为F, 进而又得Q为T. 所以QR为F, 所以前件P(QR)为F. 所以(P(QR)(PQ)(PR)为永真式. 对于给定一个题,究竟是用哪种方法,原则上哪种都可以.但是哪个方法简单,要根据具体题而定.,4.永真蕴涵式的证明, 记住常用的公式.A B,5.等价公式的证明,记住常用的公式. 方法1.列真值表. 方法2.用公式的等价变换. 例如:证明 P(QR)(PQ)R P(QR)P(QR) (PQ)R (PQ)R (PQ)R注意:不论是证明永真蕴涵式,还是证明等价公式以及后边的求公式的范式,命题逻辑推理,都应用

10、43页的公式。必须记忆一些常用的公式 如:P43表中的永真蕴涵式: I1, I3, I9, I10, I11, I12, I13, 等 价 公 式: E1 E16, E18, E19 , E20, E21,5.等价公式的证明,记住常用的公式.,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

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

12、R) (PQR )(PQR )主合取范式A(P,Q,R) (PQ)R (PQR )(PQR )(PQR),9).会写主析取范式和主合取范式.P Q R,方法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 ),方法2.用公式的等价变换.,已知A

13、(P,Q,R)的主析取范式中含有如下小项: m0,m3, m4,m5,m7求它的主合取范式.解:A(P,Q,R)的主合取范式中含有大项:M1 ,M2, M6A(P,Q,R)(PQR )(PQR)(PQR)* 范式的应用 如P39习题(7),(8): 安排工作(排课表), 判断比赛名次,携带工具箱, ,已知A(P,Q,R)的主析取范式中含有如下小项:,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

14、(PQ)PQ,7.会用三种推理方法,进行逻辑推理.,(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) AB,(AB)C)D(CD) AB3.反证法: (AB) P(假设前提)AB T E9(AB)C P C T I11 D PCD PC T I10CC T I9,(AB)C)D(CD) AB,第二章 谓词逻辑1.准确掌握有关概念.2.会命题符号化.(如P60题(2)3.掌握常用的等价公式和永真蕴涵式.包括: 带量词的

15、公式在论域内展开式,量词否定,量词辖域扩充, 量词分配公式.4.会用等价公式求谓词公式的真值.(如P66题(3)*5.会写前束范式6.熟练掌握谓词逻辑推理.,第二章 谓词逻辑,第二章 谓词逻辑1.准确掌握有关概念. 客体: 客体变元, 谓词, 量词, 量词后的指导变元, 量词的辖域, 约束变元与自由变元, 论域, 全总个体域, 谓词公式(WFF), 命题函数, 前束范式,2.会命题符号化.(如P60题(2) 命题的符号表达式与论域有关。当论域扩大时，需要添加用来表示客体特性的谓词，称此谓词为特性谓词。特性谓词往往就是给定命题中量词后边的那个名词。如“所有自然数.” 、“有些大学生.”。如何添加

16、特性谓词，这是个十分重要的问题，这与前边的量词有关。 如果前边是全称量词，特性谓词后边是蕴含联结词“”； 如果前边是存在量词，特性谓词后边是合取联结词“”。 另外有些命题里有的客体在句中没有明确的量词 ,而在写它的符号表达式时,必须把隐含的量词明确的写出来.,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

17、(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)

18、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),3.掌握常用的等价公式和永真蕴涵式.包括:,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)

19、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,6). BxA(x)x(BA(x),*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) (变元换

20、名)xyt(F(x,z) G(y) H(t,z) (辖域扩充),*5.将下面谓词公式写成前束范式,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的辖域扩充后

21、 x(P(x)Q(x) T E 量词改成为x P(c)Q(c) ES P(c)Q(c) TE,6.熟练掌握谓词逻辑推理.,下面的作法是错误的： 正确作法: 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,下面的作法是错误的： 正确作法

22、:,例如.证明下面推理的有效性.证明: 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.集合的五种运算及相关性质.*4.应用包含排斥原理.

23、,第三章 集合论初步,第三章 集合论初步基本概念:集合与元素,子集与真子集, 空集, 全集, 幂集, 并集, 交集, 相对补集(差集), 绝对补集(补集)1.集合的表示,元素与集合的属于关系. 集合的三种表示方法: 枚举法:一一列出集合中的元素. 谓词描述法:用谓词描述集合中元素的性质. 文氏图:用一个平面区域表示. 2.集合的三种关系(被包含,相等,被真包含)的定义及证明. AB x(xAxB) A=B ABBAx(xAxB) ABABABx(xAxB)x(xBxA),第三章 集合论初步,3空集,全集, 幂集 空集:无元素的集合. x是矛盾式. (空集是唯一的) 全集E:包含所讨论所有集合的

24、集合. (全集不唯一) xE是永真式 幂 集:由A的所有子集构成的集合. P(A)=X|XA |P(A)|=2|A| 4.掌握集合的五种运算及相关性质. 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),3空集,全集, 幂集,例1.已知全集E=, AE,计算:a)P()P()=( ) b)P(A)P(A)=( )c)P(E)-P()=( )解:a) 因为任何集合A, 都有 A

25、A= 所以 P()P()= b) 因为A A , 即P(A) P(A) 所以 P(A)P(A)= c) P(E)=, = P()=P( )= , P(E)-P() )=,-, =,例1.已知全集E=, AE,计算:,例2 证明各式彼此等价。 PQ (PQ)(PQ) c)AB=B, AB=A, AB, B A.证明. AB=B x(xAB xB) x(xAB xB)(xABxB)x(xAxB)xB)(xAxB)xB)x(xAxB)xB)x(xAxB)(xBxB)x(xAxB)x(xAxB) ABx(xAxB)x(xBxA)x(xBxA) B A 由 AB=B 得 A (AB)=A B A=A B

26、 类似由AB=A, 可以推出AB=B 所以 AB=B AB=A 从而证得AB=B, AB=A, AB, B A 彼此等价。,T,例2 证明各式彼此等价。 PQ (PQ),例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(xAxB)xCxA( xBxC) xA( xBxC)xA( xBC) xAxBC xA-(BC) 所以(A-B)-C=A-(BC)例4. 令全集E为信息学院的学生的集合, C表示计算机专 业学生的集合,M表示学习了离散数学的学生的集合,D表示学习了数据结构课学生的集合,F表

27、示一年级的学生的集合.用集合的关系式表达下面句子. “学习了离散数学和数据结构课的学生,一定是计算机专业的非一年级的学生”. 解. (MD)(CF),例3 证明: (A-B)-C=A-(BC),例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)= 充要条

28、件是: A BCd) (A-B)(A-C)=解. 因为 当且仅当A=B ，才有AB=所以满足此式的充要条件是: A-B=A-C,例4 .在什么条件下，下面命题为真？,*例5. 用谓词逻辑推理证明对任何集合A、B、C，如果有AB且 BC ，则AC。证明: x(xAxB)x(xBxA),x(xBxC)x(xCxB)x(xAxC) x(xCxA) x(xAxB)x(xBxA) P x(xAxB) T Ix(xBxA) T I x(xBxC)x(xCxB) P x(xBxC) T I xAxB US xBxC US xAxC T I x(xAxC) UG xBxA ES xB T I xA T I x

29、C T I xCxA T I x(xCxA) EG x(xAxC) x(xCxA) T I,*例5. 用谓词逻辑推理证明,*有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

30、|-|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,*有14位学生参加考试,9位同学数学得了优;5位同学物理,第四章 二元关系1.关系的概念,表示方法.2.二元关系的 性质的定义, 熟练掌握性质的判断及证明.3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质)4.掌握等价关系的判断,证明,求等价类和商集.*5.掌握相容关系的概念,关系图和矩阵的简化,求相容类,最大相容类和完全覆

31、盖.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:任何序偶的集合，都称之为一个二元关系。,一.关系的概念,表示方法

32、,三个特殊关系.,3.关系的表示方法1). 枚举法: 即将关系中所有序偶一一列举出，写在大括号内. 如:R=,2).(描述法)谓词公式法： 即用谓词公式描述序偶中元素的关系。例如 R=|xy3).有向图法：,3.关系的表示方法1。2。 3。 4。ABabcR,4).矩阵表示法：(实际上就是图论中的邻接矩阵) 设A=a1, a2, , am，B=b1, b2, , bn是个有限集， RAB，定义R的mn阶矩阵 MR=(rij)mn，其中4.三个特殊关系1).空关系： AB，(或AA)，即无任何元素的关系. 它的关系图中只有结点,无任何边；它的矩阵中全是0。2).完全关系(全域关系) ： AB(或

33、AA)本身是一个从A到B(或A上)的完全关系. 即含有全部序偶的关系。它的矩阵中全是1。,4).矩阵表示法：(实际上就是图论中的邻接矩阵) 1 若,3). 恒等关系IA： IAAA,且IA =|xA称之为A 上的恒等关系。例如A=1,2,3, 则IA =, A上的、完全关系AA及IA的关系图及矩阵如下：,3). 恒等关系IA：MIA =1 0 00 1 00 0,二.关系的性质: 熟练掌握性质的判断及证明.1.自反性定义:设R是集合A中的关系，如果对于任意xA都有 R (xRx)，则称R是A中自反关系。即 R是A中自反的x(xAxRx)2.反自反性定义：设R是集合A中的关系，如果对于任意的xA

34、都有 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(xAyAzAx

35、RyyRz)xRz)这些性质要求会判断,会证明.这里特别要注意的是, 这些定义都是蕴涵式, 所以当蕴涵式当前件为假时 ,此蕴涵式为真,即此性质 成立!,4.反对称性,从关系的矩阵,从关系的有向图,性质判定:,自反性反自反性对称性传递性反对称性每个结点都有环,判断下面关系的性质:,判断下面关系的性质:1。2。1。2。1。2。1。2。,1。2。1。2。1。2。1。2。3333R5R6R7,关系性质当证明方法归纳: 设R是A上关系，1.证明R的自反性：方法1 用自反定义证：任取 xA,证出R.方法2 用恒等关系IA证：证出IA R. (见教材P119(2)方法3 用自反闭包证：证出r(R)=R, 即

36、RIA=R.2.证明R的反自反性：方法1 用反自反定义证：任取 xA,证出R.3.证明R的对称性：方法1 用对称定义证： 任取 x,yA,设R, 证出 R.方法2 用求逆关系证：证出 Rc=R.方法3 用对称闭包证：证出 s(R)=R, 即RRc =R.,关系性质当证明方法归纳: 设R是A上关系，,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

37、用传递闭包证：证出 t(R)=R, 即 RR2R3. =R.方法3用定理证：证出 (见教材P119(2)同学们可以根据具体情况,选用相应方法证明.其中必须掌握的是用基本定义证明.,4.证明R的反对称性：R RRo,三.掌握关系复合,求逆及闭包运算(计算方法及性质)(一)关系的复合 1.定义 :设RXY，SYZ，则 RSXZ。 RS=|xXzZy(yY RS) 2.计算方法(俗称过河拆桥法) 枚举法 R=, S=, RS=, 有向图,三.掌握关系复合,求逆及闭包运算(计算方法及性质)a。b。,矩阵3.性质1).满足结合律:RAB SBC TCD 则 R(ST)=(RS)T2). RAB SBC

38、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为非负整数),矩阵MR S=010001100010011100,(二). 逆关系1.定义 :设RXY，R的逆关系 RC=|R RC R2. 计算方法 1). R=, RC =, 2). RC的有向图:是将R的有向图的所有边的方向颠倒. 3). RC的矩阵 MRC =(MR)T 即为R矩阵的转置3.性质 令R

39、、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。,5). RS RC SC 。,(三).闭包运算1.定义：给定 A中关系R,若A上另一个关系R，满足：RR； R是自反的(对称的、传递的)； R是“最小的”，即对于任何A上自反

40、(对称、传递)的关系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 =, , =,. , , ,闭包的运算有

41、三种形式:,b)有向图形式 .,b)有向图形式 .bacR3Rbacbac,c)矩阵形式.,c)矩阵形式.Mr(R)=MRMIA=0100011001,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),3.性质,四.等价关系 掌握等价关系的判断,证明,求等价类

42、和商集. 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,4.等价类：1).定义:R是A上的等价关系,aA,由a确定的集合aR aR=x|xAR 称集合aR为由a形成的R等价类。2).由等价关

43、系图求等价类：R图中每个独立子图上的结点构成一个等价类。不同的等价类个数=独立子图个数。3).等价类性质 R是A上等价关系，任意a,b,cA 同一个等价类中的元素，彼此有等价关系R。 aRbR=， 当且仅当 R。 aR=bR 当且仅当 R。 .A中任何元素a,a必属于且仅属于一个等价类。 .任意两个等价类 aR,bR, 要么aR=bR ，要么aRbR= 。 R的所有等价类构成的集合是A的一个划分。,4.等价类：,5.商集:定义：R是A上等价关系，由R的所有等价类构成的集合称之为A关于R的商集。记作A/R。即 A/R=aR |aA6.商集应用.1)按照集合的等势关系(是等价关系)“”对集合族S进

44、行划分，得到商集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,5.商集:定义：R是A上等价关系，由R的所有等价类构成的集合,3).图的同构关系是个等价关系. 令上述图构成的集合A=a,b,c,d,e,f,g,h,i,j,求商集A/.A/=a,h,b,i,c,e,d,f,g,j,3).图的同构关系是个等价关系.,练习1.R和S都是A上等价

45、关系,下面哪个是A上等价关系?证明或举反例说明. a) RS b) RS c) R (即AA-R) d) R-S e)R2 f) r(R-S) e) Rc解.a) c) d) f)不是. 请看反例:,练习1.R和S都是A上等价关系,下面哪个是A上等价关系?R。,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

46、= RS)因R和S都自反，所以r(R)=R, r(S)=S, r(RS)=(RS)IA= (RIA)(SIA) =r(R)r(S)=RS 所以RS也自反。,b) 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

47、 =(RS)(RcSc) =(RRc)(RSc)(SSc)(SRc) =(s(R)(RSc)(s(S)(SRc) =(R(RSc)(S(SRc)=RS (吸收律) RS对称。,2.证明RS的对称性：,3.证明RS的传递性：方法1 用传递定义证：任取 x,y,zA, 设RS,RS, (证出RS)RSRS RSRS (RR)(S S) RS （因为R、S传递） RS 所以RS传递。 所以RS是A上等价关系.,3.证明RS的传递性：,e)证明. R2是等价关系.方法1.由P119习题(3)得:如果R自反和传递,则R2 =R, 所以R2也是等价关系.方法2.证R2自反:任取aA,因为R自反,所以R,根

48、据关系的复合得, 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是等价关系。,e)证明. 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

49、传递，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上等价关系.,g). R是A上等价关系,则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

50、,1,3,2,3,1,2,3,练习2.五.设X=1,2,3 Y=1,2, 在X的,*五.相容关系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是中的相容关系，由