大连理工大学软件学院离散数学作业答案

大连理工大学软件学院离散数学作业答案 第一章 命题逻辑 1(第7页第3题 (1)解:逆命题:如果我去公园，则天不下雨; 反命题:如果天下雨，则我不去公园; 逆反命题:如果我不去公园，则天下雨了。 (2)解:(此题注意:P仅当Q翻译成) PQ, 逆命题:如果你去，那么我逗留。 反命题:如果我不逗留，那么你没去。 逆反命题:如果你没去，那么我不逗留。 nnn(3)解:逆命题:如果方程无整数解，那么n是大于2的正整数。 xyz，, nnn 反命题:如果n不是大于2的正整数，那么方程有整数解。 xyz，, nnn 逆反命题:如果方程有整数解，那么n不是大于2的正整数。 xyz，, (4)解:逆命题:如果我不完成任务，那么我不获得更多的帮助。 反命题:如果我获得了更多的帮助，那么我能完成任务。 逆反命题:如果我能完成任务，那么我获得了更多的帮助。 2(第15页第1题 (4)解: ，，,,，,(())PQPT，,,，,，()()PQPQ (重言式) ,，,，,，,，()()PQPQ (9)解:(重言式) PPQFQT,，,,,, (10)解:(可满足式) PQQTQQ,，,,,, 3(第16页第5题 (2)证明: ，，,,，(())PQP ,，,,，(())PQP ,，,,()PQP ,，,，,PQP ,，,,，PPQ ,,，FQ ,F 因此，，，,,，,(())PQPF，得证。 (4)证明: ()()PPPP,，,，, ,，,，,,()()PPPP ,，,PP ,F 因此，，得证。 ()()PPPPF,，,，,, 4(第16页第6题 (1) PQPQ,,, 证明:设为真，那么P为真，并且Q为真，因此为真。所以。 PQ,PQ,PQPQ,,, (2) PQRPQPR,,,,,,()()() PR,证明:设为假，于是为真，为假。得P为真，Q为真，()()PQPR,,,PQ,R为假。于是得为假，由P为真可得，为假。因此，QR,PQR,,() 。得证。 PQRPQPR,,,,,,()()() (5) ()()PPQPPRQR,，,,,，,,, 证明: ()()PPQPPR,，,,,，, ,,,,()()TQTR ,,QR 因此，，得证。 ()()PPQPPRQR,，,,,，,,, 5(补充:试证明 (())(())(())QACAPCAPQC,,,,,,,,, (())(())QACAPC,,,,,证明: ,，,,,，,,(())(())QACAPC ,，,,，,，,,()()ACQACP ,，,,,，()()ACPQ (())APQC,,, ,，,，,,(())APQC ,，,，，,,(())APQC ,，,,，,APQC() ,，,,,，()()ACPQ 因此，，得证。 (())(())(())QACAPCAPQC,,,,,,,,, 6(第21页第1题 (2)解: ()()()PQPQPQ,,，,,,， ,,，,,,，(())()PPQPQ ,,,，QPQ() ,,,,，()()PQQQ ,,PQ ,(0), 7(第21页第2题(只求主析取范式) (4)解: ()()PQSPQR,，,,，,, ,,，,,,,，,,，,，,,,,，,,，,()()()()PQSRPQSRPQSRPQSR ,(5,7,10,11), 8(第25页第3题 B证明:(1) P规则 (2) P规则 BAC,，,，() ，,，AC (3) T规则，(1)(2) (4) P规则 ABC,,() AC, (5) T规则,(1)(4) ()()ACAC,,，,， (6) T规则(5) (7) T规则(3) ，,()AC ，,，AC (8) T规则(6)(7) ，,()AC (9) T规则(8) AC,，,()AC因此，是题目的有效结论，不是。 9(第26页第7题 ，,，，,，,，(),,PQQRRP(a) 证明:(1) P规则 ，R (2) P规则 ，,QR (3) T规则(1)(2) ，Q (4) P规则 ，,，()PQ (5) T规则(4) ，,PQ (6) ，P T规则(3)(5) (b) (),,PQRRSSPQ,,，,，,，,， S证明:(1) P规则 ，,，RS (2) P规则 (3) ，R T规则(1)(2) (4) P规则 ()PQR,, (5) T规则(3)(4) ，,()PQ 6) T规则(5) (，,，PQ (c) (),,PQRRSQTP,,,,, 证明:(题目有问题) 10(第26页第8题 (a) ，,，,,,,PQQRRSPS,, 证明: (1) P P规则(假设前提) (2) P规则 ，,PQ (3) Q T规则(1)(2) (4) P规则 ，,QR (5) R T规则(3)(4) RS, (6) P规则 (7) S T规则(5)(6) PS, (8) CP规则(1)(7) (b)PQPPQ,,,,() 证明: (1) P P规则(假设前提) (2) PQ, P规则 (3) Q T规则(1)(2) PQ, (4) T规则(1)(3) (5) CP规则(1)(4) PPQ,,() (c) ()()PQRPQR,,,,, 证明: (1) P规则(假设前提) PQ, (2) P T规则(1) (3) Q T规则(1) (4) T规则(2)(3) PQ, (5) P规则 ()PQR,, (6) R T规则(4)(5) (7) CP规则(1)(6) ()PQR,, 11(第26页第9题 (a) (),,,RQRSSQPQP,，,,，,,， ，，P证明: (1) P规则(假设前提) (2) P T规则(1) (3) P规则 PQ, (4) Q T规则(2)(3) (5) P规则 SQ,， ，S (6) T规则(4)(5) RS, (7) P规则 (8) R T规则(6)(7) (9) P规则 RQ,， (10) T规则(8)(9) ，Q (11) T规则(4)(10) QQ,， ，P (12) F规则(1)(11) (b) SQRSRPQP,，,，,,，,,, ，，P证明: (1) P规则(假设前提) (2) P T规则(1) (3) PQ, P规则 (4) Q T规则(2)(3) SQ,， (5) P规则 (6) T规则(4)(5) ，S RS, (7) P规则 (8) R T规则(6)(7) (9) P规则 ，R (10) T规则(8)(9) RR,， (11) F规则(1)(10) ，P (c) ，,,，,,,，,,()(),(()),PQRSQPRRPQ 证明: (1) R P规则 (2) P规则 ()QPR,,， (3) T规则(1)(2) QP, RS, (4) T规则(1) (5) P规则 ，,,，,()()PQRS (6) T规则(4)(5) ，，,()PQ (7) T规则(6) PQ, (8) T规则(3)(7) ()()PQQP,,, (9) T规则(8) PQ, 第二章 谓词逻辑 1(第39页第1题 (b) ()()()()()(()())，,,,,,xAxxBxxAxBx ()()()()，,,xAxxBx ,，，,,()()()()xAxxBx 证明: ,,，,,()()()()xAxxBx ,,，,()(()())xAxBx ,,,()(()())xAxBx (还可以用推理的方法证明) 证明: (1) ，,,()(()())xAxBx P(假设前提) (2) ()((()()))，，,xAxBx T ()(()())，,，xAxBx (3) T (4) T ()()()()，,，，xAxxBx (5) T ()()，xAx (6) T ()()，，xBx (7) P ()()()()，,,xAxxBx (8) T(5)(7) ()(),xBx (9) ES(6) ，Ba() (10) US(8) Ba() (11) T(9)(10) ，,BaBa()() (12) F(1)(11) ()(()()),,xAxBx (d) ()(()()),()(()()),()()()() ,,,,，,,,xAxBxxBxCxxCxxAx 证明: (1) P ()(),xCx (2) US(1) Cx() (3) P ()(()()),,，xBxCx (4) US(3) BxCx()(),， (5) T(2)(4) ，Bx() (6) P ()(()()),,xAxBx (7) US(6) AxBx()(), (8) T(5)(7) Ax() (9) UG(8) ()() ,xAx 2(第39页2 (a)()(()())()()()(),,,,,,xPxQxxPxxQx 证明: (1) ()(),xPx P(假设前提) Px() (2) US(1) (3) P ()(()()),,xPxQx (4) US(3) PxQx()(), (5) T(2)(4) Qx() (6) UG(5) ()(),xQx (7) CP(1)(6) ()()()(),,,xPxxQx (b) ()(()())()()()(),,,,,，xPxQxxPxxQx ()()()()()(())()(),,，,，,，,,xPxxQxxQxxPx证明:由于 ,,，,,()(())()()xQxxPx因此，原题等价于证明 ()(()())()(())()(),,,,，,,xPxQxxQxxPx (1) P(假设前提) ()(()),，xQx ) US(1) (2，Qx() (3) P ()(()()),,xPxQx (4) US(3) PxQx()(), (5) T(2)(4) Px() (6) UG(5) ()(),xPx (7) CP(1)(6) ()(())()(),，,,xQxxPx 3(第39页第3题 (a)所有的有理数是实数，某些有理数是整数，因此某些实数是整数。 解:首先定义如下谓词: Pxx():是有理数 Rxx():是实数 Ixx():是整数 于是问题符号化为: ()(()()),()(()())()(()()),,，,,，,xPxRxxPxIxxRxIx 推理如下: (1) P ()(()())，,xPxIx (2) ES(1) PaIa()(), (3) P ()(()()),,xPxRx (4) US(3) PaRa()(), (5) T(2) Pa() (6) T(2) Ia() (7) T(4)(5) Ra() (8) T(6)(7) RaIa()(), (9) EG(8) ()(()())，,xRxIx (b)任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自 行车，有的人不爱骑自行车，因而有的人不爱步行。 解:首先定义如下谓词: 是人 Pxx(): 喜欢步行 Fxx(): 喜欢乘汽车 Cxx(): Bx():x喜欢骑自行车 于是问题符号化为: ()(()()()),()(()()()),,,,，,,,xPxFxCxxPxCxBx ()(()())()(()())，,，,，,，xPxBxxPxFx 推理如下: ()(()())，,，xPxBx (1) P PaBa()(),， (2) ES(1) Pa() (3) T(2) ，Ba() (4) T(2) ()(()()()),,,xPxCxBx (5) P (6) US(5) PaCaBa()()(),, (7) T(3)(6) CaBa()(), (8) T(4)(7) Ca() (9) P ()(()()()),,,，xPxFxCx (10) US(9) PaFaCa()()(),,， (11) T(8)(10) ，,(()())PaFa (12) T(11) ，,，PaFa()() (13) T(3)(12) ，Fa() (14) T(3)(13) PaFa()(),， (15) EG(14) ()(()())，,，xPxFx (c)每个科学工作者都是刻苦钻研的，每个刻苦钻研而且聪明的科学工作者在他的事业中 都将获得成功。华为是科学工作者并且他是聪明的，所以，华为在他的事业中将获得成功。 解:首先定义如下谓词: 是科学工作者 Pxx(): 是刻苦钻研的 Qxx(): Rxx():是聪明的 Sxx():在他的事业中将获得成功 定义个体a:华为 于是命题符号化为: ()(()()),()(()()()()),,,,,,,xPxQxxPxQxRxSx PaRaSa()()(),, 推理如下: ()(()()),,xPxQx (1) P PaQa()(), (2) US(1) PaRa()(), (3) P Pa() (4) T(3) (5) T(3) Ra() (6) T(2)(4) Qa() (7) P ()(()()()()),,,,xPxQxRxSx (8) US(7) PaQaRaSa()()()(),,, (9) T(3)(6) PaQaRa()()(),, (10) T(8)(9) Sa() (d)每位资深名士或是中科院院士或是国务院参事，所有的资深名士都是政协委员。张伟 是资深名士，但他不是中科院院士。因此，有的政协委员是国务院参事。 解:首先定义如下谓词: 是资深名士 Pxx(): 是中科院院士 Qxx(): 是国务院参事 Rxx(): 是政协委员 Sxx(): 定义个体a:张伟 于是命题符号化为: ()(()()()),()(()()),,,,,,xPxQxRxxPxSx PaQaxSxRx()()()(()()),，,，, 推理如下: (1) PaQa()(),， P (2) Pa() T(1) ，Qa() (3) T(1) ()(()()),,xPxSx (4) P PaSa()(), (5) US(4) Sa() (6) T(2)(5) ()(()()()),,,xPxQxRx (7) P PaQaRa()()(),, (8) US(7) (9) T(2)(8) QaRa()(), (10) T(3)(9) Ra() (11) T(6)(10) SaRa()(), (12) EG(11) ()(()())，,xSxRx (e)每一个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被2整除。并不是所有的自然数都能被2所整除。因此，有的自然数是奇数。 解:首先定义如下谓词: 是自然数 Nxx(): 是奇数 Qxx(): 是偶数 Oxx(): 能被2整除 Pxx(): 于是命题符号化为: ()(()(()())),()(()(()())),,,,,,,xNxQxOxxNxOxPx ，,,,，,()(()())()(()())xNxPxxNxQx 推理如下: (1) P ，,,()(()())xNxPx (2) ()(()())，,，xNxPx T(1) (3) NaPa()(),， ES(2) (4) Na() T(3) ，Pa() (5) T(3) ()(()(()())),,,xNxOxPx (6) P NaOaPa()(()()),, (7) US(6) OaPa()(), (8) T(4)(7) ，Oa() (9) T(5)(8) ()(()(()())),,,xNxQxOx(10) P (11) US(10) NaQaOa()(()()),, (12) T(4)(11) QaOa()(), (13) T(9)(12) Qa() (14) T(4)(13) NaQa()(), (15) EG(14) ()(()())，,xNxQx (f)如果一个人怕困难，那麽他就不会获得成功。每个人或者获得成功或者失败过。有些 人未曾失败过，所以，有些人不怕困难。 解:首先定义如下谓词: 是人 Pxx(): 怕困难 Qxx(): 曾获得成功 Rxx(): 曾获得失败 Sxx(): 于是命题符号化为: ()(()()()),()(()(()())),,,,，,,,xPxQxRxxPxRxSx ()(()())()(()())，,，,，,，xPxSxxPxQx 推理如下: (1) ()(()())，,，xPxSx P (2) PaSa()(),， ES(1) (3) Pa() T(2) ，Sa() (4) T(2) ()(()(()())),,,xPxRxSx (5) P PaRaSa()(()()),, (6) US(5) RaSa()(), (7) T(3)(6) Ra() (8) T(4)(7) ()(()()()),,,，xPxQxRx (9) P (10) US(9) PaQaRa()()(),,， (11) T(8)(10) ，,(()())PaQa (12) T(11) ，,，PaQa()() (13) T(3)(12) ，Qa() (14) T(3)(13) PaQa()(),， (15) EG(14) ()(()())，,，xPxQx4(第40页第5题 解:错误，第2行的y是泛指，第4行的y是特制 更改如下: (1) P ()()，xPx (2) ES(1) Py() 3) P (()(()()),,xPxQx (4) US(3) PyQy()(), (5) T(2)(4) Qy() (6) EG(5) ()()，xQx 5(第40页第6题 (a) ()()()((()())()),，,,,,xPxxPxQxRx ()(),()()()()(()())，，,，，,xPxxQxxyRxRy 证明: (1)()()，xPxP (2)(),(1)PaES (3)()()，xQxP (4)(),(3)QbES (5)()()()((()())())，,,,,xPxxPxQxRxP (6)()((()())()),(1),(5),,,xPxQxRxT (7)(()())(),(6)PaQaRaUS,, (8)()(),(2)PaQaT, (9)(),(7),(8)RaT (10)(()())(),PbQbRbUS,,(6) (11)()(),(4)PbQbT, (12)(),(10),(11)RbT (13)()(),(9),(12)RaRbT, (14)()(()()),(13)，,yRaRyEG (15)()()(()()),(14)，，,xyRxRyEG (b) ()()()()()(()())，,,,,,xPxxQxxPxQx证明: (1) P ()()()()，,,xPxxQx (2) T(1) ，，,,()()()()xPxxQx (3) T(2) ()()()(),，,,xPxxQx (4) T(3) ()(()()),，,xPxQx (5) T(4) ()(()()),,xPxQx 6(第42页第1题 (a) ()(()()()),,，xPxyQy 解: ()(()()()),,，xPxyQy ,,，,，()(()()())xPxyQy ,,，，,()()(()())xyPxQy (b)()()(()((,)(,))()(,,)),,，,,，xyzPxyPyzuQxyu 解: ()()(()((,)(,))()(,,)),,，,,，xyzPxyPyzuQxyu ,,,，，,,，()()(()((,)(,))()(,,))xyzPxyPyzuQxyu ,,,,，,，,，()()(()((,)(,))()(,,))xyzPxyPyzuQxyu,,,,，，,，,()()()()((,)(,)(,,))xyzuPxyPyzQxyu(c) ，,，,，,,,,()()(,)()()((,)()((,)(,)))xyAxyxyBxyyAyxBxy解: ，,，,，,,,,()()(,)()()((,)()((,)(,)))xyAxyxyBxyyAyxBxy,,，,，,,,,()()(,)()()((,)()((,)(,)))xyAxyxyBxyyAyxBxy ,,，,，,,,，,()()(,)()()((,)()((,)(,)))xyAxyxyBxyyAyxBxy,,，,，,,,，()()(,)()()((,)()((,xyAxyuvBuvzAzu)(,))),Buz ,,，，,,,,，,()()()()()((,)((,)((,)(,))))xyuvzAxyBuvAzuBuz7(第42页第2题 (b) ()(()()(()(,)()(,))),,,,,，,xPxyzQxzzRxy 解:前束析取范式 ()(()()(()(,)()(,))),,,,,，,xPxyzQxzyRxy ,,，,,,,，,()(()()(()(,)()(,)))xPxyzQxzyRxy ,,，,,，,,，,()(()()(()(,)()(,)))xPxyzQxzyRxy ,,，,,，,,，,()(()()(()(,)()(,)))xPxyzQxzuRxu ,,，,,，，,，，()(()()(()(,)()(xPxyzQxzuRxu,))),,,，，，,，,，()()()()(()((,)(,)))xyzuPxQxzRxu ,,,，，，,，,，()()()()(()(,)(,))xyzuPxQxzRxu 由于是基本和，因此前束合取范式与前束析取范式一样: ，,，,，PxQxzRxu()(,)(,) ()(()()(()(,)()(,))),,,,,，,xPxyzQxzzRxy ,,,，，，,，,，()()()()(()(,)(,))xyzuPxQxzRxu (d) ()(()(,))(()()()(,)),,,，,，xPxQxyyPyzQyz解:前束析取范式: ()(()(,))(()()()(,)),,,，,，xPxQxyyPyzQyz ,，,,,，,，()(()(,))(()()()(,))xPxQxyyPyzQyz ,，,，,,，,，()(()(,))(()()()(,))xPxQxyyPyzQyz ,，,,，,，()(()(,))(()()()(,))xPxQxyyPyzQyz ,，,,，,，()(()(,))(()()()(,xPxQxuyPyzQuz)),，，，,,,()()()((()(,))(()(,)))xyzPxQxuPyQuz 前束合取范式: ()(()(,))(()()()(,)),,,，,，xPxQxyyPyzQyz,，，，,,,()()()((()(,))(()(,)))xyzPxQxuPyQuz,，，，,,,,,()()()((()(()(,)))((,)(()(,))))xyzPxPyQuzQxuPyQuz,，，，,,,,,,()()()((()())(()(,))((,)())((,)xyzPxPyPxQuzQxuPyQxu,Quz(,))) 第三章 集合论 1(第46页第3题 CBC,AC,给出集合、和的例子，使得，而。 ABAB,解: Aa,{} Bab,{{},} Cabc,{{{},},} 2(第46页第6题 (2) {{1,{2,3}}} 解:设 A,{{1,{2,3}}} 则 ,(){,{{1,{2,3}}}}A,, (5) ,,(()), 解: ,(){},,, (()){,{}},,,,,, 3(第46页第9题 101(1)解:子集个数 2 1012100(2)解:元素的奇数的子集个数为 ,2 2(3)解:不会有102个元素的子集。 4(第46页第10题 解:把17化为二进制，是00010001，Baa,{,}; 1748 把31化为二进制，是00011111，Baaaaa,{,,,,} 3145678 {,,}aaa，编码为01000110，为B 26770 ，编码为10000001，为 {,}aaB18129 5(第53页第5题 (1) ()()ABCABC,,,,:证明: ()ABC,, ,,(~)ABC: ,(~)~ABC:: ,ABC::(~~) ,ABC::~() ,,ABC(): 上面是一种简单的方法，还可以利用文字叙述，任取x属于，。。。。。证明。 ()ABC,, 还有一种方法，就是利用第五章的特征函数证明，下面给出过程 ,()ABC,, ,,*,,,()()ABABC,, ,,,,(*)(*)* ,,,,,,,AABAABC ,,,(*)(1*)AABC,,,, ,,,(1)(1*)ABC,,, ,ABC,(): ,,*,,,AABC: ,,，,*(*) ,,,,,,AABCBC ,,，,(1(*))ABCBC,,,,,,,,(1)(1*)ABC,,, 所以， ,,,()()ABCABC,,,:从而可得，。 ()()ABCABC,,,,: (2) ()()ABCACB,,,,, 证明: ()ABC,, ,,(~)ABC: ,ABC::~~ ,ACB::~~ ,,()~ACB: ,,,()ACB (3) ()()()ABCACBC,,,,,,证明: ()()ACBC,,, ,,(~)(~)ACBC:: ,(~)~(~)ACBC::: ,(~)(~)ACBC::: ,(~~)(~)ACBACC::::: ,ABC::~~ ,,()~ABC: ,,,()ABC 因此， ()()()ABCACBC,,,,,, 6(第53页第9题 (1) ()()ABACA,,,: ACA,,AB:,,ABA,,解:由于，因此必有且。也就是()()ABACA,,,: AC:,,并且。 (2) ()()ABAC,,,,: AB,,,AC,,,AB,解:由于，因此必有且。也就是并且()()ABAC,,,,:AC,。 (3) ()()ABAC,,,,: 解: ()()ABAC,,: ,(~)(~)ABAC::: ,ABC::~~ ,ABC::~()因此，意味着 ()()ABAC,,,,:ABC,(): (4)()()ABAC,,,,, 解: ()()ABAC,,, ,,(~)(~)ABAC:: ,(~~(~))(~~(~))ABACACAB::::::: ,(~(~))(~(~))ABACACAB::::::: ,(~)(~)ABCABC::::: ,,ABC:() BC,,,两种可能，第一种，即B=C; ABC,:第二种，或者 ABC,~():因此，此题答案为。 BCABCABC,,,或者或者::~() 7(第53页第11题 (1) ABCABAC:::()()(),,, 证明: ()()ABAC::, ,(~())(~())ABACACAB::::::: ,((~~))((~~))ABACACAB::::::: ,(~)(~)(~)(~)ABAABCACAACB::::::::::: ,(~)(~)ABCACB::::: ,ABCCB::::((~)(~)) ,,ABC:() 因此，。 ABCABAC:::()()(),,, (2) ABCABAC:::()()(),,, 注意:这个题目本身不正确，举例如下:全集为{1，2，3}，A={1}，B={2},C={3} 则，，不相等。 ABC:(){1,2,3},,()(){2,3}ABAC::,,8(第57页第3题 解:设A，B，C分别表示骑木马、坐滑行轨道和乘宇宙飞船的儿童集合。 由公园的总收入知，||||||70/0.5140ABC，，,, ||20ABC::, |~||~||~|||55ABCABCABCABC::::::::，，，, ||||||ABACBC:::，， ,，，，3|||~||~||~|ABCABCABCABC:::::::: 因此， ,，552||ABC:: ,，5540 ,95 没有坐过任何一种的儿童总数为 |~~~|ABC:: ,,75||ABC:: ,,，，,,,，75(||||||||||||||)ABCABACBCABC:::::,,,，75(1409520) ,10 答:一共10个儿童没有坐过其中任何一种游乐设备。 9(第57页第5题 解:设A，B，C分别是学习数学、物理、生物的大一学生集合。 由题意可知， ||67,||47,||95,ABC,,, ||28,||26,||27,ABACBC:::,,, |~~~|50ABC::, |~~~|ABC:: ,,200||ABC:: ,,，，,,,，200(||||||||||||||)ABCABACBCABC:::::,,，，,,,200(674795262728+||)ABC::,50 解方程，得 ||=22ABC:: 因此，一共有22人三门功课都学。 数学E 35 5064 221464物理生物5 10(第59页第1题 (1) AB，，{1} 解: AB，，{1}={<0,1,1>,<0,1,2>,<1,1,1>,<1,1,2>} 2(2) AB， 解 2AB，,,,,,,,,,,,,,,,,,{0,0,1,0,1,1,1,0,1,1,1,1,0,0,2,0,1,2,1,0,2,1,1,2} 2(3) ()BA， 解: BA，,,,,,,,,,{1,0,1,1,2,0,2,1} 2(){1,0,1,0,1,0,1,1,1,0,2,0,1,0,2,1,BA，,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,1,1,1,0,1,1,1,1,1,1,2,0,1,1,2,1, ,,,,,,,,,,,,,,,,,,,,,,,,2,0,1,0,2,0,1,1,2,0,2,0,2,0,2,1, ,,,,,,,,,,2,1,1,0,2,1,1,1,2,1,2,0,2,1,2,1},,,,,,,,,,,,,,11(第60页第2题 ,,,32xXY，表示在在笛卡尔坐标系中，且的矩形区域内的点集。 解:,,,20y 12(第60页第3题 (1) ()()()()ABCDACBD:::，,，， 证明:任取,有 ,,,，xyABCD,()():: ,,,，xyABCD,()():: ,,,,xAByCD()():: ,,,,,,,,xAxByCyD ,,,,,,,,()()xAyCxByD ,,,,，,,,,，xyACxyBD,, ,,,,，，xyACBD,()(): ,,xy,由取值的任意性知，。 ()()()()ABCDACBD:::，,，， (2)当且仅当才，才有()()ABCABC::::, CA,ACA:,证明: 当时，，于是()()()()ABCACBCABC:::::::,,。 当()()ABCABC::::,时， xC,xABC,()::()()ABCABC::::,xABC,::()任取，可知，由知， CA,于是得到。所以，。 xA, 13(第60页第5题(这种题目也可以不推理，只要举出反例即可) (1) ()()()()ABCDACBD:::，,，， 解:任取,有 ,,,，xyABCD,()():: ,,,，xyABCD,()():: ,,,,xAByCD()():: ,,,,,,,,()()xAxByCyD ,,,,,,,,,,,,(())(())xAyCyDxByCyD,,,,,,,,,,,,,,,,()()()()xAyCxAyDxByCxByD,,,,，，，，xyACADBCBD,()()()()::: 选择A={1}，B={2}，C={a}，D={b} 则 ()(){1,,1,,2,,2,}ABCDabab::，,,,,,,,,, ()(){1,,2,}ACBDab，，,,,,,: 因此该等式不成立。 (2) ()()()()ABCDACBD,，,,，,， 解:任取,有 ,,,,，,xyABCD,()() ,,,,，,xyABCD,()() ,,,,，xyABCD,(~)(~):: ,,,,xAByCD(~)(~):: ,,,,,,,,()()xAxByCyD ,,,,,,,,()()xAyCxByD ,,,,,,,,()()xAyCxByD ,,,,,，,,,()()xAyCxByD 选择A={1，2}，B={1}，C={a，b}，D={a} ()(){2,}ABCDb,，,,,, ()(){1,,2,,2,}ACBDbab，,，,,,,,,, 因此，该等式不成立。 (3)()()()()ABCDACBD,，,,，,， 解:设A={1，2}，B={2}，C={3，4}，D={4} 则 ()(){1,3}ABCD,，,,,, ()(){1,3,1,4,2,3}ACBD，,，,,,,,,,因此，该等式不成立。 (4) ()()()ABCACBC,，,，,， 解:取,有 ,,,,，xyABC,() ,,,,，xyABC,() ,,,,，xyABC,(~): ,,,,xAByC(~): ,,,,,,xAxByC) ,,,,,,,,()()xAyCxByC,,,,,，,,,()()xAyCxByC,,,,，,,,,，(,)(,)xyACxyBC,,,,，,，xyACBC,() 因此，该等式成立。 (5) ()()()ABCACBC,，,，,， 解:任取取,有 ,,,，,，xyACBC,()() ,,,，,，xyACBC,()() ,,,,,，,,,,,,,,，,,,(()())(()())xAyCxByCxByCxAyC ,,,,,,,,,,,,,,,,(()())(()())xAyCxByCxByCxAyC ,,,,,,,,,,,,()()xAyCxBxAxByC ,,,,,,,,,,(()())xAxBxAxByC,,,,xABAByC((~)(~))::: ,,,,,xAByC ,,,,xy,()ABC,， 因此，该等式成立。 第四章 二元关系 1(第63页第2题 解: RR:,，，，，，，，，，，{1,2,2,4,3,3,1,3,4,2}12 RR:,，，{2,4}12 DR(){1,2,3},1 DR(){1,2,4},2 RR(){2,3,4},1 RR(){2,3,4},2 DRR(){1,2,3,4}:,12 RRR(){4}:,12 2(第63页第3题 解: L,,,,,,,,,,,,,,,{1,1,1,2,1,3,1,6,2,2,2,3,2,6, ,,,,,,3,3,3,6,6,6} D,,,,,,,,,,,,,,,,,,,{1,1,1,2,1,3,1,6,2,2,2,6,3,3,3,6,6,6} LD:,,,,,,,,,,,,,,,,,,,{1,1,1,2,1,3,1,6,2,2,2,6,3,3,3,6,6,6} 3(第63页第4题 证明:设D(R)=A, D(S)=B。 xAB,:xA,xB,xA,(1)任取，则分为两种情况，或。当时，由R是自反的， xB,知,,,xxR,，于是;当时，由S是自反的，知,,,xxS,，,,,xxRS,: 于是。因此不管任何情况，，，(),,xxAB:,,,xxRS,:,,,xxRS,:RS:是自反的。 xAB,:xA,xB,,,,xxR,(2)任取，则且。由R和S都是自反的，知并且 RS:,,,xxS,，于是。因此是自反的。 ,,,xxRS,: 4(第63页第5题 证明:设D(R)=A, D(S)=B。 (1)任取xAB,:，则且。由R和S都是自反的，知并且xA,xB,,,,xxR, RS:，于是。因此是自反的。 ,,,xxS,,,,xxRS,: (2)任取，则并且。由R和S是对称的，,,,xyR,,,,xyS,,,,xyRS,: RS:知并且，于是。因此，是对称的。 ,,,yxR,,,,yxS,,,,yxRS,:(3)任取，，可得，并,,,xyR,,,,yzR,,,,xyRS,:,,,yzRS,: 且，。由R是可传递的，知;由S是可传递的，,,,xyS,,,,yzS,,,,xzR, RS:知。于是。因此，是可传递的。 ,,,xzS,,,,xzRS,: 5(第63页第7题 xS,解:任取，除5外，，但，因此R是不自反的;若,,,xxR,,,,5,5R ，即，可得，知R是对称的;,,,xyR,xy，,10yxyxR，,,,,10,, ，，但，可得R是不可传递的。 ,,,3,7R,,,7,3R,,,3,3R 综上，R是不自反的、对称的、不可传递的。 6(第63页第8题 解:(1)R是集合A上的二元关系，A为空集。 (2)R是集合A上的二元关系，，。 A,{1,2}R,,,{1,1} (3)R是集合A上的二元关系，A为空集。 (4)R是集合A上的二元关系，A,{1,2,3}，R,,,,,,,{1,1,1,2,2,1， ,1,3},, 7(第69页第1题 解: 0 12 3 123 0 01001，， ,,M,1 0000R,, ,,21101 ,,30010，， 8(第69页第2题 23解:设，X中的二元关系有个。 X,{1,2,3,}2512,9(第69页第3题 2证明:集合X中的每个二元关系都是的子集，有个元素，有个元素，XX，XXX，nn 2n有 个元素，每一个元素都是XX，的一个子集，也是一种二元关系，因而，,()XX，2 2n在X中有个不同的二元关系。 2 10(第69页第4题(仅 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 关系的性质) (a)自反的、不对称的、不可传递的; (b)不自反的、反对称的、不可传递的; c)自反的、对称的、可传递的; ( (d)自反的、不对称的、不可传递的; (e)不自反的、不对称的、不可传递的; (f)不自反的、对称的、不可传递的; (g)自反的、反对称的、可传递的; (h)自反的、不对称的、不可传递的; (i)不自反的、对称的、可传递的; (j)自反的、反对称的、不可传递的; (k)自反的、反对称的、可传递的; (l)不自反的、反对称的、可传递的。 11(第70页第5题 解:， R,,,,,,,,,,,{0,1,1,2,2,3,0,0,2,1}1 R,,,,,{2,0,3,1}2 (1) RR,,,,,,{1,0,2,1}12 (2) RR,,,,,,,,{2,0,2,1,3,2}21 (3)RRR,,,,,,,,,{1,0,1,1,2,2} 121 3(4) R,,,,,,,,,,,,,,,{0,0,0,1,0,2,0,3,1,2,2,1,2,3}1 3(5) R,,2 12(第70页第6题 (1)证明:任取，由于和是自反的，因此，，xX,RR,,,xxR,,,,xxR,2112 可得，由x取值的任意性可知，是自反的。 RR,,,,xxRR,,1212 (2)设，则，不是反自RR,,,,{1,1}XRR,,,,,,,{1,2,3},{1,3},{3,1}1212 反的。 (3)设，则XRR,,,,,,,,,,,{1,2,3},{1,2,2,1},{3,2,2,3}12 ，不是对称的。 RR,,,,{1,3}12 (4)设，则XRR,,,,,,,,,,,{1,2,3},{1,2,3,1},{1,1,2,3}12 ，不是反对称的。 RR,,,,,,{1,3,3,1}12 (5)设 XRR,,,,,,,,,,,,,{1,2,3,4,5},{1,2,2,3,1,3,5,4},{2,3,12 ，则，不可传递。 ,,,,,,3,5,2,5,4,4}RR,,,,,,,,,,{1,3,1,5,2,5,5,4}12 13(第70页第7题 证明: (1)任取，则一定存在某一个，使得，yX,,,,xzRR,,,,,xyR,131 ，由知， RR,,,,yzR,123 ()(,,)，,,,,,,,yxyRyzR13 ,，,,,,,,,()(,,)yxyRyzR23 ,,,,xzRR,,23 ,,xz,根据RRRR,,,取值的任意性，问题得证，。 1323 yX,(2)任取，则一定存在某一个，使得，,,,xzRR,,,,,xyR,313 RR,，由知， ,,,yzR,121 ()(,,)，,,,,,,,yxyRyzR31 ,，,,,,,,,()(,,)yxyRyzR32 ,,,,xzRR,,32 ,,xz,RRRR,,,根据取值的任意性，问题得证，。 3132 14(第75页第4题 证明:设R是A上的二元关系， (1)若R是自反的，则，由于的转置仍是，因此，IR,，故是自反RIR,IIAAAA 的; (2)若R是反自反的，则。把和R都取转置，由于的转置仍是，因IR:,,IIIAAAA IR:,,此，，故是反自反的; RA ,,,yxR,(3)若R是对称的，任取，则，由R的对称性可知，,,,xyR, ,,,xyR,，于是。由x，y取值的任意性知，是对称的; ,,,yxR,R ,,,yxR,(4)若R是反对称的，任取，则，由R的反对称性可知，,,,xyR, ,,,xyR,，于是。由x，y取值的任意性知，是反对称的; ,,,yxR,R ,,,,,,xyRyzR,,,(5)若R是可传递得，任取，则，，,,,yxR,,,,zyR, 由R的可传递性，可知，于是。故是可传递的。 ,,,zxR,R,,,xzR, 15(第75页第5题 RR:解:R的关系矩阵上，主对角线有多少个非零值，的关系矩阵中就有多少非零记入值。 16(第79页第2题(画图略去) 解: (a)rRaabb(){,,,},,,,, sR(),, tR(),, rRaabbab(){,,,,,},,,,,,,(b) sRaaabba(){,,,,,},,,,,,, tRaaab(){,,,},,,,, (c)(图中假设b与c的连线箭头方向指向c) rRaabbccabbcca(){,,,,,,,,,,,},,,,,,,,,,,,, sRabbabccbacca(){,,,,,,,,,,,},,,,,,,,,,,,, tRabbccaacbacb(){,,,,,,,,,,,},,,,,,,,,,,,, 17(第85页第2题 121nn,CCC，，，,？22n,1nnn解: ,,,21 22 18(第85页第5题(改为判断这两个关系是否是等价关系) 解:左侧的关系不是等价关系，因为不满足可传递性;右侧的关系是等价关系。 19(第85页第7题 证明: (1)当R是个等价关系时，由等价关系的定义知，等价关系满足自反性，即R是自反的。任取，，由R的可传递性，知，再xyzX,,,,,,,,,xyRyzR,,,,,,xzR,由R的对称性，知。根据x，y，z取值的任意性，知R是循环的。 ,,,zxR, xX,(2)当R是自反的，可知对任意，。任取，使得，yX,,,,xyR,,,,xxR, 因为R是循环的，故当，时，。由x，y取值的,,,xyR,,,,yxR,,,,xxR, 任意性知，R是对称的;任取，，由R的循环性知，xyzX,,,,,,,,,xyRyzR,,, ，因为R是对称的，因此，由x，y，z取值的任意性，知R是,,,zxR,,,,xzR, 可传递的。因为R是自反的、对称的和可传递的，因此R是一个等价关系。 20(第86页第8题 证明:设等价关系造成的集合X的划分为，等价关系造成RCCCC,{,,,}？R1111121m2的集合X的划分为 CCCC,{,,,}？221222n (1) 当中的每一个等价类都包含于C的某一个等价类之中时，任取中的一个等价CC211 CCC,类C，则必包含在C的一个等价类里，设包含在中，。任取C中2j12ij21i1i CC,两元素x，y，由等价类的性质知，。由，可知若，xRy,,,xyR,12ij11 RR,则，即。由i,j,x,y取值的任意性知，。 ,,,xyR,xRy1222 RR,(2) 如果，那么对任意的? 永真，,,,xyR,,,,xyR,,,,xyR,12121 CCC等价于x,y落入的某个等价类中，,,,xyR,等价于x,y落入的某个211i2 CCC,等价类中，即若xyC,,，则，由x,y的任意性可知，,xyC,,2j12ij1i2j CC由i的任意性可知，中的每一个等价类都包含在的某一个等价类之中。 21 CRR,C综上所述，当且仅当中的每一个等价类都包含于的某一个等价类之中，才有。 2112 21(第89页第1题 解: x1 x2x6 x3x5 x4 (1) {,}xx56 (2)， {,}xx{,}xx5645 (3)，，，，，合并后，有 {,}xx{,}xx{,}xx{,}xx{,}xx5645343536 ， {,,}xxx{,,}xxx345356 (4)，， {,,}xxx{,,}xxx{,}xx34535623 (5)，，，，，，合并，得 {,,}xxx{,,}xxx{,}xx{,}xx{,}xx{,}xx34535623121316 ，，， {,,}xxx{,,}xxx{,,}xxx{,,}xxx123136345356 综上，最大相容类有四个，分别是，，，。 {,,}xxx{,,}xxx{,,}xxx{,,}xxx12313634535622(第90页第4题 证明:设 SIRR,::X ,,xX(1)由于，因此，,,,xxS,。知是自反的; IIRR,::IRR::XXX xyX,,,,,xyS,,,,xyR,(2)任取，，则或者或者,,,xyI,X ,,,xyR,xy,,,,yxS,。若,,,xyI,，则，,,,yxI,，;若XX ,,,yxR,,,,xyR,,,,,yxRR,,,,xyR,,,,yxS,，则，;若，则， ,,,yxS,,,,xyS,,,,yxS,IRR::。可知无论任何情况，，则。故是对X称的。 综上所述，既是自反的又是对称的，因此，是相容关系。 IRR::IRR::XX 23(第90页第5题 解: 111111111111，，，，，，，， ,,,,,,,,MMMM,,,,011,111,111,111 23 RRR,RR,,,,,,,, ,,,,,,,,101111111111，，，，，，，，24(第90页第6题 证明: 111，， ,,M,111 RS,,, ,,011，， RS,RS,可知不是对称的，因此，不是等价关系。 25(第90页第7题(举个例子即可) 解: RI,,,,,,,,,:{1,2,2,1,1,3,3,1}1X RI,,,,,:{1,2,2,1}2X 26(第95页第1题 24 12 8 6 4 3 2 1(1) 1291011 87 654 3 2 1(2) 27(第95页第4题 解:集合X上的恒等关系，既是偏序关系又是等价关系。 28(第95页第5题 证明:设R是A上的二元关系， IR,(a)若R是自反的，则，由于的转置仍是，因此，，故是自反RIR,IIAAAA 的; (b)若R是反自反的，则。把和R都取转置，由于的转置仍是，因IR:,,IIIAAAA IR:,,此，，故是反自反的; RA ,,,yxR,(c)若R是对称的，任取，则，由R的对称性可知，,,,xyR, ,,,xyR,，于是。由x，y取值的任意性知，是对称的; ,,,yxR,R ,,,yxR,(d)若R是反对称的，任取，则,,,xyR,，由R的反对称性可知， ,,,xyR,,,,yxR,，于是。由x，y取值的任意性知，是反对称的; R ,,,,,,xyRyzR,,,,,,yxR,,,,zyR,(e)若R是可传递得，任取，则，， R由R的可传递性，可知,,,zxR,，于是。故是可传递的。 ,,,xzR, 从上述5条可以证明(1)——(3) R(1)若R是拟序关系，即R是反自反的和可传递得，由(b)(e)可知，也是反自反的 R和可传递得，因此，是拟序关系。 R(2)若R是偏序关系，即R是自反的、反对称的，可传递的，由(a)(d)(e)可知， R也是自反的、反对称的，可传递的，因此，是偏序关系。 (3)若R是全序关系，则R是偏序关系，由(2)知也是偏序关系;另知，，,,xyA,R 或成立，当时，yRx，当时，xRy。因此不论任何情况，，xRyyRxxRyyRx,,xyA, xRy或yRx总成立。综上，也是全序关系。 R (4)举例子，设，N是自然数集合，则是良序，,,,,,,SRN,,,,,,,,SRN,, 但是不是良序。因为取全集N，在中没有最小成员。 ，，,,,,SRN,,，，,,,,SRN,, 第五章 函数 1(第100页第3题 解:Rf为正奇数的集合 2(第100页第4题 证明:f的陪域为，设值域为，假定f的陪域与值域不相等，即。,()ERRE,,()ff那么一定存在的一个元素A，使得。因为，因此，不存,()EfSSSS(,),:AR,1212f 在任何一个，使得。设，则对于任何，，SS,SSA:,SE,SE,,()SSS:,121212212 由知，由取值的任意性可知，。这与A的取值在中SSA:,SA,AE,,(),()ES1222 相矛盾，因此f的陪域与值域不相等不成立。即的陪域与值域相等。 f 3(第100页第5题 f,,,,,,,,,,,,,,,,,,{1,1,0,1,0,1,1,1,2,0,1,1,0,0,0, (1) ,,,,,,,,,,0,1,1,1,1,2,1,0,1,1,1,0}(2) R,,,{2,1,0,1,2}f 2(3) f{0,1}{0,0,0,0,1,1,1,0,1,1,1,0},,,,,,,,,, 2(4)f定义域元素的个数是9，值域元素的个数是5。求的个数，等同于求从9gAB:,个元素的集合到5个元素集合满射函数的个数。 4(第103页第1题 解:gfgxxx,,，,，，,，(3)2(3)127 fgfxxx,,，,，，,，(21)21324 fffxxx,,，,，，,，(3)336 gggxxx,,，,，，,，(21)2(21)143 fhfxx,,,，(/2)/23 hghxxx,,，,，,，(21)(21)/21/2 hfhxx,,，,，(3)(3)/2 fhgfhgfxxx,,,,,，,，，,，()(1/2)0.533.5 5(第103页第2题 (1)10种情况 f,,,,,,,{0,0,1,1,2,2}一对一f,,,,,,,{0,0,1,0,2,2}, ,f,,,,,,,{0,1,1,1,2,2}, ,f,,,,,,,{0,0,1,1,2,0} 二对一,f,,,,,,,{0,2,1,1,2,2}, ,f,,,,,,,{0,0,1,1,2,1} ,f,,,,,,,{0,0,1,2,2,2},f,,,,,,,{0,1,1,1,2,1}, ,f,,,,,,{0,2,1,2,2,2},三对一, ,f,,,,,,,{0,0,1,0,2,0},(2)4种情况 f,,,,,,,{0,0,1,1,2,2}f,,,,,,,{0,1,1,0,2,2} f,,,,,,,{0,2,1,1,2,0}f,,,,,,,{0,0,1,2,2,1}(3)3种情况 f,,,,,,,{0,1,1,2,2,0} f,,,,,,,{0,2,1,0,2,1}f,,,,,,,{0,0,1,1,2,2}6(第105页第2题 mmn,(1)当存在从X到Y的单射函数时，，单射函数有 Cm*!n mn,(2)当存在从X到Y的满射函数时，，满射函数的个数有 mmmnm,1 nCnnCnnCnn,,，,,，,,,(,1)(1)(,2)(2)(1)(,1)1？ (3) 当存在从X到Y的双射函数时，，双射函数的个数有个。 m!mn, 7(第115页第1题 证明: 任取，，因此，二元运xyI,,gyxyxyxyxxyxygxy(,)*(,),,，,,，,, 算*是可交换的; 任取， xyzI,,, gxgyz(,(,)) ,xyz*(*) ,，,xyzyz*() ,，，,,，,xyzyzxyzyz() ,，，,,,，xyzxyxzyzxyz ggxyz((,),) ,(*)*xyz ,，,()*xyxyz ,，,，,，,xyxyzxyxyz() ,，，,,,，xyzxyxzyzxyz ,gxgyz(,(,)) 因此，运算*是可结合的。 该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。 8(第116页第2题 证明:任取xyNxy,,,,，由xyxyxyx*,*,,,知，yxxy**,，*运算不 是可交换的。 任取xyzN,,,(*)**xyzxzx,,xyzxyx*(*)*,,，由，知， (*)**(*)xyzxyz,，*运算是可结合的。 xN,xxx*,任取，，可知N中的所有元素都是等幂的。 xyN,,xyx*,*运算有右么元，任取，，知N中的所有元素都是右么元。 *运算没有左么元。 ebe*,bNbe,,,证明:采用反证法。假定为*运算的左么元，取，由*的运算公式知，e ebb*,eb,be,由么元的性质知，，得，这与相矛盾，因此，*运算没有左么元。 第六章 代数系统 1(第121页第1题 证明: 首先，U和V都只含有一个二元运算，因此是同类型的; 第二，的定义域是自然数集合N，值域是，是V定义域的子集。 f{0,1}第三，验证是否运算的像等于像的运算。 任取，分情况讨论: xyN,, kkk12(1) x和y都可以表示成，设， 2xy,,2,2 kkkk1212，那么， fxfy()()1,,fxyff()(22)(2)1 ,,, fxfyfxy()()111() ,,, kkxy ，那么也不能表示成 (2) x和y都不能表示成22 , fxy()0 ,fxfy()()0,, fxfyfxy()()000() ,,, kkkxy (3) x可以表示成，y不能表示成，那么也不能表示成 222 fxy()0 ,,fxfy()1,()0,, fxfyfxy()()100() ,,, kkkxy (4) x不可以表示成，y能表示成，那么也不能表示成 222 fxy()0 ,fxfy()0,()1,,, fxfyfxy()()010() ,,, fxfyfxy()()() ,可知，无论x和y如何取值，都能够保证。 f综上所述，是U到V的同态映射。 2(第121页第2题 Uabc,，,，{,,},V,，,，{1,2,3},证明:设， 首先，U和V都仅有一个二元运算，因此U和V是同类型的; 第二，U和V的定义域大小相同，具备构成双射函数的条件; 第三，寻找特异元素，U中么元是a，右零元是c，三个元素都是等幂元;V中么元是3，右零元是1，三个元素都是等幂元。 第四，在U和V的定义域之间构造双射函数，使得。 ffafbfc()3,()2,()1,,,把*运算表中的元素都用f下的像点代替，得 3 2 1 3 3 2 1 2 2 2 1 1 1 2 1 调整表头的顺序为1，2，3，转变为下表 1 2 3 1 1 2 1 2 1 2 2 3 1 2 3 ,运算表完全相同，因此代数系统和是同构的。 跟V中，,，{,,},abc，,，{1,2,3},3(第121页第3题 解:首先，判断两个代数系统是否同类型，两个代数系统都只含有一个二元运算，因此满足同类型。 第二，判断两个代数系统定义域的基数是否相同，都是4，也满足。 第三，寻找特异元，为了方便起见，画出其运算表。 1 2 3 4 0 1 2 3 ，54 1 1 2 3 4 0 0 1 2 3 2 2 4 1 3 1 1 2 3 0 3 3 1 4 2 2 2 3 0 1 4 4 3 2 1 3 3 0 1 2 V1和V2都有么元，都没有零元，除么元外，都只有一个与自身互为逆元的元素;都没有等幂元;都满足交换律。 第四，构造映射。 么元对应么元: 10, 与自身互为逆元的元素对应与自身互为逆元的元素:42, 剩下两个元素不是特异元素，因此我随意指定一种指派: 21,33,,把的运算表中元素都换成对应的像点，构造一张新表。 5 0 1 3 2 0 0 1 3 2 1 1 2 0 3 3 3 0 2 1 2 2 3 1 0 为了便于比较跟是否一致，调整表头的顺序为0，1，2，3，如下:(也就是交换表头2，4 和3所在的列，交换表头2和3所在的行) 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 可以看出，上表跟的运算表完全一致。 ，4 因此，代数系统和是同构的，f为其同构V1{1,2,3,4},,,, V2{0,1,2,3},,,，,54 ffff(1)0,(2)1,(3)3,(4)2,,,,映射，定义如下:。 4(第123页第1题 xI,xxm,,,0,,解:首先，判断是否是等价关系。任取，由于，因此，xx,mmm aI,xyam,,,yxam,,,,xyI,,xy,是自反的;任取，若，即()，则，m xyam,,,,xyzI,,,yx,xyyz,,,，因此是对称的;任取，若，则mmmm ()，()，于是，aI,bI,yzbm,,,xzxyyzabm,,,，,,，,()()() ，因此，可知是可传递的。因此，是等价关系。 abI，,,,xz,mmm 其次，判断关于*是否满足代换性质。 ,m 任取，若，即存在某个，满足 xypm,,,xyI,,pI,xy,m k *()(mod)xxm, k *()(mod)yym, 则 k*()()(mod)xypmm,，, 01112220,,kkkkk ,，,，,，，,CyCypmCypmCypm()()()？kkkk 1122101,,,kkkkk,，,,，,，，,ypmCyCypmCypm(()())？kkk于是 1122101kkkk,,,*()*()(()())xypmCyCypmCypm,,,,，,，，,？kkk 1122101kkkk,,,,,，,，，,,pCyCypmCypmm(()())？kkk 1122101kkkk,,,由于，因此，pCyCypmCypmI,，,，，,,(()())？kkk ，关于*是满足代换性质。 ,*()*()xy,mm U综上所述，,是上的同余关系。 m 5(第123页第2题 解: xxyyI,,,,1212(1)对于+运算，在二元运算下，任取，验证下式是否成立 xRy,112行,xRy 22,,，，xxRyy1212 xxyy,,,,,1,2,1,21212取，可知满足，，但||||xxyy，,，，xRyxRy11221212 xxR，yy，即。可知对于运算+，R不满足代换性质。 1212 xxyyI,,,,1212(2)对于运算，在二元运算下，任取， , 若，，则必然满足 xRyxRy||||,||||xyxy,,11221122于是 ||||||||||||xxxxyyyy,,,,,,,12121212 可得。 xxRyy,,1212 由取值的任意性可知，对于运算，R满足代换性质。 xxyy,,,,1212 6(第123页第5题 (1) xRyxyxy,(00)(00)当且仅当,,,,,,,解:R不是上的同余关系，取则，，，，I,xyxy,,,,,,0,3,1,2,xRyxRy,11221122 xxR，yy，但是，，因此，不满足代换性质。 xx，,,,10yy，,,1012121212 (2), 当且仅当xy,,10 xRy 解:R不是上的同余关系，取，则，，但xyz,,,0,9,15xRyyRz，，，I, ，，R不满足可传递性，不是等价关系。 ||1510xz,,,xRz (3) xRyxyxy,(0)(00)当且仅当,,,,,,解:R不是上的同余关系，取取则，，，，I,xyxy,,,,,3,2,3,2,xRyxRy,11221122 xxR，yy，但是，，因此，不满足代换性质。 xx，,0yy，,,4012121212 (4) xRyxy,当且仅当, y,xyRxxy,,9,8xRy解:R不是上的同余关系，取，则，但，即，R不满，，，I, 足对称性，不是等价关系。 (第126页第2题 7 解: (1)设FFNN，,,，,,,, 2323 其中，NN，,,,,,,,,,,,,,{0,0,0,1,0,2,1,0,1,1,1,2} 23 任取,,,,,，ababNN,,, 112223 ,,,,,,,，，,ababaabb,,,1122122132 ,,,,,,,,,ababaabb,,, 1122122132 下面通过运算表构造*运算(这里仅给出了一个运算表，另一个照推) <0,0> <0,1> <0,2> <1,0> <1,1> <1,2> , <0,0> <0,0> <0,0> <0,0> <1,0> <1,0> <1,0> <0,1> <0,0> <0,1> <0,2> <1,0> <1,1> <1,2> <0,2> <0,0> <0,2> <0,1> <1,0> <1,2> <1,1> <1,0> <1,0> <1,0> <1,0> <0,0> <0,0> <0,0> <1,1> <1,0> <1,1> <1,2> <0,0> <0,1> <0,2> <1,2> <1,0> <1,2> <1,1> <0,0> <0,2> <0,1> (2)设 FFNN，,,，,,,',' 3232 其中， NN，,,,,,,,,,,,,,{0,0,0,1,1,0,1,1,2,0,2,1}32 任取 ,,,,,，ababNN,,,112232 ,,,,,,,，，,ababaabb,,,1122122132 ,,,,,,,,,ababaabb,,, 1122122132 运算表的构造方法与上同。 8(第130页第1题 (1)半群 (2)半群 (3)半群 (4)独异点，么元0 (5)不是半群，取a=b=1,c=2，则 ()1abc,,,33 abc,,,()233 不满足结合律 (6)不是半群，因为||不是二元运算; (7)半群 (8)独异点，么元0 (9)半群 (10)独异点，么元为恒等关系; (11)独异点，么元为a 9(第130页第2题 XX(2), 其中。(假定为丛X到X的双射函数) XX,{1,2,3}，，X,, 解:X到X有6个双射函数，分别用表示，设 ppp,,,？126 Xabc: ,,, pabc:1 pacb:2 pbac:3 pbca:4 pcab:5 pcba:6 构造运算表如下: , , pppppp123456 ppppppp1123456 ppppppp2215634 ppppppp3341265 ppppppp 4435126 ppppppp5562143 ppppppp6654321 第七章 图论 1(第135页第2题 (1)解:，其中，，V,{1,2,3,4}Eabcdef,{,,,,,}GVE,，，,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,{,2,4,,1,2,,1,1,,1,3,,3,2,,4,2}abcdef (2)解:，其中， V,{1,2,3,4,5,6,7,8,9}Eabcdefghi,{,,,,,,,,,GVE,，，,,, ， jkl,,},,,,,,,,,,,,{,{1,3},,{1,3},,{1,2},,{2,3},,{3,4},abcde ,,,,,,,,,,fghij,{2,4},,{2,5},,{6,7},,{7,9},,{7,8}, ,,,,kl,{8,9},,{9,9}} 2(第135页第3题 证明:简单有向图是没有自环，没有平行边的有向图，只要两个不同的节点之间才能有边。完全有向图是每个节点的出度和入度都是n-1的简单有向图，也就是每个节点都有到其他所有节点的边，因此，完全有向图的边数最多。 在完全有向图中，所有节点的出度之和为n(n-1)，所有节点的入度之和为n(n-1)，设边的个数为m，由握手定理可知，2m= n(n-1)+ n(n-1)，即m= n(n-1)，得证。 3(第136页第4题 证明:设三度正则图的结点个数为n，那么所有节点的度数之和为3n，由握手定理可知，边的个数为3n/2=1.5n，由于边的个数一定是整数，因此，n为偶数。得证。 4(第136页第5题 证明:设集会上的人一共有m个，可分为两部分，一部分为与奇数个人握手的人，设为x个，另一部分为与偶数个人握手的人，为m-x个。 由于握手是相互的，即一次握手，两个人握手的次数都加1，一共加2，因此，集会上所有人的握手次数之和为偶数。 与偶数个人握手的人，这些人的握手次数之和为(其中，aaa，，，？12mx, 都是偶数)，为偶数。 aaa,,,？12mx, 与奇数个人握手的人，这些人的握手次数之和为(其中，为bbb，，，？bbb,,,？12x12x基数)，由于所有人的握手次数之和偶数，因此也要为偶数，即bbb，，，？12x()mod20bbb，，，,？ 12x 又因为 ()mod2bbb，，，？12x ,，，，bbbmod2mod2mod2？ 12x ,xmod2 即，因此x为偶数，即与奇数个人握手的人是偶数个，得证。 xmod20, 5(第136页第6题 证明:首先，给这两幅图标上对应的结点编号，如下 12'233' 1' 4' 4566'5' 两个图的结点和边的数目都相同。假设函数 ，左图中相邻的节点是,,,,,,,,,,,,,,{1,1',5,2',3,3',4,4',5,2',6,6'}1和4，1和5，1和6，2和4，2和5，2和6，3和4，3和5，3和6，对应的像点1’和4’，1’和2’，1’和6’，5’和4’，5’和2’，5’和6’，3’和5’，3’和2’，3’和6’在右图中也相邻，因此，两图同构。 6(第136页第9题 解:这两图不同构，因为右图中有出度为3，入度为0的节点，而左图没有。 7(第144页第3题 解: (1) RvRvRvRvvvvvvv()()()(){,,,,,},,,,,1234123456 RvvvRvvRvvv(){,},(){},(){,},,,55666767 RvvvvRvvRvv(){,,},(){},(){},,,8678991010 (2)强分支7个，分别是 {},{},{},{},{},{},{,,,}vvvvvvvvvv91087651234 单项分支4个，分别是 {},{},{,,},{,,,,,}vvvvvvvvvvv910678123456 若分支3个，分别是 {},{},{,,,,,,,}vvvvvvvvvv91012345678 8(第152页第3题(仅写了意义) TA解:表示有向图逆图的邻接矩阵，即原图中如果有第i个节点到第j个节点长度为1的 TA路径，则中第j行第i列为1; TAA第i个节点和第j个节点引出的边，可以同时终止于某些结点，这些节点的个数为中第i行第j列的元素值。 TAA从某些结点引出的边，可以同时终止于第i个节点和第j个节点，这些节点的个数为中第i行第j列的元素值。 TAA,中第i行第j列对应元素为1表示从第i个节点和第j个节点引出的边，可以同时终 止于某些结点;为0表示第i个节点和第j个节点引出的边，不可以同时终止于某个结点。 9(证明以下结论。 (1)任何二叉树有基数个节点。 证明:在二叉树中，任何节点的出度不是0，就是2;假设出度为2的节点有x个，则该二叉树的出度之和为2x;设二叉树共有n个节点，这些节点中除了根节点的入度为0，其余节点的入度都为1，因此，所有节点的入度之和为n-1。由图的性质，可知二叉树的出度之和与入度之和相等。即n-1=2x， n=2x+1，因此，无论x如何取值，二叉树的节点总数n都是基数。得证。 (2)n阶二叉树的叶子节点数目为(n+1)/2。 证明:在二叉树中，出度为0的节点是叶子节点，出度为2的节点是分支节点，设分支节点个数为x，由上题证明过程可知，n=2x+1, x=(n-1)/2。因此，叶子节点的个数为n-x=(n+1)/2。 (3)n阶二叉树的高度h满足 log(n+1)-1?h? (n-1)/2 2 证明:n阶二叉树的叶子节点有(n+1)/2个，分支节点有(n-1)/2个。利用(n-1)/2个节点构造一棵一元或二元树，设树高为m，则h=m+1。 考察(n-1)/2个节点构造的一棵一元或二元树，树高最大的情况是一元树，高度为(n-1)/2-1，因此，h最大值是(n-1)/2-1+1=(n-1)/2。 树高最小的情况是构造了一棵满二叉树，满二叉树的高度x和节点个数(n-1)/2满足关系x+12-1=(n-1)/2，解得x=log(n+1)-2，因此h最小值是log(n+1)-1。因此，log(n+1)-1?h? (n-1)/2 2 10(第176页第8题 解:对于2,3,5,7,11,13,17,19,23,29,31,37,41，先组合两个最小的权2+3=5，得5,5,7,11,13,17,19,23,29,31,37,41;在所得到的序列中再组合5+5=10，得10,7,11,13,17,19,23,29,31,37,41;再组合10+7=17，得17,11,13,17,19,23,29,31,37,41;继续下去。。。。，过程如下: 2 3 5 7 11 13 17 19 23 29 31 37 41 5 5 7 11 13 17 19 23 29 31 37 41 10 7 11 13 17 19 23 29 31 37 41 17 11 13 17 19 23 29 31 37 41 17 24 17 19 23 29 31 37 41 24 34 19 23 29 31 37 41 24 34 42 29 31 37 41 34 42 53 31 37 41 42 53 65 37 41 42 53 65 78 95 65 78 95 143 238 所得到的最优二叉树如下图: 238 95143 425365781923242931343741 17111317 107 55 23 11(第176页第10题 解: 2 131 244 谢 谢 品 读～