2022年2022年离散数学答案 .pdf

《2022年2022年离散数学答案 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学答案 .pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题 4.1 1.（1）R=, （ 2）R=, （ 3）R=, 2.(1)2 M=0010100101 3 （2） 0 3 M=00001110111011101 2 （3）M=00000001111111110000011111111111111111110011111103. +=|名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - - |, A 上不同的 m 元关系的个数 =4.A 上含元素最少和最多的二元关系分别是空关系和全域

2、关系AxA 习题 4.2 1 (a)自反，反对称，可传递(b)反对称，可传递(c)自反，对称，可传递(d)反自反，反对称(e)反自反，反对称(f)自反，反自反，反对称，可传递2 (1)：对称，：对称，可传递，：反自反，对称，：自反，对称，反对称，可传递(2)3 M= 1000010100110111R 自反，对称4 (a) M=反自反，反对称，可传递(b)M=反自反，对称(c)M=不具有任何性质名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - -

3、- - - - 5a B c 反自反，对称a b c ：自反，反对称a b c ：对称，反对称，可传递a b c 习题 4.3 1.RS=,. RS=. R-S=, R=, 2. 1R2R1R2R21RR1RAA1R的反21RR自反反自反对称反对称传递1R2R 保持自反， 反自反， 对称。但不保持反对称，如1R=,2R = 均反对称，但1R2R =, 非反对称，也不保持传递，如1R=,2R = 均课传递，但1R2R =, 非可传递。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3

4、页，共 15 页 - - - - - - - - - 1R2R保持自反，反自反，对称，反对称，可传递。21RR保持反自反，对称，反对称。但不保持自反，如1R=,2R =, 均为 上的自反关系，但21RR=非自反，也不保持可传递，如1R=,2R= 均可传递，但21RR=,非可传递。1RAA保 持 对 称 ， 不 保 持 自 反 。 如A=,1R=,自 反 ，1RAA=, 非自反，不保持反自反，如A=1 ， 2 ，1R= 反自反，1RAA=, 非反自反，不保持反对称，如A=1 ，2，1R= 反对称，1RAA=,非反对称，不保持可传递，如A=1，2 ，1R=可传递，1RAA=,非可传递，1R保持自反

5、，反自反，对称，反对称，可传递。21RR保持自反性， 不保持反自反， 如1R =,2R = 均反自反， 但21RR=非反自反，不保持对称，如1R =,2R = 均对称，但21RR= 非对称 ， 不 保 持 反 对 称 ， 如1R=,2R=， 均 反 对 称 ，21RR=,非反对称，不保持课传递，如1R =,2R = ， 均可传递，21RR=, 3.(1)SR=, RR=, RS=, SS=, (2) 0010101000000101RM0001110000010000SM000100010000110000011100000100000010101000000101SRSRMMM名师资料总结

6、- - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 15 页 - - - - - - - - - 000000100000111100101010000001010010101000000101RRRRMMM010110100101000000101010000001010001110000010000RSRSMMM000011010000000000011100000000000001110000010000SSSSMMM4. R,S对称R=R， S=S，SR对称SR=SR（上面要加一个

