第三章集合与关系优秀课件.ppt

《第三章集合与关系优秀课件.ppt》由会员分享，可在线阅读，更多相关《第三章集合与关系优秀课件.ppt（117页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 集合与关系第1页，本讲稿共117页3.4 关系及其表示关系及其表示 定义定义3-5.1 若若 则是一个二元关系。则是一个二元关系。即：序偶作为元素的任即：序偶作为元素的任何集合何集合。关系表示方法关系表示方法（1）枚举法）枚举法（直观法、列举法）（直观法、列举法）设设R表示二元关系，用表示二元关系，用 表示特定的序偶，表示特定的序偶，若若 ，则也可写成：，则也可写成：x R y。第2页，本讲稿共117页3.4 关系及其表示关系及其表示例：二元关系定义如图：例：二元关系定义如图：可写成：可写成：由定义可见：关系是一个集合，由定义可见：关系是一个集合，定义集合的方法都可以来定义关系。定义集

2、合的方法都可以来定义关系。第3页，本讲稿共117页3.4 关系及其表示关系及其表示（2）谓词公式表示法）谓词公式表示法 前面讲述，一个集合可用谓词公式来表达，所前面讲述，一个集合可用谓词公式来表达，所以关系也可用谓词公式来表达。以关系也可用谓词公式来表达。例：实数集合例：实数集合R上的上的“”关系关系可表达为：可表达为：大于关系：大于关系：“”=父子关系：父子关系：“F”=第4页，本讲稿共117页3.4 关系及其表示关系及其表示（3）关系矩阵表示法）关系矩阵表示法 规定：规定：(a)二元关系二元关系中的序偶中左元素表示行，右中的序偶中左元素表示行，右元素表示列；元素表示列；(b)若若 ，则在对

3、应位置记上，则在对应位置记上“1”，否则为，否则为“0”。第5页，本讲稿共117页3.4 关系及其表示关系及其表示例例1：设：设并定义为并定义为列出关系矩阵：列出关系矩阵：第6页，本讲稿共117页3.4 关系及其表示 是是的全域关系，的全域关系，例例2：设：设X=a,b,c,Y=1,2,R2是是的关系，的关系，第7页，本讲稿共117页3.4 关系及其表示关系及其表示（4）关系图表示法）关系图表示法规定：规定：(a)把、集合中的元素以点的形式全部画在平面上；把、集合中的元素以点的形式全部画在平面上；(b)若若 ，则，则xi和和yi之间画一箭头弧线，反之不画任何之间画一箭头弧线，反之不画任何联线。

4、联线。例：例：是是X中的二元关系，中的二元关系，第8页，本讲稿共117页3.4 关系及其表示关系及其表示用关系图表示：用关系图表示：第9页，本讲稿共117页3.4 关系及其表示关系及其表示关系的定义域和值域：关系的定义域和值域：定义定义设设S是一个二元关系，是一个二元关系，D(s)是所有客体是所有客体x的集合，对于的集合，对于一些一些y来说，若有来说，若有 ，则称，则称D(s)为为S的定义域（简的定义域（简称称“域域”），即），即 设设R(S)是所有客体是所有客体y的集合，对于一些的集合，对于一些X来说，若有来说，若有，则称集合，则称集合R(S)是是S的值域（简称的值域（简称“值值”）,即：即

5、：第10页，本讲稿共117页3.4 关系及其表示关系及其表示 例：例：X=1,2,3,4,5,6,R为为X到到Y的二元关系：的二元关系：，则，则 一般情况，称一般情况，称X为为R的的前域前域，称，称Y为为R的的陪域陪域。第11页，本讲稿共117页3.4 关系及其表示关系及其表示关系和笛卡尔乘积关系和笛卡尔乘积笛卡尔乘积的任何子集都可以定义一种二元关系。笛卡尔乘积的任何子集都可以定义一种二元关系。例：例：X=1,2,3,4，Y=1,2，则，则 均为二元关系。均为二元关系。第12页，本讲稿共117页3.4 关系及其表示关系及其表示三个特殊关系：空白关系，全域关系，恒等关系三个特殊关系：空白关系，全

6、域关系，恒等关系 定义定义 集合集合X2定义了定义了X集合中的一种关系，通称集合中的一种关系，通称 为为X中的全域关系，用中的全域关系，用Ex表示：表示：空集也是空集也是 的一个子集，它也定义了一种关系的一个子集，它也定义了一种关系称为空白关系；称为空白关系；X集合中的恒等关系，集合中的恒等关系，在全域关系和恒等关系中前域在全域关系和恒等关系中前域=定义域，陪域定义域，陪域=值域。值域。第13页，本讲稿共117页3.4 关系及其表示关系及其表示例：例：=，则，则 同一域上的关系同一域上的关系,可进可进行集合的所有运算。行集合的所有运算。第14页，本讲稿共117页3.5 关系的性质关系的性质自反

7、性：自反性：定义 设是集合中的二元关系，对于每一个（所有的）有,则称是自反关系,X中R是自反的 例：设例：设 是自反的关系。是自反的关系。R的关系矩阵的关系矩阵 第15页，本讲稿共117页3.5 关系的性质关系的性质 定义定义 设设R是是X中的二元关系，对于每一个中的二元关系，对于每一个 ，有有x x，则称，则称R是是反自反反自反的关系，表示成：的关系，表示成：R是是X中的反中的反 自反的关系自反的关系 x x 。例：设例：设X=1,2,3,第16页，本讲稿共117页3.5 关系的性质对称性对称性 定定义 设设R是是X中的二元关系，对于每一个中的二元关系，对于每一个来讲，如果每当有来讲，如果每

8、当有xRyxRy，则必有，则必有yRxyRx，则称，则称R R是是X X中的中的对称关系，并表示成：对称关系，并表示成：R R是是X X中的中的对称对称关系关系 S4既不是自反既不是自反的，又不是反的，又不是反自反的自反的第17页，本讲稿共117页3.5 关系的性质例：设例：设X=1,2,3,R=则则R是对称的关系是对称的关系 定义定义 设设R是是X集合中的二元关系，对于每一个集合中的二元关系，对于每一个 来讲，如果每当来讲，如果每当xRy和和yRx就必有就必有x=y，则称，则称R是是反对称反对称的关系。的关系。第18页，本讲稿共117页3.5 关系的性质关系的性质 即当且仅当即当且仅当 X中

9、的R才是反对称的。讨论定义：（1）前件 为为“T”，则则x=y也为也为“T”,则为反对称的；则为反对称的；（2）前件 为为“F”，则有三种情况：后件（后件（x=y）不论是真还是假，命题公式为）不论是真还是假，命题公式为“T”。下面举例说明：第19页，本讲稿共117页3.5 关系的性质关系的性质例：设例：设X=a,b,c均是反对称的均是反对称的第20页，本讲稿共117页3.5 关系的性质关系的性质例：例：X=a,b,c,下列关系不是对称的，也不是反对称的下列关系不是对称的，也不是反对称的第21页，本讲稿共117页3.5 关系的性质关系的性质X上的恒等关系上的恒等关系 是自反、对称、反对称的。是自

10、反、对称、反对称的。第22页，本讲稿共117页3.5 关系的性质关系的性质X上的全域关系：上的全域关系：是自反的，对称的是自反的，对称的 X上的空关系是反自反、对称、反对称的。上的空关系是反自反、对称、反对称的。第23页，本讲稿共117页3.5 关系的性质关系的性质传递性：传递性：定义设R是X中的二元关系，对于每一个 来说，如果每当，就必有 则称R是可传递的，并表示成：X中R可传递 讨论定义：（1）前件 为为“T”，则则xRz也为也为“T”，R是可传递的是可传递的；（2）前件为）前件为“F”，有三种情况，有三种情况后件不论是真还是假，命题为后件不论是真还是假，命题为“T”，则，则R是可传递的是

11、可传递的 第24页，本讲稿共117页3.5 关系的性质关系的性质 例：设例：设X=a,b,c，则下列关系均是可传递的，则下列关系均是可传递的第25页，本讲稿共117页3.5 关系的性质关系的性质下列关系是不可传递的：下列关系是不可传递的：第26页，本讲稿共117页3.5 关系的性质关系的性质确定二元关系性质举例确定二元关系性质举例（1）设）设X=1,2,3，反自反，反对称，可传递的；反自反，反对称，可传递的；反对称的；反对称的；第27页，本讲稿共117页3.5 关系的性质关系的性质自反，对称，反对称，可传递的；自反，对称，反对称，可传递的；自反，对称，可传递的；自反，对称，可传递的；反自反的，

12、对称的，反对称的，反自反的，对称的，反对称的，可传递的。可传递的。第28页，本讲稿共117页3.5 关系的性质关系的性质（2）若）若，则X上的空关系 自反的，反自反的，对称的，反对称的，可传递的。从定义上看前件为假，后件不论是真还是假，从定义上看前件为假，后件不论是真还是假，命题为命题为“T”，第29页，本讲稿共117页3.6 关系的运算关系的运算一、关系的集合运算一、关系的集合运算：关系是有序对集合，集合的元素对关系仍关系是有序对集合，集合的元素对关系仍然适用。然适用。定理定理1：设：设R和和S是从是从A到到B的两个关系，则的两个关系，则RS，R S，R-S，R，R S仍是从仍是从A到到B的

13、关的关系。系。第30页，本讲稿共117页3.6 关系的运算关系的运算二、复合关系二、复合关系：引例：引例：a，b，c三人，三人，a，b是兄妹关系，是兄妹关系，b，c是母子关系，则是母子关系，则a，c是舅甥关系。是舅甥关系。如设如设R是兄妹关系，是兄妹关系，S是母子关系，则是母子关系，则R与与S的复合的复合T是舅甥关系，而是舅甥关系，而S与与R复合是母女关系。复合是母女关系。又如：又如：R是父子关系，是父子关系，R与与R的复合是祖孙关系。的复合是祖孙关系。第31页，本讲稿共117页3.6 关系的运算关系的运算1、复合关系的定义（关系的复合运算）、复合关系的定义（关系的复合运算）定义定义3-7.1

14、：设：设X，Y，Z是三个集合，设是三个集合，设R为为X到到Y的的关系，关系，S为为Y到到Z的关系，则的关系，则RS为为R和和S的复合关的复合关系，表示为：系，表示为：第32页，本讲稿共117页3.6 关系的运算关系的运算1、复合关系的定义（关系的复合运算）、复合关系的定义（关系的复合运算）说明说明：（1）R与与S能进行复合的必要条件是能进行复合的必要条件是R的值的值域所属集合域所属集合B与与S定义域所属集合定义域所属集合B是同一集合，是同一集合，否则就不能复合。否则就不能复合。（2）有这个复合关系的定义为至少有有这个复合关系的定义为至少有一个中间桥梁的元素一个中间桥梁的元素y，使，使RR与与S

15、S（3 3）R S为新的二元关系为新的二元关系（4）R S XZ第33页，本讲稿共117页3.6 关系的运算关系的运算例例1：设：设A=1,2,3,4,5,B=3,4,5,C=1,2,3,R是是A到到B的关系，的关系，S是是B到到C的关系。的关系。R=|x+y=6=,S=|y-z=2=则则RS=？RS=，第34页，本讲稿共117页3.6 关系的运算关系的运算例例2：设：设A=1,2,3,4,5，R,S均为均为AA的关系，且的关系，且R=S=SR=“”是是不可交换不可交换的的。则则RS=第35页，本讲稿共117页3.6 关系的运算关系的运算“”是是不可交换不可交换的的。说明说明：（1）R是是A到

16、到B的关系，的关系，S是是B到到C的关系，的关系，RS有有定义，而定义，而S R根本不能复合。根本不能复合。（2）若）若A=C，则，则RS是是A上的关系，而上的关系，而S R是是B上的关系，不可能相等。上的关系，不可能相等。（3）若）若A=B=C，R、S均为均为A上的关系，上的关系，RS和和S R也是也是A上的关系，一般地上的关系，一般地RS和和S R不可能相不可能相等。等。第36页，本讲稿共117页3.6 关系的运算关系的运算定理：设定理：设 则有：则有：复合关系图复合关系图 可见可见复合关系满足结合律复合关系满足结合律 第37页，本讲稿共117页3.6 关系的运算关系的运算 由关系复合的结

17、合律可知关系由关系复合的结合律可知关系R本身所组成的复合关本身所组成的复合关系可以写成：系可以写成：RR，RR R，分别记作，分别记作R（2），R（3），定义定义：给定集合：给定集合X，R是是X中的二元关系，设中的二元关系，设n N，则，则R的的n次幂次幂Rn可以定义为：可以定义为：（1）R0=X集合中的恒等关系集合中的恒等关系（2）Rn+1=Rn R 第38页，本讲稿共117页3.6 关系的运算关系的运算例例3 设设R，S是是I+中的二元关系，且中的二元关系，且则：则：第39页，本讲稿共117页3.6 关系的运算关系的运算例例4若若|X|=n，则，则X中的二元关系中的二元关系R的幂次值是有限

18、的。的幂次值是有限的。一般不用求出超过一般不用求出超过X的基数次幂。的基数次幂。第40页，本讲稿共117页3.6 关系的运算关系的运算2、复合关系的矩阵表示、复合关系的矩阵表示设有三个集合：设有三个集合：设设R为为X到到Y的关系，的关系，S为为Y到到Z的关系：的关系：而|X|=m,|Y|=n,|Z|=p，则关系矩阵第41页，本讲稿共117页3.6 关系的运算关系的运算2、复合关系的矩阵表示、复合关系的矩阵表示例例5：设：设X=1,2,3,4,5,R,S均是均是X中的二元关系，中的二元关系，R=,S=第42页，本讲稿共117页3.6 关系的运算关系的运算逆关系逆关系 定义定义3-7.23-7.2

