自考--离散数学教材课后题第三章答案(共50页).doc

《自考--离散数学教材课后题第三章答案(共50页).doc》由会员分享，可在线阅读，更多相关《自考--离散数学教材课后题第三章答案(共50页).doc（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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+y21 晓津答案：C=a(x,y)|a为直角坐标系中一点且 x2+y21,0=1,0=2 e)能被5整除的整数集E= x| x mod 5=0-2、判定下列各题的正确与错误。a) xx;正确b) xx;正确晓津观点:本命题错误。理由：x作为一个元素是一个集合，而右

2、边集合中的元素并不是集合。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式也应作如此理解，空集是一个集合，在A中并无这个集合元素,如f式则是正确的。空集包含于任何集合中，但空集不一定属于任一集合。-4、设A= ， B=(A),问下列各题是否正确。a)B,B正确b) B

3、,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),b)式均不成立。-6、设某集合有101个元素，试问：a) 可构成多少个子集；2n个元素 (子集吧)b) 其中有多少个子集元素为奇数；其中有 2n-1 个子集元素为奇数晓津不同意见：我认为

4、这个答案不成立,如集合有3个元素，则它的幂集中有5个子集中元素个数为奇数，而不是7个。可是我也还没找到这个式子。sphinx提供的答案是2100 ，可通过多项式分解找到规律，空集不算。晓津想，应该算上，若算上则是2n-1+1c) 是否有102个元素的子集。无3.2习题答案1、给定自然数集合N的下列子集：A=1,2,7,8 B=i|i250=0,1,2,3,4,5,6,7C=i|i可被3整除 0i30, =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

5、,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、a)如果对于一切集合，有XY=X，则Y=证明： XY=i|iXiY=Xi|iXiY=Xi|iXiY=i|iX由此可见：Y=晓津的证明：必要性：设Y 则Y中必有一个以上元素。若有一个元素y,yYyX

6、 则有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)晓津证明：本题也要进行双向的证明，一个是必要性，一个是充分性，这才能得出当需的结论。证：充分性：若C A则(AB)C=(AC)(BC)=A(BC)=右边。必要性：假设C不包含于A内，则C中必有一个以上元素xA，则ACA可得 (A

7、B)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-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

8、=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,证明：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

9、本题的答案感谢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、在下面各题中，如果命题为真，请给证明；如果命题为假，则给出反例；a)、 A(B-C)=(AB)-(AC)晓津证明如下：A(B-C)=x|xA(xBxC)=x|xAxB(xAxC)=x|xAxB(x

10、Ax(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=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

11、,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(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

12、)=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。即前提左边A左右不等，因此假设违反题意，不成立。所以必需A(BC)=-8、证明：a)、 A(BC)=(AB)(AC)?晓津证明如下：右边=(AB)(AC) (AB)(AC)=(A(BC)(A(BC)=

13、(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=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) A1B=

14、,1,2=,1,1,2,2b) A2B=,1,2=,1,2,1,2,1,2,1,2c) (AB)2=,2=, , , ,晓津叹气，呵呵，这道题本是(BA)2，答案就不一样了。大家做题的时候也要注意仔细看题目呀。-2、下列各式中哪些成立？哪些不成立？为什么？a) (AB)(CD)=(AC)(BD)不成立，因为笛卡尔积中。在左半式中，x的成分在A与B两个集合中，而右半式中，x的成分在A与C两个集合中。b) (A-B)(C-D)=(AC)-(BD)不成立，比如设A与B中都含有含有元素 a 。在左半式中，a是不会出现在 x 中。假设 (AC)出现(a,b),(a,e),而(BD)出现了(a,b),(a

15、,d)，那么(a,e)将被保留下来，从而 左半式 不等于 右半式。c) (AB)(CD)=(AC)(BD)不成立。因为左半式 x不可能含有 AB的成分，而在右半式 x 就包含有AB的成分。d) (A-B)C=(AC)-(BC)成立，因为左半式 x 不会出现B的成分，而右半式中 x 包含有 B的成分，也会被过滤掉的。e) (AB)C=(AC)(BC)成立。左半式中 x 不会出现 AB 的成分，而右半式中AB也会被过滤掉的。晓津道：这几个判断都是对的，只是证明过程好象有点生活化，不够科学，哪位朋友来做做?:)下面是ryz同学给出的证明:(晓津有所补充)d)证明：(1)设任意的x，y(AB)Cx(A

16、B)yCxAxByC(xAyC)xByCx，y(AC)x，y(BC)x，y(AC)(BC)；(AB)C(AC)(BC)(2)设任意的x，y(AC)(BC)；则x，y(AC)x，y(BC)xAyC(xByC)xA(yCxB)(yCyC)xAyCxB(xAxB)yCx(AB)yCx，y(AB)C(AC)(BC)(AB)C(AB)C=(AC)(BC)e)(AB)C(AB)(BA)C(AB)C)(BA)C)(ACBC)(BCAC)(AC)(BC)注：e)是利用d)的结果来证明的-3、证明若 XY=XZ,且 X，则 Y=Z证明： XY=| xX,yYXZ=| xX,zY如果 X= 那么 XY= XZ=因

17、为 X，所以 Y=Z-4、设 X=0,1,2,3,4,5,6,上关系为 R= (xy)(x是质数),写出R各元素，并求出 domR,ranR及FLDR。解： 议论一下R= (xy)(x是质数) ,我认为应改为。不然的话(x是质数)这个条件将不起作用。R=,晓津补充：若按jhju的讨论来做，应把红色三行去掉，0和1、4都不是质数,相应的，在下面的答案里，也应把红色字去掉。domR= 0,1,2,3,4,5ranR= 1,2,3,4,5,6FLDR= 0,1,2,3,4,5,6-5. 设 P=,Q=,求出 PQ，PQ,domP,domQ,ranP,ranQ,dom(PQ),ran(PQ)解： PQ

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

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

20、b 是偶数。 b) 在 1,2,3,4,5上定义的关系。 | a+b 是偶数 。 c)在所有人集合P上的关系， | a,b 是同一祖先 解：a)先列出其关系集合如下：R=，,由此可看出：A上关系R为自反的，对称的，传递的但不是反对称的。b)仍列出其关系集合：我们发现它和上面的集合是一样的：R=，,可知：A上关系R也是自反的，对称的，传递的但不是反对称的。c)这个集合不便列举，就拿一个家庭来举例吧，家里有5个人，老爸x,老妈y,哥哥z,姐姐u,我v,则列出R=,(这里我考虑老爸老妈应该不会同是一个祖先的。推广到所有人，也能得出结论,这个关系是自反的，对称的，传递的但不是反对称的。4、如果关系R和

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

22、R必有R，同时有，R则必有R 所以S是对称的，也是传递的。6、设Z是整数集 R=x,y)| xy(mod.K),证明 R是自反、对称和传递的。证明：设任意a,b,cZ，因为a-a=K0,即aa(mod K)成立R，故R是自反的。设a-b=Kt(t为整数)，则b-a=-Kt所以ba(mod K)成立，R,故R是对称的。若R且R，即ab(mod K) 且bc(mod K) a-b=Kt b-c=Ks( t,s 为整数)则 a-c=Kt+Ks=K(t+s)所以ac(mod K) 即R，故R是传递的。7、设R是集合X上的一个自反关系。求证R是对称和传递的，当且仅当,在R中，且有在R中。 证明：充分性：

23、设任意a,b,cX，因为R是自反关系，则,R，当有,R时.我发现充分性无法证明。必要性：要使R为对称的，则对任意a,bX，必须有,R，要使R为传递的，对任意a,b,cX 若有,R 必要有R，所以应有,在R中。(实际上对于此题，少给出一个或或在R中的条件，故导致充分性不足。所以 此题我没能证出来。 3.5习题答案1、设： A=1,2,3上关系R= | xy，试求： R-1, R 解： R=,(2,2, R-1=, R=, 2、设： A=0,1,2,B=0,2,4的关系为： R=|a,bAB 求：R-1,并求MR-1 解： R=, R-1=, Mr-1= | 0 0 1 | | 1 1 1 | |

24、 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=, r(R)=, s(R)=, 为了求：t(R) MR=| 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 MR2

25、MR3=, 4、设 A=1,2,3,4上的二元关系， R=,，则： r(R)=, S(R)=, t(R)= MR=| 0 1 1 0 | | 0 0 0 1 | =, | 0 0 1 0 | | 0 0 0 0 | MR2=| 0 1 1 0 | | 0 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 | =, MR3=| 0 0 1 1 | | 0 1 1 0 | 0 0 1 0 | | 0 0 0

26、 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 |=, 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 |=, 可得t(R)=, =, 3.6习题答案1、给定集合X=x1,x2,.,x6,是X上相容关系且M简化矩阵为：

27、 试求X的覆盖，并画出相容关系图。 解：覆盖如下： , , 晓津觉得覆盖中的元素应该是集合：我的答案是：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：=S1S1S2S2 =, =, 4、设是A上相容关系， a) 复合关系。是A上的相容关系吗？ 由于自反性通过,运算可保持;但对称性不能通过,保持。所以复合关系。不是A上的相容关系 b) 是A上相容关系吗？ 是的

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

29、,5,6的关系图如下所示，求： a) R,R2，R3及关系图 解： R=, 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 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=, MR3=| 0 0 1 1 0 0 | | 0 0 1 0 1 0 | 0 0 0 1 1 0 | |