大連理工大學(xué)軟件學(xué)院離散數(shù)學(xué)習(xí)題答案

TOC\o"1-5"\h\z第一章命題邏輯2第二章謂詞邏輯9第三章集合論習(xí)題答案13第四章二元關(guān)系習(xí)題答案21第五章函數(shù)習(xí)題答案42第六章代數(shù)系統(tǒng)習(xí)題答案51第七章群與環(huán)習(xí)題答案57第八章格與布爾代數(shù)習(xí)題答案66第九章圖的基本概念及其矩陣表示71第十章幾種圖的介紹82第H■$樹90第一章命題邏輯(1)不是命題；(2)不是命題；(3)不是命題；(4)是命題：(5)是命題；(1)并非大連的每條街都臨海；(2)2不是一個偶數(shù)或者8不是一個奇數(shù)；(3)2不是偶數(shù)并且-3不是負(fù)數(shù)；3.逆命題：如果我去公園，那么天不下雨。否命題：如果天下雨，我將不去公園。逆否命題：如果我不去公園，那么天下雨。逆命題：如果我逗留，那么你去。否命題：如果你不去，那么我不逗留。逆否命題：如果我不逗留，那么你不去。(3)逆命題：如果方程無整數(shù)解，那么n是大于2的正整數(shù)。否命題：如果n不是人于2的正整數(shù)，那么方程有整數(shù)解。逆否命題：如果方程有整數(shù)解，那么n不是大于2的正整數(shù)。(4)逆命題：如果我不能完成這項(xiàng)任務(wù)，那么我不獲得更多的幫助。否命題：如果我獲得更多的幫助，則我能完成這項(xiàng)任務(wù)。逆否命題：如果我能完成這項(xiàng)任務(wù)，則我獲得更多的幫助。(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,?是可結(jié)合的。(1)(PAQ)-R；nP；(-]PAnQ)R不依賴于命題變元的真值指派，而總?cè)(1)的命題公式，稱為重言式(永真式)；不依賴于命題變元的真值指派，而總?cè)(0)的命題公式，稱為永假式(矛盾式)；至少存在一組真值指派使得命題公式取值為T的命題公式稱為可滿足的。本題可用真值表求解：得真值表如下：PQ001011101111可見不論命題變元的真值指派如何，命題公式總?cè)?,故為重言式。（8）得真值表如下:pQR00010011010101111001101111011111可見不論命題變元的真值指派如何，命題公式總?cè)?，故為重言式。其他小題可用同樣的方法求解。(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右式，證明完畢。根據(jù)對偶式定義，該式的對偶式為：(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)證明：假設(shè)PAQ為真，則P為真且Q為真，則P-Q為真。所以：PAQ=>P-*Q。(3)證明：右側(cè)OPVQ,假設(shè)1P\/Q為假，則P為真且Q為假，則P-*Q為假。所以：P-*Q=>P-?PAQo(5)證明：假設(shè)Q—R為假，則Q為真且R為假，則左側(cè)為假。所以：(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)證明：左側(cè)0(-1PVQ)A(-1PVR)o(-1PVQVR)A(-1PVQV-iR)A(-1PVQVR)A(1PVnQVR)on(4,5,6)右側(cè)0-1pv<qar)o…on(4,5,6)左側(cè)0右側(cè)，得證。證明：左側(cè)(-!PVQ)V(PAQ)o(PA-iQ)V(PAQ)oE(2,3)右側(cè)0(PVQ)A(PV-iQ)o(PAP)V(PA-iQ)V(PAQ)V(QA-iQ)o(PA-iQ)V(PAQ)oE(2,3)左側(cè)0右側(cè)，得證。第(2)、(4)小題方法相同，解答略。對于A,B,C,D,E5個變元的所有真值指派，推出前提AoB,B—(CAD),Co(A\/E),AVE和結(jié)論AAE的值，得到真值表。當(dāng)真值表中各前提的真值都為1時，若結(jié)論也為1,則結(jié)論有效，否則結(jié)論無效。20.(1)采用真值表證明:PQPfQP->(PAQ)0011011110001111根據(jù)真值表可看出，當(dāng)前提為1時，結(jié)論也為1，則結(jié)論有效。(3)采用推理方法證明：PAQ為真，可得P為真且Q為真，又P-(Q-R)為真且P、Q為真，得R也為真。則結(jié)論有效。第(2)、(4)小題方法相同，解答略。21.(1)證明：假設(shè)公式全部同時成立，由「S為真得到S為假，由「P-S為真，得P為真，由P-Q為真得到Q為真，由QfR為真得到R為真，由rRVS為真得到S為真。這與前面“S

為假”矛盾，則公式不能同時成立。(2)證明：假設(shè)公式全部同時成立，由「S為真得到S為假，由「RVS為真得到R為假，由RVM為真得到M為真，由為真得到M為假，矛盾。則公式不能同時成立。22.首先符號化：P:人連獲得冠軍；Q:北京獲得亞軍：R:上海獲得亞軍；S:廣州獲得亞軍。即求公式：P-(QVR),RfiP,S-*-|Q,P=>n1S是否成立{1}(1)PP規(guī)則{2}(2)Rf-1P規(guī)則{1,2}(3)nRTj規(guī)則⑷(4)P~(QVR)規(guī)則{1,2,4}(5)QTj規(guī)則{6}(6)S-*-|Q規(guī)則{1,2,4,6}(7)1sTj規(guī)則23.(1)證明：(1)1RP規(guī)則(2)-1QVRP規(guī)則(3)-1QT規(guī)則(1)(2)(4)-1(PA-iQ)P規(guī)則(5)-1PT規(guī)則(3)(4)(3)題目有誤(5)證明：(1)PP規(guī)則(附勺件前提)(2)P~(P.AQ)P規(guī)則(3)PAQT規(guī)則(1)(2)(4)QT規(guī)則(1)(3)(5)P-QCP規(guī)貝11第(2)、(4)小題方法相同，解答略。24.(1)證明：(1)11PP規(guī)則(假i沒前提)(2)PT規(guī)則(1)(3)P-*QP規(guī)則(4)QT規(guī)則(2)(3)(5)R~*~1QP規(guī)則(6)1RT規(guī)則(4)(5)(7)RVSP規(guī)則(8)ST規(guī)則(6)(7)(9)S-*-iQP規(guī)則(10)-1QT規(guī)則(8)(9)(11)QA-iQT規(guī)則(4)(10)(12)nPF規(guī)則(1)(11)(2)證明：(1)nRP規(guī)則(2)RVSP規(guī)則(3)ST規(guī)則(1)(2)（二）（二）P?QT規(guī)則（7）證明:(4)S—iQP規(guī)則(5)-iQT規(guī)則(3)(4)(6)PiQP規(guī)則(7)-1PT規(guī)則(5)(6)(P~Q)—i(RVS),(Q->P)V-iR,R=>PoQ(1)Rp規(guī)則(2)RVST規(guī)則（1）(3)-1(P-Q)f-i(RVS)P規(guī)則(4)P-QT規(guī)則(2)(3)(5)(Q-P)VnRP規(guī)則(6)Q->PT規(guī)則(1)(5)(7)(P-Q)A(QfP)T規(guī)則(4)(6)（3）原式修改為：n第二章謂詞邏輯(1)S(x)：x聰明；L(x)：x好學(xué)；a：表示小明，命題：S(a)AL(a)oS(x)：x是素?cái)?shù);G(x,y)：x大于y,命題：(Vx)(S(x)->(3y)(S(y)AG(y,x)))U(x)：x是大學(xué)生；S(x)：x能成為科學(xué)家，命題：(3x)(U(x)A->S(x))N(x)：x是自然數(shù);A(x)：x是奇數(shù);B(x)：x是偶數(shù),命題：(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(假設(shè))(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)))第三章集合論習(xí)題答案對應(yīng)課本頁數(shù)：P51-541.寫出下列集合的表達(dá)式。所有一元一次方程的解所組成的集合：答案：集合可表示為Wax+b=O,a,beR}x'-l在實(shí)數(shù)域中的因式集。答案：集合可表示為{1，X-1,X+1,X?-X+1,X’+X+1,X’-1,X’+1,X6直角坐標(biāo)系中，單位圓內(nèi)(不包扌舌單位圓)的點(diǎn)集。答案：集合可表示為{"y>lx2+y2"}極坐標(biāo)系中單位圓外(不包括單位圓)的點(diǎn)集。答案：集合可表示為{V%y>1X>cos&,y>sin&s[0,2刃}能被5整除的整數(shù)集。答案：集合可表示為Wx=5n,nel}2?解：設(shè)戲劇、音樂、廣告分配的時間分別為x,y,z⑴x+y+z=30嚴(yán)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}}解：設(shè)A={a,{a}}則0(Q={0，{a},{{a}},{a,{a}}}⑵{{1,{2,3}}}解：設(shè)A二{{1,{2,3}}}則P(A)={0,{{1,{2,3}}}}⑶{0,a,}解：設(shè)A={0,a,}則q(厲={0,{0},{a},,{0,a},{0,},{a,},{0,a,}}⑷Q(0)解：設(shè)A=p(0)={0}則q(A)={0,{0}}⑸03(0))解：設(shè)A=p(Q(0))={0,{0}}則p?={0,{0},{{0}},{0,{0}}}設(shè)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&設(shè)某集合有101個元素，試問：可構(gòu)成多少個子集：2101其中有多少個子集的元素為奇數(shù)：2】00是否會有102個元素的子集：不會9.解：把17化為二進(jìn)制,是00010001,={a4,a8}；把3i化為二進(jìn)制，是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),當(dāng)且僅當(dāng)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)確定卞列各式的運(yùn)算結(jié)果。解：00{0}=0{0}n{0}={0}{0,{0}}_0={0,{0}}{0,{0}}-{0}={{0}}16-假設(shè)A和B是E的子集，證明下列各式中每個關(guān)系式彼此等價。證明：證明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:由以上兩點(diǎn)可知：AuBO~BAo證明：AuEOAUB=B充分性：若xgAUB,那么有xeA或xwB。若xeA,則由AuB口J■知，必有xwB,所以若xgAUB,必有xeB,即AUBcB；若xeB,那么必有XGAUB,即BcAUB,所以AUB=B,充分性得證；必要性：因?yàn)锳UB=B,所以，對于任意的XGAUB,必有XeB,所以AoB,必要性得證；由以上兩點(diǎn)可知：AyBOAUB=B證明：AuEOACB=A充分性：若XGACIB,那么必有xeA,即AHBcA；若xeA,那么由AoB可知，必有XWB,所以xgADB,即AcAflB,所以，AAB=A；必要性：因?yàn)锳ab=A,所以對于任意的xeA,必有XGAAB,XEB,所以AoB:由以上兩點(diǎn)可知，AuBOACB=A。由以上三點(diǎn)可知，AuBO~BC~A<=>AUB=B<=>ACB=A。⑵證明：aAb=0oac~b充分性：因?yàn)锳flB=0,所以對于任意的x,若xeA,則必有x住B,即XSB,所以A匸~B；必要性：因?yàn)锳SB,所以對于任意的X,若XeA,則必有XSB,即X€B,所以AHB=0：由以上兩點(diǎn)可知：aAb=0oa匸~B證明：AC|E=0OBC~A充分性：因?yàn)锳flB=0,所以對于任意的X,若XWB,則必有X住A,即XSA,所以A；必要性：因?yàn)锽C~A,所以對于任意的X,若XEB,則必有XSA,即X€A,所以AHB=0：由以上兩點(diǎn)可知：aAb=0ob匸~A.由上可知：aAb=0u>ac~b<=>bc~a.⑶證明：AUB=E<=>-AcB充分性：因?yàn)閍ub=e,所以若xgA,則必有xeB.即若xg~a,則必有xgB,所以~ACB；必要性：因?yàn)锳U~A=E,又~ACB,必有AUB=E：由以上兩點(diǎn)可知：AUB=E<=>~ACB證明：AUB=EQ~BcA充分性：因?yàn)閍ub=e,所以若xUB,則必有xwA,即若xB.則必有xwA,所以~BcA；必要性：因?yàn)锽U~B=E,又~BcA,必有AUB=E；由以上兩點(diǎn)可知：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)必要性：因?yàn)锳十B=(AA-B)U(BA-A)=4)所以AB=4)且BA=4)因?yàn)锳C~B=4所以ACB又BA-A=4),所以BcA所以A=Bo由上可知：A=B<=>A十B=e。17-化簡下述集合公式。結(jié)果：AAB結(jié)果：A-B結(jié)果：A結(jié)果：CA(AUB)1&設(shè)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-借助文氏圖，考察下列命題的正確性。設(shè)A,B,C為任意集合，是判斷下面命題的真假。如呆為真，給出證明，否則給出反例。設(shè)在10名青年中有5名是工人，7名是學(xué)時，其中兼具工人與學(xué)生雙重身份的青年有三人，求既不是學(xué)生也不是工人的青年有多少？設(shè)A,B分別代表工人、學(xué)生，貝IJ：|AUB|=10,|A|=5,|B|=7,|AnB|=3；則：10-5-74-3=1所以既不是學(xué)生也不是工人的青年有1人。22-求1到250之間能夠被2,3,5,7中任何一個整除的整數(shù)的個數(shù)。設(shè)|4|=1250/2J=125,|B|=[250/3」=83,|G=[250/5J=50,|D|=[250/7J=35則所求的答案表達(dá)式為/UBUCUDI。求解:|4UFUCUD|=125+83+50+31-(41+25+17+16+11+7円8+5+3+2)?(1)=189;所以,這樣的數(shù)共有189個。解：設(shè)A,B,C分別表示參加足球隊(duì)、籃球隊(duì)和棒球隊(duì)的隊(duì)員的集合|AnBAC|=3|AUBUC|二|_A|+|B|+|C|TACIBHACICHBCICI+IAClBPlCln|AHBI+IAnC|+|BnC|=|A|+|B|+|c|+|AnBnC|-|AUBUC|=38+15+20+3—58=18即同時參加兩個對的隊(duì)員共有18個。解：設(shè)A,B,C分別表示讀甲種、乙種、丙種雜志的學(xué)生的集合。⑴|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%所以確定讀兩種雜志的學(xué)生的百分比為60%。⑵卜捫?BCI?C|=100%—(ADCD?B|+|BDcn?A|+|ADBCl?C|+|ADBnc|)=100%-(60%+10%)=30%所以不讀任何雜志的學(xué)生的百分比為30%。第四章二元關(guān)系習(xí)題答案對應(yīng)于課本88-93頁如果A二{0,2}和B二{1,2},試求下列集合。Ax{1}xB解：Ax{l}xB={<0,1,1>產(chǎn)0,1,2>產(chǎn)1,1,1>產(chǎn)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表示在在笛卡爾坐標(biāo)系中，-3<X<2且-2'ySO的矩形區(qū)域內(nèi)的點(diǎn)集。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當(dāng)且僅當(dāng)才，才有(AQB)UC=AH(BUC)證明：當(dāng)CoA時，AUC=A,于是(AnB)UC=(AUC)n(BUC)=An(BUC)o當(dāng)(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,所以當(dāng)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=則(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)解：設(shè)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)假設(shè)結(jié)合A有n個元素，則PQ4)有2*個元素，貝爐⑷XPQ4)共有2?n個元素；則4x4有I?個元素，PQ4X4)則有2十個元素，顯然兩者元素?cái)?shù)不一樣，故命題不成立。設(shè)A={1,2,3,4},列出以下關(guān)系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為素?cái)?shù)}解：R={(1,2),(1,3),〈2,2〉，(2,3),〈3,2〉，〈3,3〉,〈4,2),(4,3〉}列出集合人={2,3,4}上的恒等關(guān)系必和全域關(guān)系殆。解：弘={〈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〉}給出下列關(guān)系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>}設(shè)％和&都是從A={1,2,3,4}到：8={2,3,4}的二元關(guān)系，并且Rj={<1,2>,<2,4>,<3,3>}R2={<U>,<2,4>,<4,2>}求RUR-RiflR-D(Rj、d(rJr(rJr(rJdCrUrJ、斑風(fēng)門企)。解：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)}設(shè)集合A={1,2,3},問A上有多少種不同的二元關(guān)系。解：232=512種關(guān)系。設(shè)關(guān)系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}設(shè)關(guān)系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說明以下關(guān)系R具有那些性質(zhì)并說明理由。:反自反的、反對稱的、可傳遞的；:反自反的、對稱的、不可傳遞的；:自反、對稱、可傳遞：：自反、對稱、可傳遞：設(shè)A是所有人的集合，定義A上的二元關(guān)系R1和R2,說明R1和R2具有哪些性質(zhì)。解：R1具有的性質(zhì)：反自反的、反對稱的、可傳遞的：R2具有的性質(zhì)：自反、對稱、可傳遞；設(shè)氏和見是集合X中的二元關(guān)系。試證或反證下列命題：如果是自反的，則氏。％也是自反的。如呆耳和巴是反自反的，則盡。巴也是反自反的。如呆巴和巴是對稱的，則為。！^也是對稱的。如果巴和見是反對稱的，則氏。％也是反對稱的。如果R】和巴是可傳遞的，則氏。％也是可傳遞的。解：(1)證明：任取xeX,由于R和R?是自反的，因此VX’X'WR,可得由x取值的任意性可知，尺。&是自反的。⑵設(shè)X二{1,2,3},^={<1,3〉}也二{<3,1〉},則R1oR2={<i,i>},不是反自反的。設(shè)X二{1,2,3},R={<1,2〉,<2,1〉},&={<3,2>,<2,3〉},則R1oR2={<1,3>},不是對稱的。設(shè)X={1,2,3},!^={<1,2>,<3,1>},!<.={<1,1>,<2,3>},則R1oR2={<1,3>,<3,1>},不是反對稱的。設(shè)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上的自反和可傳遞關(guān)系，則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;如果關(guān)系R和S都是自反的。證明：RUS,RAS也是自反的。證明：設(shè)R是集合A上的二元關(guān)系，S是集合B上的二元關(guān)系。因?yàn)镽和S都是自反的，所以對于VxeA,都有v%x>wR,對于VxeB,都有vx,x>eS。設(shè)xgAUB,那么xeA或xwB。若xeA,有vx,x>wR,那么必有vx,x>eRUS。若xeB,有vx,x>wS,那么必有vx,x>eRIJS。因此，當(dāng)xgAUB時，必有vx,x>eRUS,所以RUS也是自反的。(2)設(shè)XGATIB,那么XGAfcLxeB因此vx,x>wR且vx,x>wS，即vx,x>eRClS。所以RAS也是自反的。證明：如果關(guān)系R和S都是自反的、對稱的、可傳遞的，證明：RQS也是自反的、對稱的和可傳遞的。證明：設(shè)R是集合A上的二元關(guān)系，S是集合B上的二元關(guān)系。自反性的證明如題4。對于任意的X,yeAp|B?若vx,y>wRflS,那么vx,y>gR且vx,y>wS因?yàn)镽和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因?yàn)镽和S都是可傳遞的，所以有vx,z>wR且vx,z>wS,即vx,z>eRflSo即對于任意x,y,zeApB,若<x,y>eROS且vy,z>eRDS,都有<x,z>eRp|So所以RQS是可傳遞的。設(shè)集合A是有限集，且R|=n,求：A上有多少不同的對稱關(guān)系。解：2n(n+1)/2因?yàn)閨A|=njAxA|=if也就是說集合A有n平方個有序?qū)?，由對稱定義可知，對于a,beA,只耍(a,b)e有(b,a)wR。另外知道在n平方個有序?qū)χ杏衝個有序?qū)?(X’,XJ其中i=l,2,3.....n),相應(yīng)的就有n2-n個有序?qū)?X,Y)且XHY,定義可知后面的n?-n個有序?qū)χ荒艹蓪Τ霈F(xiàn)，所以有(n2-11)/2對。前面的那n對可以出現(xiàn)任意多對。圖片如下。(屮(2,”?……(n,n)f(l,2)(1,3)………(n-l,n)ln個有序?qū)?(2,1)(3,1)(n,n-l)J(n2-n)/2個有序?qū)ΘD共有11+(￡-11)/2個元素

即(i『+n)/2個所以得到對稱關(guān)系數(shù)為：2心】"A上有多少不同的反對稱關(guān)系。由定義：如果a,beA?僅當(dāng)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個有序?qū)梢猿霈F(xiàn)任意多次

'(12)(13).(2,1)(3,1)J(n2-n)/2個有序?qū)?n3n(n-1)/2(由62n所以得結(jié)果:2nx3n(n'1)/2即2“3心"2A上有多少不同的既非自反又非反自反的關(guān)系。解：2U'-2-2n(n-1)試著畫出R的關(guān)系圖并寫出對應(yīng)的關(guān)系矩陣。01230"1001解：Mr=100002110130010關(guān)系圖如下：21-設(shè)A={0丄2,3},&和出是A中的關(guān)系，Rj={<1,j>|j=i+1vj=1/2}%={<i.,j>1i=j+2}試求出關(guān)系矩陣：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=二內(nèi)0101K-21000000001000000000010000000Mr。MRj—0100Mr2°Mr:"1100000000100000111111000010oMR2°Mr.=0010叫=01010000000022.給定集合A={1,2,3}。圖4-6給出了A中的關(guān)系R的12個關(guān)系圖。對于每個關(guān)系圖,寫出相應(yīng)的關(guān)系矩陣，并證明被表達(dá)的關(guān)系是否是自反的或反自反的；是否是對稱的或反對稱的；是否是可傳遞的。（1）自反的、不對稱的、不可傳遞的；其對應(yīng)的關(guān)系矩陣為：110MR=111101（2）不自反的、反對稱的、其對應(yīng)的關(guān)系矩陣為：不可傳遞的；110Mr=001100

（3）自反的、對稱的、可傳遞的;其對應(yīng)的關(guān)系矩陣為：11Mr=1111111(4)自反的、不對稱的、其對應(yīng)的關(guān)系矩陣為不可傳遞的：■■110Mr=O11111(5)不自反的、不對稱的其對應(yīng)的關(guān)系矩陣為、不可傳遞的；??010Mr=111110(6)不自反的、對稱的、其對應(yīng)的關(guān)系矩陣為不可傳遞的：??111Mr=100100(7)自反的、反對稱的、其對應(yīng)的關(guān)系矩陣為可傳遞的：??101Mr=111001(8)自反的、不對稱的、其對應(yīng)的關(guān)系矩陣為不可傳遞的：??110Mr=111001(9)不自反的、對稱的、其對應(yīng)的關(guān)系矩陣為可傳遞的：此題圖有錯誤??011Mr=111111（10）自反的、反對稱的、不可傳遞的;

其對應(yīng)的關(guān)系矩陣為:101Mr=110011(11)自反的、反對稱的、可傳遞的；其對應(yīng)的關(guān)系矩陣為：100Mr=110101(12)不自反的、反對稱的、可傳遞的。其對應(yīng)的關(guān)系矩陣為：001Mr=11100123?設(shè)X是一個集合，巴和見是乂中的二元關(guān)系，并設(shè)&二巴，試證明：⑴心)》(%)(2)$(鳥)亠(％)⑶t(Rj二t(Rj證明：a)因?yàn)槌叨?，故R]U<4二二R2U/4,即r(R1)2r(R2)因?yàn)閟(R)對稱，且s(R)3R,(0R3R,故s(R)3R,由s(R)的定義，s(R)111121222是包含R,的最小對稱關(guān)系，故s(R)3s(R)■X因?yàn)閠(R)傳遞，且t(R)3R,但R3R,故t(R)因t(R)是包含R,的最小傳遞關(guān)系，所以t(R)d(R)在圖4.23中給出三個關(guān)系圖。試求每一個的自反的、對稱的和可傳遞的閉包，并畫出閉包的關(guān)系圖。解：由關(guān)系圖可知，R=0則：r(R)={<a,a>?<b?b>}s(R)=0t(R)=0解：由關(guān)系圖可知，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>}

解：由關(guān)系圖可知，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中的關(guān)系。試證明：⑴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)因?yàn)镽UR“R,由習(xí)題3-98,貝壯(RUR丿=t(R)同理t(RURJ=t(R丿]22所以t(RUR)=t(R)Ut(R)121226?設(shè)集合X={a,b,c,d,e,f,g,h},R是X中的二元關(guān)系，圖4-12給出了R的關(guān)系圖。試畫出可傳遞閉包t（R）的關(guān)系圖，并求出tsr（R）。解：由關(guān)系圖可知，<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?設(shè)R是集合X中的任意關(guān)系。試證明：(R?y=r+RoRx=R-=R*oR(ry=R*證明：(R‘)+=t(t(R)),因?yàn)閠(R)是傳遞的，根據(jù)定理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因?yàn)閞(R)是自反的，有習(xí)題3-97a),tr(R)是自反的，根據(jù)定理3-8.1,rtr(R)=tr(R),即tr(R)=R：所以，(R)29設(shè)｛a，A，...，aJ是集合a的劃分。試證明：｛ACIB,A,AB,...4Ab｝是集合AflB的劃分。證明：因?yàn)椋鸄，△，???，￡｝是集合A的劃分，所以AU曲T，2,...,D)A"=0(iHj)Ua=ai=l(l)因?yàn)锳ua所以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）構(gòu)成滿足劃分的條件，因此｛j\nB,AnB_4nB｝是集合AC1B的劃分。把n個元素的集合劃分成兩個類，共有多少種不同的分法?解:C：解:C：+C：+….+C：2在圖4.25中給出了集合｛1,2,3｝中的兩個關(guān)系圖，判斷這兩個關(guān)系是否是等價關(guān)系。解：左側(cè)的關(guān)系不是等價關(guān)系，因?yàn)椴粷M足可傳遞性；右側(cè)的關(guān)系是等價關(guān)系。在等價關(guān)系圖中，應(yīng)如何識別等價類？解：如果兩個元素之間有兩條連線，那么說明這兩個元素是等價類。33.設(shè)R是集合x中的關(guān)系。對于所有的\,Xj,xkeXf如果^RXj’XjRXk，就有,則稱關(guān)系R是循壞關(guān)系。試證明：當(dāng)且僅當(dāng)R是一個等價關(guān)系，R才是自反的和循環(huán)的。證明：（1）當(dāng)R是個等價關(guān)系時，由等價關(guān)系的定義知，等價關(guān)系滿足自反性，即R是自反的。任取x,y,zeX,<x,y>eR,<y,z>eR,由尺的可傳遞性，知vx,z>wr,再由R的對稱性，知VZ,x>wR。根據(jù)X,y,Z取值的任意性，知R是循環(huán)的。（2）當(dāng)R是自反的，可知對任意xeX,<x,x>eRotf取y€X,使得vx,y〉eR,因?yàn)閞是循環(huán)的，故當(dāng)vx,x>gr,<x,y>eR時，vy,x>wR°由丫，y取值的任意性知，R是對稱的；任取x,y,zeX,<x,y>eR,<y,z>eR,由r的循壞性知，VZ,X>wR‘因?yàn)镽是對稱的，因此VX,Z>wR，由x,y,z取值的任意性，知R是可傳遞的。因?yàn)镽是自反的、對稱的和可傳遞的，因此R是一個等價關(guān)系。34.設(shè)R和見是集合X中的等價關(guān)系。試證明：當(dāng)且僅當(dāng)C】中的每一個等價類都包含于C?的某一個等價類之中，才有R.CR.O證明：設(shè)等價關(guān)系%造成的集合x的劃分為C]二｛C]],C]2，???,Cim｝,等價關(guān)系$造成的集合x的劃分為C?二｛C21,C22,--sC2n｝（1）當(dāng)C]中的每一個等價類都包含于C?的某一個等價類之中時，任取?中的一個等價類q,則必包含在C?的一個等價類里，設(shè)包含在C2J中，ChcC2jo任取c“中兩元素X,y,由等價類的性質(zhì)知，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?的某一個等價類之中。綜上所述，當(dāng)且僅當(dāng)C］中的每一個等價類都包含于C?的某一個等價類之中，才有RuR2。37.設(shè)氏和見是集合x中的等價關(guān)系，并分別有秩片和E。試證明：氏門巴也是集合x中的等價關(guān)系，它的秩至多為5廠。還要證明gUR.不一定是集合x的一個會價關(guān)系。證明：(1)因?yàn)樾陌褪亲苑吹?，所以對于任意的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?是等價關(guān)系。⑵因?yàn)镽pR?是自反的，所以對于任意的X6X,都有對于任意的x,x>ex,x>eR>,故vx,x>e&UR^，所以RUR?是自反的：對于任意的x,yeX,若v^yxRU巴，則可能有三種補(bǔ)況：若且vx,y>iR,,那么因?yàn)镽pR?是對稱的，所以有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當(dāng)vx^yAeR^,y?z>eR>時，不能確定v%z>e&IjR^，故RUR?不是可傳遞的。