19、设设X,YX,Y是二个集合，若是二个集合，若R R是是XYXY的关系，从的关系，从YXYX的关系，称为的关系，称为R R的逆关系，的逆关系，用用 表示，或用Rc表示。讨论定义：（1）只要将R中每一个序偶中的元素全部调换位置,就可得到R的逆关系 ，故|=|R|（2）设 的关系矩阵为 的转置矩阵；（3）在R的关系图中，只要把所有箭头改换方向就可得到的关系图。（自回路箭头改变与否无关）第43页，本讲稿共117页3.6 关系的运算关系的运算3、逆关系、逆关系例例6：X=0,1,2，R=,=,第44页，本讲稿共117页3.6 关系的运算关系的运算定理定理3-7.1 设设R，R1，R2都是从都是从A到到B

20、的二元关系，的二元关系，则下列各式成立。则下列各式成立。第45页，本讲稿共117页3.6 关系的运算关系的运算定理定理3-7.2 设设T为从为从X到到Y的关系，的关系，S为从为从Y到到Z的关系，证明的关系，证明第46页，本讲稿共117页3.6 关系的运算关系的运算例：例：，试求：，试求：第47页，本讲稿共117页3.6 关系的运算关系的运算第48页，本讲稿共117页3.6 关系的运算关系的运算定理定理3-7.3 设设R为为X上的二元关系，则上的二元关系，则（1）R是对称的，当且仅当是对称的，当且仅当R=Rc（2）R是反对称的，当且仅当是反对称的，当且仅当RRc Ix第49页，本讲稿共117页3

21、.6 关系的运算关系的运算证明：证明：充分性：充分性：R是对称的是对称的 对于任一对于任一 必要性：必要性：R是对称的，是对称的，对任一对任一 R一定是对称的一定是对称的第50页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算定义定义3-8.1给定集合给定集合X，R是是X中的二元关系，若有另一关中的二元关系，若有另一关系系R满足下列条件：满足下列条件：（1）R是自反的（对称，可传递的）；是自反的（对称，可传递的）；（2）（3）对于任一自反（对称，传递的）关系）对于任一自反（对称，传递的）关系R，若若，则 则称则称R是是R的自反（对称，传递的）闭包，的自反（对称，传递的）闭包，并依次用并依

22、次用r(R),s(R),t(R)来表示之。来表示之。第51页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算讨论定义：讨论定义：（1）由（）由（2）知，）知，R是在是在R的基础上添加元素（有序对）；的基础上添加元素（有序对）；（2）由（）由（1）知，）知，R添加元素其目标是使添加元素其目标是使R具有自反具有自反性（对称性、传递性）性（对称性、传递性）（3）由（）由（3）知，在添加后使之具有自反性的所有关系中）知，在添加后使之具有自反性的所有关系中R是最小的一个，即要在保证其具有自反性的前提下，要尽是最小的一个，即要在保证其具有自反性的前提下，要尽量少添加元素，没必要的元素不要加入。量少添

23、加元素，没必要的元素不要加入。第52页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算例：设例：设X=a,b,R=，r(R)=,s(R)=,t(R)=R例：求例：求t(R)需要特别小心，要进行多次添项。需要特别小心，要进行多次添项。设设X=a,b,c,R=，求，求r(R),s(R),t(R)解：解：r(R)=s(R)=t(R)=第53页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算从关系图中可以看到：从关系图中可以看到：（1）r（R）是在）是在R的基础上添加自回路，使得每点均有自回的基础上添加自回路，使得每点均有自回路。路。（2）s（R）是在）是在R中两点间只有一条弧的情况下，再

24、添中两点间只有一条弧的情况下，再添加一条反向弧，使得两点间或是加一条反向弧，使得两点间或是0条弧，或是两条弧，条弧，或是两条弧，原来两点间没有弧不能添加。原来两点间没有弧不能添加。（3）t（R）是在）是在R中如结点中如结点a通过有向路能通到通过有向路能通到x，则添，则添加一条从加一条从a到到x的有向弧，其中包括如的有向弧，其中包括如a能达到自身，则能达到自身，则必须添从必须添从a到到a的自回路。的自回路。第54页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算定理定理3-8.1给定集合给定集合X，R是是X中的二元关系，那么：中的二元关系，那么：（1）当且仅当）当且仅当r(R)=R，则，则

25、R是自反的；是自反的；（2）当且仅当）当且仅当s(R)=R，则，则R是对称的；是对称的；（3）当且仅当）当且仅当t(R)=R，则，则R是可传递的。是可传递的。第55页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算定理定理3-8.2R是是X中的二元关系中的二元关系 是是X中的恒等关系，中的恒等关系，则有则有 证明：按定义证：（证明：按定义证：（1）设）设 ，则，则R是自反的，是自反的，（3）设有任一）设有任一R也是自反的，且也是自反的，且 则则 第56页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算定理定理3-8.3给定集合给定集合X，R是是X中的二元关系，则有中的二元关系，则有

26、 定理定理3-8.4设设X是一集合，是一集合，R是是X中的二元关系，则：中的二元关系，则：第57页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算例：例：X=a,b,c,R=，|X|=3,则则 定理定理3-8.5设设|X|=n，R是是X中的二元关系，则中的二元关系，则 第58页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算说明：说明：Rk的每条弧就是在的每条弧就是在R中，任何一点中，任何一点x，经过，经过k条弧组条弧组成的有向路到达成的有向路到达y，则，则 Rk而传递闭包而传递闭包t(R)就是就是在在R中如点中如点x经过任何条弧能到达经过任何条弧能到达y，则，则x到到y应直接有一

27、应直接有一条有向弧，故定理条有向弧，故定理3-8.4就是就是t(R)要在要在R的基础上并上的基础上并上R2，R3 而如而如A是有限集合是有限集合|A|=n，如在，如在x点有超过点有超过n步能到达步能到达y点，则必有点，则必有一条更短的有向路，至多一条更短的有向路，至多n步可以到达步可以到达y，所以得到，所以得到3-8.5。第59页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算例：例：X=a,b,c,d,R=,则则 第60页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算定理定理设设X是一集合，是一集合，R是是X中的二元关系，则有：中的二元关系，则有：（1）r(S(R)=S(r(R

28、);（2）r(t(R)=t(r(R);（3）t(S(R)S(t(R)。第61页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算证明：（证明：（1）r(S(R)常用下列符号表示一些闭包：常用下列符号表示一些闭包：“R加加”：，传递闭包，传递闭包，“R星星”：，自反可传递闭包，自反可传递闭包，第62页，本讲稿共117页3.7 关系的闭包运算关系的闭包运算例：设例：设X=a,b,c,R=（1）rS(R)=r =Sr(R)=s =（2）rt(R)=r=tr(R)=t=（3）tS(R)=t =St(R)=S=t(S(R)St(R)第63页，本讲稿共117页3.8 集合的划分和覆盖集合的划分和覆盖定

29、义定义1给定一非空集合给定一非空集合A，又设，又设 若（1）（2）则称S为A的覆盖。例例1：S=a,b,c，A=a,b,b,c，B=a,a,b,c，C=a,b,c，D=a,b,a,c 均为均为S的覆盖。的覆盖。第64页，本讲稿共117页3.8 集合的划分和覆盖集合的划分和覆盖定义定义1给定一非空集合给定一非空集合A，又设，又设 若（1）（2）则称S为A的覆盖。例例2：四个半圆覆盖一正方形。：四个半圆覆盖一正方形。第65页，本讲稿共117页3.8 集合的划分和覆盖集合的划分和覆盖定义2给定一非空集合S，设非空集合 如果有：或（i,j=1,2,m）则称集合A是集合S的一个划分。第66页，本讲稿共1

30、17页 3.8 集合的划分和覆盖集合的划分和覆盖讨论定义：（1）划分和覆盖主要差别在第（2）条；（2）划分A中的元素，称为划分的类，在定义中 均是A中的一个类，类的个数称为划分的秩；（3）若A为有限集合，则A的秩是有限的，为|A|，若A为无限集合，则划分的秩是无限的；（4）集合的划分必定是一个覆盖，而覆盖不一定是划分；（5）集合S上的秩最大的划分称最大划分，最小的称最小划分。第67页，本讲稿共117页 3.8 集合的划分和覆盖集合的划分和覆盖例例3：设：设S=a,b,c，下列，下列 均为S的一个划分：=2（秩）；最大划分，秩为3；最小划分，秩为1。=2（秩）；=2（秩）；第68页，本讲稿共11

31、7页 3.8 集合的划分和覆盖集合的划分和覆盖例4：四个直角三角形组成了正方形的一个划分 秩=4第69页，本讲稿共117页 3.8 集合的划分和覆盖集合的划分和覆盖定义定义设设A和和A是非空集合是非空集合S的二种划分，并可表示成：的二种划分，并可表示成：若若A的每一个类的每一个类 都是A的某一个类 的子集，则称划分的子集，则称划分A是划分是划分A的的加细加细，或讲或讲A加细了加细了A，若，若A加细了加细了A且且 则称则称A是是A的的真加细真加细。讨论定义：A加细了加细了A，一定有，一定有|A|A|（秩），若（秩），若|A|A|，则一定为真，则一定为真加细。加细。第70页，本讲稿共117页3.8

32、 集合的划分和覆盖集合的划分和覆盖例：例：S=a,b,c,d，S的划分：的划分：A=a,b,c,d,A=abc,d，则，则A是是A的真加细的真加细 A=abcd,则则A 是是A的真加细的真加细 第71页，本讲稿共117页3.9 3.9 等价关系与等价类等价关系与等价类定义定义3-10.1 设设R为定义在集合为定义在集合A上的一个关系，若上的一个关系，若R是自反的、是自反的、对称的和传递的，则对称的和传递的，则R称为等价关系。如果称为等价关系。如果R是一个等价关系，是一个等价关系，R称称a等价于等价于b，记作，记作ab。（1）在一群人的集合上年龄相等的关系是等价关系，而朋友关在一群人的集合上年龄

33、相等的关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递的。系不一定是等价关系，因为它可能不是传递的。（2）命题公式间的逻辑等值关系是等价关系。）命题公式间的逻辑等值关系是等价关系。（3）集合上的恒等关系和全域关系都是等价关系。）集合上的恒等关系和全域关系都是等价关系。（4）在同一平面上直线之间的平行关系，三角形之间的相）在同一平面上直线之间的平行关系，三角形之间的相似关系都是等价关系。似关系都是等价关系。第72页，本讲稿共117页3.9 3.9 等价关系与等价类等价关系与等价类例例1 A=1，2，3，4，5，6，7，R是是A上的上的“模模3同余同余”关系，关系，为整数为整数 即即

34、xy(mod 3)试验证R是等价关系，画出R的关系图，列出R的关系矩阵 第73页，本讲稿共117页3.9 3.9 等价关系与等价类等价关系与等价类（2）R的关系矩阵的关系矩阵 解：（解：（1）R=从图中可以看出，该等价关系将从图中可以看出，该等价关系将A分分成成3个类个类1,4,7,2,5,8,3,6,类类内均有关系，而类间均没有关系内均有关系，而类间均没有关系R满足自反、对称和可传递的，满足自反、对称和可传递的，R是一等价关系是一等价关系第74页，本讲稿共117页3.9 3.9 等价关系与等价类等价关系与等价类定义定义 设设mI+x，yI，若对于某个整数，若对于某个整数n有：有：（x-y）=

35、n m，则称则称x模模m等于等于y，记作：，记作：xy(mod m)定理 任何集合X I，（I的任何子集X中）的模m等价，是一个等价关系。第75页，本讲稿共117页3.9 3.9 等价关系与等价类等价关系与等价类定义定义3-10.2 设设R为集合为集合A上的等价关系，对于任何上的等价关系，对于任何aA，集合集合aR=x|x A，aRx 称为元素称为元素a形成的形成的R等价类。等价类。讨论定义：讨论定义：（1）等价类）等价类aR是一个集合，由定义可见是一个集合，由定义可见aR A（2）aR中的元素是等价关系中，所有与中的元素是等价关系中，所有与a具有关系的元素具有关系的元素所组成的集合，且所组成

36、的集合，且aR 第76页，本讲稿共117页3.9 等价关系与等价类等价关系与等价类例：设例：设X=N，关系，关系R=可被3整除 是一等价关系，则R可以找出三个等价类：=0，3，6，9，此集合中的元素除以，此集合中的元素除以3的余数为的余数为“0”；=1，4，7，10，此集合中的元素除以，此集合中的元素除以3的余数为的余数为“1”；=2，5，8，11，此集合中的元素除以，此集合中的元素除以3的余数为的余数为“2”。第77页，本讲稿共117页3.9 3.9 等价关系与等价类等价关系与等价类例：设例：设X=a,b,c,d，R是是X中的等价关系，中的等价关系，R=则则 第78页，本讲稿共117页3.9

37、 3.9 等价关系与等价类等价关系与等价类定理设X是一个集合，R是X中的等价关系，则（1）若，则（2）若xRy，则（3）（3）若x y，则第79页，本讲稿共117页3.9 等价关系与等价类等价关系与等价类例：X为全班同学的集合，则班中同姓关系是一个等价关系，（1）任何一个人均）任何一个人均某一个等价类，王某某某一个等价类，王某某王王 R张某张某 张张R （2）任何二个姓的等价类，只有二种可能）任何二个姓的等价类，只有二种可能一种：王 R=李R 二种：王 R李R=（3）全班同学的集合=同姓关系等价类的并集=王 李 （4）所有等价类的集合，一定导致全班同学集合的一个划分：）所有等价类的集合，一定导

38、致全班同学集合的一个划分：A=王王R，李李R.第80页，本讲稿共117页3.9 等价关系与等价类等价关系与等价类定理定理3-10.2设设X是一非空集合，是一非空集合，R是是X中的等价关系，中的等价关系，R等等价类的集合价类的集合xR|x X是是X的一个划分，且此集合称为的一个划分，且此集合称为X按按R的商集，用的商集，用 表示之。例：设例：设X=x1,x2.xn（1）X集合中的全域关系，集合中的全域关系，它是一个等价关系，它是一个等价关系，X按按 R1的商集的商集它形成了它形成了X的一个最小划分的一个最小划分 第81页，本讲稿共117页3.9 等价关系与等价类等价关系与等价类（2）X中的恒等关

39、系中的恒等关系 它形成了它形成了X的一个最大划分的一个最大划分 例：例：X为全班同学的集合，为全班同学的集合，|X|=n,(nN)N)（1）同学关系）同学关系R1是一个等价关系，是一个等价关系，（2）按指纹的相同关系）按指纹的相同关系R2是一个等价关系，是一个等价关系，它形成了全班同学的最大划分它形成了全班同学的最大划分 第82页，本讲稿共117页3.9 等价关系与等价类等价关系与等价类（3）同姓关系）同姓关系R3是一等价关系是一等价关系张张 R3，李李R3，它形成了全班同学的既不是最大，又不是最小划分它形成了全班同学的既不是最大，又不是最小划分第83页，本讲稿共117页3.9 等价关系与等价

40、类等价关系与等价类定理定理3-10.3X是一非空集合，是一非空集合，A为为X的一个划分，且的一个划分，且A=A1,A2,.An，则由，则由A导出的导出的X中的一个等价关系中的一个等价关系 例：例：Xa,b,c,d，A=a,b,c,d则则 R(a,b a,b)(c,d c,d)=,由此我们看到：集合由此我们看到：集合X上的等价关系与上的等价关系与X的划分之间有对应关系。的划分之间有对应关系。第84页，本讲稿共117页3.10 相容关系相容关系定义定义3-11.1给定一个集合给定一个集合X，R是是X中的二元关系，如果中的二元关系，如果R是是自反、对称的，则称自反、对称的，则称R是相容关系。是相容关

41、系。例：设例：设X=ball,bed,dog,let,egg,5个英文单词个英文单词定义定义X中一个二元关系：中一个二元关系：R=有相同的字母有相同的字母 则则R是自反的，对称的，但不可传递是自反的，对称的，但不可传递(ball R bed)(bed R egg)(ball R egg)则则R=第85页，本讲稿共117页3.10 相容关系相容关系第86页，本讲稿共117页3.10 相容关系相容关系定义定义3-11.2 设设X是一个集合，是一个集合，R是是X上的相容关上的相容关系，假定系，假定A X，若对于，若对于A中任意两个元素中任意两个元素a1，a2有有a1Ra2，称，称A是由相容关系是由相

42、容关系R产生的相容类。产生的相容类。第87页，本讲稿共117页3.10 相容关系相容关系定义定义3-11.3设设X是一个集合，是一个集合，R是是X中的相容关中的相容关系，假定系，假定A X，若任一，若任一 xA都与都与A中的其它所中的其它所有元素有相容关系，而（有元素有相容关系，而（X-A）中没有一个元）中没有一个元素与素与A中的所有元素有相容关系，则称子集中的所有元素有相容关系，则称子集A为为相容关系相容关系R的一个最大相容类。的一个最大相容类。例：上例中例：上例中 均是均是X中的最大相容类中的最大相容类,且且 定义了定义了X的一个覆盖。的一个覆盖。同样已知同样已知X集合的一个覆盖集合的一个

43、覆盖 第88页，本讲稿共117页3.10 相容关系相容关系则一定可以求出相对应的相容关系来：则一定可以求出相对应的相容关系来：讨论等价关系和相容关系后可得到结论：讨论等价关系和相容关系后可得到结论：集合集合X上的相容关系上的相容关系R的所有最大相容类集合的所有最大相容类集合A1,A2,.Am构成集合构成集合X的一个覆盖。即：的一个覆盖。即：而集合而集合X上的等价关系上的等价关系R的所有等价类集合构成的所有等价类集合构成X的的一个划分一个划分第89页，本讲稿共117页3.10 相容关系相容关系求最大相容类的方法：求最大相容类的方法：关系图法：关系图法：确定最大确定最大完全多边形完全多边形 每个顶

44、点都与其他所有顶点相联结的多边形。每个顶点都与其他所有顶点相联结的多边形。(1)孤立结点是最大的完全多边形；孤立结点是最大的完全多边形；(2)二个相互联结的结点是最大完全多边形；二个相互联结的结点是最大完全多边形；(3)三角形是三个结点的最大完全多边形；三角形是三个结点的最大完全多边形；第90页，本讲稿共117页3.10 相容关系相容关系(4)四个结点；四个结点；(5)五个结点五个结点;画出简化相容关系的关系图后，画出简化相容关系的关系图后，先结点最多的完全多边形，以后逐次减少。先结点最多的完全多边形，以后逐次减少。第91页，本讲稿共117页3.10 相容关系关系例：已知相容关系图，求出最大相

45、容类例：已知相容关系图，求出最大相容类第92页，本讲稿共117页3.10 相容关系相容关系最大相容类集合为最大相容类集合为第93页，本讲稿共117页3.113.11序关系序关系1、偏序关系、偏序关系定义定义3-12.1设设R是非空集合是非空集合A上的关系，如果上的关系，如果R具有具有自反性自反性、反对称性反对称性和和传递性传递性，则，则R是是A上上的偏序关系，并把关系的偏序关系，并把关系R记作记作“”。序偶序偶称作偏序集。称作偏序集。讨论定义：讨论定义：（1）“”不是指普通实数中的不是指普通实数中的关系，而是关系，而是代表更为普遍的关系（具有自反，反对称和可代表更为普遍的关系（具有自反，反对称

46、和可传递性的关系）；传递性的关系）；（2）如果）如果 ，则记作，则记作x y，读作，读作“x小于或等于小于或等于y”第94页，本讲稿共117页3.113.11序关系序关系1、偏序关系、偏序关系例例1、设集合、设集合A=a，b，c，A上的关系上的关系R为：为：R=，从关系图来验证，从关系图来验证R是偏序关系是偏序关系第95页，本讲稿共117页3.113.11序关系序关系例例2、设、设A是非零自然数集，是非零自然数集，R是是A上的整除关系，上的整除关系，验证验证R是偏序关系。是偏序关系。（1）x A，因，因x能整除能整除x，R具有自反性。具有自反性。（2）x，y A，如，如x能整除能整除y，且，且

47、y能整除能整除x，则，则x=y。即即 R，R，则则x=y，即，即R具有反对称性。具有反对称性。（3）x，y，z A，如，如 R，R，即，即 x能整除能整除y，y能整除能整除z，则，则x能能整除整除z，R，R具有传递性。具有传递性。R是是A上的偏序关系。上的偏序关系。第96页，本讲稿共117页3.113.11序关系序关系2、拟序关系、拟序关系 设设R是非空集合是非空集合A上的关系，如果上的关系，如果R具有具有反反自反性自反性和和传递性传递性，则，则R是是A上的拟序关系，并上的拟序关系，并把关系把关系R记作记作“”。序偶序偶称作拟序集。称作拟序集。讨论定义：讨论定义：（1）“”不是指普通实数中的不

48、是指普通实数中的关系，而是关系，而是代表拟序关系；代表拟序关系；（2）如果）如果 ，则记作，则记作x y，读作，读作“x小于小于y”第97页，本讲稿共117页3.113.11序关系序关系2、拟序关系、拟序关系例例3、A=1，2，3，4，R是是A上的大于关系。上的大于关系。R=|ab，a，bA 则则R=，注：注：R，在实数中，在实数中3大于大于1，因其是拟，因其是拟序关系，写作序关系，写作“3 1”，读作，读作“3小于小于1”，该小，该小于是拟序的于是拟序的“小于小于”，而不同于真正实数中的，而不同于真正实数中的小于。小于。第98页，本讲稿共117页3.113.11序关系序关系2、拟序关系、拟序

49、关系定理：设定理：设R是集合是集合A上的拟序关系，则上的拟序关系，则R是反对称是反对称的。的。证明：（反证法）设证明：（反证法）设R不是反对称的。则不是反对称的。则 a a，b bA，ab 且且R,R，因，因R是传递的，是传递的，R，R。与。与R是反自反的矛盾，是反自反的矛盾，R具有反对称性。具有反对称性。第99页，本讲稿共117页3.113.11序关系序关系2、拟序关系、拟序关系定理：设定理：设R是集合是集合A上的拟序关系，则上的拟序关系，则R是反对称的。是反对称的。说明说明：（1）由自反性和传递性可以推出反对称）由自反性和传递性可以推出反对称（2）拟序关系具有反自反性、反对称性和可传递性。

50、）拟序关系具有反自反性、反对称性和可传递性。（3）拟序和偏序的区别在于反自反性和自反性。）拟序和偏序的区别在于反自反性和自反性。若若R是偏序关系，则是偏序关系，则R-IA是拟序关系是拟序关系若若R是拟序关系，则是拟序关系，则RIA是偏序关系是偏序关系 第100页，本讲稿共117页3.113.11序关系序关系3、全序关系、全序关系定义定义3-12.4 设设R是是A上的偏序关系，上的偏序关系，若若 a，b A，则，则a b和和b a，两者必居其一，两者必居其一，则称则称R为为A上的全序关系，或称线序关系。上的全序关系，或称线序关系。（1）整除关系）整除关系R，集合的包含关系，集合的包含关系 ，公式