离散数学ppt课件第4章.ppt

1离散数学Discrete Mathematics&学习内容学习内容4.14.1集合的基本知识集合的基本知识集合的基本知识集合的基本知识4.2 序偶与笛卡尔积序偶与笛卡尔积4.3 4.3 关系及其性质关系及其性质关系及其性质关系及其性质4.4 n4.4 n元关系及其应用元关系及其应用元关系及其应用元关系及其应用4.5 4.5 关系的闭包关系的闭包关系的闭包关系的闭包4.6 4.6 等价关系等价关系等价关系等价关系4.7 偏序偏序等价关系等价关系一、等价关系一、等价关系1.定义定义1 1：集合集合A A上的关系叫做等价关系，如果它是自上的关系叫做等价关系，如果它是自反的、对称的和传递的。反的、对称的和传递的。若若a,ba,b A A，且，且aRbaRb，则称，则称a a与与b b等价。等价。1.1.两个由等价关系联系起来的元素叫做两个由等价关系联系起来的元素叫做等价的元素等价的元素。2.2.由于等价关系是自反的，在一个等价关系中每个元由于等价关系是自反的，在一个等价关系中每个元素都与自身等价。素都与自身等价。3.3.因为等价关系是传递的，如果因为等价关系是传递的，如果a a和和b b是等价的且是等价的且b b和和c c是等价的，那么是等价的，那么a a和和c c是等价的。是等价的。【example】设设R是英语字母串的集合上的关系并且使得是英语字母串的集合上的关系并且使得aRb当且仅当当且仅当l(a)=l(b),其中其中l(x)是是x的长度。的长度。R是等价关系吗？是等价关系吗？Solution：因为因为l(a)=l(b),从而只要从而只要a是一个串，就有是一个串，就有aRa,故故aR是自反的是自反的 其次，假设其次，假设aRb，即，即l(a)=l(b)。那么有。那么有bRa，因为，因为l(a)=l(b),因因此此R是对称的。是对称的。最后假设最后假设aRb和和bRc，那么有，那么有l(a)=l(b)和和l(b)=l(c)。因此。因此l(a)=l(c)，即，即aRc，从而，从而R使传递的。使传递的。由于由于R是自反的、对称的和传递的，是自反的、对称的和传递的，R是等价关系。是等价关系。【example】设设R是实数集上的关系，满足是实数集上的关系，满足aRb，当且仅当，当且仅当a-b是整数。是整数。R是等价关系吗？是等价关系吗？solution：因为对所有的实数因为对所有的实数a，a-a=0是整数，即对所有的实数有是整数，即对所有的实数有aRa，因此，因此R是自反的。是自反的。现在假设现在假设aRb，那么，那么a-b是整数，所以是整数，所以b-a也是整数。因此有也是整数。因此有bRa。R是对称的。是对称的。如果如果aRb和和bRc，那么，那么a-b和和b-c是整数，所以是整数，所以a-c=(a-b)+(b-c)也是整数。因此也是整数。因此aRc。于是，。于是，R是传递的。是传递的。综上所述，综上所述，R是等价关系。是等价关系。【example】模模m同余。同余。设设m是大于是大于1的正整数。证明的正整数。证明关系关系R=(a,b)|a b(mod m)是整数集上的等价关系。是整数集上的等价关系。Solution：回顾回顾2.4节，节，a b(mod m),当且仅当当且仅当m整除整除a-b。注意。注意a-a=0被被m整整除，因为除，因为0=0*m。因此。因此a a(mod m)，从而模，从而模m同余关系是自反的。同余关系是自反的。现在假设现在假设a b(mod m)，那么，那么a-b被被m整除，即整除，即a-b=km，其中，其中k是整是整数。从而数。从而b-a=(-k)m,即即b a(mod m)，因此，存在模，因此，存在模m同余关系是对称同余关系是对称的。的。下面假设下面假设a b(mod m)和和b c(mod m)，那么，那么m整除整除a-b和和b-c。因此，存在整数因此，存在整数k和和l，使得，使得a-b=km和和b-c=lm。把这两个等式加起来得。把这两个等式加起来得a-c=(a-b)+(b-c)=km+lm=(k+l)m.于是，于是，a c(mod m)，从而模，从而模m同余同余关系是传递的。关系是传递的。综上所述，模综上所述，模m同余关系是等价关系同余关系是等价关系。【example】集合集合A=1,2,3,4,5,6,7,R是是A上的模上的模3同余关系，同余关系，即即R=|x-y可被可被3整除整除(或或x/3与与y/3的余数相同的余数相同)即即 R x(mod 3)=y(mod3)则则R中的关系为：中的关系为：R=,2.等价关系的有向图等价关系的有向图 1)完全关系完全关系(全域关系全域关系AA)图，下面分别是当图，下面分别是当A中只有中只有1、2、3个元素时的完全关系图。个元素时的完全关系图。1A=112A=1,2123A=1,2,32)等价关系的有向图等价关系的有向图模模3 3同余关系同余关系R R的图：的图：从关系图可看出从关系图可看出R R是自反、对称、传递的关系，所以是自反、对称、传递的关系，所以R R是等是等价关系。价关系。1472536等价关系等价关系R R的有向图可能由若干个独立子图的有向图可能由若干个独立子图(R(R图的一部分图的一部分)构构 成的，每个独立子图都是完全关系图。成的，每个独立子图都是完全关系图。上述关系上述关系R R图就是由三个独立的完全图构成的。图就是由三个独立的完全图构成的。下面给出八个关系如图所示，根据等价关系有向图的特点，下面给出八个关系如图所示，根据等价关系有向图的特点，判断哪些是等价关系。判断哪些是等价关系。下面是下面是A=1,2,3中关系：中关系：1。2。3R21 。2。3R11。2。3R31 。2。3R41。2。3R51 。2。3R61。2。3R71 。2。3R4思考题：思考题：A=1,2,3,可构造多少个可构造多少个A中不同的等价关系？可以中不同的等价关系？可以根据等价关系有向图的特点来考虑。根据等价关系有向图的特点来考虑。如果等价关系如果等价关系R中有中有 a)三个独立子图的情形，则三个独立子图的情形，则()个等价关系个等价关系。b)二个独立子图的情形，则二个独立子图的情形，则()个等价关系个等价关系。c)一个独立子图的情形，则一个独立子图的情形，则()个等价关系个等价关系。一共有一共有()个个中不同的等价关系。中不同的等价关系。二二.等价类等价类 设设A A是学校所有的高中毕业生。考虑是学校所有的高中毕业生。考虑A A上的关系上的关系R R，R R由所有由所有的对的对(x,yx,y)构成，其中构成，其中x x和和y y从同一所高中毕业。给定学生从同一所高中毕业。给定学生x x，我们可以构造所有的关于我们可以构造所有的关于R R与与x x等价的学生的集合。这个集合等价的学生的集合。这个集合由与由与x x在同一高中毕业的所有学生构成。在同一高中毕业的所有学生构成。A A的这个子集叫做这个关系的一个的这个子集叫做这个关系的一个等价类等价类。1.定义定义2：设设R是集合是集合A上的等价关系。与上的等价关系。与A中的一个元素中的一个元素a有关有关系的所有元素的集合叫做系的所有元素的集合叫做a的的等价类等价类。A的关于的关于R的等价类记作的等价类记作aR 当只有一个关系被考虑时，我们将省去下标当只有一个关系被考虑时，我们将省去下标R R并把这个等价类并把这个等价类写作写作a.a.换句话说，如果换句话说，如果R是集合是集合A上的等价关系，元素上的等价关系，元素a的等价类是的等价类是aR=s|(a,s)R如果如果b aR，b叫做这个等价类的叫做这个等价类的代表元代表元。一个等价类的任何元素都可以作为这个类的代表元。也就是一个等价类的任何元素都可以作为这个类的代表元。也就是说，对作为这个类的代表元所选择的特定元素没有特殊要求。说，对作为这个类的代表元所选择的特定元素没有特殊要求。【example】对于关系对于关系R，满足：，满足：aRb,当且仅当当且仅当a=b或或a=-b。一个整数的等价类是什么？一个整数的等价类是什么？solution：在这个等价关系中，一个整数等价于它本身和它的相反数。在这个等价关系中，一个整数等价于它本身和它的相反数。从而从而a=-a,a.这个集合包含两个不同的整数，除非这个集合包含两个不同的整数，除非a=0.例如，例如，7=-7,7,-5=-5,5,0=0.【example】对于模对于模4同余关系，同余关系，0和和1的等价类是什么？的等价类是什么？Solution：0的等价类包含使得的等价类包含使得a 0(mod 4)的所有整数的所有整数a。这个类中的。这个类中的整数是被整数是被4整除的那些整数。因此，对于这个关系整除的那些整数。因此，对于这个关系0的等价类是的等价类是 0=,-8,-4,0,4,8,1的等价类包含使得的等价类包含使得a 1(mod 4)的所有整数的所有整数a。这个类中的。这个类中的整数是当被整数是当被4整除时余数是整除时余数是1的那些整数。因此，对于这个关系的那些整数。因此，对于这个关系1的等价类是的等价类是1=,-7,-3,1,5,9,模模m同余关系的等价类叫作同余关系的等价类叫作模模m同余类同余类。整数。整数a模模m的同余类的同余类记作记作am,满足满足am=,a-2m,a-m,a,a+m,a+2m,【example】A=1,2,3,4,5,6,7,R是是A上的模上的模3同余关系，同余关系，1R=1,4,7=4R=7R-余数为余数为1的等价类的等价类 2R=2,5=5R -余数为余数为2的等价类的等价类 3R=3,6=6R -余数为余数为0的等价类的等价类思考题思考题：此例为什么只有三个等价类？：此例为什么只有三个等价类？2.由等价关系图求等价类由等价关系图求等价类：R图中每个独立子图上的结图中每个独立子图上的结点，构成一个等价类。点，构成一个等价类。不同的等价类个数不同的等价类个数=独立子图个数。独立子图个数。1。2。3R21 。2。3R1R31 。2。3上述三个等价关系各有几个等价类？说出对应的上述三个等价关系各有几个等价类？说出对应的各个等价类。各个等价类。3.等价类性质等价类性质 R是是A上等价关系，任意上等价关系，任意a,b,c A 同一个等价类中的元素，彼此有等价关系同一个等价类中的元素，彼此有等价关系R。即任意即任意x,y aR，必有必有 R proof：任取任取x,y aR，由等价类定义得由等价类定义得 R,R,由由R对称得对称得 R，又由又由R传递得传递得 R。aRbR=，当且当且仅当仅当 R。Proof:设设 R，假设假设aRbR,则存在则存在x aRbR x aR x bR,R,R,由由R对称得对称得 R又由又由R传递得传递得 R,产生矛盾。产生矛盾。若若aRbR=,而而 R,由等价类定义得由等价类定义得b aR,又因为又因为bRb,所以所以b bR，所以所以b aRbR，产生矛盾。产生矛盾。.A中任何元素中任何元素a,a必属于且仅属于一个等价类。必属于且仅属于一个等价类。proof：A中任何元素中任何元素a,由于有由于有aRa,所以所以a aR，如果如果 a bR，所以有所以有 R.由性质由性质得：得：aR=bR。.任意两个等价类任意两个等价类 aR、bR，要么要么aR=bR，要么，要么aRbR=。(因为要么因为要么 R，要么要么 R。).R的所有等价类构成的集合是的所有等价类构成的集合是A的一个划分。的一个划分。(由性质由性质即得。即得。)(这个划分称之为这个划分称之为商集商集)三、等价类与划分三、等价类与划分1.集合的划分与覆盖集合的划分与覆盖 1)定义定义 设设X是一个非空集合是一个非空集合,A=A1,A2,.,An,Ai Ai X(i=1,2,.,n),如果满足如果满足A1 A2.An=X (i=1,2,.,n)则称则称A为集合为集合X的的覆盖覆盖。设设A=A1,A2,.,An是是X一个覆盖一个覆盖,且且Ai Aj=(i j,1i,jn)则称则称A是是X的的划分划分,每个每个Ai均称为这个划分的一个均称为这个划分的一个划分类划分类。【example】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).最小划分与最大划分最小划分与最大划分最小划分：最小划分：划分块最少的划分。即只有一个划分块的划分，这划分块最少的划分。即只有一个划分块的划分，这 个划分块就是个划分块就是X X本身。本身。如如A A1 1=1,2,3=1,2,3。最大划分：最大划分：划分块最多的划分。即每个划分块里只有一个元素划分块最多的划分。即每个划分块里只有一个元素的划分。的划分。如如A A2 2=1,2,3=1,2,3。3).交叉划分交叉划分【exampleexample】X X是东大学生集合是东大学生集合,A,A和和B B都是都是X X的划分：的划分：A=M,W,MA=M,W,M X,X,W W X,M=X,M=男生男生,W=,W=女生女生 B=L,N,LB=L,N,L X,X,N N X,L=X,L=辽宁人辽宁人,N=,N=非非辽宁人辽宁人 WMLNLMLWNMNWC=LM,LW,NM,NW 辽宁男生辽宁男生辽宁女生辽宁女生非辽宁男生非辽宁男生非辽宁女生非辽宁女生称C是X的交叉划分。定义：定义：若若A=A1,A2,.,Am与与B=B1,B2,.,Bn都是集合都是集合 X的划分的划分,则其中所有的则其中所有的Ai Bj,组成的集合组成的集合C,称为称为C 是是A与与B两种划分的两种划分的交叉划分交叉划分。proof:在在C中任取元素中任取元素,Ai Bj X (Ai X,Bj X)(A1 B1)(A1 B2).(A1 Bn)(A2 B1)(A2 Bn).(Am B1)(Am B2).(Am Bn)=(A1(B1 B2 B3.Bn)(A2(B1 B2 B3.Bn).(Am(B1 B2 B3.Bn)=(A1 A2 A3.Am)(B1 B2 B3.Bn)=X X=X 再验证再验证C中任意两个元素不相交：中任意两个元素不相交：在在C中任取两个不同元素中任取两个不同元素Ai Bh和和Aj Bk,考察考察 (Ai Bh)(Aj Bk)(i=j和和h=k不同时成立不同时成立)=(Ai Aj)(Bh Bk)ij,hk (Ai Aj)(Bh Bk)=Ai=ij,hk (Ai Aj)(Bh Bk)=ij,h=k (Ai Aj)(Bh Bk)=Bh=综上所述，综上所述，C是是X的划分。的划分。2.使用等价关系划分集合使用等价关系划分集合【example】设设A A是学校中恰好主修一个专业的学生的集合，是学校中恰好主修一个专业的学生的集合，R R是是A A上上的关系，如果的关系，如果x x和和y y是主修同一专业的学生，则是主修同一专业的学生，则(x,yx,y)属于属于R R。那么可以。那么可以验证验证R R是等价关系。可以看出是等价关系。可以看出R R将将A A中的所有学生分成不相交的子集，其中的所有学生分成不相交的子集，其中每个子集包含某个特定专业的学生。且这些子集是中每个子集包含某个特定专业的学生。且这些子集是R R的等价类。的等价类。该例子说明一个等价关系的等价类怎样把一个集合划分成不该例子说明一个等价关系的等价类怎样把一个集合划分成不相交的非空子集。相交的非空子集。定理定理1 设设R是集合是集合A上的等价关系，下面的命题是等价的。上的等价关系，下面的命题是等价的。(i)aRb (ii)a=b (iii)a b=Proof:首先证明首先证明(i)推出推出(ii)。假设。假设aRb，我们将通过，我们将通过a b 和和b a 来证明来证明a=b。假设假设c a,那么那么aRc。因为。因为aRb和和R的对称性，有的对称性，有bRa。又。又由于由于R是传递的以及是传递的以及bRa和和aRc，就得到，就得到bRc，因而有，因而有c b.这这就证明了就证明了a b。类似地可证明。类似地可证明b a。则得到则得到a=b。其次，我们将证明其次，我们将证明(ii)推出推出(iii).假设假设a=b。这就证明了。这就证明了a b=。因为因为a是非空的（由是非空的（由R的自反性的自反性a a）。）。下面证明下面证明(iii)推出推出(i)。假设。假设a b，那么存在元素，那么存在元素c满满足足c a和和c b。换句话说，换句话说，aRc和和bRc。由对称性有。由对称性有cRb。再根据传递性，。再根据传递性，由由aRc和和cRb 就有就有aRb。因为因为(i)推出推出(ii)，(ii)推出推出(iii)，(iii)推出推出(i)，三个命题，三个命题(i),(ii)和和(iii)是等价的。是等价的。我们现在将显示一个等价关系怎样划分一个集合。我们现在将显示一个等价关系怎样划分一个集合。设设R是集合是集合A上的等价关系，上的等价关系，R的所有等价类的并集就是的所有等价类的并集就是A的的 全部，因为全部，因为A的每个元素的每个元素a都在它自己的等价类即都在它自己的等价类即aR中，换中，换 句话说句话说 此外，由定理此外，由定理1，这些等价类或是相等的或是不相交的，因此，这些等价类或是相等的或是不相交的，因此 当当aRbR时，时，aRbR=这些观察证明等价类构成这些观察证明等价类构成A的划分，因为它们将的划分，因为它们将A分成不相交分成不相交的子集。更确切低说，集合的子集。更确切低说，集合S的的划分划分是一族是一族S的不相交的非空的不相交的非空子集，且子集，且S就是它们的并。就是它们的并。话句话说，一族子集话句话说，一族子集Ai,i I,(其中其中I是指标集是指标集)构成构成S的划分，的划分，当且仅当当且仅当和和（这里符号（这里符号 表示对于所有的表示对于所有的i I 集合集合Ai的并集）的并集）【example】假设假设S=1,2,3,4,5,6，一族集合，一族集合A1=1,2,3,A2=4,5和和A3=6构成构成S的一个划分，因为这些集合是不的一个划分，因为这些集合是不相交的，且它们的并是相交的，且它们的并是S.我们已经看到集合上等价关系的等价类构成这个集合我们已经看到集合上等价关系的等价类构成这个集合的划分。这个划分中的子集就是这些等价类。的划分。这个划分中的子集就是这些等价类。这里给出一个概念：商集。这里给出一个概念：商集。定义：定义：R是是A上等价关系，由上等价关系，由R的所有等价类构成的集合的所有等价类构成的集合称之为称之为A关于关于R的商集。记作的商集。记作A/R。A/R=aR|a A【example】A=1,2,3,4,5,6,7,RA=1,2,3,4,5,6,7,R上模上模3 3同余关系，同余关系，则则 A/R=1R,2R,3R A/R=1R,2R,3R=1,4,7,2,5,3,6=1,4,7,2,5,3,6【exampleexample】X=1,2,3,X X=1,2,3,X上关系上关系R R1 1、R R2 2 、R R3 3，如如下下图所示。图所示。X/RX/R1 1=1=1R1R1,2,2R1R1,3,3R1R1=1,2,3=1,2,3 X/R X/R2 2=1=1R2 R2,2,2R2R2=1,2,3=1,2,3 X/R X/R1 1=1=1R3R3=1,2,3=1,2,31 。2。31。2。3R21 。2。3R1R3集合集合A上的等价关系上的等价关系R，决定了，决定了A的一个划分，该划分就是的一个划分，该划分就是商集商集A/R。反过来，可以用集合的每个划分来构成等价关系。反过来，可以用集合的每个划分来构成等价关系。3.3.由划分确定等价关系由划分确定等价关系等价关系等价关系集合的划分集合的划分A/R？【example】X=1,2,3,4,A=1,2,3,4,A是是X的一个的一个划分，求划分，求X上一个等价关系上一个等价关系R，使得使得X/R=A。显然由然由图可得：可得：R=1,22 32 42。1234一般地一般地A=AA=A1 1,A,A2 2,A,An n 是是X X的一个划分，则构造一的一个划分，则构造一个个X X中的等价关系中的等价关系R R，使得使得X/R=AX/R=A。R=AR=A1 12 2AA2 22 2,A,An n2 2 其中其中A Ai i=A=Ai i2 2A Ai i2 2，下下面证明面证明R R是是X X中的等价关系。中的等价关系。定理定理:集合集合X X的一个划分可以确定的一个划分可以确定X X上上的一个等价关系。的一个等价关系。proof：假设假设A=A1,A2,.,An是是X的一个划分，如下构造的一个划分，如下构造X 上上的一个的一个等价关系等价关系R:RA12 A22 An2，其中其中Ai2=Ai2Ai2，1)证证R自反：任取自反：任取a X，因为因为A是是X的划分，必存在的划分，必存在 Ai A使使x Ai,于是于是 AiAi,又又AiAi R 有有aRa。2)证证R对称：对称：任取任取a,b X,设设aRb，必存在必存在Ai A使得使得 AiAi,于是于是a,b Ai,bRa,R是对称的。是对称的。3)证证R传递：传递：任取任取a,b,c X,设设aRb，bRc,必存在必存在Ai A 使得使得 AiAi,AiAi,于是于是a,b,c Ai,所以所以 AiAi，又又AiAi R 有有aRc 所以所以R传递。传递。最后得最后得R是集合是集合X中的等价关系。中的等价关系。【example】模模4同余产生的整数划分中的集合是什么？同余产生的整数划分中的集合是什么？Solution：存在存在4个同余类，对应于个同余类，对应于04,14,24,34,它们是集合它们是集合04=,-8,-4,0,4,8,14=,-7,-3,1,5,9,24=,-6,-2,2,6,10,34=,-5,-1,3,7,11,【example】设设X=1,2,3，写出集合写出集合X上的所有等价关系。上的所有等价关系。solution：先写出集合先写出集合X上的所有划分，它们是：上的所有划分，它们是：S1=1,2,3，S2=1,2,3，S3=1,3,2 S4=2,3,1,S5=1,2,3 对应的等价关系为：对应的等价关系为：R1=1,2,31,2,3=XX R2=1,21,2 33 =1,1,1,2,2,1,2,2,3,3 R3=1,31,3 22 =1,1,1,3,3,1,3,3,2,2 R4=2,32,3 11 =2,2,2,3,3,2,3,3,1,1 R5=11 22 33 =1,1,2,2,3,3=IX【example】A1=1,2,3,A2=4,5,A3=6是集合是集合S=1,2,3,4,5,6的划分，列出这个划分所产生的等价关系的划分，列出这个划分所产生的等价关系R中的中的有序对。有序对。Solution：划分中的子集是划分中的子集是R的等价类。对的等价类。对(a,b)R,当且仅当当且仅当a和和b在划在划分的同一个子集中。分的同一个子集中。由于由于A1=1,2,3,是一个等价类，因此，对是一个等价类，因此，对(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(3,2),(3,3)属于属于R;由于由于A2=4,5是一个等价类，因此，对是一个等价类，因此，对(4,4),(4,5),(5,4),(5,5)也也属于属于R;最后，由于最后，由于6是一个等价类，对是一个等价类，对(6,6)属于属于R.此外没有其他的此外没有其他的对属于对属于R.1.定义定义:给定集合给定集合X上的关系上的关系r,若若r是自反的、对称的是自反的、对称的,则则r是是A上上相相 容关系。容关系。【example】：X 是由一些英文单词构成的集合。是由一些英文单词构成的集合。X=fly,any,able,key,book,pump,fit,X上关系上关系r:r=|X,X且且与与含有相同字母含有相同字母 r的有向图：看出有自反、对称性的有向图：看出有自反、对称性，而不传递。而不传递。any。ablefly。key。bookpump。fit。yaebklyfy由于在相容关系的关系图上，每个节点处都是有自回路且每由于在相容关系的关系图上，每个节点处都是有自回路且每两个相关节点间的弧线都是成对出现的，为了简化图像，我们以两个相关节点间的弧线都是成对出现的，为了简化图像，我们以后对相容关系图，不画自回路，并用单线代替来回弧线。后对相容关系图，不画自回路，并用单线代替来回弧线。另外由于相容关系是自反和对称的，因此企管系矩阵的对角另外由于相容关系是自反和对称的，因此企管系矩阵的对角线元素都是线元素都是1，且矩阵是对称的。为此我们可以讲矩阵用梯形表，且矩阵是对称的。为此我们可以讲矩阵用梯形表示。示。简化图和简化矩阵简化图和简化矩阵1.图的简化：图的简化：不画环；不画环；两条对称边用一条无向直线代替。两条对称边用一条无向直线代替。2.矩阵矩阵的简化：因为的简化：因为r的矩阵是对称阵且主对角线全是的矩阵是对称阵且主对角线全是1，用下，用下三角矩阵三角矩阵(不含主对角线不含主对角线)代替代替r的矩阵。的矩阵。【example】令令x1=fly,x2=any,x3=able,x4=key,x5=book,x6=pump,x7=fit,X=x1,x2,x3,x4,x5,x6,x7,r的简化图为：的简化图为：x2x1x3x5x4x7x6x21x6x1x2x3x4x5x7x6x5x4x31111111 100000 0 00 0 0002.相容类相容类及最大相容类及最大相容类 a）相容类相容类定义定义：设：设r是集合是集合X上的相容关系上的相容关系,C X,如果对于如果对于C中任意元素中任意元素 x,y有有 r,称称C是是r的一个相容类。的一个相容类。上例中上例中x1,x2,x3,x4,x1,x2,x3,x2,x3,x4,x1,x2,x4,x3,x4,x5,x1,x3,x4,x1,x2,x3,x4,x1,x7,x6 都是都是相容类。上述相容类中，有些相容类间有真包含关系。相容类。上述相容类中，有些相容类间有真包含关系。b）最大相容类）最大相容类定义：定义：设设r是集合是集合X上的相容关系，上的相容关系，C是是r的一个相容类，如果的一个相容类，如果C 不能被其它不能被其它相容类所真包含，则称相容类所真包含，则称C是一个是一个最大相容类。最大相容类。也可以说，也可以说，C是一个相容类，是一个相容类，如果如果C中加入任意一个新元素中加入任意一个新元素，就不再是相容类，就不再是相容类，C就是一个就是一个最大相容类。最大相容类。x1,x2,x3,x4,x3,x4,x5,x1,x7,x6都是都是最大相容类。最大相容类。从简化图找最大相容类：从简化图找最大相容类：-找最大完全多边形。找最大完全多边形。即：含有结点最多的多边形中，每个结点都与其它结点相联结即：含有结点最多的多边形中，每个结点都与其它结点相联结.在相容关系简化图中，在相容关系简化图中，每个最大完全多边形的结点集每个最大完全多边形的结点集合构成一个最大相容类。合构成一个最大相容类。上例中最大相容类上例中最大相容类 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x3 3,x,x4 4,x,x5 5,x,x1 1,x,x7 7,xx6 6 分别对应最大完全四、三、一、零边形。分别对应最大完全四、三、一、零边形。给定给定X上相容关系上相容关系r,如图所示如图所示,r的最大相容类：的最大相容类：x1,x2,x5,x2,x3,x5,x3,x4,x5,x1,x4,x5,x1x2x3x4x53.完全覆盖：完全覆盖：定义：定义：r是中的相容关系，由是中的相容关系，由r的所有的所有最大相容类为元素构成的最大相容类为元素构成的 集合，称之为集合，称之为X的完全覆盖。记作的完全覆盖。记作Cr(X)。Cr(X)=x1,x2,x3,x4,x3,x4,x5,x1,x7,x6 Cr(X)=x1,x2,x5,x2,x3,x5,x3,x4,x5,x1,x4,x5【练习练习】1.下面是所有人集合上的关系，其中哪些是等价关系？确定一个下面是所有人集合上的关系，其中哪些是等价关系？确定一个等价关系的性质，这些性质是其他关系所欠缺的。等价关系的性质，这些性质是其他关系所欠缺的。a）（a，b）|a与与b有相同的年龄有相同的年龄 b）（a，b）|a与与b有相同的父母有相同的父母 c）（a，b）|a与与b有一个相同的父亲或者一个相同的母亲有一个相同的父亲或者一个相同的母亲 d）（a，b）|a与与b相识相识 e）（a，b）|a与与b说同一种语言说同一种语言solution：a）是等价关系。是等价关系。b）是等价关系。是等价关系。c）不是等价关系。因它不具有传递性。举例说明，假如不是等价关系。因它不具有传递性。举例说明，假如A是是W和和Y的孩子，的孩子，B是是X和和Y的孩子，的孩子，C是是Y和和Z的孩子。因此的孩子。因此A和和B有关，有关，B和和C有关，但是不能得出有关，但是不能得出A和和C是有关的结论。是有关的结论。d）等价关系。等价关系。e）不是等价关系。不满足传递性。不是等价关系。不满足传递性。2.在以下三题中确定具有所示有向图的关系是否为等价关系。在以下三题中确定具有所示有向图的关系是否为等价关系。Solution：1.我们需要考虑该题中的关系是否具有自反性、对称性、传递我们需要考虑该题中的关系是否具有自反性、对称性、传递性。从图中可以看出该题不满足传递性，缺少了边性。从图中可以看出该题不满足传递性，缺少了边(c,d)和和 (d,c)。2.该题中的关系是等价关系，等价类是该题中的关系是等价关系，等价类是a，d，b，c。3.该题不是等价关系。该题不是等价关系。3.确定由下面的确定由下面的0-1矩阵表示的关系是否为等价关系。矩阵表示的关系是否为等价关系。Solution：a)不是等价关系，不满足对称性。不是等价关系，不满足对称性。b）是等价关系。由第一和第三元素构成一个等价类，第二和是等价关系。由第一和第三元素构成一个等价类，第二和第四元素钩沉另一个等价类。第四元素钩沉另一个等价类。c）是等价关系。第一、第二和第三个元素构成一个等价类，第是等价关系。第一、第二和第三个元素构成一个等价类，第四元素构成另一个等价类。四元素构成另一个等价类。4.当当m是下面的整数时，是下面的整数时，4m的同余类是什么？的同余类是什么？a）2 b）3 c）6 d）85.描述每一个模描述每一个模6同余类。同余类。4.Solution：a）4+2n|n Z=,-2,0,2,4,b）4+3n|n Z=,-2,1,3,5,c）4+6n|n Z=,-2,4,10,16,d）4+8n|n Z=,-4,4,12,20,5.Solution：06=,-12,-6,0,6,12,16=,-11,-5,1,7,13,26=,-10,-4,2,8,14,36=,-9,-3,3,9,15,46=,-8,-2,4,10,16,56=,-7,-1,5,11,17,6.下面哪些子集族是下面哪些子集族是-3，-2，-1，0，1，2，3的划分？的划分？Solution:a）是子集族是子集族-3，-2，-1，0，1，2，3的划分。的划分。b）不是子集族的划分。不是子集族的划分。c）是子集族的划分。是子集族的划分。d）不是子集族的划分。不是子集族的划分。7.列出由列出由a,b,c,d,e,f,g的划分产生的等价关系中的有序对。的划分产生的等价关系中的有序对。Solution：a）(a,a),(a,b),(b,a),(b,b),(c,c),(c,d),(d,c),(d,d),(e,e),(e,f),(e,g),(f,e),(f,f),(f,g),(g,e),(g,f),(g,g)b)(a,a),(b,b),(c,c),(c,d),(d,c),(d,d),(e,e),(e,f),(f,e),(f,f),(g,g)c)(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,a),(c,b),(d,a),(d,b),(d,c),(d,d),(e,e),(e,f),(e,g),(f,e),(f,f),(f,g),(g,e),(g,f),(g,g)d)(a,a),(a,c),(a,e),(a,g),(c,a),(c,c),(c,e),(c,g),(e,a),(e,c),(e,e),(e,g),(g,a),(g,c),(g,e),(g,g),(b,b),(b,d),(d,b),(d,d),(f,f)本节内容到此结束本节内容到此结束