自考--离散数学教材课后题第三章答案

1、精选优质文档-倾情为你奉上3.1 习题参考答案1、写出下列集合的的表示式。a)所有一元一次方程的解组成的集合。A=x|x是所有一元一次方程的解组成的集合晓津答案：A=x| ax+b=0aRbRb) x2-1 在实数域中的因式集。B=1,(x-1),(x+1)|xRc)直角坐标系中，单位圆内（不包括单位圆周）的点集。C=x,y| x2+y2<1 晓津答案：C=a(x,y)|a为直角坐标系中一点且 x2+y2<1 d)极坐标中，单位圆外（不包括单位圆周）的点集。D=r,| r>1,0<=<=360晓津答案：D=a(r,)|a为极坐标系中一点且 r>1,0<

2、=<=2 e)能被5整除的整数集E= x| x mod 5=0-2、判定下列各题的正确与错误。a) xx;正确b) xx;正确晓津观点:本命题错误。理由：x作为一个元素是一个集合，而右边集合中的元素并不是集合。c) xx,x;正确d) xx,x;正确-3、设 A=1,2,4,B=1,3,2,指出下列各式是否成立。a) 2A; b) 2Bc) 2Ad) 2B; e) Af)A解：jhju、晓津和wwbnb 的答案经过综合补充，本题的正确答案是：b、c、d、f成立，a，d、e不成立。理由：a式中，2是一个集合，而在A中并无这样的元素。因此不能说2属于A，当然如果说2A则是正确的。对于e式也应

3、作如此理解，空集是一个集合，在A中并无这个集合元素,如f式则是正确的。空集包含于任何集合中，但空集不一定属于任一集合。-4、设A= ， B=(A),问下列各题是否正确。a)B,B正确b) B,B正确c) B,B正确-5、设A=a,a,问下列各题是否正确。a) a(A),a(A);正确晓津答案：本命题不正确。(A)=，a,a,a,a,在这个集合中，并无a这个元素，因此命题的后半个a(A)是不成立的。b) a(A),a(A);正确c) 设A=a,b,a),b) 是否正确。a 和 b都正确晓津答案：如此则a),b)均不正确。此时,(A)=，a,b,a,b。除了a式的前半句正确，其他的都不成立，因此a

4、),b)式均不成立。-6、设某集合有101个元素，试问：a) 可构成多少个子集；2n个元素 (子集吧)b) 其中有多少个子集元素为奇数；其中有 2n-1 个子集元素为奇数晓津不同意见：我认为这个答案不成立,如集合有3个元素，则它的幂集中有5个子集中元素个数为奇数，而不是7个。可是我也还没找到这个式子。sphinx提供的答案是2100 ，可通过多项式分解找到规律，空集不算。晓津想，应该算上，若算上则是2n-1+1c) 是否有102个元素的子集。无3.2习题答案1、给定自然数集合N的下列子集：A=1,2,7,8 B=i|i2<50=0,1,2,3,4,5,6,7C=i|i可被3整除 0i30

5、, =0,3,6,9,12,15,18,21,24,27,30D=i|i=2K,KZ+,1K6=2,4,8,16,32,64求下列各集合。a) A(B(CD);=2,4,8,16,32,64,0,3,6,9,12,15,18,21,24,27,30,1,5,7b) A(B(CD);=A(B=c) B-(AC);=B-0,1,2,7,8,3,6,9,12,15,18,21,24,27,30=4,5d) (AB)D=8D=2,4,8,16,32,64晓津补充:这里的(AB)应当等于(B-A)而不是(A-B), 所以最终的答案是：0,3,4,5,6D=0,2,3,4,5,6,8,16,32,64-2

6、、a)如果对于一切集合，有XY=X，则Y=证明： XY=i|iXiY=Xi|iXiY=Xi|iXiY=i|iX由此可见：Y=晓津的证明：必要性：设Y 则Y中必有一个以上元素。若有一个元素y,yYyX 则有XYX 这与前提矛盾。充分性： 若Y= 则任合集合XY=X成立。本题要注意Y有时包含于X的，若用命题表达式论证，应用到量词。b)证明对所有集合A，B和C，有：(AB)C=A(BC); iffCA。 (AB)C=i|(iAiB)iCA(BC)=i|iA(iBiC) (iAiB)iC = iA(iBiC)因为 iffCA所以 iAiC=iA得证：(AB)C=A(BC)晓津证明：本题也要进行双向的证

