離散數(shù)學(xué)第一學(xué)期習(xí)題及答案

PAGEPAGE17第一章部分習(xí)題及參考答案1設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。（1）p∨(q∧r)（2）（p?r）∧(﹁q∨s)（3）（p∧q∧r）?(p∧q∧﹁r)(4)（r∧s）→(p∧q)2．判斷下面一段論述是否為真：“是無(wú)理數(shù)。并且，如果3是無(wú)理數(shù)，則也是無(wú)理數(shù)。另外6能被2整除，6才能被4整除。”3．用真值表判斷下列公式的類型：（1）(p→q)→(q→p)（2）(p∧r)(p∧q)（3）((p→q)∧(q→r))→(p→r)4.用等值演算法判斷下列公式的類型，對(duì)不是重言式的可滿足式，再用真值表法求出成真賦值.(1)(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)5.用等值演算法證明下面等值式：(1)(p→q)∧(p→r)(p→(q∧r))(2)(p∧q)∨(p∧q)(p∨q)∧(p∧q)6.求下列公式的主析取范式與主合取范式，并求成真賦值(1)(p→q)→(q∨p)(2)(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：(1)前提：pq,(qr),r結(jié)論：p(2)前提：qp,qs,st,tr結(jié)論：pq8.在自然推理系統(tǒng)P中用附加前提法證明下面推理：前提：p(qr),sp,q結(jié)論：sr9.在自然推理系統(tǒng)P中用歸謬法證明下面各推理：前提：pq,rq,rs結(jié)論：p參考答案:1.（1）p∨(q∧r)0∨(0∧1)0（2）（p?r）∧(﹁q∨s)（0?1）∧(1∨1)0∧10（3）（p∧q∧r）?(p∧q∧﹁r)（1∧1∧1）?(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→012.p:是無(wú)理數(shù)1q:3是無(wú)理數(shù)0r:是無(wú)理數(shù)1s:6能被2整除1t:6能被4整除0命題符號(hào)化為：p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。3.（1）pqp→qqpq→p(p→q)→(q→p)0011111011011110010011110011所以公式類型為永真式（2）公式類型為可滿足式（方法如上例）（3）公式類型為永真式（方法如上例）4.(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1所以公式類型為永真式(3)Pqrp∨qp∧r（p∨q）→(p∧r)000001001001010100011100100100101111110100111111所以公式類型為可滿足式5.證明（1）(p→q)∧(p→r)(p∨q)∧(p∨r)p∨(q∧r))p→(q∧r)（2）(p∧q)∨(p∧q)(p∨(p∧q))∧(q∨(p∧q)(p∨p)∧(p∨q)∧(q∨p)∧(q∨q)1∧(p∨q)∧(p∧q)∧1(p∨q)∧(p∧q)6.（1）主析取范式(p→q)→(qp)(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq) (pq)(pq)(pq) ∑(0,2,3)主合取范式：(p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq)M1∏(1)(2)主合取范式為：(p→q)qr(pq)qr(pq)qr0所以該式為矛盾式.主合取范式為∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式為0(3)主合取范式為：(p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))111所以該式為永真式.永真式的主合取范式為1主析取范式為∑(0,1,2,3,4,5,6,7)7.證明：（1）①(qr)前提引入②qr①置換③qr②蘊(yùn)含等值式④r前提引入⑤q③④拒取式⑥pq前提引入⑦￢p（3）⑤⑥拒取式證明（2）：①tr前提引入②t①化簡(jiǎn)律③qs前提引入④st前提引入⑤qt③④等價(jià)三段論⑥（qt）(tq)

⑤置換⑦（qt）⑥化簡(jiǎn)⑧q②⑥假言推理⑨qp前提引入⑩p⑧⑨假言推理(11)pq⑧⑩合取8.證明①s附加前提引入②sp前提引入③p①②假言推理④p(qr)前提引入⑤qr③④假言推理⑥q前提引入⑦r⑤⑥假言推理9.證明：①p結(jié)論的否定引入②p﹁q前提引入③﹁q①②假言推理④￢rq前提引入⑤￢r④化簡(jiǎn)律⑥r(nóng)￢s前提引入⑦r⑥化簡(jiǎn)律⑧r﹁r⑤⑦合取由于最后一步r﹁r是矛盾式,所以推理正確.第二章部分習(xí)題及參考答案1.在一階邏輯中將下面將下面命題符號(hào)化,并分別討論個(gè)體域限制為(a),(b)條件時(shí)命題的真值:(1)對(duì)于任意x,均有x2-2=(x+2)(x(2)存在x,使得x+5=9.其中(a)個(gè)體域?yàn)樽匀粩?shù)集合.(b)個(gè)體域?yàn)閷?shí)數(shù)集合.2.在一階邏輯中將下列命題符號(hào)化:(1)沒有不能表示成分?jǐn)?shù)的有理數(shù).(2)在合肥賣菜的人不全是外地人.3.在一階邏輯將下列命題符號(hào)化:(1)火車都比輪船快.(3)不存在比所有火車都快的汽車.4.給定解釋I如下:(a)個(gè)體域D為實(shí)數(shù)集合R.(b)D中特定元素a=0.(c)特定函數(shù)f(x,y)=x-y,x,yQUOTE∈D1.(d)特定謂詞F(x,y):x=y,G(x,y):x<y,x,y.說(shuō)明下列公式在I下的含義,并指出各公式的真值:5.給定解釋I如下：（a）個(gè)體域D=N(N為自然數(shù)集合).（b）D中特定元素a=2.（c）D上函數(shù)fx,y=x+y,（d）D上謂詞F(x,y):x=y.說(shuō)明下列各式在I下的含義，并討論其真值.?xF(g(x,a),x)?x?y(F(f(x,a),y)→F(f(y,a),x)6.判斷下列各式的類型:(1)F(2)?x7.給定下列各公式一個(gè)成真的解釋，一個(gè)成假的解釋。(1)?x(F(x)(2)?x(F(x)∧G(x)∧H(x))8.給定解釋Ｉ如下:(a)個(gè)體域D={3,4};(b)f為QUOTEf3=4,f4=3;(c)QUOTEFx,y為F3,3=F試求下列公式在Ｉ下的真值.(1)(3)9.求下列各式的前束范式。(1)(2)10.在自然數(shù)推理系統(tǒng)F中,構(gòu)造下面推理的證明:前提:,結(jié)論:xR(x)前提:x(F(x)→(G(a)∧R(x))),?xF(x)結(jié)論:?x(F(x)∧R(x))參考答案：1.解：F(x):x2-2=(x+2)(xG(x):x+5=9.(1)在兩個(gè)個(gè)體域中都解釋為，在（a）中為假命題，在(b)中為真命題。(2)在兩個(gè)個(gè)體域中都解釋為，在（a）(b)中均為真命題。2.解:(1)F(x):x能表示成分?jǐn)?shù)H(x):x是有理數(shù)命題符號(hào)化為:(2)F(x):x是合肥賣菜的人H(x):x是外地人命題符號(hào)化為:3.解:(1)F(x):x是火車;G(x):x是輪船;H(x,y):x比y快命題符號(hào)化為:(2)(1)F(x):x是火車;G(x):x是汽車;H(x,y):x比y快命題符號(hào)化為:4.答:(1)對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x<y,那么xy.真值1.(2)對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x-y=0,那么x<y.真值0.5.答:(1)對(duì)于任意自然數(shù)x,都有2x=x,真值0.(2)對(duì)于任意兩個(gè)自然數(shù)x,y,使得如果x+2=y,那么y+2=x.真值0.6.解:(1)因?yàn)闉橛勒媸?；所以Fx,y(2)取解釋I個(gè)體域?yàn)槿w實(shí)數(shù)F(x,y)：x+y=5所以,前件為任意實(shí)數(shù)x存在實(shí)數(shù)y使x+y=5，前件真；后件為存在實(shí)數(shù)x對(duì)任意實(shí)數(shù)y都有x+y=5，后件假，]此時(shí)為假命題再取解釋I個(gè)體域?yàn)樽匀粩?shù)N，F(xiàn)(x,y)：:x+y=5所以,前件為任意自然數(shù)x存在自然數(shù)y使x+y=5，前件假。此時(shí)為假命題。此公式為非永真式的可滿足式。7.解:(1)個(gè)體域:本班同學(xué)F(x)：x會(huì)吃飯,G(x)：x會(huì)睡覺.成真解釋F(x)：x是合肥人,G(x)：x是巢湖人.成假解釋(2)個(gè)體域:計(jì)算機(jī)學(xué)院的學(xué)生F(x)：x出生在山東,G(x):x出生在北京,H(x):x出生在江蘇,成假解釋.F(x)：x會(huì)吃飯,G(x)：x會(huì)睡覺,H(x)：x會(huì)呼吸.成真解釋.8.解:(1) (2)9.解:(1)(2)10.證明(1)①前提引入②F(c)①EI③前提引入④①③假言推理⑤(F(c)∨G(c))→R(c))④UI⑥F(c)∨G(c)②附加⑦R(c)⑤⑥假言推理⑧xR(x)⑦EG(2)①xF(x)前提引入②F(c)①EI③x(F(x)→(G(a)∧R(x)))前提引入④F(c)→(G(a)∧R(c))③UI⑤G(a)∧R(c)②④假言推理⑥R(c)⑤化簡(jiǎn)⑦F(c)∧R(c)②⑥合取引入⑧x(F(x)∧R(x))⑦EG第三章部分習(xí)題及參考答案1.確定下列命題是否為真：（1）（2）（3）（4）（5）｛a,b｝｛a,b,c,｛a,b,c｝｝（6）｛a,b｝｛a,b,c,｛a,b｝｝（7）｛a,b｝｛a,b,｛｛a,b｝｝｝（8）｛a,b｝｛a,b,｛｛a,b｝｝｝2．設(shè)a,b,c各不相同，判斷下述等式中哪個(gè)等式為真:（1）｛｛a,b｝，c,｝ =｛｛a,b｝,c｝（2）｛a,b,a｝=｛a,b｝（3）｛｛a｝，｝=｛｛a,b｝｝（4）｛，｛｝，a,b｝=｛｛,｛｝｝,a,b｝3．求下列集合的冪集：（1）｛a,b,c｝（2）｛1，｛2，3｝｝（3）｛｝（4）｛，｛｝｝4．化簡(jiǎn)下列集合表達(dá)式：（1）（AB）B）-（AB）（2）（（ABC）-（BC））A5．某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。已知6個(gè)會(huì)打網(wǎng)球的人都會(huì)打籃球或排球。求不會(huì)打球的人數(shù)。6.設(shè)集合A＝{{1，2}，{2，3}，{1，3},{}},計(jì)算下列表達(dá)式：（1）A（2）A（3）A（4）A7、設(shè)A,B,C是任意集合，證明(1)(A-B)-C=A-BC(2)(A-B)-C=(A-C)-(B-C)8.列出集合A={2,3,4}上的恒等關(guān)系IA,全域關(guān)系EA,小于或等于關(guān)系LA,整除關(guān)系DA.9.設(shè)A={<1,2>,<2,4>,<3,3>}B={<1,3>,<2,4>,<4,2>}求AB,AB,domA,domB,dom(AB),ranA,ranB,ran(AB),fld(A-B).10.設(shè)R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求RR,R-1,11．設(shè)A={a,b,c,d}，，為A上的關(guān)系，其中=求。12．設(shè)A={1，2，3，4}，在AA上定義二元關(guān)系R，<u,v>,<x,y>AA，〈u,v>R<x,y>u+y=x+v.證明R是AA上的等價(jià)關(guān)系.(2)確定由R引起的對(duì)AA的劃分.13.設(shè)A={1，2，3，4}，R為AA上的二元關(guān)系,〈a，b〉，〈c，d〉A(chǔ)A,〈a，b〉R〈c，d〉a+b=c+d證明R為等價(jià)關(guān)系.求R導(dǎo)出的劃分.14.對(duì)于下列集合與整除關(guān)系畫出哈斯圖:(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12}15.下圖是兩個(gè)偏序集<A,R>的哈斯圖.分別寫出集合A和偏序關(guān)系R的集合表達(dá)式.(a)(b)16.分別畫出下列各偏序集<A,R>的哈斯圖,并找出A的極大元`極小元`最大元和最小元.(1)A={a,b,c,d,e}R={<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>}IA.(2)A={a,b,c,d,e},R={<c,d>}IA.參考答案：1.（1）真（2）假（3）真（4）真（5）｛a,b｝｛a,b,c,｛a,b,c｝｝真（6）｛a,b｝｛a,b,c,｛a,b｝｝真（7）｛a,b｝｛a,b,｛｛a,b｝｝｝真（8）｛a,b｝｛a,b,｛｛a,b｝｝｝假2.（1）｛｛a,b｝，c,｝ =｛｛a,b｝,c｝假（2）｛a,b,a｝=｛a,b｝真（3）｛｛a｝，｝=｛｛a,b｝｝假（4）｛，｛｝，a,b｝=｛｛,｛｝｝,a,b｝假3.（1）｛a,b,c｝P(A)={,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}（2）｛1，｛2，3｝｝P(A)={,{1},{{2,3}},{1，{2，3}}}（3）｛｝P(A)={,｛｝}（4）｛，｛｝｝P(A)={,{1},{{2,3}},{1，{2，3}}}4.解:(1)（AB）B）-（AB）=（AB）B）～（AB）=（AB）～（AB）)B=B=（2）（（ABC）-（BC））A=（（ABC）～（BC））A=（A～（BC））（（BC）～（BC））A=（A～（BC））A=（A～（BC））A=A5.解:A={會(huì)打籃球的人}，B={會(huì)打排球的人}，C={會(huì)打網(wǎng)球的人}|A|=14,|B|=12,|AB|=6,|AC|=5,|ABC|=2,|C|=6,CAB如圖所示。25-(5+4+2+3)-5-1=25-14-5-1=5不會(huì)打球的人共5人6.解:（1）A={1，2}{2，3}{1，3}{}={1，2，3,}（2）A={1，2}{2，3}{1，3}{}=（3）A==（4）A=7.證明(1)(A-B)-C=(A～B)～C=A(～B～C)=A～(BC)=A-BC(2)(A-C)-(B-C)=(A～C)～(B～C)=(A～C)(～BC)=(A～C～B)(A～CC)=(A～C～B)=A～(BC)=A-BC由（1）得證。8.解：IA={<2，2>,<3,3>,<4,4>}EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}DA={<2,4>}9.解：AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}AB={<2,4>}domA={1,2,3}domB={1,2,4}dom(A∨B)={1,2,3,4}ranA={2,3,4}ranB={2,3,4}ran(AB)={4}A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3}10.解：RR={<0,2>,<0,3>,<1,3>}R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}11.解:R1R2={<a,d>,<a,c>,<a,d>}R2R1={<c,d>}R12=R1R1={<a,a>,<a,b>,<a,d>}R22=R2R2={<b,b>,<c,c>,<c,d>}R23=R2R22={<b,c>,<c,b>,<b,d>}12.（1）證明：∵<u,v>R<x,y>u+y=x-y∴<u,v>R<x,y>u-v=x-y<u,v>AA∵u-v=u-v∴<u,v>R<u,v>∴R是自反的任意的<u,v>,<x,y>∈A×A如果<u,v>R<x,y>，那么u-v=x-y∴x-y=u-v∴<x,y>R<u,v>∴R是對(duì)稱的任意的<u,v>,<x,y>,<a,b>∈A×A若<u,v>R<x,y>,<x,y>R<a,b>則u-v=x-y,x-y=a-b∴u-v=a-b∴<u,v>R<a,b>∴R是傳遞的∴R是A×A上的等價(jià)關(guān)系(2)∏={{<1,1>,<2,2>,<3,3>,<4,4>},{<2,1>,<3,2>,<4,3>},{<3,1>,<4,2>},{<4,1>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>}}13.(1)證明：<a，b〉A(chǔ)Aa+b=a+b∴<a,b>R<a,b>∴R是自反的任意的<a,b>,<c,d>∈A×A設(shè)<a,b>R<c,d>，則a+b=c+d∴c+d=a+b∴<c,d>R<a,b>∴R是對(duì)稱的任意的<a,b>,<c,d>,<x,y>∈A×A若<a,b>R<c,d>,<c,d>R<x,y>則a+b=c+d,c+d=x+y∴a+b=x+y∴<a,b>R<x,y>∴R是傳遞的∴R是A×A上的等價(jià)關(guān)系(2)∏={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<4,1>,<2,3>,<3,2>},{<2,4>,<4,2>,<3,3>},{<3,4>,<4,3>},{<4,4>}}14.解:(1)(2)15.解:(a)A={a,b,c,d,e,f,g}R={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>}(b)A={a,b,c,d,e,f,g}R={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>}16.解: