《应用离散数学》方景龙版3.4等价关系与划分

1、3.4等价关系与划分习题3.4对于给定的集合A和其上的二元关系R,判断R是否为等价关系。a为实数集，Vx，yA，xRyx-y,2。A，1，2，3，Vx，yA，xRyx+y3A，Z+，即正整数集，Vx，yA，xRy小是奇数。A,P(X)，集合%的基数1X|2，Vx，yA，xRyx匸yvy匸xA,P(X)，集合X和c满足C匸X，Vx，yA，xRyxy匸C。解略设A，a，bc,d，对于A上的等价关系R，,vb，a,vc，d,vd，cIA画出R的关系图，并求出A中各元素关于R的等价类。解R的关系图如下：A中各元素关于R的等价类分别为：a，b，a,b,c，d，c,d考虑单词的集合W,sheet，gt,s

2、ky,was%,wind,sit。R和R2分别是由“具有同样多的字母和“具有相同的开头字母”定义的等价关系。求由R1和R2确定的商集W/R和W/R。解略给出模6同余关系，并求出所有的模6同余类。解模6同余关系R，1a,bZaa三b(mod6)所有的模6同余类为：i，5z+iIzZ,i，0,1，,5即0，20,15,10,5,0,5,10,15,20,1，,19,14,9,4,1,6,11,16,21,2二,18,13,8,3,2,7,12,17,22,二,17,12,7,2,3,&13,1&23,二-,16,11,-6,-1,4,9,14,19,24,5设A,3,4,4,6,判断(1)Rxx,

3、lx,x,eAxy-xy121212121221(2)Rx1x,y,21y2lx,1x,eAx1y1xy22下列关系是否等价关系，若是等价关系，试给出它的等价类。解略6.假如R和S是集合A上的等价关系,证明,不是的举出反例。(1)RUS(3)Rc问下面的关系是否一定是等价关系,是的给予(5)R。S(2)R，S(4)RS(6)R1解(1)、(2)、(3)、(4)略R。S不一定是等价关系，例如：取集合A二a,b，c及其上的等价关系R-,c,c,S,c,c,有R。S-,c,c,它不是对称的，从而不是等价关系。R-1一定是等价关系，证明如下：VxwA,因为R是自反的，所以x,x,GR,从而eR1,即R

4、-1是自反的;veR1,有y,x,wR,因为R是对称的，所以eR1,即R-1是对称的；v,eR1,有,z,y,wR,因为R是传递的，所以z,x,wR,从而eR1,即R-1是传递的；综上所述，若R是集合A上的等价关系，则R-1一定是等价关系。当我们构造一个关系的自反闭包的对称闭包的传递闭包时一定得到一个等价关系吗？是的请证明不是的请举出反例。解略假如R1和R2是集合A上的等价关系，兀1和兀2分别是对应于R1和R2的划分。证明R1R2当且仅当兀i是兀2的加细。（如果在划分兀1中的每个集合都是划分兀2中某个集合的子集，则兀1叫做兀2的加细）证明（1）由RiR2推出兀1是兀2的加细，这就是要证明对于兀1中的任何集合Ai，在兀2中都存在集合A2，使得A1A2。因为兀1中的任何集合A1是A中的某个元素a关于等价关系R1的等价类，即Aabla,b,eRR11现构造Aabla,b,eRR22它是A中元素a关于等价关系R2的等价类，从而是兀2中的一个集合。又由于R1R2，所以有A1A2。（2）由兀1是兀2的加细推出R1R2，这就是要证明如果对于兀1中的任何集合A1，在兀2中都存在集合A2，使得A1A2，那么R1R2。VR1，有RbR，所以在兀1中存在集合A1厂bR，使得a,beA1