離散數(shù)學屈婉玲版課后習題匯總

第一章部分課后習題參考答案16設p、q的真值為0;r、s的真值為1,求下列各命題公式的真值。(1)pVqO0VAO()(一)八]VO(-1)A1OaO()(「A「A)-AA]o(aA)-AAoLA)fA「o(A)fAOfO17.判斷下面一段論述是否為真：“兀是無理數(shù)。并且，如果3是無理數(shù)，則2也是無理數(shù)。另外6能被2整除,6才能被4整除?！贝穑簆:兀是無理數(shù)13是無理數(shù)02是無理數(shù)16能被2整除16能被4整除0命題符號化為：pA(qfr)A(tfs)的真值為1,所以這一段的論述為真。19．用真值表判斷下列公式的類型：(pfq)f(「qf「p)(pAr)?(「pA「q)(6)((pfq)A(qfr))f(pfr)答：(4)pqpfq「q「p「qf「p(pfq)f(「qf「p)0011111011011110010011110011所以公式類型為永真式(5)公式類型為可滿足式(方法如上例)(6)公式類型為永真式(方法如上例)第二章部分課后習題參考答案3.用等值演算法判斷下列公式的類型,對不是重言式的可滿足式,再用真值表法求出成真賦值.(1)](pAqfq)(2)(pf(pVq))V(pfr)(3)(pVq)f(pAr)答：(2)(pf(pVq))V(pfr)O(「pV(pVq))V(「pVr)O「pVpVqVrO1所以公式類型為永真式PqrpVqpAr(pVq)f(pAr)000001001001010100011100100100101111110100111111所以公式類型為可滿足式用等值演算法證明下面等值式：f）fop八八」V「八Op八」八證明（）。）fo「V八」Vo「V八ofAA「V「AoV」AA」V」AoV「AVA」V」A」Vo1AAA「AAoV）「A求下列公式的主析取范式與主合取范式，并求成真賦值「ff「V「。AAVAfVV解：（）主析取范式「f）「vo「A）」Vo「A「V」Vo「A「V「AV「A「VAVA「omvmvm023oE主合取范式：「ff「vo「AV「V0Av-0p-oon主合取范式為：-vAAo——V）A0A-AA0所以該式為矛盾式主合取范式為n矛盾式的主析取范式為主合取范式為：vAfVVo-vAfVVO-A-V-VVVO-VVVA-V-A/VV0A0所以該式為永真式永真式的主合取范式為主析取范式為￡第三章部分課后習題參考答案在自然推理系統(tǒng)中構造下面推理的證明：前提：-「A結論：-前提：—仆3A結論：A證明：（）①「A前提引入②「V-①置換③”「②蘊含等值式④前提引入⑤「③④拒取式前提引入⑤⑥拒取式證明（）:①證明（）:①人②③?、苕、葚阿蓿╢）A⑦（）⑧⑨1⑩前提引入①化簡律前提引入前提引入③④等價三段論—⑤置換⑥化簡②⑥假言推理前提引入⑧⑨假言推理⑧⑩合取在自然推理系統(tǒng)中用附加前提法證明下面各推理:在自然推理系統(tǒng)中用附加前提法證明下面各推理:前提：—T,結論：-證明附加前提引入—前提引入①②假言推理④——前提引入—③④假言推理前提引入⑤⑥假言推理在自然推理系統(tǒng)中用歸謬法證明下面各推理:前提：——1—1VA—I結論：—證明：①結論的否定引入②—「前提引入③[①②假言推理

④1V前提引入⑤「④化簡律⑥入「前提引入⑦⑥化簡律⑧入「⑤⑦合取由于最后一步A「是矛盾式所以推理正確第四章部分課后習題參考答案在一階邏輯中將下面將下面命題符號化并分別討論個體域限制為條件時命題的真值對于任意均有錯誤！未找到引用源。錯誤！未找到引用源。錯誤！未找到引用源。).存在使得其中個體域為自然數(shù)集合個體域為實數(shù)集合解：錯誤！未找到引用源。錯誤！未找到引用源。錯誤！未找到引用源。在兩個個體域中都解釋為VxF(x)，在()中為假命題，在中為真命題。在兩個個體域中都解釋為3在兩個個體域中都解釋為3xG(x)，在()中對均為真命題。.在一階邏輯中將下列命題符號化:(1對沒有不能表示成分數(shù)的有理數(shù).(2對在北京賣菜的人不全是外地人.解:能表示成分數(shù)是有理數(shù)命題符號化為「3x(「F(x)aH(x))是北京賣菜的人是外地人命題符號化為「Vx(F(x)TH(x)).在一階邏輯將下列命題符號化:火車(都1比對輪船快.不存(在3比對所有火車都快的汽車.解:是火車是輪船比快命題符號化為VxVy((F(x)aG(y))fH(x,y))是火車是汽車比快命題符號化為「方(G(y)aVx(F(x)fH(x,y)))給定解釋如下個體域為實數(shù)集合中特定元素錯誤！未找到引用源。特定函數(shù)錯誤！未找到引用源。錯誤！未找到引用源?！?。錯誤！未找到引用源。給特定謂詞錯誤！未找到引用源。錯誤！未找到引用源。eD說明下列公式在下的含義并指出各公式的真值VxVy(G(x,y)f「F(x,y))(2V)xVy(F(f(x,y),a)fG(x,y))答對于任意兩個實數(shù)如果那么w真值對于任意兩個實數(shù)如果那么真值給定解釋如下：()個體域為自然數(shù)集合()中特定元素錯誤！未找到引用源。()上函數(shù)錯誤！未找到引用源。錯誤！未找到引用源。()上謂詞錯誤！未找到引用源。說明下列各式在下的含義，并討論其真值錯誤！未找到引用源。錯誤！未找到引用源。錯誤！未找到引用源。一答對于任意自然數(shù)都有真值對于任意兩個自然數(shù)使得如果那么真值11給判斷下列各式的類型:(1對錯誤！未找到引用源。錯誤！未找到引用源。解因為pf(qfp)O「pv(「qvp)o1為永真式；所以錯誤！未找到引用源。為永真式；取解釋個體域為全體實數(shù)所以前件為任意實數(shù)存在實數(shù)使，前件真；后件為存在實數(shù)對任意實數(shù)都有，后件假，此時為假命題再取解釋個體域為自然數(shù)所以前件為任意自然數(shù)存在自然數(shù)使，前件假。此時為假命題。此公式為非永真式的可滿足式。13.給定下列各公式一個成真的解釋，一個成假的解釋。錯誤！未找到引用源。錯誤！未找到引用源。錯誤！未找到引用源。錯誤！未找到引用源。錯誤！未找到引用源。解:（個1體）域:本班同學:會吃飯：會睡覺成真解釋:是泰安人：是濟南人（）成假解釋（2個誤體域:泰山學院的學生:出生在山東出生在北京出生在江蘇成假解釋:會吃飯：會睡覺：會呼吸成真解釋第六章部分課后習題參考答案確.定下列命題是否為真：TOC\o"1-5"\h\z()0=0真()0￡0假(3)0={0}真()0e{0}真(){}={{}}真(){}e{}}}真(){}={{}}}}真(){}e}}}}}假.設各不相同，判斷下述等式中哪個等式為真(1)}}a}}b，c}0}=}}a}}b}c}假(2)}a}}b=}}aa}}b真(3)}}a}，}=}}a}}}b假()}0,}0},}}0}0}}}假．求下列集合的冪集：()}}0()}1}2}}0,

（）{0}0{0}（）{0,{0}}0,,.化簡下列集合表達式：（）（u）n）（u）（）（（uu）（u））u解（u）n）（u）（u）n）n?」）（u）n?（u）n0n0（）（（uu）（u））u（（uu）n?（u））u（n?（u））u（（u）n?（u））u（n?（u））u0u（n?（u））u.某班有個學生，其中人會打籃球，人會打排球，人會打籃球和排球，人會打籃球（）un（）（）nunnn00（）un0、設是任意集合，證明證明b?n?ri?ri?n?。。n?n?n?n?n?un?n?un?nn?n?u°n?uu由（）得證。第七章部分課后習題參考答案.列出集合A={2,3,4}上的恒等關系IA，全域關系Ea，小于或等于關系La，整除關系Da.解：，13.設A={<1,2>,<2,4>,<3,3>}B={<1,3>,<2,4>,<4,2>}求AuB,ACB,domA,domB,dom(AuB),ranA,ranB,ran(ACB),fld(A-B).解：uCVC214.設R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求R。R,R-1,R個{0,1,},R[{1,2}]解：。R-1,個16.設A={a,b,c,d},RR為A上的關系，其中1,2R{a,a,a,b,b,d}1=R={a,d,b,c,b,d,c,b2求RR,RR,R2,R3。TOC\o"1-5"\h\z122112.設，，，，在X上定義二元關系，V￡X,〈O證明是X上的等價關系確定由引起的對X的劃分()證明：：O???是自反的任意的￡X如果，那么??

???????是對稱的任意的￡X若貝U???是傳遞的???是X上的等價關系n設人={1,2,3,4},R為AxA上的二元關系，V〈a,b〉，〈c,d〉￡AxA,〈a,b〉R〈c,d〉O(1)證明為等價關系.

求R導出的劃分證明：Va,b〉EAxA*?????是自反的TOC\o"1-5"\h\z任意的￡X設，貝c??

???????是對稱的任意的￡X若則??

???????是傳遞的???是X上的等價關系n對于下列集合與整除關系畫出哈斯圖下圖是兩個偏序集，的哈斯圖分別寫出集合和偏序關系.的集合表達式

下圖是兩個偏序集，的哈斯圖分別寫出集合和偏序關系.的集合表達式,<A,e,<AA分別畫出下列各偏序集,的哈斯圖并找出的極大元極小元最大元和最小元(1)項目極大元:極小元:最大元:最小元:able(1)項目極大元:極小元:最大元:最小元:c(2)第八章部分課后習題參考答案1.設f:NfN,且工若x為奇數(shù)f(x)=I-若x為偶數(shù)

[2,f-1({3,5,7}).求f(0),f({0}),f(1),f({1}),f({0,2,4,6,…}),f({4,6,8}),

解：f(0)=0,f({0})={0},ff-1({3,5,7}).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:NT(1)f:NTN,f(x)=x2+2不是滿射，不是單射(2)f:NTN,f(x)=(x)mod3,x除以3的余數(shù)不是滿射，不是單射不是滿射，不是單射是滿射,不是單射[1,若x為奇數(shù)不是滿射，不是單射是滿射,不是單射⑶f：NTN^10,若x為偶數(shù)[0,若x為奇數(shù)f：NT{0，1}，f(x)=]l,若x為偶數(shù)f:N-{0}TR,f(x)=lgx不是滿射,是單射f:RTR,f(x)=x2-2x-15不是滿射,不是單射X={a,b,c,d},Y={1,2,3},f={<a,1>,<b,2>,<c,3>,}判斷以下命題的真假:(1)f是從X到Y的二元關系，但不是從X到Y的函數(shù)；對TOC\o"1-5"\h\z(2)f是從X到Y的函數(shù)，但不是滿射，也不是單射的；錯(3)f是從X到Y的滿射，但不是單射；錯(4)f是從X到Y的雙射.錯第十四章部分課后習題參考答案5、設無向圖有條邊，度與度頂點各個，其余頂點的度數(shù)均小于，問至少有多少個頂點？在最少頂點的情況下，寫出度數(shù)列、A(G)、b(G)。解：由握手定理圖的度數(shù)之和為：2x10=203度與4度頂點各2個,這4個頂點的度數(shù)之和為14度。其余頂點的度數(shù)共有6度。其余頂點的度數(shù)均小于，欲使的頂點最少，其余頂點的度數(shù)應都取所以，至少有個頂點出度數(shù)列為A(G)=4,8(G)=27設有向圖的度數(shù)列為，，，，出度列為，，，，求的入度列，并求A(D),8(D)，A+(D),8+(D)A-(D),8-(D)解：的度數(shù)列為，3,3出度列為，，，，的入度列為A(D)=3,8(D)=2A+(D)=2,8+(D)=1A-(D)=2,8-(D)=18、設無向圖中有6條邊,3度與5度頂點各，個,其余頂點都是，度點,問該圖有多少個頂點？解：由握手定理圖的度數(shù)之和為：2x6=12

x=2，該圖有個頂點設度點X個，貝u3X1+5X1+2Xx=2，該圖有個頂點14、下面給出的兩個正整數(shù)數(shù)列中哪個是可圖化的？對可圖化的數(shù)列，試給出3種非同構的無向圖，其中至少有兩個時簡單圖。解：(1(2)＋是+奇4數(shù)+，4不+可5解：(1(2)＋是+偶4數(shù)+，4可=圖1化6；,18、設有3個4階4條邊的無向簡單圖G/G2、G3,證明它們至少有兩個是同構的。證明：4階4條邊的無向簡單圖的頂點的最大度數(shù)為3，度數(shù)之和為8，因而度數(shù)列為2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1對應的圖不是簡單圖。所以從同構的觀點看，4階4條邊的無向簡單圖只有兩個：所以，G1、G2、G3至少有兩個是同構的。20、已知n階無向簡單圖G有m條邊，試求G的補圖G的邊數(shù)m'。解：21、無向圖G如下圖(1)求G的全部點割集與邊割集，指出其中的割點和橋;(2)求G的點連通度k(G)與邊連通度入(G)。解：點割集:{a,b},(d)邊割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}k(G)=入(G)=123、求G的點連通度k(G)、邊連通度入(G)與最小度數(shù)5(G)。23、解：k(G)=2、入(G)=3、5(G)=428、設n階無向簡單圖為3-正則圖，且邊數(shù)m與n滿足2n-3=m問這樣的無向圖有幾種非同構的情況？13n=2m解：<得n=6,m=9.[2n—3=m31、試確定G的階數(shù)。31、試確定G的階數(shù)。設圖G和它的部圖G的邊數(shù)分別為m和m，一n一n(n+1)解：m+m=2—1+1+8(m+m)得n=245、45、有向圖D如圖⑴求V2⑴求V2到V5長度為1⑵求V5到V5長度為12，3，4的通路數(shù)；2，3，4的回路數(shù)；⑶求D中長度為4的通路數(shù)；(4)求D中長度小于或等于4的回路數(shù);(5)寫出D的可達矩陣。解：有向圖D的鄰接矩陣為:f0101、00000101010f0101、000001010100000110100f0000、21010000002101000]2020,A3202000202020200020200]004f0f00004]40400A4=0000440400、04040,5，，，，-A+A2+A3+A4=24122522121525225254)⑴v2到肘5長度為1,2,3,4的通路數(shù)為0,2,0,0；⑵v5到v5長度為1,2,3,4的回路數(shù)為0,0,4,0；⑶D中長度為4的通路數(shù)為32；(4)D中長度小于或等于4的回路數(shù)10；f11111]

11111(4)出D的可達矩陣尸=1111111111j1111)第十六章部分課后習題參考答案1、畫出所有5階和7階非同構的無向樹.2、一棵無向樹2、一棵無向樹T有5片樹葉，3個2度分支點，其余的分支點都是3度頂點，問T有幾個頂點?解：設3度分支點了個，則5x1+3x2+31=2x(5+3+了-1)，解得了=3T有11個頂點3、無向樹T有8個樹葉，2個3度分支點，其余的分支點都是4度頂點，問T有幾個4度分支點？根據(jù)T的度數(shù)列，請至少畫出4棵非同構的無向樹。解：設4度分支點了個,則8x1+2x3+4x=2x(8+2+x—1),解得x=2度數(shù)列1111111133444、棵無向樹T有n,(i=2,3,…，錯誤！未找到引用源。個度分支點，其余頂點都是樹葉，問T應該有幾片樹葉解：設樹葉x片，則nxi+xx1=2x(n+x-1)，解得x=(i—2)n+2,,,評論：2,3,4題都是用了兩個結論,一是握手定理，二是m=n—15、n(nN階無向樹T的最大度錯誤！未找到引用源。至少為幾？最多為幾？解：2,n-16、若n(nN階無向樹T的最大度錯誤！未找到引用源。，問T中最長的路徑長度為幾？解：n-17、證明：n(nN階無向樹不是歐拉圖證明：無向樹沒有回路,因而不是歐拉圖。8、證明：n(nN階無向樹不是哈密頓圖證明：無向樹沒有回路,因而不是哈密頓圖。9、證明：任何無向樹T都是二部圖.證明：無向樹沒有回路,因而不存在技術長度的圈,是二部圖。10、什么樣的無向樹T既是歐拉圖，又是哈密頓圖解：一階無向樹14、設e為無向連通圖G中的一條邊，e在G的任何生成樹中，問e應有什么性質？解：e是橋15、設e為無向連通圖G中的一條邊，e不在G的任何生成樹中，問e應有什么性質？解：e是環(huán)23、已知n階m條的無向圖G是k(kN2)棵樹組成的森林，證明：m=n-k.；證明：數(shù)學歸納法。k=1時,m=n-1,結論成立