7、明，一个是必要性，一个是充分性，这才能得出当需的结论。证：充分性：若C A则(AB)C=(AC)(BC)=A(BC)=右边。必要性：假设C不包含于A内，则C中必有一个以上元素xA，则ACA可得 (AB)C=(AC)(BC)A(BC)假设与前提矛盾，因此假设不成立，C应当包含于A内。-3、证明对任意集合A，B，C，有：a) (A-B)-C=A-(BC);证明： (A-B)-C=x| xAxB-C=x| xAxBxC=x| xAxBxC=x| xAx(BC)=x| xAx(BC)=A-(BC)我想，本题也可以直接应用集合运算来做。b) (A-B)-C=(A-C)-B;(A-B)-C=x| x(A-

8、B)-C)=x| xAxBxC=x| x(A-C)xB=(A-C)-Bc) (A-B)-C=(A-C)-(B-C)(A-B)-C=x| x(A-B)-C)=x| xAxBxC=x| xAxBxBxC=x| x(A-B)xBxC=x| x(A-B)xBxC=x| x(A-B)x(BC)=x| x(A-B)x(BC)=x| x(A-B)x(BC)(A-C)-(BC) (题目是否有误？)晓津证明：(题目并无误)右边=(A-C)-(B-C)=(AC)(BC)=(AC)(BC)=(ACB)(ACC)=(AB)C)=(A-B)-C=左边-4、设A，B，C是全集E的任意子集。a)若 AB=AC,AB=AC,

9、证明：B=C晓津证明此题如下:证明：由 AB=AC,AB=AC得(AB)(AB)=(AC)(AC)(AB)(AB)=(AC)(AC)B(AA)=A(CC)即BE=CE因B，C是全集E的任意子集B=C本题的答案感谢kavana提供意见。-b)若 (AC)(BC),(AC)(BC),证明：AB由(AC)(BC),(AC)(BC) 得：(AC)(AC)(BC)(BC)A(CC)B(CC)AEBEA，B，C是全集E的任意子集AB-5、设 A=,B=(A),问下列各题是否正确？a) B B正确b) B B正确c) B B正确本题由kavana补充： (A)=, B=(A)=, 。 感谢kavana！-6

10、、在下面各题中，如果命题为真，请给证明；如果命题为假，则给出反例；a)、 A(B-C)=(AB)-(AC)晓津证明如下：A(B-C)=x|xA(xBxC)=x|xAxB(xAxC)=x|xAxB(xAx(AC)=x|xAxBx(AC)=(AB)-(AC)b)、 (A-B)(B-A)=(A-B)(B-A)=x| xAxBxAxB=也可以用集合运算证明：原式=(AB)(BA)=(AA)(BB)=c)、 A-(BC)=(A-B)C不成立补充实例如下：设A=1,2,3,4 B=1,5 C=2,6则 A-(BC)=3,4 而 (A-B)C=2,3,4,6d)、 (A-B)=(B-A)不成立补充实例：设E

11、=1,2,3,4,5 A=1,2 B=1,3,4则 (A-B)=1,3,4,5 而 (B-A)=1,2,5e) (AB)A不成立补充实例如下:设E=1,2,3 A=1,2 B=2,3则 (AB)=1,3 它不包含于A内。f) (AB)(B-A)=A不成立补充实例如下： A=1,2 B=1,2,3,4则(AB)(B-A)=1,2,3,4 A-7、设A，B，C是任意集，证明：a) (AB)-C=(A-C)(B-C)证明：(AB)-C=x| (xAxB)xC=x|(xAxC)(xAxC)=(A-C)(B-C)b) A-(BC)=(A-B)(A-C)证明:A-(BC)=x| xAx(BC)=x| xA

