大连理工大学软件学院离散数学习题答案

TOC\o"1-5"\h\z第一章命题逻辑2第二章谓词逻辑9第三章集合论习题答案13第四章二元关系习题答案21第五章函数习题答案42第六章代数系统习题答案51第七章群与环习题答案57第八章格与布尔代数习题答案66第九章图的基本概念及其矩阵表示71第十章几种图的介绍82第H■$树90第一章命题逻辑(1)不是命题；(2)不是命题；(3)不是命题；(4)是命题：(5)是命题；(1)并非大连的每条街都临海；(2)2不是一个偶数或者8不是一个奇数；(3)2不是偶数并且-3不是负数；3.逆命题：如果我去公园，那么天不下雨。否命题：如果天下雨，我将不去公园。逆否命题：如果我不去公园，那么天下雨。逆命题：如果我逗留，那么你去。否命题：如果你不去，那么我不逗留。逆否命题：如果我不逗留，那么你不去。(3)逆命题：如果方程无整数解，那么n是大于2的正整数。否命题：如果n不是人于2的正整数，那么方程有整数解。逆否命题：如果方程有整数解，那么n不是大于2的正整数。(4)逆命题：如果我不能完成这项任务，那么我不获得更多的帮助。否命题：如果我获得更多的帮助，则我能完成这项任务。逆否命题：如果我能完成这项任务，则我获得更多的帮助。(1)T：(2)T；(3)T；(4)F；5.(1)PQR00010011010101111000101111011111(3)PQR00000010010101111001101111011110(2)(4)略

6.P:他聪明；Q:他用功；命题：PAQoP:天气好；Q:我骑车上班；命题：Q-P。P:老李是球迷；Q:小李是球迷：命题：PVQoP:休息好；Q:身体好；命题：Q-P。7.证明：PQP>QQfPP分Q00111011001001011111&真值表:Xyz(xAy)AzxA(yAz)(xVy)VzxV(yVz)0000000001001101000110110011100001110100111111111Xyz(x—y)fzx~(yfz)(xOy)<->zxO(yOz)0000100001111101001110111100100111110111001111111可得：A,V,・是可结合的。(1)(PAQ)-R；nP；(-]PAnQ)R不依赖于命题变元的真值指派，而总取T(1)的命题公式，称为重言式(永真式)；不依赖于命题变元的真值指派，而总取F(0)的命题公式，称为永假式(矛盾式)；至少存在一组真值指派使得命题公式取值为T的命题公式称为可满足的。本题可用真值表求解：得真值表如下：PQ001011101111可见不论命题变元的真值指派如何，命题公式总取1,故为重言式。（8）得真值表如下:pQR00010011010101111001101111011111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。其他小题可用同样的方法求解。(2)原式oi((P\/Q)/\R)VPVR0-1(PVQ)V-IRVPVRo-i(PVQ)VPVToT原式oPV(n(-1QAR)VP)oPV(QV-iRVP)<=>PVQV-iR<=>"i("iPAnQAR)第(1)、(3)、(5)小题方法相同，解答略。(3)原式oiPA-iQA(RVP)o(-1PA-IQAR)V(-1PA-IQAP)o(-1PA-iQAR)VFo-I(PVQVnR)第(1)、(2)小题方法相同，解答略。(2)左式o(PV(-1QAQ))A(-1PVnQ)o(PVF)A(-1PVnQ)o(PA-iP)V(PA-iQ)oFV(PA-iQ)oPAnQ右式op/\iQ故：左式0右式，证明完毕。根据对偶式定义，该式的对偶式为：(PA-iQ)V(PAQ)V(-1PA-iQ)第(1)、(3)小题方法相同，解答略。(1)原式o(P/\(nPVQ))-Qo((PA-iP)V(PAQ))-Qo(FV(PAQ))-Qo(-]PVnQ)VQo-iPVToT原式o((-iPVQ)A(-1QVR))〜(-1PVR)o(PA-iQ)V(QA-iR)V(-1PVR)o((PA-iQ)VQ)A((PA-iQ)V-iR)V(iPVR)o(PVQ)A(-1QVQ)A(PV-iR)A(iQVnR)V(-]PVR)o(PV(QA-iR))A(-]QV-iR)V(iPVR)o((PV(QA-iR))AnQ)V((PV(QA-iR))AnR)V(iPVR)o(PAnQ)V(QA-iRA-iQ)V(PA-iR)V(QAiRAiR)V(iPVR)o(PAnQ)V(PAnR)V(QA-iR)Vi(PAnR)o(PAnQ)V(QA-iR)VToT第(2)、(4)小题方法相同，解答略。(1)证明：假设PAQ为真，则P为真且Q为真，则P-Q为真。所以：PAQ=>P-*Q。(3)证明：右侧OPVQ,假设1P\/Q为假，则P为真且Q为假，则P-*Q为假。所以：P-*Q=>P-»PAQo(5)证明：假设Q—R为假，则Q为真且R为假，则左侧为假。所以：(PV-iPfQ)-*(PV-iP-*R)=>Q-*Ro第(2)、(4)、(6)小题方法相同，解答略。(1)代入可得：(((P-*Q)〜((P~Q)fR))-*(P~Q))-*(P-Q)代入可得：((Q-*-lP)-*(-]P-*Q))(1)主析取范式：原式o(PAQ)V(PA-iQ)oni2Vm3oE(2,3)主合取范式：原式o((PAQ)VP)A((PAQ)V-iQ)oP/\(PVQ)A(PV-iQ)AToPV(QA-iQ)<=>M0AMion(o,i)主析取范式：原式o(((-1PVQ)A-1P)V((-IPVQ)AR))A(((PV-1Q)AP)V((PViQ)A-iR))o(-1PV(-]PAQ)V(-]PAR)V(QAR))A((PAQ)V(PAnQ)V(PAiR)(~iQA~iR))o((-1PA-IQ)V(-1PAQ)V(-1PAR)V(QAR))A((PAQ)V(PAnQ)(PA-iR)V(-1QA-iR))o((-iPA(-1QVR))V(QA(-1PVR)))A((PA(QVnR)V(iQA(PVnR)))oFV(QA(-1PVR)APA(QV-iR))V(iPA(~iQVR)AnQA(PVnR))VFo(PAQARAQ)V(PAQARA-iR)V(iPAnQAnR)V(iPAiRAR)o(PAQAR)V(-1PA-iQA-iR)<=>1110Vm：OE(0,7)主合取范式：原式o(-1PV(QAR))A(PV(-1QA-iR))o(-1PVQ)A(-1PVR)A(PV-iQ)A(PV-iR)o(-1PVQ)V(RA-iR)A(-1PVR)V(QAiQ)A(PVnQ)V(RAnR)A(PV-iR)V(QA-iQ)o(iPVQVR)A(-]PVQV-iR)A(iPVQVR)A(iPV-]QVR)A(PVnQVR)A(PV-iQV-iR)A(PVQV-iR)A(PVnQVnR)oMiAM2AM3AM4AM5AM6on(1,234,5,6)第(2)、(4)小题方法相同，解答略。(1)证明：左侧0(-1PVQ)A(-1PVR)o(-1PVQVR)A(-1PVQV-iR)A(-1PVQVR)A(1PVnQVR)on(4,5,6)右侧0-1pv<qar)o…on(4,5,6)左侧0右侧，得证。证明：左侧(-!PVQ)V(PAQ)o(PA-iQ)V(PAQ)oE(2,3)右侧0(PVQ)A(PV-iQ)o(PAP)V(PA-iQ)V(PAQ)V(QA-iQ)o(PA-iQ)V(PAQ)oE(2,3)左侧0右侧，得证。第(2)、(4)小题方法相同，解答略。对于A,B,C,D,E5个变元的所有真值指派，推出前提AoB,B—(CAD),Co(A\/E),AVE和结论AAE的值，得到真值表。当真值表中各前提的真值都为1时，若结论也为1,则结论有效，否则结论无效。20.(1)采用真值表证明:PQPfQP->(PAQ)0011011110001111根据真值表可看出，当前提为1时，结论也为1，则结论有效。(3)采用推理方法证明：PAQ为真，可得P为真且Q为真，又P-(Q-R)为真且P、Q为真，得R也为真。则结论有效。第(2)、(4)小题方法相同，解答略。21.(1)证明：假设公式全部同时成立，由「S为真得到S为假，由「P-S为真，得P为真，由P-Q为真得到Q为真，由QfR为真得到R为真，由rRVS为真得到S为真。这与前面“S

为假”矛盾，则公式不能同时成立。(2)证明：假设公式全部同时成立，由「S为真得到S为假，由「RVS为真得到R为假，由RVM为真得到M为真，由为真得到M为假，矛盾。则公式不能同时成立。22.首先符号化：P:人连获得冠军；Q:北京获得亚军：R:上海获得亚军；S:广州获得亚军。即求公式：P-(QVR),RfiP,S-*-|Q,P=>n1S是否成立{1}(1)PP规则{2}(2)Rf-1P规则{1,2}(3)nRTj规则⑷(4)P~(QVR)规则{1,2,4}(5)QTj规则{6}(6)S-*-|Q规则{1,2,4,6}(7)1sTj规则23.(1)证明：(1)1RP规则(2)-1QVRP规则(3)-1QT规则(1)(2)(4)-1(PA-iQ)P规则(5)-1PT规则(3)(4)(3)题目有误(5)证明：(1)PP规则(附勺件前提)(2)P~(P.AQ)P规则(3)PAQT规则(1)(2)(4)QT规则(1)(3)(5)P-QCP规贝11第(2)、(4)小题方法相同，解答略。24.(1)证明：(1)11PP规则(假i没前提)(2)PT规则(1)(3)P-*QP规则(4)QT规则(2)(3)(5)R~*~1QP规则(6)1RT规则(4)(5)(7)RVSP规则(8)ST规则(6)(7)(9)S-*-iQP规则(10)-1QT规则(8)(9)(11)QA-iQT规则(4)(10)(12)nPF规则(1)(11)(2)证明：(1)nRP规则(2)RVSP规则(3)ST规则(1)(2)（二）（二）P・QT规则（7）证明:(4)S—iQP规则(5)-iQT规则(3)(4)(6)PiQP规则(7)-1PT规则(5)(6)(P~Q)—i(RVS),(Q->P)V-iR,R=>PoQ(1)Rp规则(2)RVST规则（1）(3)-1(P-Q)f-i(RVS)P规则(4)P-QT规则(2)(3)(5)(Q-P)VnRP规则(6)Q->PT规则(1)(5)(7)(P-Q)A(QfP)T规则(4)(6)（3）原式修改为：n第二章谓词逻辑(1)S(x)：x聪明；L(x)：x好学；a：表示小明，命题：S(a)AL(a)oS(x)：x是素数;G(x,y)：x大于y,命题：(Vx)(S(x)->(3y)(S(y)AG(y,x)))U(x)：x是大学生；S(x)：x能成为科学家，命题：(3x)(U(x)A->S(x))N(x)：x是自然数;A(x)：x是奇数;B(x)：x是偶数,命题：(Vx)(N(x)-»(A(x)VB(x)))P(x)：x是诗人；T(x,y)：x游览y：V(x)：x是名山犬川；a：表示李白命题:(Vx)(P(a)AV(x)AT(a,x))(1)约束变元：x,辖域：P(x)tQ(x)和R(x,y)；自由变元：y。约束变元:P(x)VQ(y)中的x,y和R(x)AS(z)中的z；自由变元:R(x)AS(z)中的X。约束变元：x,y,辖域：P(x,y)AQ(y,z)；自由变元:z。参考教材2.3部分。(1)证明：(1)(Vx)-B(x)P(2)「B(x)US(1)(3)(Px)(「A(x)tB(x))P(4)「A(x)tB(x)US(3)(5)A(x)T(2)(4)(6)(3x)A(x)EG(5)(3)证明：由于：(0x)(A(x)tB(x))=>(Vx)A(x)t(0x)B(x)；(Vx)(C(x)->-B(x))=>(Vx)C(x)->(Vx)「B(x)；(Vx)(C(x)^_1A(x))=>(Vx)C(x)—>(Vx)-'A(x)即证：(Vx)A(x)t(Vx)B(x),(Vx)C(x)t(Vx)「B(x)=>(0x)C(x)t(Vx)「A(x)(1)(Vx)C(x)p(附加)(2)C(x)US(1)(3)(Vx)C(x)^(Vx)「B(x)p(4)C(x)t「B(x)US(3)(5)「B(x)T(2)(4)(6)(Vx)A(x)-^(Vx)B(x)p(7)A(x)tB(x)US(6)(8)「A(x)T(5)(7)(9)(Vx)~A(x)UG(8)(10)(Vx)C(x)t(Vx)_1A(x)CP(1)(9))、(4)小题方法相同，解答略。证明：(1)(Vx)P(x)p(附加)(2)P(x)US(1)(3)(Vx)(P(x)^Q(x))p(4)P(x)tQ(x)US(3)(5)Q(X)T(2)(4)(6)(Vx)Q(x)UG(5)(7)(Vx)P(x)t(0x)Q(x)CP(1)(6)

证明:由于:(Vx)P(x)V(3x)Q(x)ogx)「P(x)->(3x)Q(x)即证:(Vx)(P(x)VQ(x))=>(mx)「P(x)—>(3x)Q(x)(1)(3x)-P(x)p(附加)(2)「P(x)ES(1)(3)(Vx)(P(x)VQ(x))P(4)P(x)VQ(x)US(3)(5)Q(x)T(2)(4)(6)(3x)Q(x)EG(5)(7)(3x)-P(x)Tgx)Q(x)CP(1)((1)W(x)：x喜欢步行；C(x)：x喜欢乘汽车；B(x)：x喜欢骑自行车:即需证：(Vx)(W(x)->「C(x)),(Vx)(C(x)VB(x))>(3x)-B(x)=>(3x)-W(x)证明：(1)(3x)-B(x)p(2)「B(x)ES(1)(3)(Vx)(C(x)VB(x))P(4)C(x)VB(x)US(3)(5)C(x)T(2)(4)(6)(Vx)(W(x)Y(x))p(7)W(x)t-C(x)US(6)(8)「W(x)T(5)(7)(9)(3x)^V(x)EG(8)(3)F(x)：x是资深人士；S(x)：x是院士；P(x)：x是参事;C(x)：x是委员：a：即需证：(Vx)(F(x)^(S(x)VP(x))),(Vx)(F(x)tC(x)),F(a)A-S(a)=>(3x)(C(x)AP(x))证明：(1)(Vx)(F(x)tC(x))p(2)F(a)TC(a)US(1)(3)F(a)A~1S(a)p(4)F(a)T(3)(5)C(a)T(2)(4)(6)(Vx)(F(x)t(S(x)VP(x)))p(7)F(a)TS(a)VP(a))US(6)(8)-S(a)T(3)(9)P(a)T(4)(7)(8)(10)C(a)AP(a)T(5)(9)(11)(3x)(C(x)AP(x))EG(10)第(2)、(4)小题方法相同，解答略。伟;(d)是错误的。错误。第二行的y是泛指，第四行的y是特指。修改如下：(1)(3x)P(x)p(2)P(x)ES,(1)(3)(\/x)P(x)tQ(x)p

(4)P(x)tQ(x)US,(3)(5)Q(x)T,(2),(4)和Iio(6)(3x)Q(x)EG，(5)9.(1)证明:(1)(3x)P(x)p(2)P(a)ES(1)(3)(3x)Q(x)P(4)Q(b)ES(3)(5)(3x)P(x)t(\/x)((P(x)VQ(x))->R(x))P(6)(Vx)((P(x)VQ(x))^R(x))T(1)(5)(7)(P(a)VQ(a))TR(a)US(6)(8)P(a)VQ(a)T(2)(9)R(a)T(7)(8)(10)(P(b)VQ(b))TR(b)US(6)(11)P(b)VQ(b)T(4)(12)R(b)T(10)(11)(13)R(a)AR(b)T(9)(12)(14)(3y)(R(a)AR(y))EG(13)(15)(3x)(3y)(R(x)AR(y))EG(14)(2)证明:(1)(3x)P(x)^(Vx)Q(x)p(假设)(2)「(3x)P(x)V(Vx)Q(x)T(1)(3)(Vx)-P(x)V(Vx)Q(x)T(2)(4)(Vx)rP(x)VQ(x»T(3)(5)(Vx)(P(x)^Q(x))T(4)10.(1)原式o(0x)(「P(x)Vgy)Q(y))^(Vx)(3y)(-P(x)VQ(y))(3)原式<=>(Vx)(3y)A(x,y)V(3x)(Vy)(B(x,y)A(Vy)(A(x,y)->B(x,y)))<^>(Vx)(3y)A(x,y)V(3u)(Vv)(B(u,v)A(Vz)(「A(z,u)VB(u,z)))<^>(Vx)(3y)(3u)(Vv)(Vz)(A(x,y)V(B(u,v)A(-A(z,u)VB(u,z))))11.(2)解：前束析取范式：(Vx)(P(x)t(Vy)((Vz)Q(x,z)t^(Vy)R(x,y)))O(0x)(「P(x)v(Vy)((Vz)Q(x,z)t-.(Vy)R(x,y)))O(0x)(「P(x)v(Vy)(^(Vz)Q(x,z)v->(Vy)R(x,y)))O(0x)(「P(x)v(Vy)(-.(Vz)Q(x,z)v-,(Vu)R(x,u)))O(Vx)(->P(x)v(Vy)((3z)->Q(x,z)v(3u)^R(x,u)))o(Vx)(Vy)(3z)(3u)(^P(x)v(」Q(x,z)v-R(x,u)))O(Vx)(Vy)(3z)(3u)(^P(x)v->Q(x,z)v->R(x,u))由于「P(x)v-1Q(x,z)v^R(x,u)是基本和，因此前束合取范式与前束析取范式一样:(Vx)(P(x)t(Vy)((Vz)Q(x,z)t-n(Vz)R(x,y)))O(Vx)(Vy)(3z)(3u)(-.P(x)v^Q(x,z)v^R(x,u))解：前束析取范式：(Vx)(P(x)->Q(x,y))->((3y)P(y)A(3z)Q(y,z))o->(Vx)(P(x)->Q(x,y))v((3y)P(y)a(3z)Q(y,z))O-n(Vx)(^P(x)vQ(x,y))v((3y)P(y)A(3z)Q(y,z))o(3x)(P(x)aQ(x,y))v((3y)P(y)A(3z)Q(y,z))O(3x)(P(x)aQ(x,u))v((3y)P(y)a(3z)Q(u,z))O(3x)(3y)(3z)((P(x)aQ(x,u))v(P(y)AQ(u,z)))前束合取范式：(Vx)(P(x)TQ(x,y))T((3y)P(y)A(3z)Q(y,z))O(3x)(3y)(3z)((P(x)aQ(x,u))v(P(y)aQ(u,z)))o(3x)(3y)(3z)((P(x)v(P(y)AQ(u,z)))a(Q(x,u)v(P(y)AQ(u,z))))O(3x)(3y)(3z)((P(x)vP(y))A(P(x)vQ(u,z))a(Q(x,u)vP(y))A(Q(x,u)vQ(u,z)))第三章集合论习题答案对应课本页数：P51-541.写出下列集合的表达式。所有一元一次方程的解所组成的集合：答案：集合可表示为Wax+b=O,a,beR}x'-l在实数域中的因式集。答案：集合可表示为{1，X-1,X+1,X?-X+1,X’+X+1,X’-1,X’+1,X6直角坐标系中，单位圆内(不包扌舌单位圆)的点集。答案：集合可表示为{"y>lx2+y2"}极坐标系中单位圆外(不包括单位圆)的点集。答案：集合可表示为{V%y>1X>cos&,y>sin&s[0,2刃}能被5整除的整数集。答案：集合可表示为Wx=5n,nel}2•解：设戏剧、音乐、广告分配的时间分别为x,y,z⑴x+y+z=30严y,z=511,11g1}⑴可表不为{<y,z>|x+y+z=30,x>y,x,y,z=5n,ne1}可表不为{<x,y,z>|x+y+z=30、z=xvz=y,x,y,z=5n,ne1}⑷可表示为{<x,y,z>|x+y+z=30,y=5,x,y,z=5n,ne1}给出集合A、B和C的例子，使得AeB,BeC而AgC。解：A={a}B={{a},b}C={{{a},b},c}确定下列命题是否为真。该命题为真命题该命题为假命题该命题为真命题该命题为真命题该命题为真命题该命题为真命题该命题为真命题该命题为假命题。AcB,AeB是可能的么，给予证明。解：口J能。若A={1},B={1,2,{1}},则A^B且AwB。6.{a,{a}}解：设A={a,{a}}则0(Q={0，{a},{{a}},{a,{a}}}⑵{{1,{2,3}}}解：设A二{{1,{2,3}}}则P(A)={0,{{1,{2,3}}}}⑶{0,a,{b}}解：设A={0,a,{b}}则q(厲={0,{0},{a},{b},{0,a},{0,{b}},{a,{b}},{0,a,{b}}}⑷Q(0)解：设A=p(0)={0}则q(A)={0,{0}}⑸03(0))解：设A=p(Q(0))={0,{0}}则p®={0,{0},{{0}},{0,{0}}}设A={0},B=P(玖◎)解：A={0}p(A)={0,{0}}B=P3E={0,{0},{{0}},{0,{0}}}0eB,0oB{0}eB,{0}cB⑶{{0}}eB,{{0}}gB&设某集合有101个元素，试问：可构成多少个子集：2101其中有多少个子集的元素为奇数：2】00是否会有102个元素的子集：不会9.解：把17化为二进制,是00010001,={a4,a8}；把3i化为二进制，是00011U1,B31={a4,a5,a6,a7,a8}{a2,a6,a7},编码为o1000110,为B?。{坷,％},编码为10000001,为B^9求AUB,AnBo解：A={0,1,2,3,4}B={2,4,6}AUB={0,l,2,3,4,6}AAB={2,4}解：A={b,o,k}B={b,l,a,c,k}AljB={b,l,a,c,k,o}AAB={b,k}解：A={1,2,7,8}B={1,2,3,4,5,6,7}C={0,3,6,9,12,15,1&21,24,27,30}D={1,2,4,8,16,32,64}AU(BU(CUD))={0,1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,30,32,64}An(Bn(CAD))=0AUC={0,l,2,3,6,7,&9,12,15,18,21,24,27,30}⑶B-(AUC)二{4,5}AAB={3,4,5,6}〜(AHB)UD={1,2,3,4,5,6,8,16,32,64}13-证明对于所有集合A,B,C有(AHB)UC=AQ(BUC),当且仅当CqA。证明：充分性：由于(AT)B)UC=An(BUC)=(AC|B)U(AnC)所以C=AAC,即CoA充分性得证。必要性：由于CoA所以C=AAC所以(ADB)UC=(ACB)U(AnC)必要性得证。证明对所有集合A,B,C,有:(A-B)-C=A-(BUC)证明：(A-B)-C=(仆B)-C=(仆B)n〜C=AR(〜B.〜C)=M〜(BUC)=A-(BUC)(A-B)-C=(A-C)-B证明：(A-B)-C=(茁〜B)-C二朋〜br〜c=帕〜cn〜b=(A-C)C|〜B=(A-C)-B(A-B)-C=(A-C)-(B-C)证明：(A-C)-(B-C)=(AQ〜C)_(BD〜C)=(朋〜c)n〜(br〜C)=(仆c)n(〜buc)=(aa〜cn〜b)u(ah〜cnc)二仆EC〜C=(A-B)n-C=(A-B)-C因此，(A—E)—C=(A—C)—(E—C)确定卞列各式的运算结果。解：00{0}=0{0}n{0}={0}{0,{0}}_0={0,{0}}{0,{0}}-{0}={{0}}16-假设A和B是E的子集，证明下列各式中每个关系式彼此等价。证明：证明AuEO~BU~A。充分性：若AoB,则若xeA,那么必有xeBo因此，若x《B,则必有x^A,即TfxB,贝I」有xG~A,即~BA；必要性：若~BC~A,则若xG~B,则有xG~A,即若xgB,则必有X那么，若XWA，那么必有xeB»即AOB:由以上两点可知：AuBO~BAo证明：AuEOAUB=B充分性：若xgAUB,那么有xeA或xwB。若xeA,则由AuB口J■知，必有xwB,所以若xgAUB,必有xeB,即AUBcB；若xeB,那么必有XGAUB,即BcAUB,所以AUB=B,充分性得证；必要性：因为AUB=B,所以，对于任意的XGAUB,必有XeB,所以AoB,必要性得证；由以上两点可知：AyBOAUB=B证明：AuEOACB=A充分性：若XGACIB,那么必有xeA,即AHBcA；若xeA,那么由AoB可知，必有XWB,所以xgADB,即AcAflB,所以，AAB=A；必要性：因为Aab=A,所以对于任意的xeA,必有XGAAB,XEB,所以AoB:由以上两点可知，AuBOACB=A。由以上三点可知，AuBO~BC~A<=>AUB=B<=>ACB=A。⑵证明：aAb=0oac~b充分性：因为AflB=0,所以对于任意的x,若xeA,则必有x住B,即XSB,所以A匸~B；必要性：因为ASB,所以对于任意的X,若XeA,则必有XSB,即X€B,所以AHB=0：由以上两点可知：aAb=0oa匸~B证明：AC|E=0OBC~A充分性：因为AflB=0,所以对于任意的X,若XWB,则必有X住A,即XSA,所以A；必要性：因为BC~A,所以对于任意的X,若XEB,则必有XSA,即X€A,所以AHB=0：由以上两点可知：aAb=0ob匸~A.由上可知：aAb=0u>ac~b<=>bc~a.⑶证明：AUB=E<=>-AcB充分性：因为aub=e,所以若xgA,则必有xeB.即若xg~a,则必有xgB,所以~ACB；必要性：因为AU~A=E,又~ACB,必有AUB=E：由以上两点可知：AUB=E<=>~ACB证明：AUB=EQ~BcA充分性：因为aub=e,所以若xUB,则必有xwA,即若xB.则必有xwA,所以~BcA；必要性：因为BU~B=E,又~BcA,必有AUB=E；由以上两点可知：AUB=E<=>~BcA.由上可知：AUB=E<=>~ACB<=>~B匸A,证明：A=B<=>A㊉B=4)充分性：由^A=B,所以AC~B=A=4)所以A㊉B=(AB)U(BA)=4)必要性：因为A㊉B=(AA-B)U(BA-A)=4)所以AB=4)且BA=4)因为AC~B=4所以ACB又BA-A=4),所以BcA所以A=Bo由上可知：A=B<=>A㊉B=e。17-化简下述集合公式。结果：AAB结果：A-B结果：A结果：CA(AUB)1&设A,B,C是任意集合，分别求使得下述等式成立的充分必要条件。BcABAA=0B=A=0B=AB=0B=A(A-B)n(A-C)=A解：由于(A-B)n(A-C)=A,因此必有A-B=A且A—C二A。也就是Ap|B=0并且AQC=0°(A-B)U(A-C)=0解：由于(A-B)U(A-C)=0,因此必有A-B=0且A—C=0。也就是AcB并且AcCo（9）（A-B）n（A-C）=0解：（A-B）p（A-C）=（曲〜B）n（AH〜C）=帕〜BR〜C討〜（BUC）因此，（a-b）D（a-c）=0意味着Ac（BUC）（10）（A-B）®（A-C）=0解：（A-B）㊉（A—C）=（朋〜B）㊉（M〜C）=（朋〜br〜（朋〜c））u（却〜cn〜（ah〜B））=（仆br（〜auc））u（m〜cn（〜aub））=（朋〜Bnc）u（A・Bn〜C）=Ap（B㊉C）两种可能，第一种B㊉C=0,即B二C：第二种，AoBQC或者A匚〜（BUC）19-借助文氏图，考察下列命题的正确性。设A,B,C为任意集合，是判断下面命题的真假。如呆为真，给出证明，否则给出反例。设在10名青年中有5名是工人，7名是学时，其中兼具工人与学生双重身份的青年有三人，求既不是学生也不是工人的青年有多少？设A,B分别代表工人、学生，贝IJ：|AUB|=10,|A|=5,|B|=7,|AnB|=3；则：10-5-74-3=1所以既不是学生也不是工人的青年有1人。22-求1到250之间能够被2,3,5,7中任何一个整除的整数的个数。设|4|=1250/2J=125,|B|=[250/3」=83,|G=[250/5J=50,|D|=[250/7J=35则所求的答案表达式为/UBUCUDI。求解:|4UFUCUD|=125+83+50+31-(41+25+17+16+11+7円8+5+3+2)・(1)=189;所以,这样的数共有189个。解：设A,B,C分别表示参加足球队、篮球队和棒球队的队员的集合|AnBAC|=3|AUBUC|二|_A|+|B|+|C|TACIBHACICHBCICI+IAClBPlCln|AHBI+IAnC|+|BnC|=|A|+|B|+|c|+|AnBnC|-|AUBUC|=38+15+20+3—58=18即同时参加两个对的队员共有18个。解：设A,B,C分别表示读甲种、乙种、丙种杂志的学生的集合。⑴|AnBnc|=10%14=60%|B|=50%|B|=50%AAB|=30%|BDC|=30%|AT|C|=30%Iaabti〜c|+iApen〜E|+|BCicn〜ai=|aciB|+|Bnc|+|Anc|-3|AnBnc|=30%+30%+30%-3*10%=60%所以确定读两种杂志的学生的百分比为60%。⑵卜扪〜BCI〜C|=100%—(ADCD〜B|+|BDcn〜A|+|ADBCl〜C|+|ADBnc|)=100%-(60%+10%)=30%所以不读任何杂志的学生的百分比为30%。第四章二元关系习题答案对应于课本88-93页如果A二{0,2}和B二{1,2},试求下列集合。Ax{1}xB解：Ax{l}xB={<0,1,1>产0,1,2>产1,1,1>产1,1,2>}A^xB解A2xB={<0,0,1>,<0,1,1>,<1,0,1>,<1,1,1>,<0,0,2〉,<0,1,2>,<1,0,2>,<1,1,2〉}⑶(BxA)2解：BxA={<1,0>,<1,1>,<2,0>,<2,1>}(BxA)2={«1,0〉,<1，0»,«1,0>,<1,1»,«1,0>,V2,0»,«1,0〉,V2,1»,«1，1>,<1,0>>,«1，1〉,<1,1»,«1,1>,<2,0>>,«1,1>,v2,1»,«2,0>,v1,0»,«2,0>,<1,1»,«2,0>,<2,0»,«2,0>,<2,1»,«2,1〉,<1，0»,«2,1>,<1,1»,«2,l>,<2,0〉〉,«2,1〉,<2,1»}2.解：XxY表示在在笛卡尔坐标系中，-3<X<2且-2'ySO的矩形区域内的点集。3.(AAB)x(CnD)=(AxC)n(BxD)证明：任取<x,y>e(ADB)x(cnD),有<x,y>e(AHB)x(CHD)<=>xe(AQB)aye(CHD)<=>xeAaxgBayeCayeD<=>(xgAayeC)a(xgBayeD)<=><x,y>GAxCa<x，y>gBxD<=><x,y>G(AxC)n(BxD)由ny>取值的任意性知，(AnB)x(cnD)=(Axc)n(BxD)o当且仅当才，才有(AQB)UC=AH(BUC)证明：当CoA时，AUC=A,于是(AnB)UC=(AUC)n(BUC)=An(BUC)o当(AAB)UC=AH(BUC)时，任取XeC,可知xw(AHB)UC,由(AAB)|JC=AD(BUC)知xwAH(EUC),于是得到XeAo所以，CuA。证明：必要性：若A=0,AxB=BxA=0.同理，若B=0,AxB=BxA=0.若A=B,则显然有AxB=BxA;必要性得证。充分性性：由于AxB=BxA所以对于任意的V爼y>eAxE,必有vx,y>eBxA<x,y>eAxBoxcAayeB<x,y>eBxAoxcBayeA即若xwA则必有xeB.若ywE,则必有yeA,所以当a工时，A=B.■充分性得证。5.(1)(AUB)x(CUD)=(AxC)U(BxD)解：任取<x,y>e(AUB)x(CUD)有<x,y>e(AUB)x(CUD)oxw(AUB)Aye(CUD)<=>(xeAvxeB)A(yeCvyeD)<=>(xeAA(yeCvyeD))v(xeBA(yeCvyeD))<=>(xeAayeC)v(xeAayeD)v(xeBAyeC)v(xeBAyeD)<=><x,y>e(AxC)U(AxD)U(BxC)U(BxD)选择A二⑴，B二⑵,C二{a},D={b}则(AIJB)x(CUD)={vl,a>,vl,b>,v2,a>,<2,b>}(AxC)U(BxD)={<l,a>,<2,b>}因此该等式不成立。(A-B)x(C-D)=(AxC)-(BxD)解：任取<x,y>e(A-B)x(C-D),有<x,y>e(A-B)x(C-D)U>vx,y>w(AA〜E)x(cn〜D)Oxe(AQ〜B)ayg(CH〜D)O(xeAax^B)A(yeCAy^D)O(xeAayeC)a(x^BayD)O(xeAayeC)a(x^BayD)O(xeAayeC)a^(xgBvygD)选择A={1,2},B二⑴，C={a,b),D={a}(A-B)x(C-D)={<2,b>}(AxC)—(BxD)={<l,b>,<2,a>,v2,b>}因此，该等式不成立。(A6)B)x(C®D)=(AxC)©(BxD)解：设A二{1,2},B二⑵，C二{3,4},D二⑷则(A©B)x(C®D)={<1,3>}(AxC)®(BxD)={<1,3>,<1,4>,<2,3>}因此，该等式不成立。(A-B)xC=(AxC)-(BxC)解：取<x,y>e(A-B)xC<x,y>e(A-B)xCO<x,y>w(AQ〜B)xCOxe(AH〜B)aygCOxgAax^B)AyeCo(xeAayeC)a(x^Bvy^C)O(xeAayeC)a->(xgBaygC)O(<x,y>gAxC)a(<x,yBxC)O<x,y>e(AxC-BxC)因此，该等式成立。(A©B)xC=(AxC)©(BxC)解：任取取Sy〉"AxC)㊉(BxC),有<x,y>e(AxC)3(BxC)O((xgAayeC)A-«(xeBayeC))v((xgBayeC)a->(xgAayeC))O((xgAAyeC)a(x^Bvy^C))v((xeBayeC)a(x^AvygC))O(xgAayeCAX^B)v(x^AaxgBayeC)O((xgAax^B)v(x^AaxgB))ayeCOxe((Ap~B)UApB))ayeCOxeA®BayeCO<x,y>e(A©B)xC因此，该等式成立。存在集合A使得ACAxA；取人=0,则该命题成立。P(i4)xP(/4)=P(Ax>4)假设结合A有n个元素，则PQ4)有2*个元素，贝炉⑷XPQ4)共有2?n个元素；则4x4有I?个元素，PQ4X4)则有2十个元素，显然两者元素数不一样，故命题不成立。设A={1,2,3,4},列出以下关系RoR={〈x,y)k，y6AA%+y=#2}解：R={(1,2),(1,3),(1,4),⑵1〉，⑵2〉，(2,3),〈2,4〉，〈3,1〉，〈3,2〉，(3,3),〈3,4),〈4,1〉，〈4,2〉，〈4,3),(4,4)}R={〈x,y〉|x,y6AA|x-y|=1}解：R={(1,1),(1,3),〈1,4),(2,2),〈2,4),(3,1),〈3,3〉，〈4,1〉，〈4,2〉，〈4,4)}R=[{xfy}\xfy6AKx/yEA}解：R={(1,1),(2,1),〈2,2〉，(3,1),(3,3),(4,1),(4,2〉，〈4,4)}R={〈x,y〉k，yG4/\y为素数}解：R={(1,2),(1,3),〈2,2〉，(2,3),〈3,2〉，〈3,3〉,〈4,2),(4,3〉}列出集合人={2,3,4}上的恒等关系必和全域关系殆。解：弘={〈2,2〉，〈3,3〉，〈4,4)}；oEa={〈2,2〉，〈2,3〉,(2,4),〈3,2),〈3,3),〈3,4〉,(4,2),〈4,3〉，〈4,4〉}给出下列关系R的所有序偶。⑴A={0,1,2},B={0,2,4}R={<x,y>|x,yeAQB}解：AOB={0,2}R={<0,0>,<0,2>,<2,0>,<2,2>}A={1,2,3,4,5},B={1,2,3}R={<x,y>|xGAaygBax=y2}解：R={<1,1>,<4,2>}设％和&都是从A={1,2,3,4}到：8={2,3,4}的二元关系，并且Rj={<1,2>,<2,4>,<3,3>}R2={<U>,<2,4>,<4,2>}求RUR-RiflR-D(Rj、d(rJr(rJr(rJdCrUrJ、斑风门企)。解：R,UK={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}RiAR>={<2,4>}。(尺)={1,2,3}D(R.)={1,2,4}1^(^)={2,3,4}R(Rj={2,3,4}。(叫u巴)={123,4}斑耳门尽)=(4,4}fid®-&)=fld({(l,2),(3,3〉})={1,2}U{2,3}={1,2,3}弘。&={〈1，4),〈2,2〉}/?2。心={〈1,3〉,〈4,4)}Ri={4,4〉,(3,3〉}能={(4,4〉,⑵2)}设集合A={1,2,3},问A上有多少种不同的二元关系。解：232=512种关系。设关系R={〈0,1),〈0,2〉，(0,3),〈1,2),(1,3),(2,3)},求RoR,H,R|{1,2},R[{1,2}]解：R°R={(0,2),(0,3〉，(1,3)}R-1={〈1,0),〈2,0),〈3,0),(2,1),〈3,1),〈3,2〉}R|{1,2}={〈1,2),(1,3〉，(2,3)}R[{1,2}]={2,3}设关系R={〈0,{0,{0}}〉，〈{0},0)},求R-l,R2,r3,r|{0},R|0,R|{{0}},R[0],R[{{0}}]°解：R-1={({0,{0}},0),(0,{0}〉}R2={〈{0}，{0，{0}}>}R3=0R|{0}={(0,{0,{0}})}R|0=0R|{{0}}={({0}，0)}R[0]=0说明以下关系R具有那些性质并说明理由。:反自反的、反对称的、可传递的；:反自反的、对称的、不可传递的；:自反、对称、可传递：：自反、对称、可传递：设A是所有人的集合，定义A上的二元关系R1和R2,说明R1和R2具有哪些性质。解：R1具有的性质：反自反的、反对称的、可传递的：R2具有的性质：自反、对称、可传递；设氏和见是集合X中的二元关系。试证或反证下列命题：如果是自反的，则氏。％也是自反的。如呆耳和巴是反自反的，则尽。巴也是反自反的。如呆巴和巴是对称的，则為。！^也是对称的。如果巴和见是反对称的，则氏。％也是反对称的。如果R】和巴是可传递的，则氏。％也是可传递的。解：(1)证明：任取xeX,由于R和R?是自反的，因此VX’X'WR,可得由x取值的任意性可知，尺。&是自反的。⑵设X二{1,2,3},^={<1,3〉}也二{<3,1〉},则R1oR2={<i,i>},不是反自反的。设X二{1,2,3},R={<1,2〉,<2,1〉},&={<3,2>,<2,3〉},则R1oR2={<1,3>},不是对称的。设X={1,2,3},!^={<1,2>,<3,1>},!<.={<1,1>,<2,3>},则R1oR2={<1,3>,<3,1>},不是反对称的。设X={1,2,3,4,5},={<1,2>,<2,3>,<1,3>,<5,4>},R2={<2,3>,<3,5〉,<2,5〉,<4,4〉},则RjoR.={<1,3>,<1,5>,<2,5>,<5,4>},不可传递。证明：若r是集合a上的自反和可传递关系，则RoR=R2证明：任意取x,yGA,〈x,y)ER,由于R是集合A上的自反,则可知(y,y)，(x,x〉ER,则R={(x,y),〈x,y),(y,y),(x,x)}R。R={(x,y),〈x,y),(y,y),〈x,x)}=R;如果关系R和S都是自反的。证明：RUS,RAS也是自反的。证明：设R是集合A上的二元关系，S是集合B上的二元关系。因为R和S都是自反的，所以对于VxeA,都有v%x>wR,对于VxeB,都有vx,x>eS。设xgAUB,那么xeA或xwB。若xeA,有vx,x>wR,那么必有vx,x>eRUS。若xeB,有vx,x>wS,那么必有vx,x>eRIJS。因此，当xgAUB时，必有vx,x>eRUS,所以RUS也是自反的。(2)设XGATIB,那么XGAfcLxeB因此vx,x>wR且vx,x>wS，即vx,x>eRClS。所以RAS也是自反的。证明：如果关系R和S都是自反的、对称的、可传递的，证明：RQS也是自反的、对称的和可传递的。证明：设R是集合A上的二元关系，S是集合B上的二元关系。自反性的证明如题4。对于任意的X,yeAp|B»若vx,y>wRflS,那么vx,y>gR且vx,y>wS因为R和S都是对称的，所以vy,x>wR且vy,x>wS,所以vy,x>eROS。即对于任意的x,yeAQB,若vx,y>eRnS,则必有<丫，X>WRDS,所以RQS是对称的。对于任意x,y,zeAOB，若vx,y>wRflS且vy,z>wRflS,那么有vx,y>eR,<y,z>eRLLvx,y>eS,<y,z>eSo因为R和S都是可传递的，所以有vx,z>wR且vx,z>wS,即vx,z>eRflSo即对于任意x,y,zeApB,若<x,y>eROS且vy,z>eRDS,都有<x,z>eRp|So所以RQS是可传递的。设集合A是有限集，且R|=n,求：A上有多少不同的对称关系。解：2n(n+1)/2因为|A|=njAxA|=if也就是说集合A有n平方个有序对，由对称定义可知，对于a,beA,只耍(a,b)e有(b,a)wR。另外知道在n平方个有序对中有n个有序对((X’,XJ其中i=l,2,3.....n),相应的就有n2-n个有序对(X,Y)且XHY,定义可知后面的n?-n个有序对只能成对出现，所以有(n2-11)/2对。前面的那n对可以出现任意多对。图片如下。(屮(2,”•……(n,n)f(l,2)(1,3)………(n-l,n)ln个有序对1(2,1)(3,1)(n,n-l)J(n2-n)/2个有序对对―共有11+(£-11)/2个元素

即(i『+n)/2个所以得到对称关系数为：2心】"A上有多少不同的反对称关系。由定义：如果a,beA?仅当a=b时(a,b)wR和(b’a)wR如下图。(n-l.ii)(n-l.ii)(n>n-l)(1,1)(2,2)(n,n)n个有序肝这n个有序对可以出现任意多次

'(12)(13).(2,1)(3,1)J(n2-n)/2个有序对对2n3n(n-1)/2(由62n所以得结果:2nx3n(n'1)/2即2“3心"2A上有多少不同的既非自反又非反自反的关系。解：2U'-2-2n(n-1)试着画出R的关系图并写出对应的关系矩阵。01230"1001解：Mr=100002110130010关系图如下：21-设A={0丄2,3},&和出是A中的关系，Rj={<1,j>|j=i+1vj=1/2}%={<i.,j>1i=j+2}试求出关系矩阵：MRj；Mr?:MrOMR2MroM&oMr；M&3。解：$={v0,0>5<0,1>,<1?2>,<2,3>,<2,1>}兀={<2,0>,<3,1>}由此可得：凡。巴={v1,0>?<2,1>}

巴。R={v2,0>,<2,1>,<3,2>}R。％。R={v1,0>,<1,1>,<2,2>}R/={<0,0>,<0,1>,<0,2>,<0,3>,<1,2>,<2,1>,<2,3>}所以:1100000000100000Mr=mr=二內0101K-21000000001000000000010000000Mr。MRj—0100Mr2°Mr:"1100000000100000111111000010oMR2°Mr.=0010叫=01010000000022.给定集合A={1,2,3}。图4-6给出了A中的关系R的12个关系图。对于每个关系图,写出相应的关系矩阵，并证明被表达的关系是否是自反的或反自反的；是否是对称的或反对称的；是否是可传递的。（1）自反的、不对称的、不可传递的；其对应的关系矩阵为：110MR=111101（2）不自反的、反对称的、其对应的关系矩阵为：不可传递的；110Mr=001100

（3）自反的、对称的、可传递的;其对应的关系矩阵为：11Mr=1111111(4)自反的、不对称的、其对应的关系矩阵为不可传递的：■■110Mr=O11111(5)不自反的、不对称的其对应的关系矩阵为、不可传递的；••010Mr=111110(6)不自反的、对称的、其对应的关系矩阵为不可传递的：••111Mr=100100(7)自反的、反对称的、其对应的关系矩阵为可传递的：••101Mr=111001(8)自反的、不对称的、其对应的关系矩阵为不可传递的：••110Mr=111001(9)不自反的、对称的、其对应的关系矩阵为可传递的：此题图有错误••011Mr=111111（10）自反的、反对称的、不可传递的;

其对应的关系矩阵为:101Mr=110011(11)自反的、反对称的、可传递的；其对应的关系矩阵为：100Mr=110101(12)不自反的、反对称的、可传递的。其对应的关系矩阵为：001Mr=11100123・设X是一个集合，巴和见是乂中的二元关系，并设&二巴，试证明：⑴心)》(%)(2)$(鸟)亠(％)⑶t(Rj二t(Rj证明：a)因为尺二巴，故R]U<4二二R2U/4,即r(R1)2r(R2)因为s(R)对称，且s(R)3R,(0R3R,故s(R)3R,由s(R)的定义，s(R)111121222是包含R,的最小对称关系，故s(R)3s(R)■X因为t(R)传递，且t(R)3R,但R3R,故t(R)因t(R)是包含R,的最小传递关系，所以t(R)d(R)在图4.23中给出三个关系图。试求每一个的自反的、对称的和可传递的闭包，并画出闭包的关系图。解：由关系图可知，R=0则：r(R)={<a,a>?<b?b>}s(R)=0t(R)=0解：由关系图可知，R={<a,a>,<a.b>}则：r(R)={<a,a>,<b,b>,<a.b>}s(R)={<a,a>,<a,b>,<b,a>}t(R)={<a,a>,<a,b>}

解：由关系图可知，R={<a,b>,<b,c>,<c,a>}贝叽r(R)={<a,a>,<b?b>,<c?c>,<a?b>,<b,c>,<c,a>}s(R)={<a,b>,<b,a>,<b,c>,<c,b>,<c,a>,<a,c>}t(R)={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>,<a,a>,vb,b>,<c,c>}R,和见是集合A中的关系。试证明：⑴r(R1UR2)=r(R1)Ur(R2)sRurJusCrJUsCrJUR2)=t(R1)Ut(R2)证明：r(RUR)=RURUI=RUIURUI=r(R)rU(R)'1212A1A2A122)s(RUR)=(RUR)U(RUR)C121212CC=RUR^URUR.cc=(RUR)U(RUR)1122=s(R)Us(R)123)因为RUR“R,由习题3-98,贝壯(RUR丿=t(R)同理t(RURJ=t(R丿]22所以t(RUR)=t(R)Ut(R)121226•设集合X={a,b,c,d,e,f,g,h},R是X中的二元关系，图4-12给出了R的关系图。试画出可传递闭包t（R）的关系图，并求出tsr（R）。解：由关系图可知，<a,b〉,vb,c>,vc,a〉,vd，e<a,b〉,vb,c>,vc,a〉,vd，e〉,ve、f>,<f,g〉,vg.h>,<h,d>,<a,a>,vb,b〉，<c,c>,<d,d>,<e,e>,<f,f>,<g9g>9<h,h>,<b,a>9<c,b>,<a,c>,<d,f>,vd，g>,vd,h>,ve,g>,ve，h>,ve,d>,<f,h>,<f,d>,<f,e>,<g,d>,vg,e>,<g,f>,<h,e>,<h,f>,<h,d>t（R）=<a,b>,<b,c>,<c,a>,<d.e>,<e,f>,<f,g>,<g,h>,<h.d>,<a,a>,<b.b>,tsr(tsr(R)=<d,g>,<d,h>,<e,g>,<e,h>,<e,d>,<f,h>,<f,d>,<f,e>,<g,d>,<g,e>,<g,f>,<h,e>,<h,f>,<h,d>27•设R是集合X中的任意关系。试证明：(R・y=r+RoRx=R-=R*oR(ry=R*证明：(R‘)+=t(t(R)),因为t(R)是传递的，根据定理3-8.1,t(t(R))=t(R),即(R)+=Ro*RoR=Ro(tr(R))=Ro(rt(R))=Ro(t(R)UI)A8i=l=Rot(R)RoUI=RoRUAggii+i=2i=l=RUR=RUU=t(R)=R同理口J证R=RoR因为r(R)是自反的，有习题3-97a),tr(R)是自反的，根据定理3-8.1,rtr(R)=tr(R),即tr(R)=R：所以，(R)29设｛a，A，...，aJ是集合a的划分。试证明：｛ACIB,A,AB,...4Ab｝是集合AflB的划分。证明：因为｛A，△，•••，£｝是集合A的划分，所以AU曲T，2,...,D)A"=0(iHj)Ua=ai=l(l)因为Aua所以A仃B匚ADB(i二1,2,...n)B)=(A")nB=0fiB=0

UAnB=（AnB）n（A,nB）n....n（4AB）i=l=（agn…naJcb=adb（1）,（2）,（3）构成满足划分的条件，因此｛j\nB,AnB_4nB｝是集合AC1B的划分。把n个元素的集合划分成两个类，共有多少种不同的分法?解:C：解:C：+C：+….+C：2在图4.25中给出了集合｛1,2,3｝中的两个关系图，判断这两个关系是否是等价关系。解：左侧的关系不是等价关系，因为不满足可传递性；右侧的关系是等价关系。在等价关系图中，应如何识别等价类？解：如果两个元素之间有两条连线，那么说明这两个元素是等价类。33.设R是集合x中的关系。对于所有的\,Xj,xkeXf如果^RXj’XjRXk，就有,则称关系R是循坏关系。试证明：当且仅当R是一个等价关系，R才是自反的和循环的。证明：（1）当R是个等价关系时，由等价关系的定义知，等价关系满足自反性，即R是自反的。任取x,y,zeX,<x,y>eR,<y,z>eR,由尺的可传递性，知vx,z>wr,再由R的对称性，知VZ,x>wR。根据X,y,Z取值的任意性，知R是循环的。（2）当R是自反的，可知对任意xeX,<x,x>eRotf取y€X,使得vx,y〉eR,因为r是循环的，故当vx,x>gr,<x,y>eR时，vy,x>wR°由丫，y取值的任意性知，R是对称的；任取x,y,zeX,<x,y>eR,<y,z>eR,由r的循坏性知，VZ,X>wR‘因为R是对称的，因此VX,Z>wR，由x,y,z取值的任意性，知R是可传递的。因为R是自反的、对称的和可传递的，因此R是一个等价关系。34.设R和见是集合X中的等价关系。试证明：当且仅当C】中的每一个等价类都包含于C?的某一个等价类之中，才有R.CR.O证明：设等价关系%造成的集合x的划分为C]二｛C]],C]2，・・・,Cim｝,等价关系$造成的集合x的划分为C?二｛C21,C22,--sC2n｝（1）当C]中的每一个等价类都包含于C?的某一个等价类之中时，任取©中的一个等价类q,则必包含在C?的一个等价类里，设包含在C2J中，ChcC2jo任取c“中两元素X,y,由等价类的性质知，xRy。由chCc2j,可知若<x,y>eRlf则<x,y>eR2,即xR?y。由i,j.x,y取值的任意性知，RuR,(2)如果RuR?,那么对任意的vx’y'wRf<x,y>eR2永真，vx’y'eR等价于X,y落入C］的某个等价类C”中，VX,y&等价于x,y落入C?的某个等价类C?j中，即若x?yeCh,则兀y丈鸟厂由禺丫的任意性可知，ChcC2j,由i的任意性可知，©中的每一个等价类都包含在C?的某一个等价类之中。综上所述，当且仅当C］中的每一个等价类都包含于C?的某一个等价类之中，才有RuR2。37.设氏和见是集合x中的等价关系，并分别有秩片和E。试证明：氏门巴也是集合x中的等价关系，它的秩至多为5厂。还要证明gUR.不一定是集合x的一个會价关系。证明：(1)因为心巴是自反的，所以对于任意的xeX,都有对于任意的x,x>ex,x>eR>,故vx,x>e&门巴，所以R门巴是自反的：对于任意的X,yeX>若<乂汙>已巴0兀，则vx^yKR^且<%丫>已巴。又鸟,见是对称的，所以有vy’xAwRp<y,x>eRyf故vy,x>E尺门兀，即鸟门巴是对称的；对于任意的X,y,zeX,若<%丫>已$门巴，<y,z>eOR,t则y,z>e且vx,y>wR「<y,z>eo又R’R?是可传递的，所以有x?z>g,故vx,z>eRiARo»即RiC|R2是可传递的：综上，RCIR?是等价关系。⑵因为RpR?是自反的，所以对于任意的X6X,都有对于任意的x,x>ex,x>eR>,故vx,x>e&UR^，所以RUR?是自反的：对于任意的x,yeX,若v^yxRU巴，则可能有三种補况：若且vx,y>iR,,那么因为RpR?是对称的，所以有y,x>eRyf故vy,x>e&U巴，即RUR?是对称的：若vx?y>eRi但vx,y>$&,那么有vy?x>c且vy,x>gR2,此时y,x>eUR.•即RiUR.是对称的；所以RjUR.是对称的；若vx,y>eIL.但vx.y>eK，那么有vy,x>e且vy,x>eR,，此时y,x>eRiU•即RiUfC是对称的；对于任意的x,y,zeX,若vx^yAwRiUR^，<y,z>eURoJ当vx^yAeR^,y?z>eR>时，不能确定v%z>e&IjR^，故RUR?不是可传递的。

由上可知，RiUR2不是等价关系。由上可知，RiUR2不是等价关系。(2)(3)｛沙｝,仪pXj,化儿｝,｛期士｝,｛期虽｝,合并后,有(3)(4)｛屯,知％｝,｛电屁屁｝,｛禺,屯｝{x3,x4?x5},化吗,奄}(4)｛屯,知％｝,｛电屁屁｝,｛禺,屯｝｛洛,冯,电｝,｛心沙｝,｛x2>x3｝,｛无禺｝,｛XpXj,仪,禺｝,合并，得｛冯遇対｝,｛无靭奄｝,债內,比｝,倍,莎｝综上，最大相容类有四个，分别是｛Xj,x2,x3｝,｛无冯,务｝,亿丛4，兀｝,｛西,*,吿｝°38.给定集合S=｛y\,A„..4｝的覆盖，如何才能确定此覆盖的相容关系。解：相容关系是具有反对称性的关系，集合S的任何一个覆盖X均能确定一个相容关系，反之亦然。设x=｛S],S2，...Sk｝是集合s二広厲…人｝的一个覆盖，则由此覆盖确定的s上的相容关系是：(S1x,S1)U(S2xS2)U...U(SkxSk)>其中SkxSk指S的子集Sk的笛卡尔积。如X=｛｛1,2｝,｛2,3｝｝是S=｛1,2,3｝的一个覆盖，则此覆盖确定的S上的相容关系是：｛1,2｝x｛1,2｝U｛2,3｝x｛2,3｝=｛<1,,1>,<1,2>,<2,1>,<2,2>,<2,3>,<3,2>,<3,3>｝设集合X=｛1,2,3,4,5,6｝,R是X中的关系。图4-23给出了R的关系图。试画出R’和史的关系图。解：R?={<1,5>,<1,6>,<2,5>,<3,6>,<4,5>,<5,4>}R6={<1,4>,<1,6>,<2,4>,v3,6>,<4,4>,<5,5>}假定I*是集合x中的恒等关系，r是x中的任何关系。试证明：IXURUR是相容关系。证明：设S=IxURUR由于IxcIxURUR>因此VxeX,<x,x>GSO知IxURU反是自反的；任取x,yeX,<x,y>eS,则vxywIx或者vx,y>wR或者<x,y>wR。若<x,y〉wlx，则*=丫，<y,x>elx,<y,x>eS;若<x,y〉wR,则<y,x>wR,<y,x>eS;若<x,y〉wR,则vy,x>eR,<y,x>eSo可知无论任何情况，若vx,y〉wS,则vy,x〉wS。故ixURUR是对称的。综上所述，IXURUR既是自反的「又是对称的,因此，IXURUR是相容关系41.给定等价关系R和S,它们的关:系矩阵是110110Mr=110Ms=111001011试证明：RoS不是等价关系。证明：_11rMr°s=111o11可知RoS不是对称的，因此，RoS不是等价关系。设集合X={1,2,3}。求出X中的等价关系R］和R?,使得RioR,也是个等价关系。解：设Ri={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<3,1>}R,={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>}则巴和见是集合X中的等价关系。此时R。巴={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>},也是个等价关系。对于下列集合中的整除关系画出哈斯图。（1）{1,2,3,4,6,8,12,24}2424{1,2,3,…,12}解：(1)121263(2)44.如果R是集合X中的偏序关系，且ACX。试证明：RQ（AxA）是A中的偏序关系。证明：因为R是集合X中的偏序关系，所以R是自反的，反对称的，可传递的。（1）因为R是自反的，所以IxcR;又A^X,所以IAClx；所以R是自反的。（2）对于任意x,yeA*若<x,y>wRQ（AxA）,那么vx,y>eR且v%yAxA;又R是反对称的，所以vy,x>gR,即vy,x>$Rn（AxA）,所以RPl（Ax曲是反对称的。（3）对于任意x,y,zeAt若vx,y>,vy,z>wRD（AxA）,那么vy>,<y,z>eR且vx,y>,vy,z>eAxA。又R是可传递的，所以vx,z>wR,<x,z>eAxA，即：<x,z>eRp（AxA）♦所以RP（Ax勾是可传递的。由此可知，RQ（AxA）满足自反性、反对称性、可传递性，即RA（AxA）是A中的偏序关系。45-试给出集合X的实例，它能使(p(X),u)是全序集合。解：X={0},则q(X)={0,{0}}此时，对于任意的x,yep(X)»都有xqyUyqx所以(Q(x),u)是全序集合。46给出一个关系，它是集合中的偏序关系又是等价关系。解：集合X上的恒等关系，既是偏序关系又是等价关系。47.证明下列命题：如果R是拟序关系，则復也是拟序关系。(2)如呆R是偏序关系，则R也是偏序关系。如果R是全序关系，则反也是全序关系。存在一个集合S和S中的关系R,使得VS,R>是良序的，但<S,R>不是良序的。证明：设R是A上的二元关系，若R是自反的，则IacR,由于Ia的转置仍是Ia，因此IauR，故住是自反的；若R是反自反的，则IAC|R=0。把Ia和R都取转置，由于【A的转置仍是【A，因此，IaAR=0,故反是反自反的；(C)若R是对称的，任取<y,x>eR,则Vx,y>eR,由R的对称性可知，<y,x>eR,于是<x,y>wR。由x,y取值的任意性知，復是对称的；若R是反对称的，任取<y,x〉wR,则<x,y>wR,由R的反对称性可知，<y,x〉gR,于是<x,y>wR。由x,y取值的任意性知，良是反对称的；若R是可传递得，任取<x,y>w^,vy,z>E文，则<y,x>eR,<乙y〉wR,由R的可传递性，可知v乙x>wR,于是<x,z〉wR。故復是可传递的。从上述5条可以证明(1)一一(3)(1)若R是拟序关系，即R是反自反的和可传递得，由(b)(e)可知，反也是反自反的和可传递得，因此，良是拟序关系。（2）若R是偏序关系，即R是自反的、反对称的，可传递的，由（a）（d）（e）可知,復也是自反的、反对称的，可传递的，因此，復是偏序关系。（3）若R是全序关系，则R是偏序关系，由（2）知復也是偏序关系；另知，Vx,yeA,xRy或yRx成立，当xRy时，y触，当興时，画。因此不论任何情况,Vx,yeA,加7或y触总成立。综上，良也是全序关系。（4）举例子，设VS,R>=VN,O,N是自然数集合，则VS,R>=VN,仝是良序，但是<S,Rx<N,n>不是良序。因为取全集N,在vS,R>=vN,A中没有最小成员。48.设R是集合A上的二元关系，证明，当且仅当RAR=0和只=1<+,R才是拟序的。当且仅当R"R=IX和R二R*，R才是偏序的。证明：设R是集合A上的关系（1）充分性：r=r+,故R是可传递的；RP|R=0，所以对于任意的xwA,都有vx,x>$R,即R是反自反的。所以，当RAR=0和R=R・时，R是拟序的。必要性：因为R是拟序的，所以R是反自反的、可传递的、反对称的。R是可传递的，故R=R+:R=R+是反对称的，所以对于任意x,ywAxHy,若vx,y>eR,则<x,y>eR：又R是反自反的，所以RAR=0o所以，当R是拟序时，RAR=0且只=时。（2）充分性：RAR=IX,故quR，即R是自反的；又RAR=IX,所以对于任意x,ywA,xHy,若vx,y>eR»则vy,x>$R，即R是反对称的：又R=R\所以R是可传递的;所以，当RPlR=Ix和只=只*时，R是偏序关系。必要性：因为R是偏序关系，所以R是自反的，反对称的，可传递的。R是自反的，故ixCR且ixcR；R是反对称的，故对于任意的％ywAxHy,若vx,y>eR,则<x,y>gR,所以RnR=IXo又R是自反的，可传递的，所以它的自反可传递闭包是其本身，即R=R*；所以，当R是偏序关系时，RnR=Ix且R二R*。49•图4-28给出了偏序集合vP,R>的哈斯图,这里P二{比理宀轴屁}。(1)下列关系中哪一个是真的：x1Rx2,x4Rx1,x3Rx5,x2Rx55x1Rx1,x2Rx3,x4^求出P中的最人成员和最小成员，如果他们存在的话。求出P中的极人成员和极小成员。求出子集{X2,X3,X4},{X3,X4,X5}^{X1,X2,X3}的上届及下届。并指出这些子集的LUB和GLB,如果它们存在的话。解：⑴X4RX1，^RX］是真的，(2)最大成员：X］；最小成员：无。极大成员：极小成员：X4,X5子集{X2，X3,X4}上届：X］;卜届：x4:LUB：X］；GLB：x4<>子集{XpX4,X^}上届：X］,X3；卜-届：无；LUB：X3；GLB：无。子集X2,X3}上届：X］；卜届：x4:LUB：X】；GLB：x4■>第五章函数习题答案P[109-lll]1.卜列关系中哪些能够构成函数？对于不是函数的关系，说明不能构成函数的原因。1^={<x,y>|(x,yeN)A(x+y<10)}⑵R2={<x,y>|(x,yeR)A(y=x2)}(3)R3={<x,y>|(x,yeR)A(y2=x)}解：(1)不能构成函数。对于某些XEN,不止存在一个yeN使得x+yvl0成立。能构成函数。不能构成函数。对于某些对于某些xeR,存在两个yeR使得y2=X成立。2•下列集合中，哪些能够用来定义函数？试求出所定义的函数的域和值域。Sj={<1,<2,3»,<2,<3,4»,<3,<1,4»,<4,<1,4»}S2={<1,<2,3»,<2,<3,4»,<3,<3,2»}⑶S3={<1,<2,3»,<2,<3,4»,<1,<2,4»}S1={<1,<2,3>>,v2,v2,3»,<3,<2,3»}解：(1)能够用来定义函数。域：{1,2,3,4}值域:{<2,3>,<3,4>,<1,4>}能够用来定义函数。域：{1,2,3}值域：{<2,3>,<3,4>,<3,2>}不能够用来定义函数。能够用来定义函数。域：{1,2,3}值域:{<2,3>}设I是证书集合，-是正整数集合，并且把函数F:ItI+，定义为f(i)=|2i|+l°试求出函数f的值域Rf。解：Rf为正奇数的集合。设E是全集，Q(E)是E的幕集，q(e)xq(e)是由E的子集所构成的所有序偶的集合,对任意的S”S2ep(E),IEf:p(E)xP(E)^p(E)定义为f(S1,S2)=SlflS2-试证明:f的陪域与值域相等。・证明：f的陪域为q(E)，设值域为％,假定f的陪域与值域不相等，即RfCZ/7(E)0

那么一定存在q(E)的一个元素a,使得AgRf。因为f(Sp^)=^05^因此，不存在任何一个Sps2,使得S】nS2=A。设S]=E，则对于任何S2e/?(E),由SiflSpHA知A,由S?取值的任意性可知，Agp(E)。这与a的取值在p(E)中相矛盾，因此f的陪域与值域不相