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

第一章部分課后習(xí)題參考答案16設(shè)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命題符號(hào)化為：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)公式類型為永真式(方法如上例)第二章部分課后習(xí)題參考答案3.用等值演算法判斷下列公式的類型,對(duì)不是重言式的可滿足式,再用真值表法求出成真賦值.(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所以該式為永真式永真式的主合取范式為主析取范式為￡第三章部分課后習(xí)題參考答案在自然推理系統(tǒng)中構(gòu)造下面推理的證明：前提：-「A結(jié)論：-前提：—仆3A結(jié)論：A證明：（）①「A前提引入②「V-①置換③”「②蘊(yùn)含等值式④前提引入⑤「③④拒取式前提引入⑤⑥拒取式證明（）:①證明（）:①人②③妗④?、葚阿蓿╢）A⑦（）⑧⑨1⑩前提引入①化簡(jiǎn)律前提引入前提引入③④等價(jià)三段論—⑤置換⑥化簡(jiǎn)②⑥假言推理前提引入⑧⑨假言推理⑧⑩合取在自然推理系統(tǒng)中用附加前提法證明下面各推理:在自然推理系統(tǒng)中用附加前提法證明下面各推理:前提：—T,結(jié)論：-證明附加前提引入—前提引入①②假言推理④——前提引入—③④假言推理前提引入⑤⑥假言推理在自然推理系統(tǒng)中用歸謬法證明下面各推理:前提：——1—1VA—I結(jié)論：—證明：①結(jié)論的否定引入②—「前提引入③[①②假言推理

④1V前提引入⑤「④化簡(jiǎn)律⑥入「前提引入⑦⑥化簡(jiǎn)律⑧入「⑤⑦合取由于最后一步A「是矛盾式所以推理正確第四章部分課后習(xí)題參考答案在一階邏輯中將下面將下面命題符號(hào)化并分別討論個(gè)體域限制為條件時(shí)命題的真值對(duì)于任意均有錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。).存在使得其中個(gè)體域?yàn)樽匀粩?shù)集合個(gè)體域?yàn)閷?shí)數(shù)集合解：錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。在兩個(gè)個(gè)體域中都解釋為VxF(x)，在()中為假命題，在中為真命題。在兩個(gè)個(gè)體域中都解釋為3在兩個(gè)個(gè)體域中都解釋為3xG(x)，在()中對(duì)均為真命題。.在一階邏輯中將下列命題符號(hào)化:(1對(duì)沒有不能表示成分?jǐn)?shù)的有理數(shù).(2對(duì)在北京賣菜的人不全是外地人.解:能表示成分?jǐn)?shù)是有理數(shù)命題符號(hào)化為「3x(「F(x)aH(x))是北京賣菜的人是外地人命題符號(hào)化為「Vx(F(x)TH(x)).在一階邏輯將下列命題符號(hào)化:火車(都1比對(duì)輪船快.不存(在3比對(duì)所有火車都快的汽車.解:是火車是輪船比快命題符號(hào)化為VxVy((F(x)aG(y))fH(x,y))是火車是汽車比快命題符號(hào)化為「方(G(y)aVx(F(x)fH(x,y)))給定解釋如下個(gè)體域?yàn)閷?shí)數(shù)集合中特定元素錯(cuò)誤！未找到引用源。特定函數(shù)錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。￡。錯(cuò)誤！未找到引用源。給特定謂詞錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。eD說明下列公式在下的含義并指出各公式的真值VxVy(G(x,y)f「F(x,y))(2V)xVy(F(f(x,y),a)fG(x,y))答對(duì)于任意兩個(gè)實(shí)數(shù)如果那么w真值對(duì)于任意兩個(gè)實(shí)數(shù)如果那么真值給定解釋如下：()個(gè)體域?yàn)樽匀粩?shù)集合()中特定元素錯(cuò)誤！未找到引用源。()上函數(shù)錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。()上謂詞錯(cuò)誤！未找到引用源。說明下列各式在下的含義，并討論其真值錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。一答對(duì)于任意自然數(shù)都有真值對(duì)于任意兩個(gè)自然數(shù)使得如果那么真值11給判斷下列各式的類型:(1對(duì)錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。解因?yàn)閜f(qfp)O「pv(「qvp)o1為永真式；所以錯(cuò)誤！未找到引用源。為永真式；取解釋個(gè)體域?yàn)槿w實(shí)數(shù)所以前件為任意實(shí)數(shù)存在實(shí)數(shù)使，前件真；后件為存在實(shí)數(shù)對(duì)任意實(shí)數(shù)都有，后件假，此時(shí)為假命題再取解釋個(gè)體域?yàn)樽匀粩?shù)所以前件為任意自然數(shù)存在自然數(shù)使，前件假。此時(shí)為假命題。此公式為非永真式的可滿足式。13.給定下列各公式一個(gè)成真的解釋，一個(gè)成假的解釋。錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。解:（個(gè)1體）域:本班同學(xué):會(huì)吃飯：會(huì)睡覺成真解釋:是泰安人：是濟(jì)南人（）成假解釋（2個(gè)誤體域:泰山學(xué)院的學(xué)生:出生在山東出生在北京出生在江蘇成假解釋:會(huì)吃飯：會(huì)睡覺：會(huì)呼吸成真解釋第六章部分課后習(xí)題參考答案確.定下列命題是否為真：TOC\o"1-5"\h\z()0=0真()0￡0假(3)0={0}真()0e{0}真(){}={{}}真(){}e{}}}真(){}={{}}}}真(){}e}}}}}假.設(shè)各不相同，判斷下述等式中哪個(gè)等式為真(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,,.化簡(jiǎn)下列集合表達(dá)式：（）（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.某班有個(gè)學(xué)生，其中人會(huì)打籃球，人會(huì)打排球，人會(huì)打籃球和排球，人會(huì)打籃球（）un（）（）nunnn00（）un0、設(shè)是任意集合，證明證明b?n?ri?ri?n?。。n?n?n?n?n?un?n?un?nn?n?u°n?uu由（）得證。第七章部分課后習(xí)題參考答案.列出集合A={2,3,4}上的恒等關(guān)系IA，全域關(guān)系Ea，小于或等于關(guān)系La，整除關(guān)系Da.解：，13.設(shè)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.設(shè)R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求R。R,R-1,R個(gè){0,1,},R[{1,2}]解：。R-1,個(gè)16.設(shè)A={a,b,c,d},RR為A上的關(guān)系，其中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.設(shè)，，，，在X上定義二元關(guān)系，V￡X,〈O證明是X上的等價(jià)關(guān)系確定由引起的對(duì)X的劃分()證明：：O???是自反的任意的￡X如果，那么??

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

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

???????是對(duì)稱的任意的￡X若則??

???????是傳遞的???是X上的等價(jià)關(guān)系n對(duì)于下列集合與整除關(guān)系畫出哈斯圖下圖是兩個(gè)偏序集，的哈斯圖分別寫出集合和偏序關(guān)系.的集合表達(dá)式

下圖是兩個(gè)偏序集，的哈斯圖分別寫出集合和偏序關(guān)系.的集合表達(dá)式,<A,e,<AA分別畫出下列各偏序集,的哈斯圖并找出的極大元極小元最大元和最小元(1)項(xiàng)目極大元:極小元:最大元:最小元:able(1)項(xiàng)目極大元:極小元:最大元:最小元:c(2)第八章部分課后習(xí)題參考答案1.設(shè)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(jié)的二元關(guān)系，但不是從X到Y(jié)的函數(shù)；對(duì)TOC\o"1-5"\h\z(2)f是從X到Y(jié)的函數(shù)，但不是滿射，也不是單射的；錯(cuò)(3)f是從X到Y(jié)的滿射，但不是單射；錯(cuò)(4)f是從X到Y(jié)的雙射.錯(cuò)第十四章部分課后習(xí)題參考答案5、設(shè)無向圖有條邊，度與度頂點(diǎn)各個(gè)，其余頂點(diǎn)的度數(shù)均小于，問至少有多少個(gè)頂點(diǎn)？在最少頂點(diǎn)的情況下，寫出度數(shù)列、A(G)、b(G)。解：由握手定理圖的度數(shù)之和為：2x10=203度與4度頂點(diǎn)各2個(gè),這4個(gè)頂點(diǎn)的度數(shù)之和為14度。其余頂點(diǎn)的度數(shù)共有6度。其余頂點(diǎn)的度數(shù)均小于，欲使的頂點(diǎn)最少，其余頂點(diǎn)的度數(shù)應(yīng)都取所以，至少有個(gè)頂點(diǎn)出度數(shù)列為A(G)=4,8(G)=27設(shè)有向圖的度數(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、設(shè)無向圖中有6條邊,3度與5度頂點(diǎn)各，個(gè),其余頂點(diǎn)都是，度點(diǎn),問該圖有多少個(gè)頂點(diǎn)？解：由握手定理圖的度數(shù)之和為：2x6=12

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

11111(4)出D的可達(dá)矩陣尸=1111111111j1111)第十六章部分課后習(xí)題參考答案1、畫出所有5階和7階非同構(gòu)的無向樹.2、一棵無向樹2、一棵無向樹T有5片樹葉，3個(gè)2度分支點(diǎn)，其余的分支點(diǎn)都是3度頂點(diǎn)，問T有幾個(gè)頂點(diǎn)?解：設(shè)3度分支點(diǎn)了個(gè)，則5x1+3x2+31=2x(5+3+了-1)，解得了=3T有11個(gè)頂點(diǎn)3、無向樹T有8個(gè)樹葉，2個(gè)3度分支點(diǎn)，其余的分支點(diǎn)都是4度頂點(diǎn)，問T有幾個(gè)4度分支點(diǎn)？根據(jù)T的度數(shù)列，請(qǐng)至少畫出4棵非同構(gòu)的無向樹。解：設(shè)4度分支點(diǎn)了個(gè),則8x1+2x3+4x=2x(8+2+x—1),解得x=2度數(shù)列1111111133444、棵無向樹T有n,(i=2,3,…，錯(cuò)誤！未找到引用源。個(gè)度分支點(diǎn)，其余頂點(diǎn)都是樹葉，問T應(yīng)該有幾片樹葉解：設(shè)樹葉x片，則nxi+xx1=2x(n+x-1)，解得x=(i—2)n+2,,,評(píng)論：2,3,4題都是用了兩個(gè)結(jié)論,一是握手定理，二是m=n—15、n(nN階無向樹T的最大度錯(cuò)誤！未找到引用源。至少為幾？最多為幾？解：2,n-16、若n(nN階無向樹T的最大度錯(cuò)誤！未找到引用源。，問T中最長(zhǎng)的路徑長(zhǎng)度為幾？解：n-17、證明：n(nN階無向樹不是歐拉圖證明：無向樹沒有回路,因而不是歐拉圖。8、證明：n(nN階無向樹不是哈密頓圖證明：無向樹沒有回路,因而不是哈密頓圖。9、證明：任何無向樹T都是二部圖.證明：無向樹沒有回路,因而不存在技術(shù)長(zhǎng)度的圈,是二部圖。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(kN2)棵樹組成的森林，證明：m=n-k.；證明：數(shù)學(xué)歸納法。k=1時(shí),m=n-1,結(jié)論成立