12、(xBxC)=x| xAxBxAxC)=(A-B)(A-C)c)、(A-B)(A-C)=A,当需 A(BC)=时成立。证明:(A-B)(A-C)=x| (xAxB)(xAxC)=x| xA(xBxC)=x| xAx(BC)我怎么觉得：A(BC)=时，(A-B)(A-C)=A题目是否出错了？晓津认为：红色的其实应为，xB或xC 应用德摩根律，就是说x(BC).以上证明并未证得结论。现证明如下：充分性：若A(BC)=则前提的左边=(AB)(AC)=A(BC)=A(BC)=A-(BC)=A-(BC)=A-(A(BC)=A-=A=右边可得等式成立必要性：若设A(BC)则由上面证明可知A-(BC)A。即

13、前提左边A左右不等，因此假设违反题意，不成立。所以必需A(BC)=-8、证明：a)、 A(BC)=(AB)(AC)?晓津证明如下：右边=(AB)(AC) (AB)(AC)=(A(BC)(A(BC)=(A(BC)(A(BC)=(A(BC)A)(A(BC)(BC)=(A(BC)(BC)=A(BC)=左边证毕 我想，有时候从右边化到左边会更简便些吧。b)、 A(BC)=(AB)(AC)，不一定成立。?晓津证明如下:设有集合A=1,2,3 B=4,5 C=5,6则A(BC)=1,2,3,4,6 且 (AB)(AC)=1,2,3,4,6 左右相等。等式成立。又设有集合A=1,2,3,5 B=4,5 C=

14、5,6则则A(BC)=1,2,3,4,5,6 而 (AB)(AC)=1,2,3,4,6 左右不等，因此证得原式不一定成立。3.3 习题答案1、设A=0,1,B=1,2,确定下面集合。a) A×1×B= <0,1>,<1,1>×1,2=<<0,1>,1>,<<1,1>,1>,<<0,1>,2>,<<0,1>,2>b) A2×B=<0,1>,<0,2>,<1,1>,<1,2>×1,2

15、=<<0,1>,1>,<<0,1>,2>,<<0,2>,1>,<<0,2>,2>,<<1,1>,1>,<<1,1>,2>,<<1,2>,1>,<<1,2>,2>c) (A×B)2=<0,1>,<0,2>,<1,1>,<1,2>2=<<0,1>,<0,1>>,<<0,1>,<0,2>&

16、gt;,<<0,1>,<1,1>>,<<0,1>,<1,2>>, <<0,2>,<0,1>>,<<0,2>,<0,2>>,<<0,2>,<1,1>>,<<0,2>,<1,2>>, <<1,1>,<0,1>>,<<1,1>,<0,2>>,<<1,1>,<1,1>>,<&l

17、t;1,1>,<1,2>>, <<1,2>,<0,1>>,<<1,2>,<0,2>>,<<1,2>,<1,1>>,<<1,2>,<1,2>>晓津叹气，呵呵，这道题本是(B×A)2，答案就不一样了。大家做题的时候也要注意仔细看题目呀。-2、下列各式中哪些成立？哪些不成立？为什么？a) (AB)×(CD)=(A×C)(B×D)不成立，因为笛卡尔积中。在左半式中，x的成分在A与B两个集合中，而右

18、半式中，x的成分在A与C两个集合中。b) (A-B)×(C-D)=(A×C)-(B×D)不成立，比如设A与B中都含有含有元素 a 。在左半式中，a是不会出现在 x 中。假设 (A×C)出现(a,b),(a,e),而(B×D)出现了(a,b),(a,d)，那么(a,e)将被保留下来，从而 左半式 不等于 右半式。c) (AB)×(CD)=(A×C)(B×D)不成立。因为左半式 x不可能含有 AB的成分，而在右半式 x 就包含有AB的成分。d) (A-B)×C=(A×C)-(B×C)成立，

19、因为左半式 x 不会出现B的成分，而右半式中 x 包含有 B的成分，也会被过滤掉的。e) (AB)×C=(A×C)(B×C)成立。左半式中 x 不会出现 AB 的成分，而右半式中AB也会被过滤掉的。晓津道：这几个判断都是对的，只是证明过程好象有点生活化，不够科学，哪位朋友来做做?:)下面是ryz同学给出的证明:(晓津有所补充)d)证明：(1)设任意的x，y(AB)×Cx(AB)yCxAxByC(xAyC)xByCx，y(A×C)x，y(B×C)x，y(A×C)(B×C)；(AB)×C(A×C)(

20、B×C)(2)设任意的x，y(A×C)(B×C)；则x，y(A×C)x，y(B×C)xAyC(xByC)xA(yCxB)(yCyC)xAyCxB(xAxB)yCx(AB)yCx，y(AB)×C(A×C)(B×C)(AB)×C(AB)×C=(A×C)(B×C)e)(AB)×C(AB)(BA)×C(AB)×C)(BA)×C)(A×CB×C)(B×CA×C)(A×C)(B×C)注：e

