第一章集合習題1.11.{0,1,2,3,4}{11,13,17,19}{12,24,36,48,64}2.{x|xN且x100}Ev={x|xN且2整除x} Od={x|xN且2不能整除x}{y|存在xI使得y=10x}或{x|x/10I}3.極小化步驟省略=1\*GB3① {0,1,2,3,4,5,6,7,8,9}A；=2\*GB3②假設,A，那么A。或=1\*GB3① {0,1,2,3,4,5,6,7,8,9}A；=2\*GB3②假設A且a{0,1,2,3,4,5,6,7,8,9}，那么aA。或=1\*GB3① {0,1,2,3,4,5,6,7,8,9}A；=2\*GB3②假設A且a{0,1,2,3,4,5,6,7,8,9}，那么aA。=1\*GB3① {0,1,2,3,4,5,6,7,8,9}A；=2\*GB3②假設,A且0，那么A。c)=1\*GB3①假設a{0,1,2,3,4,5,6,7,8,9}，那么a.A；=2\*GB3②假設A且a{0,1,2,3,4,5,6,7,8,9}，那么aA；假設A且a{0,1,2,3,4,5,6,7,8,9}，那么aA。或=1\*GB3① {0.,1.,2.,3.,4.,5.,6.,7.,8.,9.}A；=2\*GB3②假設A且a{0,1,2,3,4,5,6,7,8,9}，那么aA；假設A且a{0,1,2,3,4,5,6,7,8,9}，那么aA。d)=1\*GB3① {0,10}A；=2\*GB3②假設A，那么1A；假設,A且0，那么A。e) Ev定義如下：=1\*GB3① {0}Ev或0Ev；=2\*GB3②假設Ev，那么+2Ev。 Od定義如下：=1\*GB3① {1}Od或1Od；=2\*GB3②假設Od，那么+2Od。f)=1\*GB3① {0}A或0A；=2\*GB3②假設A，那么A。4.A=G；C=F；B=E。5.題號是否正確 a) b)〔空集不含任何元素〕 c) d) e) f) g) h)6.題號是否正確 a)〔反例：A={a}；B=；C={{a}}〕 b)〔反例：A=；B={}；C={}〕 c)〔反例：A=；B={a}；C={}〕 d)〔反例：A=；B={}；C={{}}〕能。例如：B=A{A}。8.；{1}；{2}；{3}；{1,2}；{1,3}；{2,3}；{1,2,3}；；{1}；{{2,3}}；{1,{2,3}}；；{{1,{2,3}}}；；{}；；{}；{{}}；{,{}}；；{{1,2}}；；{{,2}}；{{2}}；{{,2},{2}}；9.{，{a}，{{b}}，{a,{b}}}；{，{1}，{}，{1,}}；{，{x}，{y}，{z}，{x,y}，{x,z}，{y,z}，{x,y,z}}；{，{}，{a}，{{a}}，{,a}，{,{a}}，{a,{a}}，{,a,{a}}}。習題1.21.A~B={4}；(AB)~C={1,3,5}；~(AB)={2,3,4,5}；~A~B={2,3,4,5}；(A–B)–C=；A–(B–C)={4}；(AB)C={5}；(AB)(BC)={1,2}。2.BC或B–E；AD；(A–B)C；C–B或C–A；(AC)(E–B)或(A–E)(E–B)；3.證明：對于任意xAC，因為xAC，所以xA或xC。假設xA，那么由于AB，因此xB；假設xC，那么由于CD，因此xD。所以，xB或xD，即xBD。所以，ACBD。類似可證ACBD。d) A–(BC)=A~(BC)=A(~B~C)=(AA)(~B~C) =(A~B)(A~C)=(A–B)(A–C)f) A–(A–B)=A~(A–B)=A~(A~B)=A(~AB) =(A~A)(AB)=(AB)=AB4.)假設A=B，那么AB=A且AB=A。因此，AB=(AB)–(AB)=A–A=。)假設AB=，那么AB=AB。又因為ABAAB且ABBAB，所以 AB=A=B=AB。所以A=B。證明略。 a) b) c)〔反例：A={a,b}，B={a}，C={b}〕 d)〔反例：A={a}，B={a,b}，C={a,c}〕 e) f)〔反例：A={a,b}，B={a}，C={b}〕 g)〔反例：A={a}，B={a,b}，C={a,c}〕6.BC~A；ABC；A~(BC)，即BC~A；ABC；(A–B)(A–C)=(A~B)(A~C)=((A~B)(A~C))–((A~B)(A~C))=((A~B)(A~C))~((A~B)(A~C))=((A~B)(A~C))(~(A~B)~(A~C))=((A~B)(A~C))((~AB)(~AC))=(A(~B~C))(~A(BC))=(A(~B~C))(BC)=A((BC)~(BC))=A(BC)因此，假設(A–B)(A–C)=A，那么A(BC)=A。所以，A(BC)。由上題，(A–B)(A–C)=A(BC)因此，假設(A–B)(A–C)=，那么A(BC)=。A=B；A=B=；A=B；B=；BA或AB。7.對于任意x(A)(B)，那么x(A)或x(B)。假設x(A)，那么xA。因為AAB，所以，xAB。因此，x(AB)。假設x(B)，那么xB。因為BAB，所以，xAB。因此，x(AB)。所以，總有x(AB)。因此，(A)(B)(AB)。對于任意x(A)(B)，那么x(A)且x(B)。x(A)，因此xA。x(B)，因此xB。所以，xAB。因此，x(AB)。所以，(A)(B)(AB)。8.{{}}={}，{{}}={}；{,{}}={}，{,{}}=；{{a},{b},{a,b}}={a,b}，{{a},{b},{a,b}}=。9.證明：假設xR0，那么xR且x1。所以對于任意iI+均有x<1+1/i。即對于任意iI+均有xRi。所以，x。假設x，那么對于任意iI+均有xRi。所以對于任意iI+均有x<1+1/i。所以，x1，故x。10.因為An+1An，所以，。11.，。12.；。習題1.31.a)證明：用第一歸納法 i)當n=1時，左邊=1/2=右邊； ii)對任意的k1，假設當n=k時命題為真，即因為即當n=k+1時命題也為真。由i)ii)可知，對于任意n1均有。b)證明：用第一歸納法 i)當n=1時，左邊=2=右邊； ii)對任意的k1，假設當n=k時命題為真，即 2+22+23++2k=2k+1-2因為 2+22+23++2k+2k+1=2k+1-2+2k+1=2k+2-2即當n=k+1時命題也為真。由i)ii)可知，對于任意n1均有 2+22+23++2n=2n+1-2。c)證明：用第一歸納法 i)當n=0時，左邊=10=右邊；當n=1時，左邊=22=右邊； ii)對任意的k1，假設當n=k時命題為真，即 2k2k因為 2k+1=22k22k2k+2=2(k+1)〔因為k1〕即當n=k+1時命題也為真。由i)ii)可知，對于任意n1均有 2n=2n。d)證明：用第一歸納法 i)當n=1時，左邊=3，右邊=3，3|3，所以n=1時命題為真； ii)對任意的k1，假設當n=k時命題為真，即 3|k3+2k因為 (k+1)3+2(k+1)=k3+3k2+3k+1+2k+2=(k3+2k)+3(k2+k+1)由于3|k3+2k且3|3(k2+k+1)，因此，3|(k+1)3+2(k+1)即當n=k+1時命題也為真。由i)ii)可知，對于任意n1均有 3|n3+2n。e)證明：用第一歸納法 i)當n=1時，左邊=6=右邊=3，所以n=1時命題為真； ii)對任意的k1，假設當n=k時命題為真，即 123+234++k(k+1)(k+2)=k(k+1)(k+2)(k+3)/4因為 123+234++k(k+1)(k+2)+(k+1)(k+2)(k+3)=k(k+1)(k+2)(k+3)/4+(k+1)(k+2)(k+3)= (k+1)(k+2)(k+3)(k+4)/4即當n=k+1時命題也為真。由i)ii)可知，對于任意n1均有 123+234++n(n+1)(n+2)=n(n+1)(n+2)(n+3)/4。證明：證明分三局部=1\*GB3①三個相鄰整數中最小者0；=2\*GB3②三個相鄰整數中最小者=-1；=3\*GB3③三個相鄰整數中最小者-2。對=1\*GB3①用第一歸納法，即證9|n3+(n+1)3+(n+2)3 i)當n=0時，9|9，所以n=0時命題為真； ii)對任意的k0，假設當n=k時命題為真，即9|k3+(k+1)3+(k+2)3因為(k+1)3+(k+2)3+(k+3)3= k3+3k2+3k+1+(k+1)3+3(k+1)2+3(k+1)+1+(k+2)3+3(k+2)2+3(k+2)+1= k3+(k+1)3+(k+2)3+3k2+3k+1+3(k+1)2+3(k+1)+1+3(k+2)2+3(k+2)+1= k3+(k+1)3+(k+2)3+9k2+27k+27= k3+(k+1)3+(k+2)3+9(k2+3k+3)由于9|k3+(k+1)3+(k+2)3且9|9(k2+3k+3)所以，9|(k+1)3+(k+2)3+(k+3)3，即當n=k+1時命題也為真。由i)ii)可知，對于任意n0均有 9|n3+(n+1)3+(n+2)3對=3\*GB3③由于9|n3+(n+1)3+(n+2)3，所以，9|(-n)3+(-(n+1))3+(-(n+2))3。對=2\*GB3②因為9|0，所以此時命題也為真。根據以上證明可知，任意三個相鄰整數的立方和能被9整除。g)證明：用第一歸納法 i)當n=0時，112+121=133，133|133，所以n=0時命題為真； ii)對任意的k0，假設當n=k時命題為真，即 133|11k+2+122k+1因為 11k+3+122(k+1)+1=1111k+2+122122k+1=11(11k+2+122k+1)+133122k+1由于 133|11k+2+122k+1且 133|133122k+1因此，133|11(11k+2+122k+1)+133122k+1。即當n=k+1時命題也為真。由i)ii)可知，對于任意n1均有 133|11n+2+122n+13.證明：用第二歸納法 i)當n=1時，，所以n=1時命題為真；當n=2時，，所以n=2時命題為真； ii)對任意的k2，假設當2nk時命題均為真，那么由對于任意nI+，Fn+1=Fn+Fn-1可知 Fk+1=Fk+Fk-1 Fk+1=Fk+Fk-1即當n=k+1時命題也為真。由i)ii)可知，對于任意n1均有。4.分析：〔證明略〕設n=(m+1)q+r，mr>0。首先，甲扳倒r根，然后每當乙扳倒x〔1xm〕根，因為1(m+1)–xm，所以此時甲可扳倒(m+1)–x根，故甲總能獲勝。證明：對q〔即n除以m+1的商〕用第一歸納法。 i)當q=0時，因為n=r且mr1，所以甲可一次將r根全部扳倒，那么甲獲勝。 ii)對任意的k0，假設當q=k時命題為真，那么當q=k+1時，即存在r使得n=(m+1)(q+1)+r，mr>0，由于此時甲可扳倒r根，然后乙只能扳倒x〔1xm〕根，此時剩下n=(m+1)q+(m+1)-q根，因為1(m+1)–xm，那么根據歸納假設可知甲總能獲勝。即當q=k+1時命題也為真。由i)ii)可知，對于任意q0均有甲總能獲勝。證明：用第一歸納法對于每個ii0，用Q(i)表示以下命題：對于任意jj0，P(i,j)皆真。下面驗證：Q(i)滿足第一歸納法的條件。i) Q(i0)為真，因為〔對j用第一歸納法〕：a)P(i0,j0)為真； b)假設P(i0,j)為真，那么P(i0,j+1)為真；由歸納法可知，Q(i0)為真。ii)假設Q(i)為真〔ii0〕，即對于任意ii0，jj0，P(i,j)為真。那么對于任意jj0，P(i+1,j)為真，即Q(i+1)為真。由i)和ii)可知，對于任意ii0，Q(i)皆真。所以，對于任意ii0，jj0，P(i,j)為真。6.證明：假設有nN使nn，即{n}n，故n+={n}nn，同時nn+，所以n=n+。矛盾！〔與皮亞諾公理矛盾〕證明：假設有mN使n<m，那么由“<〞定義可知nm，所以由習題7有nm。因為nm且nm，所以n{n}m，即n+m。而m<n+，那么由“<〞定義可知mn+，由習題7有mn+。n+m與mn+矛盾，所以假設不成立，即不可能有mN使n<m<n+。習題1.41.a) A{1}B={<0,1,1>,<0,1,2>,<1,1,1>,<1,1,2>}b) A2B={<0,0,1>,<0,0,2>,<0,1,1>,<0,1,2>,<1,0,1>,<1,0,2>,<1,1,1>,<1,1,2>}(BA)2={ <1,0,1,0>,<1,0,1,1>,<1,0,2,0>,<1,0,2,1>,<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>}2.題號是否正確 a)〔反例：A=D={a}，B=C=，那么左邊={<a,a>}，而右邊=〕 b) c)〔反例：A=C=D=N，B=，那么左邊=，而右邊=NN〕d)〔反例：A=C={1,2}，B={1}，D={2}，那么左邊={<2,1>}，而右邊={<1,1>,<2,1>,<2,2>}〕7.證明：題目等價于證明：假設<a,b>=<c,d>，那么a=c且b=d。設<a,b>=<c,d>，那么{{a,A},{b,B}}={{c,A},{d,B}}=1\*GB3① {a,A}={c,A}且{b,B}={d,B}所以，a=c且b=d。=2\*GB3② {a,A}={d,B}且{b,B}={c,A}那么因為AB，所以a=B,d=A,b=A且c=B。所以，a=c且b=d。故總有：a=c且b=d。第二章二元關系習題2.11.R={<0,0>,<0,2>,<2,0>,<2,2>}R={<1,1>,<4,2>}2.R1R2 ={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}R1R2 ={<2,4>}domR1 ={1,2,3}domR2 ={1,2,4}ranR1 ={2,3,4}ranR2 ={2,3,4}dom(R1R2)={1,2,3,4}ran(R1R2) ={4}3.證明：〔根據定義域和值域的定義進行證明〕因為xdom(R1R2)當且僅當有yB使得<x,y>(R1R2)當且僅當有yB使得<x,y>R1或<x,y>R2當且僅當有yB使得<x,y>R1或有yB使得<x,y>R2當且僅當xdom(R1)或xdom(R2)當且僅當xdom(R1)dom(R2)所以，dom(R1R2)=dom(R1)dom(R2)。因為假設xran(R1R2)，那么有xA使得<x,y>(R1R2)；有xA使得<x,y>R1且<x,y>R2；有xA使得<x,y>R1且有xA使得<x,y>R2；xran(R1)且xran(R2)；xran(R1)ran(R2)。所以，ran(R1R2)ran(R1)ran(R2)。4.L={<1,2>,<1,3>,<1,6>,<2,3>,<2,6>,<3,6>}；D={<1,1>,<1,2>,<1,3>,<1,6>,<2,2>,<2,6>,<3,3>,<3,6>,<6,6>}；LD={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>}。5.上的空關系；集合{1,2}上的二元關系{<1,1>}；集合{1,2}上的二元關系{<1,1>}；集合{1,2,3}上的二元關系{<1,2>,<2,1>,<1,3>}；6.假設R,S自反，那么RS,RS自反，R–S,RS必不自反。假設R,S反自反，那么RS,RS,R–S,RS反自反。假設R,S對稱，那么RS,RS,R–S,RS對稱。假設R,S反對稱，那么RS,R–S反對稱，RS,RS不一定反對稱。假設R,S傳遞，那么RS傳遞，,R–S,RS,RS不一定傳遞。S是對稱的、傳遞的；S是自反的、對稱的；S是反對稱的、傳遞的；S是反自反的、反對稱的、傳遞的；8.n(Am)=nm；n((Am))=；因為RAm，所以A上共有個m元關系。10.證明：用反證法。假設R不是反對稱的，即存在a,bA，使得<a,b>A,<b,a>A且ab。因為R是傳遞的，所以由<a,b>A且<b,a>A可知<a,a>A。這與R反自反性質矛盾。所以假設不成立。即R是反對稱的。11.證明：因為R={<x,y>|x,yA且<x,y>R}={{{x},{x,y}}|x,yA且<x,y>R}所以，R={{x},{x,y}|x,yA且<x,y>R}。所以，(R)={x|xA且有yA使得<x,y>R}{y|yA且有xA使得<x,y>R}。 =domRranR。即：fldR=domRranR。12.證明：因為domRfldR=(R)，ranRfldR=(R)，所以，RdomRranR(R)(R)。習題2.21.R是自反的、對稱的、傳遞的。2.自反的；反對稱的、傳遞的；自反的、對稱的、傳遞的；自反的、傳遞的；無；對稱的；自反的、反對稱的、傳遞的；對稱的；對稱的；反對稱的；自反的、反對稱的；反對稱的、傳遞的。4.A上共有個不相同的自反關系；A上共有個不相同的反自反關系；A上共有個不相同的對稱關系；A上共有個不相同的反對稱關系；A上共有個不相同的既是對稱的又是反對稱的關系；習題2.31.最多能有n(A)個元素為1。2.證明：i)RR-1為A上包含R的最小對稱關系=1\*GB3①RRR-1。所以，RR-1包含R。=2\*GB3②因為對于任意<a,b>RR-1，有<a,b>R或<a,b>R-1。假設<a,b>R，那么<b,a>R-1；假設<a,b>R-1，那么<b,a>R。因此，<b,a>RR-1。所以，RR-1為A上的對稱關系。=3\*GB3③設R為任意的A上包含R的對稱關系，那么對于任意<a,b>RR-1，有<a,b>R或<a,b>R-1。假設<a,b>R，由于R包含R，所以<a,b>R；假設<a,b>R-1，那么<b,a>R，由于R包含R，所以<b,a>R，而R對稱，所以<a,b>R。因此，總有<a,b>R。所以，RR-1R。由=1\*GB3①=2\*GB3②=3\*GB3③可知，RR-1為A上包含R的最小對稱關系。ii)RR-1為A上包含在R中的最大對稱關系=1\*GB3①RR-1R。所以，RR-1包含在R中。=2\*GB3②因為對于任意<a,b>RR-1，有<a,b>R且<a,b>R-1。<a,b>R，所以<b,a>R-1；<a,b>R-1，所以<b,a>R。因此，<b,a>RR-1。所以，RR-1為A上的對稱關系。=3\*GB3③設R為任意的A上包含在R中的對稱關系，那么對于任意<a,b>R，由于R包含在R中，所以<a,b>R；又由于R對稱，所以<b,a>R，而R包含在R中，所以<b,a>R，因此，<a,b>R-1；因此，總有<a,b>RR-1。所以，RRR-1。由=1\*GB3①=2\*GB3②=3\*GB3③可知，RR-1為A上包含在R中的最大對稱關系。習題2.41.R2R1={<c,d>}； R1R2={<a,d>,<a,c>}；R12={<a,a>,<a,b>,<a,d>}； R22={<b,b>,<c,c>}；2.m=1,n=16。4. A={1,2,3}令R1={<1,2>,<1,3>}；R2={<2,2>}；R3={<3,2>}；那么R1(R2R3)=；(R1R2)(R1R3)={<1,3>}；所以，R1(R2R3)(R1R2)(R1R3)。令R2={<2,2>}；R3={<2,3>}；R4={<2,1>,<3,1>}；那么(R2R3)R4=；(R2R4)(R3R4)={<2,1>}；所以，(R2R3)R4(R2R4)(R3R4)；5.正確。不正確。令A={1,2}，那么R1={<1,2>},R2={<2,1>}都是反自反的，但R1R2={<1,1>}不是反自反的。不正確。令A={1,2,3}，那么R1={<1,2>,<2,1>},R2={<2,3>,<3,2>}都是對稱的，但R1R2={<1,3>}不是對稱的。不正確。令A={1,2,3}，那么R1={<1,2>,<3,1>},R2={<2,3>,<1,1>}都是反對稱的，但R1R2={<1,3>,<3,1>}不是反對稱的。不正確。令A={1,2,3}，那么R1={<1,2>,<3,1>,<3,2>},R2={<2,3>,<1,1>}都是傳遞的，但R1R2={<1,3>,<3,1>,<3,3>}不是傳遞的。證明：a)對于任意kN，因為Rs=Rt，所以Rs+k=RsRk=RtRk=Rt+k。b)用關于k的歸納法證明。i)當k=0時，Rs+i=Rs+i。所以命題成立。ii)假設當k=m時命題成立，即Rs+mp+i=Rs+i。那么當k=m+1時，因為Rs+(m+1)p+i=Rs+p+mp+i=Rt+mp+i=RtRmp+i=RsRmp+i=Rs+mp+i。由歸納假設，Rs+(m+1)p+i=Rs+mp+i=Rs+i。由i)ii)可知對于任意k,iN，均有Rs+kp+i=Rs+i。假設kt-1，那么Rk{R0,R1,…,Rt-1}；假設kt，那么k=s+(t-s)q+r，即k=s+pq+r；〔其中，qN,0r<t-s=p〕此時，由b)可知Rk=Rs+pq+r=Rs+r{R0,R1,…,Rt-1}。所以，假設kN，那么Rk{R0,R1,…,Rt-1}。習題2.52.使t(R1R2)t(R1)t(R2)的R1和R2的具體實例如下：A={1,2}，R1={<1,2>}，R1={<2,1>}；那么t(R1)=R1，t(R2)=R2，t(R1R2)={<1,2>,<2,1>,<1,1>,<2,2>}，故真包含。4.b)使s(R1R2)s(R1)s(R2)的R1和R2的具體實例如下：A={1,2}，R1={<1,2>}，R1={<2,1>}；那么s(R1)=s(R2)={<1,2>,<2,1>}，s(R1R2)=s()=。故真包含：s(R1R2)s(R1)s(R2)。b)使t(R1R2)t(R1)t(R2)的R1和R2的具體實例如下：A={1,2,3}，R1={<1,2>,<2,1>}，R1={<1,3>,<3,1>}；那么t(R1)={<1,2>,<2,1>,<1,1>,<2,2>}，t(R2)={<1,3>,<3,1>,<1,1>,<3,3>}，t(R1R2)=s()=。故真包含：t(R1R2)t(R1)t(R2)。6.令A={1,2}，R={<1,2>}，那么ts(R)=t({<1,2>,<2,1>})={<1,2>,<2,1>,<1,1>,<2,2>}st(R)=s({<1,2>})={<1,2>,<2,1>}所以，st(R)ts(R)。習題2.61.正確；正確；不正確；〔不自反〕不正確；〔不自反〕不正確；〔不一定對稱〕正確。2. R的所有極大相容類為：{x1,x2,x3}，{x1,x3,x6}，{x3,x4,x5}，{x3,x5,x6}。3. A上共有個不相同的相容關系。習題2.71.不正確；〔不自反〕不正確；〔不自反〕不正確；〔不自反〕不正確；〔不傳遞，<-1,0>R,<0,1>R,但<-1,1>R〕不正確；〔不對稱〕不正確；〔不對稱〕不正確；〔不傳遞〕正確；不正確。〔不自反，i=10k時，<i,i>R〕2.不對。應加上條件：對于任意xA，總存在yA使得<x,y>R。3.證明：=1\*GB3①條件：假設<a,b>R，<a,c>R，那么<b,c>R。先證對稱性：假設<a,b>R，那么由于R自反，所以<a,a>R，由上式有<b,a>R。所以R對稱。再證傳遞性：假設<a,b>R，<b,c>R，那么因為R對稱，所以<b,a>R。由條件，因為<b,a>R且<b,c>R，所以<a,c>R。所以R傳遞。因此，R時等價關系。=2\*GB3②條件：R是等價關系。假設<a,b>R，<a,c>R，那么因為R對稱，所以<b,a>R。又由于R傳遞，所以，<b,c>R。因此，假設<a,b>R，<a,c>R，那么<b,c>R。習題2.81.半序；半序、全序、良序；無；〔不是反對稱的〕無；〔不是傳遞的〕半序；無；〔不是傳遞的〕無；〔不是傳遞的〕擬序。4.設R是集合A上的二元關系，證明：a) R是A上的半序，當且僅當RR-1=A且R=R*。自反、反對稱 __________________傳遞b) R是A上的擬序，當且僅當RR-1=且R=R+。反自反 __________________傳遞6.a)斷言中為真的有：x4Rx1,x1Rx1。b) P的最小元：無；P的最大元：x1；P的極小元：x4和x5；P的極大元：x1。c) {x2,x3,x4}的上界：x1；下界：x4；上確界：x1；下確界：x4。{x3,x4,x5}的上界：x1,x3；下界：無；上確界：x3；下確界：無。{x1,x2,x3}的上界：x1；下界：x4；上確界：x1；下確界：x4。7.<I,>中的非空子集I無最小元。<I+,|>〔“|〞為整除關系〕中的非空子集{x|x>4}無最大元。<R,>中的非空子集(0,1)由下確界0，但無最小元。書上例4中的非空子集{4}有上界8和12，但無上確界。8.歸納法。9.歸納法。第三章函數習題3.11.不是局部函數；原因：存在<0,1>,<0,2>f，但12。局部函數；不是局部函數。原因：存在<4,2>,<4,-2>f，但2-2。2.局部函數；定義域為：{1,2,3,4}，值域為：{<2,3>,<3,4>,<1,4>}。局部函數；定義域為：{1,2,3}，值域為：{<2,3>,<3,4>,<3,2>}。不是局部函數；局部函數。定義域為：{1,2,3}，值域為：{<2,3>}。3.證明：證明分兩局部：=1\*GB3①局部函數之單值性；=2\*GB3②domf=(A)(A)。5.證明：對于任意yf[A]–f[B]，那么yf[A]且yf[B]。因為yf[A]，所以存在xA使得f(x)=y。又因為yf[B]，所以xB。〔用反證法，假設xB，那么f(x)f[B]，而y=f(x)，所以yf[B]。矛盾〕所以，xA-B。因此，y=f(x)f[A-B]。于是，f[A-B]f[A]–f[B]。“=〞不能代替“〞的反例，令X={x1,x2}，Y={y}，f={<x1,y>,<x2,y>}。A={x1,x2}，B={x1}。那么f[A-B]={y}，而f[A]–f[B]=。6.f={<<-1,-1>,0>,<<-1,0>,-1>,<<-1,1>,-2>,<<0,-1>,1>,<<0,0>,0>,<<0,1>,-1>,<<1,-1>,2>,<<1,0>,1>,<<1,1>,0>}；ranf={-2,-1,0,1,2}；f{0,1}2={<<0,0>,0>,<<0,1>,-1>,<<1,0>,1>,<<1,1>,0>}；參見下題。7.a)=1\*GB3①mn，個；=2\*GB3②m>n，0個。b)=1\*GB3①m<n，0個；=2\*GB3②n=0且m0，0個；=3\*GB3③n=0且m=0，1個；=4\*GB3④mn1，第二類Stirling數。8.證明：f(99)=f(f(110))=f(100)=f(f(111))=f(101)=91。證明：=1\*GB3①f(100)=f(99)=91；=2\*GB3②i{1,2,…,9}，f(89+i)=f(90+i)，所以f(89)=f(90)=…=f(99)=91。f(89+i)=f(f(89+i+11))=f(90+i)。=3\*GB3③假設當k+1x100時，f(x)均等于91。(0k89)那么當x=k(k0)時，那么有f(k)=f(f(k+11))。而0k89，所以k+1k+11100，由歸納假設有f(k+11)=91，即f(k)=f(91)=91。所以，f(x)=91對于0k89也成立。習題3.24.歸納法。5.證明：=1\*GB3①因為f:AA為滿射，所以aA.xaA使得f(xa)=a。又因為ff=f，所以f(a)=f(f(xa))=ff(xa)=f(xa)=a，即f(a)=a。所以Af。=2\*GB3②對于任意<x,y>f，因為Af，所以<x,x>f。而f為局部函數，即“單值〞，于是，x=y。所以<x,y>=<x,x>A。所以fA。=2\*GB3②另證下面要證明Af不可能。用反證法，假設Af，那么存在aa使得f(a)=a。因為f為滿射，所以必存在xaA使得f(xa)=a。因為ff=f，所以a=f(xa)=ff(xa)=f(f(xa))=f(a)=a，即a=a。這與aa矛盾。所以假設不成立，即Af不可能。由=1\*GB3①=2\*GB3②可知A=f。6.證明：首先，dom(gf)=f-1[domg]。因為ranfdomg，所以domf=f–1[ranf]f–1[domg]。又因為domgY，而f-1[Y]=domgf，所以f–1[domg]f–1[Y]=domf。所以，dom(gf)=domf。8.因為ff=f，所以對于任意iA，均有f(f(i))=f(i)。即假設f(i)=j(ji)，那么f(j)=i。設m為集合{i|iA且f(i)=i}的元素個數，即m為f中對應到自身的二元序偶個數。那么對m求累加和得到滿足ff=f的函數個數為個。ff=A，所以f為雙射，并且對于任意iA，均有f(f(i))=i〔即假設<i,j>f且ij，那么<j,i>f〕。〔特征：未對應到自身的二元序偶個數必為偶數個。〕設k為集合{i|iA且f(i)=i}的元素個數/2，即2k為f中對應到自身的二元序偶個數。那么對k求累加和得到滿足ff=A的函數個數：當n為偶數時，有個；當n為奇數時，有個。fff=A，所以f為雙射，因此滿足fff=A的函數個數：當n=3k+1(kN)時，有個；當n=3k+2(kN)時，有個；當n=3k(kN)時，有個。9.證明：因為gf為滿射，所以g為滿射。而g又是內射，所以g為雙射。假設f不是滿射，那么存在yY使得yranf。而g是雙射，所以g(y)Z，又gf為滿射，所以ran(gf)=Z。即g(y)ran(gf)。所以存在xX使得g(y)=gf(x)=g(f(x))。因為g為內射，所以y=f(x)。因此，yranf。這與yranf矛盾。所以假設不成立，即f是滿射。證明：因為gf為內射，所以f為內射。而f又是滿射，所以f為雙射。假設g不是內射，那么存在y1,y2Y使得y1y2并且g(y1)=g(y2)。因為f為雙射，所以存在x1,x2X使得x1x2并且f(x1)=y1，f(x2)=y2。而gf為內射，那么gf(x1)gf(x2)，即g(y1)g(y2)。這與g(y1)=g(y2)矛盾。所以假設不成立，即g是內射。習題3.33.k(x)=x/3；k(x)=(x+1)/3；4.f左可逆，但g不一定左可逆。證明：因為gf左可逆，那么gf為內射，所以f為內射。g不一定左可逆，反例如下： A={a}，B={b1,b2}，C={c}。f={<a,b1>}，g={<b1,c>,<b2,c>}，gf={<a,c>}。所以，gf是內射，即是左可逆的；但g不是內射，即不是左可逆的。5.證明：f是可逆的，那么易證f又唯一的左〔右〕逆。另一邊證明以“f有唯一左逆，那么f可逆。〞為例。aA，g=f-1((Y–ranf){a})就是f的一個左逆。而f僅有唯一左逆且n(A)2，這說明Y–ranf=，即ranf=Y。所以，f為滿射。又因為f左可逆，所以f為內射。即f為雙射。所以f可逆。習題3.42.ABC=；A=B；B=；A=B。習題3.51.b)或c) f(x)=1/2–x/4或f(x)=1/2cos(x/3)。2.證明：假設存在1kn使得x1+…+xk被n整除，那么取i=1,k=k即可。否那么，x1,x1+x2,…,x1+…+xn共n個數，而它們被n除的余數除0外僅有n-1個。根據抽屜原那么，其中必有兩個它們被n除的余數相等。假設它們為：〔j1<j2〕x1+…+xj1和x1+…+xj2那么取i=j1+1,k=j2即可。4.證明：共有n組數據。任取n+1個小于等于2n正整數中必有兩個數處于同一組，這兩個數互素。6.證明：一個整數被100除的余數共有100個，可以將它們分成51組。任取52個整數中必有兩個數除100后余數同處于一組。這是有兩種情況：一是它們除100后余數相同，此時兩個數相減即可；一是它們除100后余數不同，此時兩個數相加即可。8.#*=0。其中雙射為：f(ai)=i。#Q=0。正有理數a=m/n，m>0,n>0并且m和n互質，那么：Q+~NN~N。所以#Q+=0。#Q=2#Q++1=1+0+0=0。0。10.。第四章命題邏輯習題4.11.題號是否為命題命題的真值 a)〔沒有確定的真假〕 b)F c)T d)T e)F f)〔祈使句〕 g)〔疑問句〕2.PRQQRPQRP〔需考慮優先級〕3.〔答案不止一種，只要真值表相同即可〕a)P:PPPQ:(PQ)(PQ)即(PQ)PQ:(PP)(QQ)PQ:P(QQ)PQ:(PQ)((PP)(QQ))或(P(QQ))(Q(PP))b)P:PPPQ:(PQ)(PQ)即(PQ)PQ:(PP)(QQ)和參考c)或d)定義c)PQ:(PQ)PQ:PQPQ:(PQ)(PQ)d)PQ:(PQ)PQ:(PQ)PQ:(PQ)(QP)e)PQ:PQ其它參考c)f)證明：要證明用、、、不能表示，只需證明僅用、、、不能表達出含的某些公式即可。因為PPP；PPP；PPT；PPT。增加T之后，TPPTP；PTTPT；TPP；PTT； TPPTP。這也就是說，由、、、只能得出P或T，不能得出P。習題4.21.a)T b)T c)T d)F e)F f)T2.以e)為例PQPQPQFFFFTFTTFTTFFTFFFTTTFTFTTFTTTFTFTTTFTTTFFTTFTFFT解釋以P、Q、R的順序排列，那么為真的解釋如下所示：(FFT)、(FTT)、(TFT)、(TTT)(FFF)、(FTF)4. a)是永真的 b)是永真的 c)是永真的 d)是可滿足的 e)是可滿足的 f)是可滿足的 g)是永真的 h)是永真的 i)是永假的 j)是永假的5. a) (((PQ)((PQ)R))(PQ))(PQ)〔有的括號可省略〕(Q(PP))((PP)Q)〔有的括號可省略〕6. c)是a)的代換實例〔 Q/P，(PP)/Q〕 d)是a)的代換實例〔 (P(QP))/Q〕 e)是b)的代換實例〔 R/P，S/Q，Q/R，P/S〕 b)是e)的代換實例〔 S/P，R/Q，P/R，Q/S〕習題4.31.以a)為例：a) P(QP)P(PQ)的真值表如下：PQP(QP)P(PQ)FFFTFTFTTFTFTFFTFTTFFTTFTFTTTFTTFTTTFTTTFFTTTTTTTTFTTTTT上述真值表說明P(QP)P(PQ)為永真式。所以，P(QP)P(PQ)。2.(PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ)(PQ)(PQ) P(QQ) PT P所以，(PQ)(PQ) P。根據對偶原理得出的新的等價式為：(PQ)(PQ) P。(PQ)(PQ)(PQ) (P(QQ))(PQ)(PF)(PQ)P(PQ)(PP)(PQ)F(PQ)(PQ)(PQ)(PQ)所以，(PQ)(PQ)(PQ)(PQ)。根據對偶原理得出的新的等價式為：(PQ)(PQ)(PQ)(PQ)。4.PQ Q〔I2〕 PQ〔I6〕PQ PPPQ〔I9〕 PPQ〔I1〕e) (PPQ)(PPR) (TQ)(PPR)〔E23〕 (TQ)(TR)〔E23〕 (FQ)(TR)〔E16〕 (FQ)(FR)〔E16〕(TQ)(FR)(TQ)(TR)(QT)(RT)〔E3〕QR〔E14〕上述均為等價變換，所以蘊含式也成立。5.以b)為例：b) P(QRP) P((QR)P) P((QR)P) P((QR)P) P(P(QR)) (PP)(QR)PQR(PQR)(PQR)為P(QRP)只包含和的化簡式。習題4.41.e)PQ(PQ)PQ((PQ)(PQ))〔化去〕(PQ)((PQ)(PQ))〔化去〕(PQ)((PQ)(PQ))〔內移〕(PQ)((PQ)(PQ))〔最多保存一個〕(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)為PQ(PQ)的主合取范式。 (PQ)(PQ)(PQ)(P(QQ))(PQ)(PT)(PQ)P(PQ)(PP)(PQ)T(PQ)PQPQ為PQ(PQ)的主合取范式。g) (PQR)(PQR)(P(QR))(P(QR))〔化去〕(P(QR))(P(QR))〔最多保存一個〕(PQ)(PR)(PQ)(PR)〔關于的分配率〕(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)〔變為極大項〕(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)〔合并相同項〕(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)為(PQR)(PQR)的主合取范式。 (PQR)(PQR)(P(QR))(P(QR))〔化去〕(P(QR))(P(QR))〔最多保存一個〕(PP)(PQR)(QRP)(QRQR)〔關于的分配率〕F(PQR)(QRP)F〔化簡〕(PQR)(QRP)〔化簡〕(PQR)(QRP)為(PQR)(PQR)的主析取范式。2.a) (PQ)(PR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)PQRP(QR)(PQ)(PR)(PQR)(PQR)(PQR)所以，(PQ)(PR)PQR。c) PQ(PQ)(PQP)(PQQ)FFFPQ(PQ)(PQP)(PQQ)FFF所以，PQ(PQ)PQ(PQ)。3.合式公式P既是主合取范式，又是主析取范式。4.求wffA的主析取范式的算法：利用E16和E22刪去和在A中的所有出現，得到A1；利用德摩爾根律將A1中的內移到原子之前，并用E1使每個原子之前至多僅有一個；在用分配律將ii)的結果化為假設干個合取式的析取，其中每個合取式的因子皆為原子或原子的否認；對于iii)的結果中的每個合取式B，假設命題變元P在B中不出現，利用 (BP)(BP)(B(PP)BTB)取代B，直到每個合取式都變為極小項，最后刪除相同項。第五章謂詞邏輯習題5.11.每個自然數都有唯一的后繼；解：“每個〞是全稱的概念；“自然數〞需引進一個特性謂詞；“有〞表示存在；“唯一〞表示所有具有該性質的元素均相等〔即假設x具有該性質，y也具有該性質，那么x等于y〕；“后繼〞用謂詞表示。于是，可令：N(x)：x是自然數；Q(x,y)：y是x的后繼；E(x,y)：x等于y；那么上述命題可以符號化為： (x)(N(x)(y)(Q(x,y)(z)(Q(x,z)E(y,z))b)沒有以0為后繼的自然數；解：“沒有〞表示不存在；“自然數〞用特性謂詞表示；“后繼〞用謂詞表示。于是，可令：N(x)：x是自然數；Q(x,y)：y是x的后繼；那么上述命題可以符號化為：(x)(N(x)Q(x,0))注意：=1\*GB3①對于引進的特性謂詞，在全稱量詞約束下要用邏輯聯結詞“〞，在存在量詞約束下要用邏輯聯結詞“〞。=2\*GB3②“唯一〞概念的符號化。2.存在唯一的偶素數；解：“存在〞是存在量詞的概念；“唯一〞可參照上題；“偶數〞、“素數〞用謂詞表示。于是，可令：E(x)：x是偶數；S(x)：x是素數；R(x,y)：x等于y；那么上述命題可以符號化為：(x)(E(x)S(x)(y)(E(y)S(y)R(x,y))沒有既是奇數又是偶數的數；解：“沒有〞表示不存在；“奇數〞、“偶數〞、“數〞用謂詞表示。于是，可令：O(x)：x是奇數；E(x)：x是偶數； Q(x)：x是數；那么上述命題可以符號化為：(x)(Q(x)O(x)E(x))3.所有可證明的算術命題都是真的；存在真的但不可證明的算術命題；對于任意的三個算術命題x,y,z，假設z=xy且z是可證明的，那么x是可證明的或y是可證明的；對于任意的三個算術命題x,y,z，假設x是真的并且z=xy，那么z是真的；4.對任意整數x,y和z，x<z是x<y且y<z的必要條件；解：“任意〞是全稱的概念；“整數〞需引進一個特性謂詞；“<〞用謂詞表示；“必要條件〞用邏輯聯結詞來表示。于是，可令：I(x)：x是整數；L(x,y)：x<y；那么上述命題可以符號化為： (x)(y)(z)(I(x)I(y)I(z)(L(x,y)L(y,z)L(x,z)))b)對任意整數x，假設x=2，那么3x=6；反之亦然；解：“任意〞是全稱的概念；“整數〞需引進一個特性謂詞；“=〞用謂詞表示；“〞用函詞表示。于是，可令：〔2、3、6可以用常元表示〕I(x)：x是整數；E(x,y)：x=y；f(x,y)：xy；那么上述命題可以符號化為： (x)(I(x)(E(x,2)E(f(3,x),6))(E(f(3,x),6)E(x,2)))或 (x)(I(x)(E(x,2)E(f(3,x),6)))習題5.21.除了最后一個x是自由出現外，其它的6次x的出現都是約束出現。第一個(x)的轄域為下面的劃線局部：(x)(P(x)(x)Q(x))((x)P(x)Q(x))第一個(x)的轄域為下面的劃線局部：(x)(P(x)(x)Q(x))((x)P(x)Q(x))第二個(x)的轄域為下面的劃線局部：(x)(P(x)(x)Q(x))((x)P(x)Q(x))a)T；b)F；c)F；d)T；e)T；f)T。以a)為例：解：因為P(a,a)為T，所以(y)P(a,y)為T；因為P(b,b)為T，所以(y)P(b,y)為T；因為(y)P(a,y)和(y)P(b,y)均為T，所以(x)(y)P(x,y)也為T。3.a)F；b)T；c)F。4.a)T；b)F；c)T。習題5.31.(x)(P(x)Q(x))((x)P(x)(x)Q(x))為永真式。證明：給定(x)(P(x)Q(x))((x)P(x)(x)Q(x))在論域D上的任意解釋I，如果(x)P(x)(x)Q(x)在I下為假，那么(x)P(x)在I下為真，并且(x)Q(x)在I下為假。因為(x)Q(x)在I下為假，所以存在cD使Q(c)在I下為假。因為(x)P(x)在I下為真，所以P(c)在I下為真。因此，P(c)Q(c)在I下為假。所以，(x)(P(x)Q(x))在I下為假。于是，(x)(P(x)Q(x))((x)P(x)(x)Q(x))為永真式。b)((x)P(x)(x)Q(x))(x)(P(x)Q(x))不是永真式。解：取上述合式公式的解釋I如下：論域D={a,b}；P(a)P(b)Q(a)Q(b)_____________________________FTFF那么(x)(P(x)Q(x))在I下為假，((x)P(x)(x)Q(x))在I下為真。所以，((x)P(x)(x)Q(x))(x)(P(x)Q(x))在I下為假。((x)P(x)(x)Q(x))(x)(P(x)Q(x))為永真式。證明：給定((x)P(x)(x)Q(x))(x)(P(x)Q(x))在論域D上的任意解釋I，如果(x)(P(x)Q(x))在I下為假，那么存在cD使P(c)Q(c)在I下為假。即P(c)在I下為真并且Q(c)在I下為假。因為P(c)在I下為真，所以(x)P(x)在I下為真。因為Q(c)在I下為假，所以(x)Q(x)在I下為假。所以，(x)P(x)(x)Q(x)在I下為假。于是，((x)P(x)(x)Q(x))(x)(P(x)Q(x))為永真式。d)(x)(P(x)Q(x))((x)P(x)(x)Q(x))不是永真式。解：取上述合式公式的解釋I如下：論域D={a,b}；P(a)P(b)Q(a)Q(b)_____________________________FTFT那么(x)(P(x)Q(x))在I下為真，((x)P(x)(x)Q(x))在I下為假。所以，(x)(P(x)Q(x))((x)P(x)(x)Q(x))在I下為假。2.(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))〔因為y在P(x)中沒有自由出現〕(x)P(x)(y)Q(y)〔因為x在(y)Q(y)中沒有自由出現〕所以，(x)(y)(P(x)Q(y))(x)P(x)(y)Q(y)。(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))〔因為y在P(x)中沒有自由出現〕(x)P(x)(y)Q(y)〔因為x在(y)Q(y)中沒有自由出現〕(x)P(x)所以，(x)(y)(P(x)Q(y))(x)P(x)。(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))〔因為y在P(x)中沒有自由出現〕(x)P(x)(y)Q(y)〔因為x在(y)Q(y)中沒有自由出現〕所以，(x)(y)(P(x)Q(y))(x)P(x)(y)Q(y)。(x)(y)(P(x)Q(y))(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))〔因為y在P(x)中沒有自由出現〕(x)(P(x))(y)Q(y)〔因為x在(y)Q(y)中沒有自由出現〕(x)P(x)(y)Q(y)(x)P(x)(y)Q(y)所以，(x)(y)(P(x)Q(y))(x)P(x)(y)Q(y)。(x)(y)(P(x)Q(y))(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))〔因為y在P(x)中沒有自由出現〕(x)(P(x))(y)Q(y)〔因為x在(y)Q(y)中沒有自由出現〕(x)P(x)(y)Q(y)(x)P(x)(y)Q(y)所以，(x)(y)(P(x)Q(y))(x)P(x)(y)Q(y)。3.解：(x)(P(x)Q(x))((x)(P(x))(x)(Q(x)))____上述這一步不正確。根據書中105頁I16：(x)(P(x)Q(x))(x)(P(x))(x)(Q(x))可知：(x)(P(x)Q(x))((x)(P(x))(x)(Q(x)))因此，最后應該證明出： (x)(P(x)Q(x)) (x)P(x)(x)Q(x))這就是書中的I15。習題5.41.a)(y)(z)(P(z,y)(x)(P(z,x)P(x,z)))(y)(z)((P(z,y)(x)(P(z,x)P(x,z)))(P(z,y)(x)(P(z,x)P(x,z))))〔化去〕(y)(z)((P(z,y)(x)(P(z,x)P(x,z)))(P(z,y)(x)(P(z,x)P(x,z))))〔內移〕(y)(z)((x)(P(z,y)(P(z,x)P(x,z)))(x)(P(z,y)(P(z,x)P(x,z))))〔、前移〕(y)(z)((x)(P(z,y)(P(z,x)P(x,z)))(u)(P(z,y)(P(z,u)P(u,z))))〔換名〕(y)(z)(x)(u)((P(z,y)(P(z,x)P(x,z)))(P(z,y)(P(z,u)P(u,z))))〔、前移〕上述公式即為原公式的前束范式。令f為二元函詞，那么原公式的無前束范式為：(z)(x)((P(z,a)(P(z,x)P(x,z)))(P(z,a)(P(z,f(z,x))P(f(z,x),z))))(x)(y)(z)((P(x,y)P(y,z)P(z,z))(P(x,y)Q(x,y)Q(x,z)Q(z,z)))(x)(y)(z)((P(x,y)(P(y,z)P(z,z)))((P(x,y)Q(x,y))(Q(x,z)Q(z,z))))〔化去〕(x)(y)(z)((P(x,y)(P(y,z)P(z,z)))((P(x,y)Q(x,y))(Q(x,z)Q(z,z))))〔內移〕上述公式即為原公式的前束范式。令g為二元函詞，那么原公式的無前束范式為：(x)(y)((P(x,y)(P(y,g(x,y))P(g(x,y),g(x,y))))((P(x,