第三篇 二元关系特殊关系PPT讲稿.ppt
《第三篇 二元关系特殊关系PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《第三篇 二元关系特殊关系PPT讲稿.ppt(94页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第三篇第三篇 二元关系特殊关系二元关系特殊关系第1页,共94页,编辑于2022年,星期二2022/9/242022/9/24第三篇第三篇 二元关系二元关系第第7 7章章 特殊关系特殊关系第2页,共94页,编辑于2022年,星期二2022/9/242022/9/247.0 7.0 内容提要内容提要集合的概念集合的概念1集合的表示方法集合的表示方法2偏序关系偏序关系3良序关系良序关系4等价关系等价关系1拟序关系拟序关系2全序关系全序关系4第3页,共94页,编辑于2022年,星期二2022/9/242022/9/247.17.1本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1
2、 几个特殊关几个特殊关系的概念系的概念2 2 等价和偏序等价和偏序关系的证明关系的证明3 3 等价类和商等价类和商集的计算集的计算4 84 8个特殊元个特殊元31 1 拟序、全序拟序、全序和良序关系的和良序关系的相关性质。相关性质。21 1 拟序、全序拟序、全序和良序关系的和良序关系的定义;定义;2 2拟序与偏序关拟序与偏序关的联系的联系3 3 拟序、全序、拟序、全序、良序的联系。良序的联系。第4页,共94页,编辑于2022年,星期二2022/9/242022/9/24判定下列关系具有哪些性质判定下列关系具有哪些性质1 1、在全体中国人所组成的集合上定义的、在全体中国人所组成的集合上定义的“同
3、姓同姓”关系;关系;2 2、对任何非空集合、对任何非空集合A A,A A上的全关系上的全关系;3 3、三角形的、三角形的“相似关系相似关系相似关系相似关系”、“全等关系全等关系”;4 4、直线的、直线的“平行关系平行关系”;5 5、“朋友朋友朋友朋友”关系关系;解:解:1 1,2 2,3 3都都具有具有自反性,对称性和传递性自反性,对称性和传递性;4 4 具有具有反自反,对称和传递性,反自反,对称和传递性,不具有自反性;不具有自反性;5 5 具有自反和对称性,具有自反和对称性,不具有传递性。不具有传递性。等价等价关系关系第5页,共94页,编辑于2022年,星期二2022/9/242022/9/
4、247.2 7.2 等价关系等价关系定义定义7.2.17.2.1设设R R是定义在非空集合是定义在非空集合A A上的关系,如上的关系,如果果R R是是自反的、对称的、传递的自反的、对称的、传递的,则称,则称R R为为A A上的上的等等价关系价关系。由定义由定义7.2.17.2.1知:知:(1 1)关系关系R R是等价关系是等价关系当且仅当当且仅当R R同时具备自反性、同时具备自反性、对称性和传递性;对称性和传递性;(2 2)关系)关系R R不是等价关系不是等价关系当且仅当当且仅当R R不具备自反性或不具备自反性或对称性或传递性。对称性或传递性。第6页,共94页,编辑于2022年,星期二2022
5、/9/242022/9/24例例7.2.17.2.1 1.1.幂集上定义的幂集上定义的“”关系;关系;2.2.整数集上定义的整数集上定义的“”关系;关系;3.3.全全体体中中国国人人所所组组成成的的集集合合上上定定义义的的“同同性性别别”关关系。系。不具有对称性不具有对称性不具有对称性,自反性不具有对称性,自反性是等价关系是等价关系判定下列关系是否是等价关系判定下列关系是否是等价关系?第7页,共94页,编辑于2022年,星期二2022/9/242022/9/24例例7.2.27.2.2在时钟集合在时钟集合A A1,1,24,24上定义上定义整除关系:整除关系:R R|x,y|x,y A)(x-
6、y)A)(x-y)被被1212所整除所整除)。(1 1)写出)写出R R中的所有元素;中的所有元素;(2 2)画出)画出R R的关系图;的关系图;(3 3)证明)证明R R是一个等价关系。是一个等价关系。第8页,共94页,编辑于2022年,星期二2022/9/242022/9/24例例7.2.2 7.2.2 解解(2 2)此等价关系的关系图:)此等价关系的关系图:(1 1)R=,R=,113图图7.2.12143151224第9页,共94页,编辑于2022年,星期二2022/9/242022/9/241 1、对、对 xAxA,有,有(x-x)(x-x)被被1212所整除,所以所整除,所以RR,
7、即,即R R是自是自反的反的。2 2、对、对 x,yA,x,yA,若若R,R,有有(x-y)(x-y)被被1212整除,则整除,则(y-x)(y-x)-(x-y)(x-y)被被1212整除整除,所以所以,R,R,即即R R是对称的是对称的。3 3、对、对 x,y,zA,x,y,zA,若若RR且且R,R,有有(x-y)(x-y)被被1212所整除所整除且且(y-z)(y-z)被被1212所整除所整除,所以所以(x-z)(x-z)(x-y)(x-y)(y-z)(y-z)被被1212所整所整除除,所以所以,R,R,即即R R是传递的是传递的.由由1,2,31,2,3知知R R是等价关系。是等价关系。
8、例例7.2.2 7.2.2 解解 (续续)第10页,共94页,编辑于2022年,星期二2022/9/242022/9/24从例从例7.2.27.2.2可以看出可以看出关系关系R R将集合将集合A A分成了如下的分成了如下的1212个子集:个子集:1,13,2,14,3,15,4,16,5,17,1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,22,6,18,7,19,8,20,9,21,10,22,11,23,12,2411,23,12,24。这这1212个个A A的子集具有的子集具有如下特点如下特点:1 1、在同一个子集中的元素之间都有关系、在
9、同一个子集中的元素之间都有关系R R;2 2、不同子集的元素之间无关系、不同子集的元素之间无关系R R。第11页,共94页,编辑于2022年,星期二2022/9/242022/9/24例例7.2.37.2.3设设n n为正整数,考虑整数集合为正整数,考虑整数集合Z Z上的上的整除关系整除关系如下:如下:R=|x,yZ(n|(x-y)R=|x,yZ(n|(x-y)证明证明R R是一个等价关系。是一个等价关系。是一个等价关系。是一个等价关系。证明证明 (1)(1)对对 x x Z Z,有,有n|(x-x)n|(x-x),所以所以 R R,即即R R是自反的。是自反的。(2)(2)对对 x,yx,y
10、 Z Z,若,若 R R,即即n|(x-y)n|(x-y),所以,所以m|(y-x)m|(y-x),所以,所以,R R,即,即R R是对称的是对称的。(3)(3)对对 x,y,zx,y,z Z Z,若,若 R R且且 R R,有,有n|(x-y)n|(x-y)且且n|(y-z)n|(y-z),所以由,所以由(x-z)=(x-y)+(y-z)(x-z)=(x-y)+(y-z)得得n|(x-z)n|(x-z),所以,所以,R R,即,即R R是传递是传递的。的。由由(1)(1)、(2)(2)、(3)(3)知,知,R R是是Z Z上的等价关系。上的等价关系。第12页,共94页,编辑于2022年,星期
11、二2022/9/242022/9/24以以n n为模的同余关系为模的同余关系(CongruenceRelation)(CongruenceRelation)上述上述R R称为称为Z Z上上以以n n为模的同余关系为模的同余关系,记,记xRyxRy为为x xy(mod n)y(mod n)称为称为同余式同余式。如用。如用resresn n(x)(x)表示表示x x除以除以n n的余数,则的余数,则x xy(mod n)y(mod n)resresn n(x)(x)resresn n(y)(y)。此时,此时,R R将将Z Z分成了如下分成了如下n n个子集:个子集:,-3n,-2n,-n,0,n,
12、2n,3n,-3n,-2n,-n,0,n,2n,3n,-3n+1,-2n+1,-n+1,1,n+1,2n+1,3n+1,-3n+1,-2n+1,-n+1,1,n+1,2n+1,3n+1,-3n+2,-2n+2,-n+2,2,n+2,2n+2,3n+2,-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,-2n-1,-n-1,-1,n-1,2n-1,3n-1,4n-1,第13页,共94页,编辑于2022年,星期二2022/9/242022/9/24说明说明 同样地,这同样地,这n n个个Z Z的子集具有的子集具有如下
13、特点:如下特点:1 1、在同一个子集中的元素之间都有关系、在同一个子集中的元素之间都有关系R R;2 2、不同子集的元素之间没有关系、不同子集的元素之间没有关系R R;3 3、不同子集的交集是空集;、不同子集的交集是空集;4 4、所有这些子集的并集就构成集合、所有这些子集的并集就构成集合Z Z。称为集合称为集合Z Z Z Z的一个划的一个划的一个划的一个划分分分分第14页,共94页,编辑于2022年,星期二2022/9/242022/9/247.2.2 7.2.2 集合的划分集合的划分定义定义7.2.2给定非空集合给定非空集合A,设有集合,设有集合S=S1,S2,S3.Sm.如果满足如果满足S
14、i A且且Si,i1,2,.,m;SiSj,ij,i,j1,2,.,m;。则集合则集合S S称作集合称作集合A A的一个的一个划分划分划分划分(Partition)(Partition),而,而S S1 1,S,S2 2,.S,.Sm m叫做这个划分的叫做这个划分的块块(Block)(Block)或或类类类类(Class)(Class)。第15页,共94页,编辑于2022年,星期二2022/9/242022/9/24例例7.2.47.2.4试给出非空集合试给出非空集合A A上上2 2个不同的划分个不同的划分解解(1 1)在)在A A中设定一个非空子集中设定一个非空子集A A1 1,令令A A2
15、 2=A-A=A-A1 1,则根则根据集合划分的定义,据集合划分的定义,AA1 1,A,A2 2 就构成了集合就构成了集合A A的一个的一个划分,见图划分,见图 (a)(a);(2 2)在在A A中设定两个不相交非空子集中设定两个不相交非空子集A A1 1和和A A2 2,令,令A A3 3=A-=A-(A(A1 1AA2 2),则根据集合划分的定义,则根据集合划分的定义,AA1 1,A,A2 2,A,A3 3 就构就构成了集合成了集合A A的一个划分,见图的一个划分,见图 (b)(b)。AAA1A1A2(a)(b)第16页,共94页,编辑于2022年,星期二2022/9/242022/9/2
16、4例例7.2.57.2.5设设设设A=0,1,2,4,5,8,9A=0,1,2,4,5,8,9,1 1、写出、写出R R是是A A上的上的以以4 4为模的同余关系为模的同余关系R R的所有元素;的所有元素;2 2、求分别、求分别与元素与元素1,2,3,41,2,3,4有关系有关系R R的所有元素所作成的集的所有元素所作成的集合。合。解:解:1 1、R=,R=,.,.显然,显然,R R是是A A的一个等价关系。的一个等价关系。第17页,共94页,编辑于2022年,星期二2022/9/242022/9/24集合1,5,9称为元素1关于等价关系R的等价类,记为1R,即1R=1,5,9;例例7.2.5
17、 7.2.5 解解2 2、与元素、与元素1 1有关系有关系R R的所有元素所作成的集合的所有元素所作成的集合1,5,9;1,5,9;与元素与元素2 2有关系有关系R R的所有元素所作成的集合的所有元素所作成的集合2;2;与元素与元素4 4有关系有关系R R的所有元素所作成的集合的所有元素所作成的集合0,4,8.0,4,8.2R=2,44R R=0,4,8.0,4,8.第18页,共94页,编辑于2022年,星期二2022/9/242022/9/247.2.3 7.2.3 等价类与商集等价类与商集定义定义7.2.37.2.3 设设R R是是非空集合非空集合A A上的等价关系,对任意上的等价关系,对
18、任意xAxA,称集合,称集合 xxR Ry|yARy|yAR为为x x关于关于R R的的等价类等价类(equivalence class)(equivalence class),或叫作,或叫作由由x x生成的一个生成的一个R R等价类,其中等价类,其中x x称为称为xxR R的的生成元生成元(或叫或叫代表元代表元,或,或典型元典型元)(generator)(generator)。第19页,共94页,编辑于2022年,星期二2022/9/242022/9/24由定义由定义7.2.37.2.3可以看出:可以看出:(1 1)等价类产生的前提等价类产生的前提是是A A上的关系上的关系R R必须是等价必
19、须是等价关系;关系;(2 2)A A中所有中所有与与x x有关系有关系R R的元素的元素y y构成了构成了xxR R;(3 3)A A中中任意一个元素任意一个元素一定一定对应对应一个一个由它生成的等由它生成的等价类;价类;(4 4)R R具有具有自反性自反性意味着对意味着对 xAxA,xxR R;(5 5)R R具有具有对称性对称性意味着对任意意味着对任意x x,yAyA,若有若有yxyxR R,则一定有,则一定有xyxyR R。第20页,共94页,编辑于2022年,星期二2022/9/242022/9/24例例7.2.5(7.2.5(续续)设设A=0,1,2,4,5,8,10A=0,1,2,
20、4,5,8,10,R R是是A A上的以上的以4 4为模的同余为模的同余关系。关系。求求(1 1)R R的所有等价类;(的所有等价类;(2 2)画出)画出R R的关系图。的关系图。解解:(1):(1)11R R1,5,91,5,955R R99R R;22R R=2=2;44R R0,4,8=0,4,8=00R R88R R。图图7.2.32159159第21页,共94页,编辑于2022年,星期二2022/9/242022/9/24定理定理7.2.17.2.1设设R R是非空集合是非空集合A A上的等价关系,则有下面的结论成立:上的等价关系,则有下面的结论成立:1)1)对对 x x A A,x
21、xR R;2)2)对对 x,yAx,yA,a)a)如果如果yxyxR R,则有,则有xxR R=y=yR R,b)b)如果如果y xy xR R,则有,则有xxR RyyR R。3)3)A A;第22页,共94页,编辑于2022年,星期二2022/9/242022/9/24定理定理7.2.17.2.1的证明的证明2)2)对任意对任意x,yAx,yA,若若yxyxR R,则,则RR。a)a)对对 zxzxR R,则有:,则有:RR,又,又RR,由由R R的对称性有:的对称性有:RR,由,由R R的传递性的传递性有:有:RR。所以所以zyzyR R,即:,即:xxR R yyR R。证明:证明:1
22、 1)对任意)对任意xAxA,因为因为R R是等价关系是等价关系,所以,所以R R是自反的,是自反的,因此因此RR,即,即xxxxR R,故,故xxR R。b)b)对对 zyzyR R,则有:,则有:RR,又,又RR,由由R R的传递性有:的传递性有:RR。所以,。所以,zxzxR R,即:,即:yyR R xxR R。所以,由所以,由a)a)和和b)b)知:知:xxR RyyR R。第23页,共94页,编辑于2022年,星期二2022/9/242022/9/243 3)因为对任意因为对任意xAxA,xxR R A A,所以所以 A A。定理定理7.2.17.2.1的证明(续)的证明(续)对对
23、任意任意xAxA,因,因R R是自反的,所以是自反的,所以RR,即,即xxxxR R。所以所以xx,即,即A A 。故。故=A=A。(2(2)若若y y xxR R,设设xxR RyyR R,则存在则存在zxzxR RyyR R。即即zxzxR R,zyzyR R,则有:,则有:RR,RR,由,由R R的对称的对称性,性,RR。由。由R R的传递性有:的传递性有:RR,即,即yxyxR R,矛盾矛盾。所以所以xxR RyyR R。第24页,共94页,编辑于2022年,星期二2022/9/242022/9/24商商 集集定义定义7.2.47.2.4 设设R R是非空集合是非空集合A A上的上的等
24、价关系等价关系,由由R R确确定的一切等价类的集合定的一切等价类的集合,称为集合,称为集合A A上关于上关于R R的商的商集集(QuotientSet)(QuotientSet),记为,记为A/RA/R,即,即 A/RA/RxxR R|(xA)|(xA)例例7.2.67.2.6 设集合设集合A=0,1,2,4,5,8,10A=0,1,2,4,5,8,10,R R为为A A上以上以4 4为模为模的同余关系的同余关系。求。求A/RA/R。解解 根据例根据例7.2.57.2.5,商集,商集A/R=0A/R=0R R,1,1R R,2,2R R=0,4,8,1,5=0,4,8,1,5,9,29,2。第
25、25页,共94页,编辑于2022年,星期二2022/9/242022/9/24例例7.2.77.2.7设集合设集合A=1,2,3,4,5,8A=1,2,3,4,5,8,R R为为A A上以上以3 3为模的同余关为模的同余关系。系。求求A/RA/R。解解 根据例根据例7.2.37.2.3知,知,A A上以上以3 3为模的同余关系为模的同余关系R R是等是等价关系。价关系。因为因为11R R=1,4=4=1,4=4R R,2,2R R=5=5R R=8=8R R=2,5,8,=2,5,8,3 3R R=3=3,所以根据商集的定义,所以根据商集的定义,A/R=1A/R=1R R,2,2R R,3,3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三篇 二元关系特殊关系PPT讲稿 第三 二元关系 特殊 关系 PPT 讲稿
限制150内