21、)是利用d)的结果来证明的-3、证明若 X×Y=X×Z,且 X，则 Y=Z证明： X×Y=<x,y>| xX,yYX×Z=<x,z>| xX,zY如果 X= 那么 X×Y= X×Z=因为 X，所以 Y=Z-4、设 X=0,1,2,3,4,5,6,上关系为 R=<x,y> (x<y)(x是质数),写出R各元素，并求出 domR,ranR及FLDR。解： 议论一下R=<x,y> (x<y)(x是质数) ,我认为应改为。不然的话(x是质数)这个条件将不起作用。R=<0,1&g

22、t;,<0,2>,<0,3>,<0,4>,<0,5>,<0,6>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,3>,<2,4>,<2,5>,<2,6>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,6>,晓津补充：若按jhju的讨论来做，应把红色三行去掉，0和1、4都不是质数,相应的，在下面的答案里，也应把红色字去掉

23、。domR= 0,1,2,3,4,5ranR= 1,2,3,4,5,6FLDR= 0,1,2,3,4,5,6-5. 设 P=<1,2>,<2,4>,<3,3>Q=<1,3>,<2,4>,<4,2>求出 PQ，PQ,domP,domQ,ranP,ranQ,dom(PQ),ran(PQ)解： PQ=<1,2>,<1,3>,<2,4>,<3,3>,<4,2>PQ=<2,4>domP=1,2,3domQ=1,2,4ranP=2,4,3ranQ=2,4,3dom

24、(PQ)=2ran(PQ)=4-6、设 A=1,2,3,4,定义A上二元关系R：<a,b>R,iff(a-b)/2是整数，称R为模2同余系，亦可称<a,b>R,iffab(mod2),求出R的序偶表达式， domR，ranR.解：R=<4,2>,<3,1>,<2,4>,<1,3>domR=4,3,2,1ranR=2,1,4,3黄色字是晓津所补充。-7、设A=1,2,3,4,5,6,7,8,9,10 R=<x,y> | x,yAx是y的因子x<=5,求 domR,ranR解： R=<1,1>,&

25、lt;1,2>,<1,3>,<1,4>,<1,5>，<1，6><1，7>，<1，8>，<1，9>，<1，10>，<2,2><2,4>,<2,6>,<2,8>,<2,10>,<3,3>,<3,6>,<3,9>,<4,4>,<4,8>,<5,5>,<5,10> domR=1,2,3,4,5ranR=1,2,3,4,5,6,7,8,9,10本题答案由spin

26、x补充纠正，特此感谢。3.4节习题答案1、给定A=1,2,3,4,考虑A上的关系R,若R=<1,3>,<1,4>,<2,3>,<2,4>,<3,4>, a) 在A×A的坐标图上标出R，并给出关系图。 b) R是自反的？对称的？可传递的?反对称吗？解：我以表格形式表示坐标：4×××××3211234关系图如下：由图中可见，R不是自反的，不是对称的，是可传递的，是反对称的。2、举出A=1,2,3上关系R的例子，使它有下列性质。 a) 既是对称的又是反对称的。 b) R既不是对称的

27、，又不是反对称的；c) R是可传递的。解：a)R=<1,1>b)R=<1,3>,<2,3>,<3,1>c)R=<1,2>,<2,3>,<1,3>3) 说明下列关系是否是自反的，对称的，传递的或反对称的。 a) 在 1,2,3,4,5上定义的关系。 <a,b>| a-b 是偶数。 b) 在 1,2,3,4,5上定义的关系。 <a,b> | a+b 是偶数 。 c)在所有人集合P上的关系， <a,b> | a,b 是同一祖先 解：a)先列出其关系集合如下：R=<1,1>

28、;，<1，3>,<1,5>,<2,2>,<2,4>,<3,3>,<3,5>,<3,1>,<4,4>,<4,2>,<5,5>,<5,3>,<5,1>由此可看出：A上关系R为自反的，对称的，传递的但不是反对称的。b)仍列出其关系集合：我们发现它和上面的集合是一样的：R=<1,1>，<1，3>,<1,5>,<2,2>,<2,4>,<3,3>,<3,5>,<3,1>

29、,<4,4>,<4,2>,<5,5>,<5,3>,<5,1>可知：A上关系R也是自反的，对称的，传递的但不是反对称的。c)这个集合不便列举，就拿一个家庭来举例吧，家里有5个人，老爸x,老妈y,哥哥z,姐姐u,我v,则列出R=<x,x>,<y,y>,<z,z>,<u,u>,<v,v><z,u>,<u,z>,<u,v>,<v,u>,<z,v>,<v,z>(这里我考虑老爸老妈应该不会同是一个祖先的。推广到所有人

30、，也能得出结论,这个关系是自反的，对称的，传递的但不是反对称的。4、如果关系R和S是自反的、对称的和可传递的，证明 RS也是自反的、对称和可传递的。证明：设有任意x,y,有<x,y>R 且<x,y>S因为R是自反的,则有<x,x>,<y,y>R,又因为S是自反的，则有<x,x>,<y,y>S 所以<x,x>,<y,y>(RS) 即RS是自反的。因为 R和S都是对称的，则有<y,x>R且<y,x>S因此 <y,x>RS即RS是对称的。再设有任意z,因为R是可传递的，

31、则当xRy且yRz时必有xRz,同样当xSy且ySz时必有xSz,即有：<x,y>,<y,z>，<x,z>RS所以RS是可传递的。5、设S=<a,b>|对任一C有<a,c>R,<c,b>R,其中R是二元关系，证明若R是自反、对称和传递的，则S也是自反的、对称和传递的。证明：因为对于任一c有<a,c>R且<c,b>R，若R是自反的，则有<a,a>,<b,b>,<c,c>R因为<a,b>S即有<a,a>，<b,b>S，因此S是自反的

32、。若R是对称的和传递的，则由<a,c>R,<c,b>R必有<a,b>R，同时有<c,a>，<b,c>R则必有<b,a>R 所以S是对称的，也是传递的。6、设Z是整数集 R=<x,y)| xy(mod.K),证明 R是自反、对称和传递的。证明：设任意a,b,cZ，因为a-a=K·0,即aa(mod K)成立<a,a>R，故R是自反的。设a-b=Kt(t为整数)，则b-a=-Kt所以ba(mod K)成立，<b,a>R,故R是对称的。若<a,b>R且<b,c>R，

33、即ab(mod K) 且bc(mod K) a-b=Kt b-c=Ks( t,s 为整数)则 a-c=Kt+Ks=K(t+s)所以ac(mod K) 即<a,c>R，故R是传递的。7、设R是集合X上的一个自反关系。求证R是对称和传递的，当且仅当<a,b>,<a,c>在R中，且有<b,c>在R中。 证明：充分性：设任意a,b,cX，因为R是自反关系，则<a,a>,<b,b>,<c,c>R，当有<a,b>,<a,c>,<b,c>R时.我发现充分性无法证明。必要性：要使R为对称的，

34、则对任意a,bX，必须有<a,b>,<b,a>R，要使R为传递的，对任意a,b,cX 若有<a,b>,<b,c>R 必要有<a,c>R，所以应有<a,b>,<b,a>,<a,c>,<b,c>在R中。(实际上对于此题，少给出一个<b,a>或<c,a>或<c,b>在R中的条件，故导致充分性不足。所以 此题我没能证出来。 3.5习题答案1、设： A=1,2,3上关系R=<x,y> | xy，试求： R-1, R 解： R=<1,1>,

35、<1,2>,<1,3>,(2,2>,<2,3>,<3,3> R-1=<1,1>,<2,1>,<3,1>,<2,2>,<3,2>,<3,3> R=<2,1>,<3,1>,<3,2> 2、设： A=0,1,2,B=0,2,4的关系为： R=<a,b>|a,bAB 求：R-1,并求MR-1 解： R=<0,0>,<0,2>,<2,2>,<2,0> R-1=<0,0>,&

36、lt;2,0>,<2,2>,<0,2> Mr-1=  | 0 0 1 | | 1 1 1 | | 0 0 1 | 应为：Mr-1=| 1 1 0 | | 1 1 0 | | 0 0 0 | 3、集合 A=a,b,c上关系R的关系图下图所示，求 r(R),s(R),t(R)，并分别画出各闭包的图形。 R=<a,a>,<a,b> r(R)=<a,a>,<a,b>,<b,b>,<c,c> s(R)=<a,a>,<a,b>,<b,a> 为了求：t(R) M

37、R=| 1 1 0 | 0 0 0 | | 0 0 0 | MR2=| 1 1 0 | 0 0 0 | 0 0 0 |。| 1 1 0 | | 0 0 0 | | 0 0 0 | =| 1 1 0 | | 0 0 0 | | 0 0 0 |   MR3=| 1 1 0 | | 0 0 0 | | 0 0 0 |   可见： t(R)=MR MR2MR3=<a,a>,<a,b> 4、设 A=1,2,3,4上的二元关系， R=<1,2>,<2,4>,<3,3>,<1,3>，则： r(R)

38、=<1,1>,<2,2>,<4,4>,<1,2>,<2,4>,<3,3>,<1,3> S(R)=<1,2>,<2,4>,<3,3>,<1,3>,<2,1>,<4,2>,<3,1> t(R)= MR=| 0 1 1 0 | | 0 0 0 1 | =<1,2>,<2,4>,<3,3>,<1,3> | 0 0 1 0 | | 0 0 0 0 | MR2=| 0 1 1 0 | | 0

39、1 1 0 | 0 0 1 1 | | 0 0 0 1 | | 0 0 0 1 | =| 0 0 0 0 | | 0 0 1 0 | 。| 0 0 1 0 | 0 0 1 0 | | 0 0 0 0 | | 0 0 0 0 | 0 0 0 0 | =<1,3>,<1,4>,<3,3> MR3=| 0 0 1 1 | | 0 1 1 0 | 0 0 1 0 | | 0 0 0 0 | | 0 0 0 1 | =| 0 0 0 0 | | 0 0 1 0 | 。| 0 0 1 0 | 0 0 1 0 | | 0 0 0 0 | | 0 0 0 0 | 0 0 0

40、 0 |=<1,3>,<3,3> MR4=| 0 0 1 0 | | 0 1 1 0 | 0 0 1 0 | | 0 0 0 0 | | 0 0 0 1 | =| 0 0 0 0 | | 0 0 1 0 | 。| 0 0 1 0 | 0 0 1 0 | | 0 0 0 0 | | 0 0 0 0 | 0 0 0 0 |=<1,3>,<3,3> 可得t(R)=<1,2>,<2,4>,<3,3>,<1,3><1,3>,<1,4>,<3,3><1,3>,&l

41、t;3,3><1,3>,<3,3> =<1,2>,<1,4>,<2,4>,<3,3>,<1,3> 3.6习题答案1、给定集合X=x1,x2,.,x6,是X上相容关系且M简化矩阵为： 试求X的覆盖，并画出相容关系图。 解：覆盖如下： <x2,x1>,<x1,x2>,<x3,x1>,<x1,x3>,<x3,x2>,<x2,x3>,<x4,x3><x5,x2>,<x2,x5>,<x5,x3>,

42、<x3,x5>,<x5,x4> ,<x4,x5>,<x6,x1>,<x1,x6>,<x6,x3>,<x3,x6>,<x6,x5>,<x5,x6> 晓津觉得覆盖中的元素应该是集合：我的答案是：S=x1,x2,x3,x4,x5,x6 当然这只是一个覆盖。 2、从下面给出的关系图中，说明哪个是相容关系。 答：图3、4是相容关系。 3、设集合A=1,2,3,4中的一个覆盖为 B=1,2,2,3,4,求出确定的相容关系。 解： S1=1,2 S2=2,3,4 根据定理3.6.1：=S1×

43、S1S2×S2 =<1,1>,<1,2>,<2,1>,<2,2><2,2>,<2,3>,<2,4>,<3,2>,<3,4>,<3,3>,<4,2>,<4,3>,<4,4> =<1,1>,<1,2>,<2,1>,<2,2>,<2,3>,<2,4>,<3,2>,<3,4>,<3,3>,<4,2>,<4,3>

44、;,<4,4> 4、设是A上相容关系， a) 复合关系。是A上的相容关系吗？ 由于自反性通过,运算可保持;但对称性不能通过,保持。所以复合关系。不是A上的相容关系 b) 是A上相容关系吗？ 是的 晓津补充证明如下:(1)因为，是A上相容关系，若有任意xA，则<x,x>且<x,x>，所以<x,x>因此是自反的。(2)因为，是A上的相容关系，若有任意x,yA且<x,y> 则有<y,x>；若有任意u,vA且<u,v>，则有<v,u>，所以有<x,y>，<y,x>,<u,v&g

45、t;,<v,u>因此是对称的。可得是A上相容关系。c) 是A上相容关系吗？ 是的 晓津证明如下：(1)因为，是A上相容关系，则若有任意xA,就有<x,x>，因此是自反的。(2)因为，是A上相容关系，则若有任意x,yA且<x,y>且<x,y>则有<y,x>且<y,x>即<x,y>,<y,x>因此是对称的。可得是A上相容关系。 5、设R、Q都是集合A上自反、对称、传递关系，则 s(RQ)=_，t(RQ)=_.因为_也是自反、对称、传递的。 s(R)s(Q) t(R)t(Q) RQ 6、集合 A=1,2,

46、3,4,5,6的关系图如下所示，求： a) R,R2，R3及关系图 解： R=<1,3>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4> MR2= | 0 0 1 0 1 0 | | 0 0 1 0 1 0 | | 0 0 1 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 0 1 0 0 | | 0 0 1 0 0 0 | | 0 0 1 0 0 0 | = | 0 0 1 0 0 0 | | 0 0 0 0 1 0 | 。| 0 0 0 0 1 0 | | 0 0

47、 0 1 0 0 | | 0 0 0 1 0 0 | | 0 0 0 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | R2=<1,3>,<1,4>,<2,4>,<3,3>,<4,4>,<5,5> MR3=| 0 0 1 1 0 0 | | 0 0 1 0 1 0 | 0 0 0 1 1 0 | | 0 0 0 1 0 0 | | 0 0 0 0 1 0 | 0 0 0 0 1 0 | | 0 0 1 0 0 0 | 。| 0 0

48、 1 0 0 0 | =| 0 0 1 0 0 0 | | 0 0 0 1 0 0 | | 0 0 0 0 1 0 | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 0 1 0 0 | 0 0 0 1 0 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | 0 0 0 0 0 0 | R3=<1,4>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4> b) r(R),s(R); r(R)=<1,3>,<1,5>,<2,5>,<

49、3,3>,<4,5>,<5,4>,<1,1>,<2,2>,<4,4>,<5,5>,<6,6> s(R)=<1,3>,<3,1>,<1,5>,<5,1>,<2,5>,<5,2>,<4,5>,<5,4> 7、令S为从X到Y的关系，T为从Y到Z的关系，对于 AX，定义S(A)=y|<x,y>SxA 证明： a) S(A)Y b) (S。T)(A)=T(S(A); c) S(AB)=S(A)S(B),其中B

50、X d) S(AB)S(A)S(B) 对这道题我不能理解题目的意思，S(A)是指什么?请学友们帮助解释一下：) 8、设： R1和R2是A上的关系，证明： a) r(R1R2)=r(R1)r(R2); 证明如下：因为R1，R2是A上关系，所以R1R2也是A上关系；由r(R1)=R1IA 和r(R2)=R2IA可得r(R1)r(R2)= R1R2IA又因r(R1R2)=(R1R2)IA所以左右相等。 b) s(R1R2)=s(R1)s(R2); 证明如下：左边=s(R1R2)=(R1R2)(R1R2)-1右边=s(R1)s(R2)=R1R1-1R2R2-1=R1R2R1-1R2-1=(R1R2)(

51、R1R2)-1=左边等式成立。c) t(R1R2)t(R1)t(R2); 因为:t(R1)=R1R12R13.R1n(n为A中元素个数) t(R2)=R2R22R23.R2n则 t(R1)t(R2)=R1R2R12R22R13R23.R1nR2n左边=t(R1R2)=(R1R2)(R1R2)2.(R1R2)n设A中有任意<x1,y1>R1 ，任意<x2,y2>R2则有<x1,y1>t(R1) <x2,y2>t(R2) (1)因为<x1,y1>,<x2,y2>(R1R2) (2)则有<x1,y1>,<x2,

52、y2>t(R1R2)(3)因此由(1)(2)(3)式可得：t(R1R2)t(R1)t(R2); 3.7习题参考答案1、设R是一个二元关系，设S=<a,b>|存在某个C，使<a,c>R且<c,b>R，证明R是一个等价关系，则S也是一个等价关系。证明：如果题目反一下是：S是一个等价关系，则R也是一个等价关系。或许能证出吧晓津看法:题中的大写C应为小写c;请学友提供您的看法。 感谢阮允准给出了证明：（1）R是自反，若有xA就有x，xRx，xSS是自反的。（2）因有a，bS 且存在c，使a，cR且c，bR R是对称的c，aR，b，cRb，aSS是对称的（3）设

53、a，b，b，cS则存在d,e使a，d，d，b，b，e，e，cRR是传递的a，b，b，c>Ra，cS 即S是传递的因此得证S是等价关系。 2、设R是A上一个自反关系，证明：R是一个等价关系，当且仅当若<a,b>R,<a,c>R,则<b,c>R。证明：由于R是一个等价关系，所以R是传递的。由此可知：若<a,b>R,根据对称性，则有<b,a>R已知：<b,a>R且<a,c>R,根据传递性，必有<b,c>R 晓津认为：jhju的证明中，已经在前提中确定了R是一个等价关系，这种理解应是不正确的。我的理解

54、是：前提：R是A上的自反关系结论：R是一个等价关系 iff (aRb,aRcbRc)等价关系的充要条件是R为自反的，对称的和传递的。但是我也无法证出来。请胖胖、sphinx、菜虫虫和ryz和其他朋友提供您的思路好吗? 下面是linuxcn 和阮允准同学给出的证明(晓津作了综合)： 证明：1）设有a,b,cA，若有<a,b>R，<a,c>R因为R是对称的，所以必有<b,a>R又因为R是传递的，由<b,a>,<a,c>R，有<b,c>R。2）由(a,b)R,(a,c)R,则(b,c)R。证等价关系,其实只需证传递关系和对称关系

55、。如下： 设有任意的<a,b>R R是自反的 <a,a>R <b,a>R R是对称的 对任意的<a,b>,<b,c>R 由R是对称的 <b,a>R 由<b,a>R，<b,c>R 可得<a,c>RR是传递的 R是等价关系。 不对之处，还请多多指正。 3、设R为集合A上一个等价关系，对任何aA,集合aR=_aR=x|xA,aRx_称为元素a形成的等价类。aR，因为_A=_。阮允准给出后一空的正确答案： aa R4、设R是A上的自反和传递关系， 证明：RR-1 是A上的一个等价关系。 证明：R

56、是A上的自反关系，所以 <a,a>R 且 <a,a>R-1 <a,a>RR-1 R是A上的传递关系, 则：若有<a,b>R 且 <b,c>R,则有<a,c>R 由于R又具有对称性，所以<b,a>R且<c,b>R,则有<c,a>RR-1也有：<b,a>R-1 且<c,b>R-1,则有<c,a>R-1可见：<b,a>RR-1 且<c,b>RR-1,则有<c,a>RR-1R是A上的对称关系，则有<a,b>R、&

57、lt;b,a>RR-1是A上的对称关系，也有 <a,b>R、<b,a>R 则有： <a,b>RR-1 、<b,a>RR-1 由于RR-1 有对称性，传递性、自反性。所以说RR-1 是等价关系。 上面的红色部分有点问题，已知条件中并未给出这样的前提。晓津证明如下：(1)因为R是A上的自反关系,若有aA，则<a,a>R且<a,a>R-1即<a,a>RR-1所以RR-1是自反的。(2)因为R是A上的传递关系，则R-1也是A上传递关系，若有a,b,cA,则若<a,b>RR-1且<b,c>RR-1必有<a,b>R<b,c>R 且<a,b>R-1<b,c>因此有<a,c>R <a,c>R-1即<a,c>RR-1所以RR-1是传递的。(3)若有a,bA 则若<a,b>