7、弯弯，打不出来） =RS=RS5.(1) R反自反RIRxxIxxRxxAxAA,(2) R反对称RxyRyx,，即Ryx,，亦即RRyx,，有yx，即AAIRRIyx,. (3) R可传递Rzyyx,，即RRzx,，有RRRRzx,。6.(1) )()()()()()(21212121RrRrIRIRIRRRRrAAA(2)(21RRs)()(2121RRRR(第 二 个 括 号 上 面 有 一 个 大 弯 弯 ， 打 不 出 来 ) 2121RRRR)()(2211RRRR)()(21RsRs(3)题目有误，应改为)()()(2121RtRtRRt)()()()()(),(,2121212

8、12121RRtRtRtRRtRtRtRRRR(4) 1R =,2R =,11)(RRt,22)(RRt,)(21RRt=, )()(21RtRt=,)(21RRt)()(21RtRt名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 15 页 - - - - - - - - - 7.(1)AIRRRRr)()(2121)()()()(2121RrRrIRIRAA(2) )()()()(),()(,212121212121RsRsRRsRsRsRRsRRRR(3) 1R, 2

9、R, )()(21RsRs, )()(21RsRs, )(21RRs, )(21RRs)()(21RsRs(4) )()()()(),()(,212121212121RtRtRRtRtRtRRtRRRR(5) 1R, 2R, )(1Rt, )(2Rt, )()(21RtRt, )(21RRt, )()()(2121RRtRtRt8.(1) iiiiiiRRRRIi211121,，即)()(21RtRt（2）AIRRr)(（*）AIR=AIR=)( Rr；)(RtiiR1iiR1（iR上面有） =iiR1iiR1)( Rt；)()(RrtRtr，R可传递RRt)()()()(RrRrRtr可传递

10、。(3)先用数学归纳法证明：1)(iiiARRIRAIRIi。当1i时，显然成立。设1iiRRAIRiAIR)(则1)(iAIR1()()()(iiAiAARRIRIRIR)AIR)()(1iAiARIRRIR)()(AAAIIRRIR)()(iAiRIRR)()()()(AAAAIIIRRIRR)(1iiRR)()(2AIRRRiiRR1AIR故得证11)()()(iAiiAIRIRtRrt1(iiRR)AIR名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 15 页 -

11、 - - - - - - - - iAiIR)(1iiRr)(1)( RtriiiRRRRIiRRRR)(,iiiRRRRIi)(,。)()(RtRst)(Rt（*）)(1iiR)(1iiR（* ）)(1iiiRR)()(1RtsRRii（* ）有此标记的为前面的符号上面有符号。9，题目有误，应改为yRzxRyAzAyAxzyx(1) 如3,2,2,1R(2)R反传递Rzyyx,，即2,RRRzx，有RRRzx2,。习题 4.41.(1)A 上最大等价关系为AA，有2n个元素，秩为1 (2)A 上最小等价关系为AI，有 n 个元素，秩为n 2、 （1）否。如1RAI为等价关系，但 AAAI非自

12、反，故非等价关系。（2）否。如 A1，2，3 ，1R， 。（3）是。1R自反1RIAAI2AI21R21R自反; 1R对称21R21R21R21R对称; 1R可传递121RR（）21221)(RR21R可传递。（4）否。如 A1，2，3 ，1R，均为等价关系。 但 r（1R2R），非可传递，故非等价关系。（5）否。如 A1，2，3 ，1R， ，2R，均为等价关系。 但1R2R ，非等价关系。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 15 页 - - - - - -

13、- - - （6）否。如（ 5）中，1R，2R ，1R2R ，非可传递，故非等价关系。3、yx,R，R 自反， R 循环R，R 循环R R 对称。yx,，zy,R，R 循环R，R 对称R R 可传递，故 R 为等价关系。4、Ax，1R自反1R2R2R 自反 ; yx,2R1R1R1R1R2R2R 对称 ; yx,，zy,2R， ， 1R，1R可传递，1R2R2R 可传递，故2R 为等价关系。5、不正确。因为该题中a，b 不一定具有任意性，而自反性定义中要求Ax，xRx。6、 （ 1）非（2）非（ 3）是， R，7、2,BAiBAikj，BAiAiBAiBAikjkj)()()(B；BxAxBA

14、x, . . . ,2,1mp，BAixBxAixpp,)(1BAiUBAlml；又BABAiUBABAimllmll)(,.,2,11，故BABAiUlml)(1。故2为划分。8、R1R5 1，5R2R4 2，4R3R6 3， 6R 诱导的划分 1，5 ， 2，4 ， 3，6 。9、yx,AB，1R，2R 自反1R，2R，3R3R 自反。221,12,132211,RyyRxxRyxyx，1R，2R对称31122212,11,2,RyxyxRyyRxx3R 对称。33,32,22,21, 1,Ryxyxyxyx13,22,1,Rxxxx，23,22,1,Ryyyy1R，2R 可传递23,11

15、3,1,RyyRxx33,31,1,Ryxyx3R 可传递。故3R 为等价关系。10、 （1）否。如 A1，2 ，1 1，2 ，2 1 ， 2 ，21 1，2 ， 1 ， 2 非 A 的划分。（2）否。如（ 1） ，21，非 A 的划分。（3）否。1 1 ， 2，3 ，2 1 ， 2 ， 3 ，12 2，3 ，非 A 的划分。（4）是。1121)(1121)(11习题 4.5 1、 （1）fcfdecab,成立。（2）a. e.f.b.d.c. （ 3） （a）极大元a, e, f；极小元 c；最小元 c；下界 c；最大下界c。（ b）极大元b, d；极小元 b, d；下界 c；上界 e；最大

16、下界c；最小上界e。（ c）极大元e；极小元 b；最大元 e；最小元 b；下界 b, c；上界 e；最大下界b；最小上界 e。（ d）极大元 e；极小元 b, d；最大元 e；最小元 b；下界 c；上界 e；最大下界c；最小上界 e。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - - - - - - - - - 2、 （ 1）1R是，；2R 是，；3R 是，；4R 是，；5R 非；6R 非。（2）均非拟序关系；1R是全序关系，也是良序关系，其余均非全序关系和

17、良序关系。3、 （ 1）R 为偏序关系R 自反，反对称，可传递，由习题4.3，可知R自反，反对称，可传递R为偏序关系。（2）R 为拟序关系R 反自反，可传递，由习题4.3，可知R反自反，可传递R为拟序关系。（3）R 为全序关系R 为偏序关系， 且RyxAyx,或Rxy,R为偏序关系，且xyAyx,R或yx ,RR为全序关系。（4）如,N为良序关系，但,NN非良序关系。4（1）若AB，则Ax，但Bx，从而BBxx,，故,Rxx，即R非自反，故R非偏序关系；若B A，则R)(AARR为偏序关系。（ 2 ） R为 拟 序 关 系R反 自 反 ，RRR反 自 反 ；Bzyx,， 若zyyx,RR，R可

18、传递Rzx,，又BBzx,)(,RBBRzx可传递，故R为拟序关系。（ 3）若AB，则由（ 1） ，R非偏序关系，故R也非全序关系；若BA，则RR为全序关系。（ 4） 若AB，则由（ 1） ，R非偏序关系，故R也非良序关系；若BA，则RR名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 15 页 - - - - - - - - - 为良序关系。5、,AAAba为全序集自反bbaa,baRba,11R 自反。AAdcba,， 若dcRba,1， 且baRdc,1，则bdac

19、dbca,，反对称1,Rdcbadbca反对称。AAfedcba,，若dcRba,1，且feRdc,1，则fdecdbca,名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 15 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 15 页 - - - - - - - - - 习题 4.6 名师资料总结 - -

20、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 15 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 15 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -