《離散數(shù)學(xué)屈婉玲版課后習(xí)題.doc》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)屈婉玲版課后習(xí)題.doc（34頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、.第一章部分課后習(xí)題參考答案16 設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。 （1）p(qr) 0(01) 0 （2）（pr）(qs) （01）(11) 010. （3）（pqr）(pqr) （111） (000)0(4)（rs）(pq) （01）(10) 00117判斷下面一段論述是否為真：“是無理數(shù)。并且，如果3是無理數(shù)，則也是無理數(shù)。另外6能被2整除，6才能被4整除?！贝穑簆: 是無理數(shù) 1 q: 3是無理數(shù) 0 r: 是無理數(shù) 1 s:6能被2整除 1t: 6能被4整除 0 命題符號化為： p(qr)(ts)的真值為1，所以這一段的論述為真。19用真值表判斷下列公式
2、的類型：（4）(pq) (qp)（5）(pr) (pq)（6）(pq) (qr) (pr)答： （4） p q pq q p qp (pq)(qp) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式類型為永真式（5）公式類型為可滿足式（方法如上例）（6）公式類型為永真式（方法如上例）第二章部分課后習(xí)題參考答案3.用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值.(1) (pqq) (2)(p(pq)(pr)(3)(pq)(pr)答：(2)（p(pq)）(pr)(p(pq)(pr)ppqr1
3、所以公式類型為永真式(3) P q r pq pr （pq）(pr)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1 所以公式類型為可滿足式4.用等值演算法證明下面等值式：(2)(pq)(pr)(p(qr)(4)(pq)(pq)(pq) (pq)證明（2）(pq)(pr) (pq)(pr)p(qr)p(qr)（4）(pq)(pq)(p(pq) (q(pq)(pp)(pq)(qp) (qq)1(pq)(pq)1(pq)(pq) 5.求下列公式的主析取范式與主合取范式，并
4、求成真賦值(1)(pq)(qp)(2)(pq)qr(3)(p(qr)(pqr)解：（1）主析取范式(pq)(qp) (pq)(qp) (pq)(qp) (pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq) (0,2,3) 主合取范式： (pq)(qp) (pq)(qp) (pq)(qp) (p(qp)(q(qp) 1(pq) (pq) M1 (1) (2) 主合取范式為： (pq)qr(pq)qr (pq)qr0 所以該式為矛盾式. 主合取范式為(0,1,2,3,4,5,6,7) 矛盾式的主析取范式為 0 (3)主合取范式為：(p(qr)(pqr) (p(qr)(pqr)(p(qr
5、)(pqr)(p(pqr)(qr)(pqr) 11 1 所以該式為永真式. 永真式的主合取范式為 1 主析取范式為(0,1,2,3,4,5,6,7)第三章部分課后習(xí)題參考答案14. 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明： (2)前提：pq,(qr),r結(jié)論：p (4)前提：qp,qs,st,tr結(jié)論：pq證明：（2）(qr) 前提引入qr 置換qr 蘊含等值式r 前提引入q 拒取式pq 前提引入p（3） 拒取式證明（4）：tr 前提引入t 化簡律qs 前提引入st 前提引入qt 等價三段論（qt）(tq) 置換（qt） 化簡q 假言推理qp 前提引入p 假言推理(11)pq 合取 15在自然推
6、理系統(tǒng)P中用附加前提法證明下面各推理：(1) 前提：p(qr),sp,q結(jié)論：sr證明s 附加前提引入sp 前提引入p 假言推理p(qr) 前提引入qr 假言推理q 前提引入r 假言推理16在自然推理系統(tǒng)P中用歸謬法證明下面各推理：(1)前提：pq,rq,rs 結(jié)論：p證明：p 結(jié)論的否定引入pq 前提引入q 假言推理rq 前提引入r 化簡律rs 前提引入r 化簡律rr 合取由于最后一步rr 是矛盾式,所以推理正確.第四章部分課后習(xí)題參考答案3. 在一階邏輯中將下面將下面命題符號化,并分別討論個體域限制為(a),(b)條件時命題的真值:(1) 對于任意x,均有2=(x+)(x).(2) 存在x
7、,使得x+5=9.其中(a)個體域為自然數(shù)集合. (b)個體域為實數(shù)集合.解：F(x): 2=(x+)(x). G(x): x+5=9.(1)在兩個個體域中都解釋為，在（a）中為假命題，在(b)中為真命題。(2)在兩個個體域中都解釋為，在（a）(b)中均為真命題。4. 在一階邏輯中將下列命題符號化:(1) 沒有不能表示成分?jǐn)?shù)的有理數(shù).(2) 在北京賣菜的人不全是外地人.解:(1)F(x): x能表示成分?jǐn)?shù) H(x): x是有理數(shù)命題符號化為: (2)F(x): x是北京賣菜的人 H(x): x是外地人命題符號化為: 5. 在一階邏輯將下列命題符號化: (1) 火車都比輪船快. (3) 不存在比
8、所有火車都快的汽車. 解:(1)F(x): x是火車; G(x): x是輪船; H(x,y): x比y快命題符號化為: (2) (1)F(x): x是火車; G(x): x是汽車; H(x,y): x比y快命題符號化為: 9.給定解釋I如下: (a) 個體域D為實數(shù)集合R. (b) D中特定元素=0. (c) 特定函數(shù)(x,y)=xy,x,y. (d) 特定謂詞(x,y):x=y,(x,y):xy,x,y. 說明下列公式在I下的含義,并指出各公式的真值:(1)(2)答:(1) 對于任意兩個實數(shù)x,y,如果xy, 那么xy. 真值1.(2) 對于任意兩個實數(shù)x,y,如果x-y=0, 那么xy.
9、真值0.10. 給定解釋I如下： （a） 個體域D=N(N為自然數(shù)集合). （b） D中特定元素=2. （c） D上函數(shù)=x+y,(x,y)=xy. （d） D上謂詞(x,y):x=y.說明下列各式在I下的含義，并討論其真值.(1) xF(g(x,a),x)(2) xy(F(f(x,a),y)F(f(y,a),x)答:(1) 對于任意自然數(shù)x, 都有2x=x, 真值0.(2) 對于任意兩個自然數(shù)x,y,使得如果x+2=y, 那么y+2=x. 真值0.11. 判斷下列各式的類型:(1) (3) yF(x,y).解:(1)因為 為永真式； 所以 為永真式；(3)取解釋I個體域為全體實數(shù)F(x,y)
10、：x+y=5所以,前件為任意實數(shù)x存在實數(shù)y使x+y=5，前件真；后件為存在實數(shù)x對任意實數(shù)y都有x+y=5，后件假，此時為假命題再取解釋I個體域為自然數(shù)N，F(xiàn)(x,y)：:x+y=5所以,前件為任意自然數(shù)x存在自然數(shù)y使x+y=5，前件假。此時為假命題。/錯誤的吧此公式為非永真式的可滿足式。13. 給定下列各公式一個成真的解釋，一個成假的解釋。(1) (F(x)(2) x(F(x)G(x)H(x)解:(1)個體域:本班同學(xué)F(x)：x會吃飯, G(x)：x會睡覺.成真解釋F(x)：x是泰安人,G(x)：x是濟(jì)南人.（2）成假解釋(2)個體域:泰山學(xué)院的學(xué)生F(x)：x出生在山東,G(x):x
11、出生在北京,H(x):x出生在江蘇,成假解釋.F(x)：x會吃飯,G(x)：x會睡覺,H(x)：x會呼吸. 成真解釋.第六章部分課后習(xí)題參考答案5.確定下列命題是否為真：（1） 真 （2） 假（3） 真（4） 真（5）a,ba,b,c,a,b,c 真（6）a,ba,b,c,a,b 真（7）a,ba,b,a,b 真（8）a,ba,b,a,b 假6設(shè)a,b,c各不相同，判斷下述等式中哪個等式為真:（1）a,b，c,=a,b,c 假（2）a ,b,a=a,b 真（3）a，b=a,b 假（4），a,b=,a,b 假8求下列集合的冪集：（1）a,b,c P(A)= ,a,b,c,a,b,a,c,b,c,
12、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 14化簡下列集合表達(dá)式：（1）（AB）B ）-（AB）（2）（ABC）-（BC）A解:(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=A18某班有25個學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。已知6個會打網(wǎng)球的人都會打籃球或排球。求不
13、會打球的人數(shù)。解: 阿A=會打籃球的人，B=會打排球的人，C=會打網(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不會打球的人共5人21.設(shè)集合A1，2，2，3，1，3,計算下列表達(dá)式：（1）A（2）A（3）A（4）A解: （1）A=1，22，31，3=1，2，3,（2）A=1，22，31，3=（3）A=123= （4）A=27、設(shè)A,B,C是任意集合，證明(1)(A-B)-C=A- BC(2)(A-B)-C=(A-C)-(B-C)證明(1) (A-B)-C=(AB)
14、C= A( BC)= A(BC) =A- BC(2) (A-C)-(B-C)=(AC) (B C)= (AC) (BC)=(ACB) (ACC)= (ACB) = A(BC) =A- BC 由（1）得證。第七章部分課后習(xí)題參考答案7.列出集合A=2,3,4上的恒等關(guān)系I A,全域關(guān)系EA,小于或等于關(guān)系LA,整除關(guān)系DA.解：IA =, EA=,LA=,DA=13.設(shè)A=, B=,求AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB ), fld(A-B).解：AB=, AB=domA=1,2,3 domB=1,2,4 dom(AB)=1,2,3,4r
15、anA=2,3,4 ranB=2,3,4ran(AB)=4A-B=,，fld(A-B)=1,2,314.設(shè)R=,求RR, R-1, R0,1, R1,2解：RR=, R-1,=,R0,1=,R1,2=ran(R|1,2)=2,316設(shè)A=a,b,c,d，為A上的關(guān)系，其中=求。解: R1R2=, R2R1=R12=R1R1=,R22=R2R2=,R23=R2R22=,36設(shè)A=1，2，3，4，在AA上定義二元關(guān)系R， ,AA ，u,v R u + y = x + v.(1) 證明R 是AA上的等價關(guān)系.(2)確定由R 引起的對AA的劃分.（1）證明：R u+y=x-yRu-v=x-yAAu-v
16、=u-vRR是自反的任意的,AA如果R ，那么u-v=x-yx-y=u-v R R是對稱的任意的,AA若R,R則u-v=x-y,x-y=a-bu-v=a-b RR是傳遞的R是AA上的等價關(guān)系(2) =, , , , , 41.設(shè)A=1，2，3，4，R為AA上的二元關(guān)系, a，b，c，d AA , a，bRc，da + b = c + d(1) 證明R為等價關(guān)系.(2) 求R導(dǎo)出的劃分.(1)證明：a，b AA a+b=a+bR R是自反的任意的,AA設(shè)R，則a+b=c+dc+d=a+b RR是對稱的任意的,AA若R,R則a+b=c+d,c+d=x+ya+b=x+y RR是傳遞的R是 AA上的等
17、價關(guān)系(2)=, , , , , , 43. 對于下列集合與整除關(guān)系畫出哈斯圖:(1) 1,2,3,4,6,8,12,24(2) 1,2,3,4,5,6,7,8,9,10,11,12解: (1) (2)45.下圖是兩個偏序集的哈斯圖.分別寫出集合A和偏序關(guān)系R的集合表達(dá)式. (a) (b)解: (a)A=a,b,c,d,e,f,g R=, (b) A=a,b,c,d,e,f,gR=,46.分別畫出下列各偏序集的哈斯圖,并找出A的極大元極小元最大元和最小元.(1)A=a,b,c,d,eR=,IA.(2)A=a,b,c,d,e, R=IA.解: (1) (2)項目 (1) (2)極大元: e a,
18、b,d,e 極小元: a a,b,c,e最大元: e 無最小元: a 無第八章部分課后習(xí)題參考答案1 設(shè)f :NN,且 f (x)=求f (0), f (0), f (1), f (1), f (0,2,4,6,)，f (4,6,8), f -1(3,5,7).解：f (0)=0, f (0)=0, f (1)=1, f (1)=1, f (0,2,4,6,)=N，f (4,6,8)=2,3,4, f -1 (3,5,7)=6,10,14.4. 判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪些是雙射的? (1) f:NN, f(x)=x2+2 不是滿射，不是單射 (2) f:NN,f(x)=(x
19、)mod 3,x除以3的余數(shù) 不是滿射，不是單射 (3) f:NN,f(x)= 不是滿射，不是單射 (4) f:N0,1,f(x)= 是滿射，不是單射 (5) f:N-0R,f(x)=lgx 不是滿射，是單射 (6) f:RR,f(x)=x2-2x-15 不是滿射，不是單射5. 設(shè)X=a,b,c,d,Y=1,2,3,f=,判斷以下命題的真假: (1)f是從X到Y(jié)的二元關(guān)系,但不是從X到Y(jié)的函數(shù); 對 (2)f是從X到Y(jié)的函數(shù),但不是滿射,也不是單射的; 錯 (3)f是從X到Y(jié)的滿射,但不是單射; 錯 (4)f是從X到Y(jié)的雙射. 錯第十四章部分課后習(xí)題參考答案5、設(shè)無向圖G有10條邊，3度與4度
20、頂點各2個，其余頂點的度數(shù)均小于3，問G至少有多少個頂點？在最少頂點的情況下，寫出度數(shù)列、。解：由握手定理圖G的度數(shù)之和為：3度與4度頂點各2個，這4個頂點的度數(shù)之和為14度。其余頂點的度數(shù)共有6度。其余頂點的度數(shù)均小于3，欲使G的頂點最少，其余頂點的度數(shù)應(yīng)都取2,所以，G至少有7個頂點, 出度數(shù)列為3,3,4,4,2,2,2,.7、設(shè)有向圖D的度數(shù)列為2，3，2，3，出度列為1，2，1，1，求D的入度列，并求，,.解：D的度數(shù)列為2，3，2，3，出度列為1，2，1，1，D的入度列為1,1,1,2.,8、設(shè)無向圖中有6條邊，3度與5度頂點各1個，其余頂點都是2度點，問該圖有多少個頂點？解：由握
21、手定理圖G的度數(shù)之和為：設(shè)2度點個，則，該圖有4個頂點.14、下面給出的兩個正整數(shù)數(shù)列中哪個是可圖化的？對可圖化的數(shù)列，試給出3種非同構(gòu)的無向圖，其中至少有兩個時簡單圖。(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4解：(1) 2+2+3+3+4+4+5=23 是奇數(shù)，不可圖化；(2) 22+2+2+3+3+4+4=16, 是偶數(shù)，可圖化；18、設(shè)有3個4階4條邊的無向簡單圖G1、G2、G3，證明它們至少有兩個是同構(gòu)的。證明：4階4條邊的無向簡單圖的頂點的最大度數(shù)為3，度數(shù)之和為8，因而度數(shù)列為2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1對應(yīng)的圖
22、不是簡單圖。所以從同構(gòu)的觀點看，4階4條邊的無向簡單圖只有兩個：所以，G1、G2、G3至少有兩個是同構(gòu)的。20、已知n階無向簡單圖G有m條邊，試求G的補(bǔ)圖的邊數(shù)。解：21、無向圖G如下圖(1)求G的全部點割集與邊割集，指出其中的割點和橋；(2) 求G的點連通度與邊連通度。解：點割集: a,b,(d)邊割集e2,e3,e3,e4,e1,e2,e1,e4e1,e3,e2,e4,e5=123、求G的點連通度、邊連通度與最小度數(shù)。解：、 、28、設(shè)n階無向簡單圖為3-正則圖，且邊數(shù)m與n滿足2n-3=m問這樣的無向圖有幾種非同構(gòu)的情況？解： 得n=6,m=9.31、設(shè)圖G和它的部圖的邊數(shù)分別為和，試確
23、定G的階數(shù)。解： 得45、有向圖D如圖 (1)求到長度為1，2，3，4的通路數(shù)；(2)求到長度為1，2，3，4的回路數(shù)；(3)求D中長度為4的通路數(shù)；(4)求D中長度小于或等于4的回路數(shù)；(5)寫出D的可達(dá)矩陣。解：有向圖D的鄰接矩陣為：， (1)到長度為1，2，3，4的通路數(shù)為0,2,0,0；(2)到長度為1，2，3，4的回路數(shù)為0,0,4,0；(3)D中長度為4的通路數(shù)為32；(4)D中長度小于或等于4的回路數(shù)10；(4)出D的可達(dá)矩陣第十六章部分課后習(xí)題參考答案1、畫出所有5階和7階非同構(gòu)的無向樹.2、一棵無向樹T有5片樹葉，3個2度分支點，其余的分支點都是3度頂點，問T有幾個頂點?解：
24、設(shè)3度分支點個，則 ，解得T有11個頂點3、無向樹T有8個樹葉，2個3度分支點，其余的分支點都是4度頂點，問T有幾個4度分支點？根據(jù)T的度數(shù)列，請至少畫出4棵非同構(gòu)的無向樹。解：設(shè)4度分支點個，則 ，解得度數(shù)列1111111133444、棵無向樹T有 (i=2，3，k)個i度分支點，其余頂點都是樹葉，問T應(yīng)該有幾片樹葉?解：設(shè)樹葉片，則 ，解得評論：2，3，4題都是用了兩個結(jié)論,一是握手定理，二是5、n(n3)階無向樹T的最大度至少為幾？最多為幾？解：2，n-16、若n(n3)階無向樹T的最大度 =2，問T中最長的路徑長度為幾？解：n-17、證明：n(n2) 階無向樹不是歐拉圖.證明：無向樹沒
25、有回路，因而不是歐拉圖。8、證明：n(n2) 階無向樹不是哈密頓圖.證明：無向樹沒有回路，因而不是哈密頓圖。9、證明：任何無向樹T都是二部圖.證明：無向樹沒有回路，因而不存在技術(shù)長度的圈，是二部圖。10、什么樣的無向樹T既是歐拉圖，又是哈密頓圖?解：一階無向樹14、設(shè)e為無向連通圖G中的一條邊， e在G的任何生成樹中，問e應(yīng)有什么性質(zhì)?解：e是橋15、設(shè)e為無向連通圖G中的一條邊， e不在G的任何生成樹中， 問e應(yīng)有什么性質(zhì)?解：e是環(huán) 23、已知n階m條的無向圖 G是k(k2)棵樹組成的森林，證明：m = n-k.；證明：數(shù)學(xué)歸納法。k=1時, m = n-1，結(jié)論成立；設(shè)k=t-1(t-1
26、)時，結(jié)論成立，當(dāng)k=t時, 無向圖 G是t棵樹組成的森林,任取兩棵樹，每棵樹任取一個頂點，這兩個頂點連線。則所得新圖有t-1棵樹，所以m = n-（k-1）.所以原圖中m = n-k得證。24、在圖16.6所示2圖中，實邊所示的生成子圖T是該圖的生成樹. (1)指出T的弦，及每條弦對應(yīng)的基本回路和對應(yīng)T的基本回路系統(tǒng).(2) 指出T的所有樹枝， 及每條樹枝對應(yīng)的基本割集和對應(yīng)T的基本割集系統(tǒng). (a) (b) 圖16.16 解：(a)T的弦：c,d,g,hT的基本回路系統(tǒng): S=a,c,b,a,b,f,d,e,a,b,h,e,a,b,f,gT的所有樹枝: e,a,b,fT的基本割集系統(tǒng): S
27、=e,g,h,a,c,d,g,h,b,c,d,g,h,f,d,g(b)有關(guān)問題仿照給出25、求圖16.17所示帶權(quán)圖中的最小生成樹. (a) (b)圖16.17解：注：答案不唯一。37、畫一棵權(quán)為3，4，5，6，7，8，9的最優(yōu)2叉樹，并計算出它的權(quán).38.下面給出的各符號串集合哪些是前綴碼? A1=0，10，110，1111 是前綴碼 A2=1，01，001，000 是前綴碼 A3=1，11，101，001，0011 不是前綴碼 A4=b，c，aa，ac，aba，abb，abc 是前綴碼 A5= b，c，a，aa，ac，abc，abb，aba 不是前綴碼41.設(shè)7個字母在通信中出現(xiàn)的頻率如下: a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5%用Huffman算法求傳輸它們的前綴碼.要求畫出最優(yōu)樹，指出每個字母對應(yīng)的編碼.并指出傳輸10n(n2)個按上述頻率出現(xiàn)的字母，需要多少個二進(jìn)制數(shù)字.解：a:01 b:10 c:000 d:110 e:001 f:1111 g:1110W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255傳輸10n(n2)個按上述頻率出現(xiàn)的字母，需要255*10n-2個二進(jìn)制數(shù)字.
離散數(shù)學(xué)屈婉玲版課后習(xí)題.doc
