國防科大版離散數(shù)學(xué)習(xí)題答案

第一章集合習(xí)題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②假設(shè),A，那么A。或=1\*GB3① {0,1,2,3,4,5,6,7,8,9}A；=2\*GB3②假設(shè)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②假設(shè)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②假設(shè),A且0，那么A。c)=1\*GB3①假設(shè)a{0,1,2,3,4,5,6,7,8,9}，那么a.A；=2\*GB3②假設(shè)A且a{0,1,2,3,4,5,6,7,8,9}，那么aA；假設(shè)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②假設(shè)A且a{0,1,2,3,4,5,6,7,8,9}，那么aA；假設(shè)A且a{0,1,2,3,4,5,6,7,8,9}，那么aA。d)=1\*GB3① {0,10}A；=2\*GB3②假設(shè)A，那么1A；假設(shè),A且0，那么A。e) Ev定義如下：=1\*GB3① {0}Ev或0Ev；=2\*GB3②假設(shè)Ev，那么+2Ev。 Od定義如下：=1\*GB3① {1}Od或1Od；=2\*GB3②假設(shè)Od，那么+2Od。f)=1\*GB3① {0}A或0A；=2\*GB3②假設(shè)A，那么A。4.A=G；C=F；B=E。5.題號(hào)是否正確 a) b)〔空集不含任何元素〕 c) d) e) f) g) h)6.題號(hào)是否正確 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}，{}，{a,}}；{，{1}，{}，{1,}}；{，{x}，{y}，{z}，{x,y}，{x,z}，{y,z}，{x,y,z}}；{，{}，{a}，{{a}}，{,a}，{,{a}}，{a,{a}}，{,a,{a}}}。習(xí)題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.證明：對(duì)于任意xAC，因?yàn)閤AC，所以xA或xC。假設(shè)xA，那么由于AB，因此xB；假設(shè)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.)假設(shè)A=B，那么AB=A且AB=A。因此，AB=(AB)–(AB)=A–A=。)假設(shè)AB=，那么AB=AB。又因?yàn)锳BAAB且ABBAB，所以 AB=A=B=AB。所以A=B。證明略。 a) b) c)〔反例：A={a,b}，B={a}，C=〕 d)〔反例：A={a}，B={a,b}，C={a,c}〕 e) f)〔反例：A={a,b}，B={a}，C=〕 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)因此，假設(shè)(A–B)(A–C)=A，那么A(BC)=A。所以，A(BC)。由上題，(A–B)(A–C)=A(BC)因此，假設(shè)(A–B)(A–C)=，那么A(BC)=。A=B；A=B=；A=B；B=；BA或AB。7.對(duì)于任意x(A)(B)，那么x(A)或x(B)。假設(shè)x(A)，那么xA。因?yàn)锳AB，所以，xAB。因此，x(AB)。假設(shè)x(B)，那么xB。因?yàn)锽AB，所以，xAB。因此，x(AB)。所以，總有x(AB)。因此，(A)(B)(AB)。對(duì)于任意x(A)(B)，那么x(A)且x(B)。x(A)，因此xA。x(B)，因此xB。所以，xAB。因此，x(AB)。所以，(A)(B)(AB)。8.{{}}={}，{{}}={}；{,{}}={}，{,{}}=；{{a},,{a,b}}={a,b}，{{a},,{a,b}}=。9.證明：假設(shè)xR0，那么xR且x1。所以對(duì)于任意iI+均有x<1+1/i。即對(duì)于任意iI+均有xRi。所以，x。假設(shè)x，那么對(duì)于任意iI+均有xRi。所以對(duì)于任意iI+均有x<1+1/i。所以，x1，故x。10.因?yàn)锳n+1An，所以，。11.，。12.；。習(xí)題1.31.a)證明：用第一歸納法 i)當(dāng)n=1時(shí)，左邊=1/2=右邊； ii)對(duì)任意的k1，假設(shè)當(dāng)n=k時(shí)命題為真，即因?yàn)榧串?dāng)n=k+1時(shí)命題也為真。由i)ii)可知，對(duì)于任意n1均有。b)證明：用第一歸納法 i)當(dāng)n=1時(shí)，左邊=2=右邊； ii)對(duì)任意的k1，假設(shè)當(dāng)n=k時(shí)命題為真，即 2+22+23++2k=2k+1-2因?yàn)?2+22+23++2k+2k+1=2k+1-2+2k+1=2k+2-2即當(dāng)n=k+1時(shí)命題也為真。由i)ii)可知，對(duì)于任意n1均有 2+22+23++2n=2n+1-2。c)證明：用第一歸納法 i)當(dāng)n=0時(shí)，左邊=10=右邊；當(dāng)n=1時(shí)，左邊=22=右邊； ii)對(duì)任意的k1，假設(shè)當(dāng)n=k時(shí)命題為真，即 2k2k因?yàn)?2k+1=22k22k2k+2=2(k+1)〔因?yàn)閗1〕即當(dāng)n=k+1時(shí)命題也為真。由i)ii)可知，對(duì)于任意n1均有 2n=2n。d)證明：用第一歸納法 i)當(dāng)n=1時(shí)，左邊=3，右邊=3，3|3，所以n=1時(shí)命題為真； ii)對(duì)任意的k1，假設(shè)當(dāng)n=k時(shí)命題為真，即 3|k3+2k因?yàn)?(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)即當(dāng)n=k+1時(shí)命題也為真。由i)ii)可知，對(duì)于任意n1均有 3|n3+2n。e)證明：用第一歸納法 i)當(dāng)n=1時(shí)，左邊=6=右邊=3，所以n=1時(shí)命題為真； ii)對(duì)任意的k1，假設(shè)當(dāng)n=k時(shí)命題為真，即 123+234++k(k+1)(k+2)=k(k+1)(k+2)(k+3)/4因?yàn)?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即當(dāng)n=k+1時(shí)命題也為真。由i)ii)可知，對(duì)于任意n1均有 123+234++n(n+1)(n+2)=n(n+1)(n+2)(n+3)/4。證明：證明分三局部=1\*GB3①三個(gè)相鄰整數(shù)中最小者0；=2\*GB3②三個(gè)相鄰整數(shù)中最小者=-1；=3\*GB3③三個(gè)相鄰整數(shù)中最小者-2。對(duì)=1\*GB3①用第一歸納法，即證9|n3+(n+1)3+(n+2)3 i)當(dāng)n=0時(shí)，9|9，所以n=0時(shí)命題為真； ii)對(duì)任意的k0，假設(shè)當(dāng)n=k時(shí)命題為真，即9|k3+(k+1)3+(k+2)3因?yàn)?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，即當(dāng)n=k+1時(shí)命題也為真。由i)ii)可知，對(duì)于任意n0均有 9|n3+(n+1)3+(n+2)3對(duì)=3\*GB3③由于9|n3+(n+1)3+(n+2)3，所以，9|(-n)3+(-(n+1))3+(-(n+2))3。對(duì)=2\*GB3②因?yàn)?|0，所以此時(shí)命題也為真。根據(jù)以上證明可知，任意三個(gè)相鄰整數(shù)的立方和能被9整除。g)證明：用第一歸納法 i)當(dāng)n=0時(shí)，112+121=133，133|133，所以n=0時(shí)命題為真； ii)對(duì)任意的k0，假設(shè)當(dāng)n=k時(shí)命題為真，即 133|11k+2+122k+1因?yàn)?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。即當(dāng)n=k+1時(shí)命題也為真。由i)ii)可知，對(duì)于任意n1均有 133|11n+2+122n+13.證明：用第二歸納法 i)當(dāng)n=1時(shí)，，所以n=1時(shí)命題為真；當(dāng)n=2時(shí)，，所以n=2時(shí)命題為真； ii)對(duì)任意的k2，假設(shè)當(dāng)2nk時(shí)命題均為真，那么由對(duì)于任意nI+，F(xiàn)n+1=Fn+Fn-1可知 Fk+1=Fk+Fk-1 Fk+1=Fk+Fk-1即當(dāng)n=k+1時(shí)命題也為真。由i)ii)可知，對(duì)于任意n1均有。4.分析：〔證明略〕設(shè)n=(m+1)q+r，mr>0。首先，甲扳倒r根，然后每當(dāng)乙扳倒x〔1xm〕根，因?yàn)?(m+1)–xm，所以此時(shí)甲可扳倒(m+1)–x根，故甲總能獲勝。證明：對(duì)q〔即n除以m+1的商〕用第一歸納法。 i)當(dāng)q=0時(shí)，因?yàn)閚=r且mr1，所以甲可一次將r根全部扳倒，那么甲獲勝。 ii)對(duì)任意的k0，假設(shè)當(dāng)q=k時(shí)命題為真，那么當(dāng)q=k+1時(shí)，即存在r使得n=(m+1)(q+1)+r，mr>0，由于此時(shí)甲可扳倒r根，然后乙只能扳倒x〔1xm〕根，此時(shí)剩下n=(m+1)q+(m+1)-q根，因?yàn)?(m+1)–xm，那么根據(jù)歸納假設(shè)可知甲總能獲勝。即當(dāng)q=k+1時(shí)命題也為真。由i)ii)可知，對(duì)于任意q0均有甲總能獲勝。證明：用第一歸納法對(duì)于每個(gè)ii0，用Q(i)表示以下命題：對(duì)于任意jj0，P(i,j)皆真。下面驗(yàn)證：Q(i)滿足第一歸納法的條件。i) Q(i0)為真，因?yàn)椤矊?duì)j用第一歸納法〕：a)P(i0,j0)為真； b)假設(shè)P(i0,j)為真，那么P(i0,j+1)為真；由歸納法可知，Q(i0)為真。ii)假設(shè)Q(i)為真〔ii0〕，即對(duì)于任意ii0，jj0，P(i,j)為真。那么對(duì)于任意jj0，P(i+1,j)為真，即Q(i+1)為真。由i)和ii)可知，對(duì)于任意ii0，Q(i)皆真。所以，對(duì)于任意ii0，jj0，P(i,j)為真。6.證明：假設(shè)有nN使nn，即{n}n，故n+={n}nn，同時(shí)nn+，所以n=n+。矛盾！〔與皮亞諾公理矛盾〕證明：假設(shè)有mN使n<m，那么由“<〞定義可知nm，所以由習(xí)題7有nm。因?yàn)閚m且nm，所以n{n}m，即n+m。而m<n+，那么由“<〞定義可知mn+，由習(xí)題7有mn+。n+m與mn+矛盾，所以假設(shè)不成立，即不可能有mN使n<m<n+。習(xí)題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.題號(hào)是否正確 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.證明：題目等價(jià)于證明：假設(shè)<a,b>=<c,d>，那么a=c且b=d。設(shè)<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}那么因?yàn)锳B，所以a=B,d=A,b=A且c=B。所以，a=c且b=d。故總有：a=c且b=d。第二章二元關(guān)系習(xí)題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.證明：〔根據(jù)定義域和值域的定義進(jìn)行證明〕因?yàn)閤dom(R1R2)當(dāng)且僅當(dāng)有yB使得<x,y>(R1R2)當(dāng)且僅當(dāng)有yB使得<x,y>R1或<x,y>R2當(dāng)且僅當(dāng)有yB使得<x,y>R1或有yB使得<x,y>R2當(dāng)且僅當(dāng)xdom(R1)或xdom(R2)當(dāng)且僅當(dāng)xdom(R1)dom(R2)所以，dom(R1R2)=dom(R1)dom(R2)。因?yàn)榧僭O(shè)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.上的空關(guān)系；集合{1,2}上的二元關(guān)系{<1,1>}；集合{1,2}上的二元關(guān)系{<1,1>}；集合{1,2,3}上的二元關(guān)系{<1,2>,<2,1>,<1,3>}；6.假設(shè)R,S自反，那么RS,RS自反，R–S,RS必不自反。假設(shè)R,S反自反，那么RS,RS,R–S,RS反自反。假設(shè)R,S對(duì)稱，那么RS,RS,R–S,RS對(duì)稱。假設(shè)R,S反對(duì)稱，那么RS,R–S反對(duì)稱，RS,RS不一定反對(duì)稱。假設(shè)R,S傳遞，那么RS傳遞，,R–S,RS,RS不一定傳遞。S是對(duì)稱的、傳遞的；S是自反的、對(duì)稱的；S是反對(duì)稱的、傳遞的；S是反自反的、反對(duì)稱的、傳遞的；8.n(Am)=nm；n((Am))=；因?yàn)镽Am，所以A上共有個(gè)m元關(guān)系。10.證明：用反證法。假設(shè)R不是反對(duì)稱的，即存在a,bA，使得<a,b>A,<b,a>A且ab。因?yàn)镽是傳遞的，所以由<a,b>A且<b,a>A可知<a,a>A。這與R反自反性質(zhì)矛盾。所以假設(shè)不成立。即R是反對(duì)稱的。11.證明：因?yàn)镽={<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.證明：因?yàn)閐omRfldR=(R)，ranRfldR=(R)，所以，RdomRranR(R)(R)。習(xí)題2.21.R是自反的、對(duì)稱的、傳遞的。2.自反的；反對(duì)稱的、傳遞的；自反的、對(duì)稱的、傳遞的；自反的、傳遞的；無；對(duì)稱的；自反的、反對(duì)稱的、傳遞的；對(duì)稱的；對(duì)稱的；反對(duì)稱的；自反的、反對(duì)稱的；反對(duì)稱的、傳遞的。4.A上共有個(gè)不相同的自反關(guān)系；A上共有個(gè)不相同的反自反關(guān)系；A上共有個(gè)不相同的對(duì)稱關(guān)系；A上共有個(gè)不相同的反對(duì)稱關(guān)系；A上共有個(gè)不相同的既是對(duì)稱的又是反對(duì)稱的關(guān)系；習(xí)題2.31.最多能有n(A)個(gè)元素為1。2.證明：i)RR-1為A上包含R的最小對(duì)稱關(guān)系=1\*GB3①RRR-1。所以，RR-1包含R。=2\*GB3②因?yàn)閷?duì)于任意<a,b>RR-1，有<a,b>R或<a,b>R-1。假設(shè)<a,b>R，那么<b,a>R-1；假設(shè)<a,b>R-1，那么<b,a>R。因此，<b,a>RR-1。所以，RR-1為A上的對(duì)稱關(guān)系。=3\*GB3③設(shè)R為任意的A上包含R的對(duì)稱關(guān)系，那么對(duì)于任意<a,b>RR-1，有<a,b>R或<a,b>R-1。假設(shè)<a,b>R，由于R包含R，所以<a,b>R；假設(shè)<a,b>R-1，那么<b,a>R，由于R包含R，所以<b,a>R，而R對(duì)稱，所以<a,b>R。因此，總有<a,b>R。所以，RR-1R。由=1\*GB3①=2\*GB3②=3\*GB3③可知，RR-1為A上包含R的最小對(duì)稱關(guān)系。ii)RR-1為A上包含在R中的最大對(duì)稱關(guān)系=1\*GB3①RR-1R。所以，RR-1包含在R中。=2\*GB3②因?yàn)閷?duì)于任意<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上的對(duì)稱關(guān)系。=3\*GB3③設(shè)R為任意的A上包含在R中的對(duì)稱關(guān)系，那么對(duì)于任意<a,b>R，由于R包含在R中，所以<a,b>R；又由于R對(duì)稱，所以<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中的最大對(duì)稱關(guān)系。習(xí)題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(yù)={1,2}，那么R1={<1,2>},R2={<2,1>}都是反自反的，但R1R2={<1,1>}不是反自反的。不正確。令A(yù)={1,2,3}，那么R1={<1,2>,<2,1>},R2={<2,3>,<3,2>}都是對(duì)稱的，但R1R2={<1,3>}不是對(duì)稱的。不正確。令A(yù)={1,2,3}，那么R1={<1,2>,<3,1>},R2={<2,3>,<1,1>}都是反對(duì)稱的，但R1R2={<1,3>,<3,1>}不是反對(duì)稱的。不正確。令A(yù)={1,2,3}，那么R1={<1,2>,<3,1>,<3,2>},R2={<2,3>,<1,1>}都是傳遞的，但R1R2={<1,3>,<3,1>,<3,3>}不是傳遞的。證明：a)對(duì)于任意kN，因?yàn)镽s=Rt，所以Rs+k=RsRk=RtRk=Rt+k。b)用關(guān)于k的歸納法證明。i)當(dāng)k=0時(shí)，Rs+i=Rs+i。所以命題成立。ii)假設(shè)當(dāng)k=m時(shí)命題成立，即Rs+mp+i=Rs+i。那么當(dāng)k=m+1時(shí)，因?yàn)镽s+(m+1)p+i=Rs+p+mp+i=Rt+mp+i=RtRmp+i=RsRmp+i=Rs+mp+i。由歸納假設(shè)，Rs+(m+1)p+i=Rs+mp+i=Rs+i。由i)ii)可知對(duì)于任意k,iN，均有Rs+kp+i=Rs+i。假設(shè)kt-1，那么Rk{R0,R1,…,Rt-1}；假設(shè)kt，那么k=s+(t-s)q+r，即k=s+pq+r；〔其中，qN,0r<t-s=p〕此時(shí)，由b)可知Rk=Rs+pq+r=Rs+r{R0,R1,…,Rt-1}。所以，假設(shè)kN，那么Rk{R0,R1,…,Rt-1}。習(xí)題2.52.使t(R1R2)t(R1)t(R2)的R1和R2的具體實(shí)例如下：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的具體實(shí)例如下：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的具體實(shí)例如下：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(yù)={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)。習(xí)題2.61.正確；正確；不正確；〔不自反〕不正確；〔不自反〕不正確；〔不一定對(duì)稱〕正確。2. R的所有極大相容類為：{x1,x2,x3}，{x1,x3,x6}，{x3,x4,x5}，{x3,x5,x6}。3. A上共有個(gè)不相同的相容關(guān)系。習(xí)題2.71.不正確；〔不自反〕不正確；〔不自反〕不正確；〔不自反〕不正確；〔不傳遞，<-1,0>R,<0,1>R,但<-1,1>R〕不正確；〔不對(duì)稱〕不正確；〔不對(duì)稱〕不正確；〔不傳遞〕正確；不正確?！膊蛔苑?，i=10k時(shí)，<i,i>R〕2.不對(duì)。應(yīng)加上條件：對(duì)于任意xA，總存在yA使得<x,y>R。3.證明：=1\*GB3①條件：假設(shè)<a,b>R，<a,c>R，那么<b,c>R。先證對(duì)稱性：假設(shè)<a,b>R，那么由于R自反，所以<a,a>R，由上式有<b,a>R。所以R對(duì)稱。再證傳遞性：假設(shè)<a,b>R，<b,c>R，那么因?yàn)镽對(duì)稱，所以<b,a>R。由條件，因?yàn)?lt;b,a>R且<b,c>R，所以<a,c>R。所以R傳遞。因此，R時(shí)等價(jià)關(guān)系。=2\*GB3②條件：R是等價(jià)關(guān)系。假設(shè)<a,b>R，<a,c>R，那么因?yàn)镽對(duì)稱，所以<b,a>R。又由于R傳遞，所以，<b,c>R。因此，假設(shè)<a,b>R，<a,c>R，那么<b,c>R。習(xí)題2.81.半序；半序、全序、良序；無；〔不是反對(duì)稱的〕無；〔不是傳遞的〕半序；無；〔不是傳遞的〕無；〔不是傳遞的〕擬序。4.設(shè)R是集合A上的二元關(guān)系，證明：a) R是A上的半序，當(dāng)且僅當(dāng)RR-1=A且R=R*。自反、反對(duì)稱 __________________傳遞b) R是A上的擬序，當(dāng)且僅當(dāng)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+,|>〔“|〞為整除關(guān)系〕中的非空子集{x|x>4}無最大元。<R,>中的非空子集(0,1)由下確界0，但無最小元。書上例4中的非空子集{4}有上界8和12，但無上確界。8.歸納法。9.歸納法。第三章函數(shù)習(xí)題3.11.不是局部函數(shù)；原因：存在<0,1>,<0,2>f，但12。局部函數(shù)；不是局部函數(shù)。原因：存在<4,2>,<4,-2>f，但2-2。2.局部函數(shù)；定義域?yàn)椋簕1,2,3,4}，值域?yàn)椋簕<2,3>,<3,4>,<1,4>}。局部函數(shù)；定義域?yàn)椋簕1,2,3}，值域?yàn)椋簕<2,3>,<3,4>,<3,2>}。不是局部函數(shù)；局部函數(shù)。定義域?yàn)椋簕1,2,3}，值域?yàn)椋簕<2,3>}。3.證明：證明分兩局部：=1\*GB3①局部函數(shù)之單值性；=2\*GB3②domf=(A)(A)。5.證明：對(duì)于任意yf[A]–f[B]，那么yf[A]且yf[B]。因?yàn)閥f[A]，所以存在xA使得f(x)=y。又因?yàn)閥f[B]，所以xB。〔用反證法，假設(shè)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，個(gè)；=2\*GB3②m>n，0個(gè)。b)=1\*GB3①m<n，0個(gè)；=2\*GB3②n=0且m0，0個(gè)；=3\*GB3③n=0且m=0，1個(gè)；=4\*GB3④mn1，第二類Stirling數(shù)。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③假設(shè)當(dāng)k+1x100時(shí)，f(x)均等于91。(0k89)那么當(dāng)x=k(k0)時(shí)，那么有f(k)=f(f(k+11))。而0k89，所以k+1k+11100，由歸納假設(shè)有f(k+11)=91，即f(k)=f(91)=91。所以，f(x)=91對(duì)于0k89也成立。習(xí)題3.24.歸納法。5.證明：=1\*GB3①因?yàn)閒:AA為滿射，所以aA.xaA使得f(xa)=a。又因?yàn)閒f=f，所以f(a)=f(f(xa))=ff(xa)=f(xa)=a，即f(a)=a。所以Af。=2\*GB3②對(duì)于任意<x,y>f，因?yàn)锳f，所以<x,x>f。而f為局部函數(shù)，即“單值〞，于是，x=y。所以<x,y>=<x,x>A。所以fA。=2\*GB3②另證下面要證明Af不可能。用反證法，假設(shè)Af，那么存在aa使得f(a)=a。因?yàn)閒為滿射，所以必存在xaA使得f(xa)=a。因?yàn)閒f=f，所以a=f(xa)=ff(xa)=f(f(xa))=f(a)=a，即a=a。這與aa矛盾。所以假設(shè)不成立，即Af不可能。由=1\*GB3①=2\*GB3②可知A=f。6.證明：首先，dom(gf)=f-1[domg]。因?yàn)閞anfdomg，所以domf=f–1[ranf]f–1[domg]。又因?yàn)閐omgY，而f-1[Y]=domgf，所以f–1[domg]f–1[Y]=domf。所以，dom(gf)=domf。8.因?yàn)閒f=f，所以對(duì)于任意iA，均有f(f(i))=f(i)。即假設(shè)f(i)=j(ji)，那么f(j)=i。設(shè)m為集合{i|iA且f(i)=i}的元素個(gè)數(shù)，即m為f中對(duì)應(yīng)到自身的二元序偶個(gè)數(shù)。那么對(duì)m求累加和得到滿足ff=f的函數(shù)個(gè)數(shù)為個(gè)。ff=A，所以f為雙射，并且對(duì)于任意iA，均有f(f(i))=i〔即假設(shè)<i,j>f且ij，那么<j,i>f〕。〔特征：未對(duì)應(yīng)到自身的二元序偶個(gè)數(shù)必為偶數(shù)個(gè)。〕設(shè)k為集合{i|iA且f(i)=i}的元素個(gè)數(shù)/2，即2k為f中對(duì)應(yīng)到自身的二元序偶個(gè)數(shù)。那么對(duì)k求累加和得到滿足ff=A的函數(shù)個(gè)數(shù)：當(dāng)n為偶數(shù)時(shí)，有個(gè)；當(dāng)n為奇數(shù)時(shí)，有個(gè)。fff=A，所以f為雙射，因此滿足fff=A的函數(shù)個(gè)數(shù)：當(dāng)n=3k+1(kN)時(shí)，有個(gè)；當(dāng)n=3k+2(kN)時(shí)，有個(gè)；當(dāng)n=3k(kN)時(shí)，有個(gè)。9.證明：因?yàn)間f為滿射，所以g為滿射。而g又是內(nèi)射，所以g為雙射。假設(shè)f不是滿射，那么存在yY使得yranf。而g是雙射，所以g(y)Z，又gf為滿射，所以ran(gf)=Z。即g(y)ran(gf)。所以存在xX使得g(y)=gf(x)=g(f(x))。因?yàn)間為內(nèi)射，所以y=f(x)。因此，yranf。這與yranf矛盾。所以假設(shè)不成立，即f是滿射。證明：因?yàn)間f為內(nèi)射，所以f為內(nèi)射。而f又是滿射，所以f為雙射。假設(shè)g不是內(nèi)射，那么存在y1,y2Y使得y1y2并且g(y1)=g(y2)。因?yàn)閒為雙射，所以存在x1,x2X使得x1x2并且f(x1)=y1，f(x2)=y2。而gf為內(nèi)射，那么gf(x1)gf(x2)，即g(y1)g(y2)。這與g(y1)=g(y2)矛盾。所以假設(shè)不成立，即g是內(nèi)射。習(xí)題3.33.k(x)=x/3；k(x)=(x+1)/3；4.f左可逆，但g不一定左可逆。證明：因?yàn)間f左可逆，那么gf為內(nèi)射，所以f為內(nèi)射。g不一定左可逆，反例如下： A={a}，B={b1,b2}，C={c}。f={<a,b1>}，g={<b1,c>,<b2,c>}，gf={<a,c>}。所以，gf是內(nèi)射，即是左可逆的；但g不是內(nèi)射，即不是左可逆的。5.證明：f是可逆的，那么易證f又唯一的左〔右〕逆。另一邊證明以“f有唯一左逆，那么f可逆。〞為例。aA，g=f-1((Y–ranf){a})就是f的一個(gè)左逆。而f僅有唯一左逆且n(A)2，這說明Y–ranf=，即ranf=Y。所以，f為滿射。又因?yàn)閒左可逆，所以f為內(nèi)射。即f為雙射。所以f可逆。習(xí)題3.42.ABC=；A=B；B=；A=B。習(xí)題3.51.b)或c) f(x)=1/2–x/4或f(x)=1/2cos(x/3)。2.證明：假設(shè)存在1kn使得x1+…+xk被n整除，那么取i=1,k=k即可。否那么，x1,x1+x2,…,x1+…+xn共n個(gè)數(shù)，而它們被n除的余數(shù)除0外僅有n-1個(gè)。根據(jù)抽屜原那么，其中必有兩個(gè)它們被n除的余數(shù)相等。假設(shè)它們?yōu)椋骸瞛1<j2〕x1+…+xj1和x1+…+xj2那么取i=j1+1,k=j2即可。4.證明：共有n組數(shù)據(jù)。任取n+1個(gè)小于等于2n正整數(shù)中必有兩個(gè)數(shù)處于同一組，這兩個(gè)數(shù)互素。6.證明：一個(gè)整數(shù)被100除的余數(shù)共有100個(gè)，可以將它們分成51組。任取52個(gè)整數(shù)中必有兩個(gè)數(shù)除100后余數(shù)同處于一組。這是有兩種情況：一是它們除100后余數(shù)相同，此時(shí)兩個(gè)數(shù)相減即可；一是它們除100后余數(shù)不同，此時(shí)兩個(gè)數(shù)相加即可。8.#*=0。其中雙射為：f(ai)=i。#Q=0。正有理數(shù)a=m/n，m>0,n>0并且m和n互質(zhì)，那么：Q+~NN~N。所以#Q+=0。#Q=2#Q++1=1+0+0=0。0。10.。第四章命題邏輯習(xí)題4.11.題號(hào)是否為命題命題的真值 a)〔沒有確定的真假〕 b)F c)T d)T e)F f)〔祈使句〕 g)〔疑問句〕2.PRQQRPQRP〔需考慮優(yōu)先級(jí)〕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)證明：要證明用、、、不能表示，只需證明僅用、、、不能表達(dá)出含的某些公式即可。因?yàn)镻PP；PPP；PPT；PPT。增加T之后，TPPTP；PTTPT；TPP；PTT； TPPTP。這也就是說，由、、、只能得出P或T，不能得出P。習(xí)題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)〔有的括號(hào)可省略〕(Q(PP))((PP)Q)〔有的括號(hào)可省略〕6. c)是a)的代換實(shí)例〔 Q/P，(PP)/Q〕 d)是a)的代換實(shí)例〔 (P(QP))/Q〕 e)是b)的代換實(shí)例〔 R/P，S/Q，Q/R，P/S〕 b)是e)的代換實(shí)例〔 S/P，R/Q，P/R，Q/S〕習(xí)題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。根據(jù)對(duì)偶原理得出的新的等價(jià)式為：(PQ)(PQ) P。(PQ)(PQ)(PQ) (P(QQ))(PQ)(PF)(PQ)P(PQ)(PP)(PQ)F(PQ)(PQ)(PQ)(PQ)所以，(PQ)(PQ)(PQ)(PQ)。根據(jù)對(duì)偶原理得出的新的等價(jià)式為：(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〕上述均為等價(jià)變換，所以蘊(yùn)含式也成立。5.以b)為例：b) P(QRP) P((QR)P) P((QR)P) P((QR)P) P(P(QR)) (PP)(QR)PQR(PQR)(PQR)為P(QRP)只包含和的化簡式。習(xí)題4.41.e)PQ(PQ)PQ((PQ)(PQ))〔化去〕(PQ)((PQ)(PQ))〔化去〕(PQ)((PQ)(PQ))〔內(nèi)移〕(PQ)((PQ)(PQ))〔最多保存一個(gè)〕(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))〔最多保存一個(gè)〕(PQ)(PR)(PQ)(PR)〔關(guān)于的分配率〕(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)〔變?yōu)闃O大項(xiàng)〕(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)〔合并相同項(xiàng)〕(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)為(PQR)(PQR)的主合取范式。 (PQR)(PQR)(P(QR))(P(QR))〔化去〕(P(QR))(P(QR))〔最多保存一個(gè)〕(PP)(PQR)(QRP)(QRQR)〔關(guān)于的分配率〕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中的所有出現(xiàn)，得到A1；利用德摩爾根律將A1中的內(nèi)移到原子之前，并用E1使每個(gè)原子之前至多僅有一個(gè)；在用分配律將ii)的結(jié)果化為假設(shè)干個(gè)合取式的析取，其中每個(gè)合取式的因子皆為原子或原子的否認(rèn)；對(duì)于iii)的結(jié)果中的每個(gè)合取式B，假設(shè)命題變?cè)狿在B中不出現(xiàn)，利用 (BP)(BP)(B(PP)BTB)取代B，直到每個(gè)合取式都變?yōu)闃O小項(xiàng)，最后刪除相同項(xiàng)。第五章謂詞邏輯習(xí)題5.11.每個(gè)自然數(shù)都有唯一的后繼；解：“每個(gè)〞是全稱的概念；“自然數(shù)〞需引進(jìn)一個(gè)特性謂詞；“有〞表示存在；“唯一〞表示所有具有該性質(zhì)的元素均相等〔即假設(shè)x具有該性質(zhì)，y也具有該性質(zhì)，那么x等于y〕；“后繼〞用謂詞表示。于是，可令：N(x)：x是自然數(shù)；Q(x,y)：y是x的后繼；E(x,y)：x等于y；那么上述命題可以符號(hào)化為： (x)(N(x)(y)(Q(x,y)(z)(Q(x,z)E(y,z))b)沒有以0為后繼的自然數(shù)；解：“沒有〞表示不存在；“自然數(shù)〞用特性謂詞表示；“后繼〞用謂詞表示。于是，可令：N(x)：x是自然數(shù)；Q(x,y)：y是x的后繼；那么上述命題可以符號(hào)化為：(x)(N(x)Q(x,0))注意：=1\*GB3①對(duì)于引進(jìn)的特性謂詞，在全稱量詞約束下要用邏輯聯(lián)結(jié)詞“〞，在存在量詞約束下要用邏輯聯(lián)結(jié)詞“〞。=2\*GB3②“唯一〞概念的符號(hào)化。2.存在唯一的偶素?cái)?shù)；解：“存在〞是存在量詞的概念；“唯一〞可參照上題；“偶數(shù)〞、“素?cái)?shù)〞用謂詞表示。于是，可令：E(x)：x是偶數(shù)；S(x)：x是素?cái)?shù)；R(x,y)：x等于y；那么上述命題可以符號(hào)化為：(x)(E(x)S(x)(y)(E(y)S(y)R(x,y))沒有既是奇數(shù)又是偶數(shù)的數(shù)；解：“沒有〞表示不存在；“奇數(shù)〞、“偶數(shù)〞、“數(shù)〞用謂詞表示。于是，可令：O(x)：x是奇數(shù)；E(x)：x是偶數(shù)； Q(x)：x是數(shù)；那么上述命題可以符號(hào)化為：(x)(Q(x)O(x)E(x))3.所有可證明的算術(shù)命題都是真的；存在真的但不可證明的算術(shù)命題；對(duì)于任意的三個(gè)算術(shù)命題x,y,z，假設(shè)z=xy且z是可證明的，那么x是可證明的或y是可證明的；對(duì)于任意的三個(gè)算術(shù)命題x,y,z，假設(shè)x是真的并且z=xy，那么z是真的；4.對(duì)任意整數(shù)x,y和z，x<z是x<y且y<z的必要條件；解：“任意〞是全稱的概念；“整數(shù)〞需引進(jìn)一個(gè)特性謂詞；“<〞用謂詞表示；“必要條件〞用邏輯聯(lián)結(jié)詞來表示。于是，可令：I(x)：x是整數(shù)；L(x,y)：x<y；那么上述命題可以符號(hào)化為： (x)(y)(z)(I(x)I(y)I(z)(L(x,y)L(y,z)L(x,z)))b)對(duì)任意整數(shù)x，假設(shè)x=2，那么3x=6；反之亦然；解：“任意〞是全稱的概念；“整數(shù)〞需引進(jìn)一個(gè)特性謂詞；“=〞用謂詞表示；“〞用函詞表示。于是，可令：〔2、3、6可以用常元表示〕I(x)：x是整數(shù)；E(x,y)：x=y；f(x,y)：xy；那么上述命題可以符號(hào)化為： (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)))習(xí)題5.21.除了最后一個(gè)x是自由出現(xiàn)外，其它的6次x的出現(xiàn)都是約束出現(xiàn)。第一個(gè)(x)的轄域?yàn)橄旅娴膭澗€局部：(x)(P(x)(x)Q(x))((x)P(x)Q(x))第一個(gè)(x)的轄域?yàn)橄旅娴膭澗€局部：(x)(P(x)(x)Q(x))((x)P(x)Q(x))第二個(gè)(x)的轄域?yàn)橄旅娴膭澗€局部：(x)(P(x)(x)Q(x))((x)P(x)Q(x))a)T；b)F；c)F；d)T；e)T；f)T。以a)為例：解：因?yàn)镻(a,a)為T，所以(y)P(a,y)為T；因?yàn)镻(b,b)為T，所以(y)P(b,y)為T；因?yàn)?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。習(xí)題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下為假。因?yàn)?x)Q(x)在I下為假，所以存在cD使Q(c)在I下為假。因?yàn)?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下為假。因?yàn)镻(c)在I下為真，所以(x)P(x)在I下為真。因?yàn)镼(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àn)閥在P(x)中沒有自由出現(xiàn)〕(x)P(x)(y)Q(y)〔因?yàn)閤在(y)Q(y)中沒有自由出現(xiàn)〕所以，(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àn)閥在P(x)中沒有自由出現(xiàn)〕(x)P(x)(y)Q(y)〔因?yàn)閤在(y)Q(y)中沒有自由出現(xiàn)〕(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àn)閥在P(x)中沒有自由出現(xiàn)〕(x)P(x)(y)Q(y)〔因?yàn)閤在(y)Q(y)中沒有自由出現(xiàn)〕所以，(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àn)閥在P(x)中沒有自由出現(xiàn)〕(x)(P(x))(y)Q(y)〔因?yàn)閤在(y)Q(y)中沒有自由出現(xiàn)〕(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àn)閥在P(x)中沒有自由出現(xiàn)〕(x)(P(x))(y)Q(y)〔因?yàn)閤在(y)Q(y)中沒有自由出現(xiàn)〕(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)))____上述這一步不正確。根據(jù)書中105頁I16：(x)(P(x)Q(x))(x)(P(x))(x)(Q(x))可知：(x)(P(x)Q(x))((x)(P(x))(x)(Q(x)))因此，最后應(yīng)該證明出： (x)(P(x)Q(x)) (x)P(x)(x)Q(x))這就是書中的I15。習(xí)題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))))〔內(nèi)移〕(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))))〔內(nèi)移〕上述公式即為原公式的前束范式。令g為二元函詞，那么原公式的無前束范式為：(x)(y)((P(x,y)(P(y,g(x,y))P(g(x,y),g(x,y))))((P(x,