离散数学PPT电子教案第07章特殊关系.ppt

《离散数学PPT电子教案第07章特殊关系.ppt》由会员分享，可在线阅读，更多相关《离散数学PPT电子教案第07章特殊关系.ppt（65页珍藏版）》请在三一办公上搜索。

1、离 散 数 学,2023年2月28日星期二,2023/2/28,第三篇 二元关系,第7章 特殊关系,2023/2/28,7.0 内容提要,2023/2/28,7.1 本章学习要求,2023/2/28,判定下列关系具有哪些性质,1、在全体中国人所组成的集合上定义的“同姓”关系;2、对任何非空集合A,A上的全关系;3、三角形的“相似关系”、“全等关系”;4、直线的“平行关系”;5、“朋友”关系；,解：1,2,3具有自反性，对称性和传递性；4 具有反自反,对称和传递性，不具有自反性；5 具有自反和对称性，不具有传递性。,等价关系,2023/2/28,7.2 等价关系,定义7.2.1设R是定义在非空集

2、合A上的关系，如果R是自反的、对称的、传递的，则称R为A上的等价关系。,由定义7.2.1知：（1）关系R是等价关系当且仅当R同时具备自反性、对称性和传递性；（2）关系R不是等价关系当且仅当R不具备自反性或对称性或传递性。,2023/2/28,例7.2.1 判定下列关系是否是等价关系?,1.幂集上定义的“”关系；2.整数集上定义的“”关系；3.全体中国人所组成的集合上定义的“同性别”关系。,不具有对称性,不具有对称性,自反性,是等价关系,练习:P217 4 令A=1,2,3,判断A上的关系(如图7.5.1所示)是否是等价关系.,2023/2/28,例7.2.2,在时钟集合A1,24上定义整除关系

3、：R|(x,yA)(x-y)被12整除)。（1）写出R中的所有元素；（2）画出R的关系图；（3）证明R是一个等价关系。,2023/2/28,例7.2.2 解,(2)关系图为：,(1)R=,2023/2/28,(3)对xA，有(x-x)被12所整除，所以R,即 R是自反的。对x,yA,若R,有(x-y)被12整除,则(y-x)-(x-y)被12整除,所以 R,即R是对称的。对x,y,zA,若R且R,有(x-y)被12所整除且(y-z)被12所整除,所以(x-z)(x-y)(y-z)被12所整除,所以,R,即R是传递的.由知,R是等价关系。,例7.2.2 解(续),2023/2/28,从例7.2.

4、2可以看出,关系R将集合A分成了如下的12个子集：1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,22,11,23,12,24。,这12个A的子集具有如下特点：1、在同一个子集中的元素之间都有关系R；2、不同子集的元素之间无关系R。,2023/2/28,以n为模的同余关系,记xRy为 xy(mod n),则 R 是Z上的等价关系。如用resn(x)表示x除以n的余数，则xy(mod n)resn(x)resn(y)。,此时，R将Z分成了如下n个子集：,-3n,-2n,-n,0,n,2n,3n,-3n+1,-2n+1,-n+1,1,n+1,2n+1

5、,3n+1,-3n+2,-2n+2,-n+2,2,n+2,2n+2,3n+2,-2n-1,-n-1,-1,n-1,2n-1,3n-1,4n-1,2023/2/28,7.2.2 集合的划分,定义7.2.2给定非空集合A，设有集合S=S1,S2,S3.Sm.如果满足SiA 且 Si,i1,2,.,m;SiSj，ij,i,j1,2,.,m;,则集合S称作集合A的一个划分，而S1,S2,.Sm叫做这个划分的块或类。,2023/2/28,例7.2.5,设A=0,1,2,4,5,8,9,R是A上的以4为模的同余关系。(1)写出R的所有元素；(2)求分别与元素1,2,4有关系R的所有元素所作成的集合。,解:

6、(1)R=,.显然，R是A的一个等价关系。,2023/2/28,集合1,5,9称为元素1关于等价关系R的等价类，记为1R，即1R=1,5,9;,例7.2.5 解,(2)与元素1有关系R的所有元素所作成的集合1,5,9;与元素2有关系R的所有元素所作成的集合2;与元素4有关系R的所有元素所作成的集合0,4,8.,同理:2R=2,4R=0,4,8.,2023/2/28,7.2.3 等价类与商集,定义7.2.3 设R是非空集合A上的等价关系，对任意xA，称集合 xRy|yAR为x关于R的等价类，或叫作由x生成的一个R等价类，其中x称为xR的生成元(或叫代表元)。,2023/2/28,由定义7.2.3

7、可以看出：,（1）等价类产生的前提:A上的关系R是等价关系；（2）A中所有与x有关系R的元素y构成了xR；（3）A中每个元素都对应一个由它生成的等价类；（4）R具有自反性意味着对xA，xR；（5）R具有对称性意味着对任意x,yA,若有yxR,则一定有xyR。,2023/2/28,定理7.2.1,设R是非空集合A上的等价关系,则有：,(1)对xA,xR；(2)对x,yA,a)如果yxR，则有xR=yR，b)如果y xR，则有xRyR。(3)A；,2023/2/28,例7.2.5(续),设A=0,1,2,4,5,8,9,R是A上的以4为模的同余关系。求（1）R的所有等价类；（2）画出R的关系图。,

8、解:(1)1R=1,5,9=5R=9R；2R=2；4R=0,4,8=0R=8R。,2023/2/28,商 集,定义7.2.4 设R是非空集合A上的等价关系，由R确定的一切等价类的集合，称为集合A上关于R的商集,记为A/R,即 A/RxR|(xA),例7.2.6 设集合A=0,1,2,4,5,8,9,R为A上以4为模的同余关系。求A/R。解 根据例7.2.5，商集 A/R=0R,1R,2R=0,4,8,1,5,9,2。,2023/2/28,计算商集A/R的通用过程：,(1)任选A中一个元素a,计算aR；(2)如果aRA,任选一个元素bA-aR,计算bR;(3)如果aRbRA,任选一个元素cA-a

9、R-bR,计算cR;以此类推,直到A中所有元素都包含在计算出的等价类中。,2023/2/28,例7.2.7,设集合A=1,2,3,4,5,8，R为A上以3为模的同余关系。求A/R。解 根据例7.2.3知，A上以3为模的同余关系R是等价关系。因为 1R=1,4=4R,2R=5R=8R=2,5,8,3R=3，所以根据商集的定义，A/R=1R,2R,3R=1,4,2,5,8,3。,2023/2/28,练习:P217 6,8,6.设A=1,2,3,4,在P(A)上规定二元关系如下:R=|(s,tP(A)(|s|=|t|)证明:R是P(A)上的等价关系并写出商集P(A)/R.8.设A=A1,A2,A3,

10、.,An是集合A的划分,若 AiB,i1,2,.,n;问:A1B,A2B,A3B,.,AnB 是AB的划分吗?提示:6.P(A)/R=R,1R,1,2R,1,2,3R,AR 8.是划分,2023/2/28,7.2.4 等价关系与划分,定理7.2.2 设R是非空集合A上的等价关系，则A对R的商集A/R是A的一个划分，称之为由R所导出的等价划分。,定理7.2.3 给定集合A的一个划分=A1,A2,An,则由该划分确定的关系R=(A1A1)(A2A2)(AnAn)是A上的等价关系,称为由划分所导出的等价关系。,2023/2/28,例7.2.8,解 只有1个划分块的划分为S1,见图(a)；具有2个划分

11、块的划分为S2,S3和S4,见图(b),(c)和(d);具有3个划分块的划分为S5，见图(e)。,设A=1,2,3，求A上所有的等价关系及其对应的商集。,2023/2/28,例7.2.8(续）,假设由Si导出的对应等价关系为Ri,i=1,2,3,4,5，则有 R1=S1S1=AA，A/R1=1,2,3；R2=1,21,2 33=,A/R2=1,2,3；R3=1,31,3 22=,A/R3=1,3,2；,2023/2/28,例7.2.8(续）,R4=2,32,311=,A/R4=1,2,3；R5=112233=,=IA,A/R5=1,2,3。,2023/2/28,例7.2.10(等价关系=循环关

12、系+自反),设R是集合A上的一个关系.对a,b,cA,如果当R并且R时,都有R,则称R为A上的循环关系。试证明:R是A上的一个等价关系的充要条件是 R既是循环关系又是自反关系。,2023/2/28,例7.2.10 证明,“”若R是等价关系。1)显然R是自反的。2)对任意a,b,cA,若R,R,则 由R是对称的,有R并且R.又由R是传递的，所以,R。即R是循环的关系。由1),2)知R是自反的和循环的。,2023/2/28,“”若R是自反的和循环的。1)显然R是自反性的；2)对任意a,bA,若R,则 由R是自反的,有R，又因R是循环的，所以,有R，即R是对称的。3)对任意a,b,cA,若,R,则由

13、R对称的,有R并且R;由R是循环的，所以 R，即R是传递的。由1),2),3)知,R是A上的一个等价关系。,例7.2.10证明(续),2023/2/28,练习:P217 10,10.设A=1,2,3,4,5,找出A上的等价关系R,此关系R能够产生划分 1,2,3,4,5,并画出R的关系图.提示:R的关系图如下,2023/2/28,总结,1、熟记等价关系的定义;2、利用等价关系的定义证明一个关系是等价关系;3、给定A上的等价关系R,会求所有的等价类和商集A/R;并求出对应的集合的划分;4、给定集合A上的划分,会求对应的等价类。,2023/2/28,作业,第217-218页 9,11 预习:7.3

14、 次序关系,2023/2/28,判定下列关系具有哪些性质,1、对任何非空集合A，A上的恒等关系；2、多边形的“相似关系”、“全等关系”；3、集合A的幂集P(A)上定义的“包含关系”；4、集合A的幂集P(A)上定义的“真包含关系”。,解:1,2都具有自反性,对称性和传递性,是等价关系;3 具有自反性，反对称性和传递性；4 具有反自反性，反对称性和传递性。,偏序关系,拟序关系,2023/2/28,7.3 次序关系,拍摄一张室内闪光灯照片，需要完成如下任务：1、打开镜头盖；2、照相机调焦；3、打开闪光灯；4、按下快门按钮。这些任务中有的必须在其他任务之前完成。例如，任务1必须在任务2之前完成，任务2

15、，3必须在任务4之前完成，即任务之间存在“先后”关系，即次序关系。,2023/2/28,7.3.1 拟序关系,定义7.3.1 设R是非空集合A上的关系，如果R是反自反和传递的，则称R是A上的拟序关系，简称拟序，记为“”，读作“小于”，并将“”记为“ab”。序偶 称为拟序集。,2023/2/28,由定义7.3.1知：,(1)R是拟序关系R同时具有反自反性和传递性;(2)R不是拟序关系R不具有反自反性或者传递性;(3)拟序“”的逆关系“-1”也是拟序,用“”表示,读作“大于”。,2023/2/28,例7.3.1,设R是集合A上的拟序关系，则R是反对称的。证明 假设R不是反对称的关系，则必存在x,y

16、A,且xy,满足R并且R。因为R是A上的拟序关系,所以R具有传递性,从而有R。这与R是反自反的矛盾,从而假设错误,即R一定是反对称的。,2023/2/28,例7.3.2,判断下列关系是否为拟序关系（1）集合A的幂集P(A)上定义的“”；（2）实数集R上定义的“小于”关系()；解（1）集合A的幂集P(A)上定义的“”具有反自反性和传递性，所以是拟序集。（2）实数集合R上定义的“小于”关系()具有反自反性和传递性，所以是拟序集。,2023/2/28,7.3.2 偏序关系,定义7.3.2 设R是非空集合A上的关系,如果R是自反的、反对称的和传递的，则称R是A上的偏序关系,简称偏序,记为“”,读作“小