由上可知，RiUR2不是等價關(guān)系。由上可知，RiUR2不是等價關(guān)系。(2)(3)｛沙｝,儀pXj,化兒｝,｛期士｝,｛期雖｝,合并后,有(3)(4)｛屯,知％｝,｛電屁屁｝,｛禺,屯｝{x3,x4?x5},化嗎,奄}(4)｛屯,知％｝,｛電屁屁｝,｛禺,屯｝｛洛,馮,電｝,｛心沙｝,｛x2>x3｝,｛無禺｝,｛XpXj,儀,禺｝,合并，得｛馮遇対｝,｛無靭奄｝,債內(nèi),比｝,倍,莎｝綜上，最大相容類有四個，分別是｛Xj,x2,x3｝,｛無馮,務(wù)｝,億叢4，兀｝,｛西,*,吿｝°38.給定集合S=｛y\,A?..4｝的覆蓋，如何才能確定此覆蓋的相容關(guān)系。解：相容關(guān)系是具有反對稱性的關(guān)系，集合S的任何一個覆蓋X均能確定一個相容關(guān)系，反之亦然。設(shè)x=｛S],S2，...Sk｝是集合s二広厲…人｝的一個覆蓋，則由此覆蓋確定的s上的相容關(guān)系是：(S1x,S1)U(S2xS2)U...U(SkxSk)>其中SkxSk指S的子集Sk的笛卡爾積。如X=｛｛1,2｝,｛2,3｝｝是S=｛1,2,3｝的一個覆蓋，則此覆蓋確定的S上的相容關(guān)系是：｛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>｝設(shè)集合X=｛1,2,3,4,5,6｝,R是X中的關(guān)系。圖4-23給出了R的關(guān)系圖。試畫出R’和史的關(guān)系圖。解：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中的恒等關(guān)系，r是x中的任何關(guān)系。試證明：IXURUR是相容關(guān)系。證明：設(shè)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是相容關(guān)系41.給定等價關(guān)系R和S,它們的關(guān):系矩陣是110110Mr=110Ms=111001011試證明：RoS不是等價關(guān)系。證明：_11rMr°s=111o11可知RoS不是對稱的，因此，RoS不是等價關(guān)系。設(shè)集合X={1,2,3}。求出X中的等價關(guān)系R］和R?,使得RioR,也是個等價關(guān)系。解：設(shè)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中的等價關(guān)系。此時R。巴={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>},也是個等價關(guān)系。對于下列集合中的整除關(guān)系畫出哈斯圖。（1）{1,2,3,4,6,8,12,24}2424{1,2,3,…,12}解：(1)121263(2)44.如果R是集合X中的偏序關(guān)系，且ACX。試證明：RQ（AxA）是A中的偏序關(guān)系。證明：因?yàn)镽是集合X中的偏序關(guān)系，所以R是自反的，反對稱的，可傳遞的。（1）因?yàn)镽是自反的，所以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中的偏序關(guān)系。45-試給出集合X的實(shí)例，它能使(p(X),u)是全序集合。解：X={0},則q(X)={0,{0}}此時，對于任意的x,yep(X)?都有xqyUyqx所以(Q(x),u)是全序集合。46給出一個關(guān)系，它是集合中的偏序關(guān)系又是等價關(guān)系。解：集合X上的恒等關(guān)系，既是偏序關(guān)系又是等價關(guān)系。47.證明下列命題：如果R是擬序關(guān)系，則復(fù)也是擬序關(guān)系。(2)如呆R是偏序關(guān)系，則R也是偏序關(guān)系。如果R是全序關(guān)系，則反也是全序關(guān)系。存在一個集合S和S中的關(guān)系R,使得VS,R>是良序的，但<S,R>不是良序的。證明：設(shè)R是A上的二元關(guān)系，若R是自反的，則IacR,由于Ia的轉(zhuǎn)置仍是Ia，因此IauR，故住是自反的；若R是反自反的，則IAC|R=0。把Ia和R都取轉(zhuǎn)置，由于【A的轉(zhuǎn)置仍是【A，因此，IaAR=0,故反是反自反的；(C)若R是對稱的，任取<y,x>eR,則Vx,y>eR,由R的對稱性可知，<y,x>eR,于是<x,y>wR。由x,y取值的任意性知，復(fù)是對稱的；若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。故復(fù)是可傳遞的。從上述5條可以證明(1)一一(3)(1)若R是擬序關(guān)系，即R是反自反的和可傳遞得，由(b)(e)可知，反也是反自反的和可傳遞得，因此，良是擬序關(guān)系。（2）若R是偏序關(guān)系，即R是自反的、反對稱的，可傳遞的，由（a）（d）（e）可知,復(fù)也是自反的、反對稱的，可傳遞的，因此，復(fù)是偏序關(guān)系。（3）若R是全序關(guān)系，則R是偏序關(guān)系，由（2）知復(fù)也是偏序關(guān)系；另知，Vx,yeA,xRy或yRx成立，當(dāng)xRy時，y觸，當(dāng)興時，畫。因此不論任何情況,Vx,yeA,加7或y觸總成立。綜上，良也是全序關(guān)系。（4）舉例子，設(shè)VS,R>=VN,O,N是自然數(shù)集合，則VS,R>=VN,仝是良序，但是<S,Rx<N,n>不是良序。因?yàn)槿∪疦,在vS,R>=vN,A中沒有最小成員。48.設(shè)R是集合A上的二元關(guān)系，證明，當(dāng)且僅當(dāng)RAR=0和只=1<+,R才是擬序的。當(dāng)且僅當(dāng)R"R=IX和R二R*，R才是偏序的。證明：設(shè)R是集合A上的關(guān)系（1）充分性：r=r+,故R是可傳遞的；RP|R=0，所以對于任意的xwA,都有vx,x>$R,即R是反自反的。所以，當(dāng)RAR=0和R=R?時，R是擬序的。必要性：因?yàn)镽是擬序的，所以R是反自反的、可傳遞的、反對稱的。R是可傳遞的，故R=R+:R=R+是反對稱的，所以對于任意x,ywAxHy,若vx,y>eR,則<x,y>eR：又R是反自反的，所以RAR=0o所以，當(dāng)R是擬序時，RAR=0且只=時。（2）充分性：RAR=IX,故quR，即R是自反的；又RAR=IX,所以對于任意x,ywA,xHy,若vx,y>eR?則vy,x>$R，即R是反對稱的：又R=R\所以R是可傳遞的;所以，當(dāng)RPlR=Ix和只=只*時，R是偏序關(guān)系。必要性：因?yàn)镽是偏序關(guān)系，所以R是自反的，反對稱的，可傳遞的。R是自反的，故ixCR且ixcR；R是反對稱的，故對于任意的％ywAxHy,若vx,y>eR,則<x,y>gR,所以RnR=IXo又R是自反的，可傳遞的，所以它的自反可傳遞閉包是其本身，即R=R*；所以，當(dāng)R是偏序關(guān)系時，RnR=Ix且R二R*。49?圖4-28給出了偏序集合vP,R>的哈斯圖,這里P二{比理宀軸屁}。(1)下列關(guān)系中哪一個是真的：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■>第五章函數(shù)習(xí)題答案P[109-lll]1.卜列關(guān)系中哪些能夠構(gòu)成函數(shù)？對于不是函數(shù)的關(guān)系，說明不能構(gòu)成函數(shù)的原因。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)不能構(gòu)成函數(shù)。對于某些XEN,不止存在一個yeN使得x+yvl0成立。能構(gòu)成函數(shù)。不能構(gòu)成函數(shù)。對于某些對于某些xeR,存在兩個yeR使得y2=X成立。2?下列集合中，哪些能夠用來定義函數(shù)？試求出所定義的函數(shù)的域和值域。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)能夠用來定義函數(shù)。域：{1,2,3,4}值域:{<2,3>,<3,4>,<1,4>}能夠用來定義函數(shù)。域：{1,2,3}值域：{<2,3>,<3,4>,<3,2>}不能夠用來定義函數(shù)。能夠用來定義函數(shù)。域：{1,2,3}值域:{<2,3>}設(shè)I是證書集合，-是正整數(shù)集合，并且把函數(shù)F:ItI+，定義為f(i)=|2i|+l°試求出函數(shù)f的值域Rf。解：Rf為正奇數(shù)的集合。設(shè)E是全集，Q(E)是E的幕集，q(e)xq(e)是由E的子集所構(gòu)成的所有序偶的集合,對任意的S”S2ep(E),IEf:p(E)xP(E)^p(E)定義為f(S1,S2)=SlflS2-試證明:f的陪域與值域相等。?證明：f的陪域?yàn)閝(E)，設(shè)值域?yàn)椋?假定f的陪域與值域不相等，即RfCZ/7(E)0

那么一定存在q(E)的一個元素a,使得AgRf。因?yàn)閒(Sp^)=^05^因此，不存在任何一個Sps2,使得S】nS2=A。設(shè)S]=E，則對于任何S2e/?(E),由SiflSpHA知A,由S?取值的任意性可知，Agp(E)。這與a的取值在p(E)中相矛盾，因此f的陪域與值域不相