17、于等于”,并将“”记为ab。序偶称为偏序集。,2023/2/28,由定义7.3.2知,（1）R是偏序关系R同时具有自反性、反对称性和传递性；（2）R不是偏序关系R不具备自反性或反对称性或传递性；（3）偏序“”的逆关系“-1”也是一个偏序，我们用“”表示，读作“大于等于”；（4）(“”-IA)为A上的拟序关系，(“”IA)为A上的偏序关系。,2023/2/28,试判断下列关系是否为偏序关系(1)集合A的幂集P(A)上的包含关系“”；(2)实数集合R上的小于等于关系“”；(3)自然数集合N上的模m同余关系；(4)自然数集合N上的整除关系“|”；解:(1),(2),(4)所对应的关系同时具有自反性,

18、反对称性和传递性,所以都是偏序关系；而(3)所对应的关系不具有反对称性,所以不是偏序关系；,例7.3.3,2023/2/28,2 偏序集的哈斯图,（1）用小圆圈或点表示A中的元素，省掉关系图中所有的环；（因自反性)（2）对任意x,yA,若xy,则将x画在y的下方,可省掉关系图中所有边的箭头；（因反对称性）（3）对任意x,yA,若x y,且x与y之间不存在zA,使得xz,zy,则x与y之间用一条线相连,否则无线相连。（因传递性）,2023/2/28,例7.3.7,设A=2,3,6,12,24,36,“”是A上的整除关系R,画出其关系图和哈斯图。解 由题意可得 R=,.该偏序集的关系图和哈斯图如下

19、：,2023/2/28,例7.3.7（续）,关系图,哈斯图,2,3,6,12,36,24,2,3,6,12,36,24,2023/2/28,练习:P218 15,对于下列集合上的整除关系画出其哈斯图.(1)A=1,2,3,4,6,8,12,24;(2)B=1,2,3,4,5,6,7,8,9.,2023/2/28,3 特殊元素,定义7.3.3 设是偏序集,B是A的任何一个子集.若存在元素bB,使得对xB,(1)都有xb,则称b为B的最大元素,简称最大元;(2)都有bx,则称b为B的最小元素,简称最小元;(3)满足bxx=b,则称b为B的极大元素,简称极大元；(4)满足xbx=b,则称b为B的极小

20、元素,简称极小元。,2023/2/28,定义7.3.3 可以符号化为：,2023/2/28,例7.3.8 A=2,3,6,12,24,36,“”是A上的整除关系.,设B1=6,12,B2=2,3,B3=24,36,B4=2,3,6,12是集合A的子集.试求出B1,B2,B3和B4的最大元,最小元,极大元和极小元。解 A的子集合B1,B2,B3和B4的最大元,最小元,极大元和极小元见下表。,2023/2/28,定义7.3.4 上、下(确)界,设是偏序集,B是A的任何一个子集。若存在元素aA,使得（1）对任意xB,都有xa,则称a为B的上界;（2）对任意xB,都有ax,则称a为B的下界;（3）设a

21、A是B的上界,若对于B的任一上界aA,均有aa,则称 a 为B的最小上界或上确界,记 a=SupB;（4）设aA是B的下界,若对于B的任一下界aA,均有aa,则称 a 为B的最大下界或下确界,记 a=InfB。,2023/2/28,由定义7.3.4知,（1）子集合B的上、下界和上、下确界可在集合A中寻找；（2）一个子集合B的上、下界不一定存在，如果存在，可以不唯一的；（3）一个子集合B的上、下确界不一定存在，如果存在，一定唯一；（4）一个子集合B有上(下)确界，一定有上(下)界，反之不然。,2023/2/28,例7.3.10,A=x1,x2,x3,x4，A上定义偏序集的哈斯图如图7.3.4所示

22、。求B=x1,x2和C=x3,x4的上界、下界、上确界和下确界。,解 B、C的各种特殊元见下表。,2023/2/28,定理7.3.1,设是一偏序集，B是A的子集。则：（1）若b是B的最大元,则b是B的极大元、上界、上确界；（2）若b是B的最小元,则b是B的极小元、下界、下确界；（3）若a是B的上确界且aB,则a是B的最大元；（4）若a是B的下确界且aB,则a是B的最小元。,2023/2/28,定理7.3.2,设是一偏序集，B是A的子集。则：（1）若B存在最大元，则B的最大元是惟一的；（2）若B存在最小元，则B的最小元是惟一的；（3）b是B的最大元，则b是B的惟一极大元；（4）b是B的最小元，则

23、b是B的惟一极小元；（5）若B存在上确界，则B的上确界是惟一的；（6）若B存在下确界，则B的下确界是惟一的。,2023/2/28,例7.3.12,设集合X=x1,x2,x3,x4,x5上的偏序关系如下图所示,求X的最大元、最小元、极大元、极小元;子集X1=x2,x3,x4，X2=x3,x4,x5，X3=x1,x3,x5的上界、下界、上确界、下确界、最大元、最小元、极大元和极小元;子集X4=x1,x2,x3的8种特殊元。,2023/2/28,例7.3.12 解,X1=x2,x3,x4,X2=x3,x4,x5X3=x1,x3,x5,X4=x1,x2,x3,X1,X2和X3的各种特殊元见下表,X4的

24、特殊元呢?,2023/2/28,7.3.3 全序关系,定义7.3.5 设是一个偏序关系,若对任意x,yA,总有xy或yx,二者必居其一,则称关系“”为全序关系,简称全序,或者线序关系,简称线序。称为全序集,或者线序集,或者链。从定义7.3.5可以看出：全序关系是偏序关系，反之则不然。,2023/2/28,例7.3.13,试判断下列关系是否为全序关系，如果是，请画出其哈斯图。（1）设集合A=a,b,c，其上的关系“”=,（2）实数集R上定义的小于等于关系“”；（3）实数集R上定义的小于关系“”；（4）集合A的幂集P(A)上定义的包含关系“”。,2023/2/28,例7.3.13 解,（1）是全序

25、集，其哈斯图见图(a)；（2）是全序集，其哈斯图是数轴，见图(b),其中x,y,zR；（3）不是全序关系；（4）当|A|是全序集，其哈斯图见图(c)和(d)；当|A|2，则不是全序集。,2023/2/28,例7.3.13 解（续）,2023/2/28,7.3.4 良序关系,定义7.3.6 设是一偏序集，若A的任何一个非空子集都有最小元素，则称“”为良序关系，简称良序，此时称为良序集。从定义7.3.6可以看出：（1）R是良序关系 R是偏序关系和A的任何非空子集都有最小元；（2）良序关系一定是偏序关系，反之则不然；（3）良序关系一定是全序关系，反之则不然。,2023/2/28,例7.3.14 试判

26、断下列是否为良序关系。,(1)A=a,b,c，关系“”=,(2)实数集R上定义的小于等于关系“”；解（1）是良序集；（2）不是良序集。注：1、良序关系 全序关系 偏序关系;2、有限全序集一定是良序集。,2023/2/28,作业,第218-219页 17,22,23(a)(b)预习:第8章 函数,2023/2/28,7.4 本章总结,（1）等价关系的概念及证明、等价类和商集的计算;（2）集合划分的定义、求给定集合的划分；（3）等价关系与集合划分的关系；（4）偏序关系、拟序关系、全序关系和良序关系的定义,它们之间的异同；（5）哈斯图的画法；（6）八种特殊元的定义和基本性质。,2023/2/28,习题类型,（1）基本概念题：涉及寻找偏序关系的8种特殊元;（2）判断题：涉及对证明过程正误的判断，集合的划分，关系特殊性的保持以及特殊关系的判定；（3）计算题：涉及等价类和商集的计算和给定集合的划分，计算对应的等价关系；（4）证明题：涉及特殊关系的证明；（5）画图题：涉及等价关系的关系图、偏序关系的哈斯图。,