【正文】 的，每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學工作者，并且是聰明的，所以王大海在他的事業(yè)中將獲得成功。設F(x):x是科學工作者，G(x)：x是刻苦鉆研的，H(x):x是聰明的，I(x):x在事業(yè)中獲得成功前提 x(F(x)174。G(x))，x(G(x)217。H(x)174。I(x))，a:王大海，F(xiàn)(a),H(a)結論 I(a)證明：1 F(a)前提引入x(F(x)174。G(x))前提引入F(a)174。G(a)2UI G(a)3假言推論H(a)前提引入 x(G(x)217。H(x)174。I(x))前提引入G(a)217。H(a)174。I(a)6UI G(a)217。H(a)5合取I(a)8假言推論第四篇：離散數(shù)學課后習題答案第一章部分課后習題參考答案 設p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。（1）p∨(q∧r)219。 0∨(0∧1)219。0（2）（p?r）∧(﹁q∨s)219。（0?1）∧(1∨1)219。0∧1219。0.（3）（216。p∧216。q∧r）?(p∧q∧﹁r)219。（1∧1∧1）?(0∧0∧0)219。0(4)（216。r∧s）→(p∧216。q)219。（0∧1）→(1∧0)219。0→0219。1 17．判斷下面一段論述是否為真：“p是無理數(shù)。并且，如果3是無理數(shù)，則2也是無理數(shù)。另外，只有6能被2整除，6才能被4整除?！贝穑簆: p是無理數(shù)q: 3是無理數(shù)0r: 2是無理數(shù)s: 6能被2整除t: 6能被4整除0命題符號化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。19．用真值表判斷下列公式的類型：（4）(p→q)→(216。q→216。p)（5）(p∧r)171。(216。p∧216。q)（6）((p→q)∧(q→r))→(p→r)答：（4）pqp→q216。q216。p216。q→216。p(p→q)→(216。q→216。p)0000000000所以公式類型為永真式（5）公式類型為可滿足式（方法如上例）（6）公式類型為永真式（方法如上例）第二章部分課后習題參考答案，對不是重言式的可滿足式，(1)216。(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)219。(216。p∨(p∨q))∨(216。p∨r)219。216。p∨p∨q∨r219。1所以公式類型為永真式(3)Pqrp∨qp∧r（p∨q）→(p∧r)0000000000000 000 10000 101000 1所以公式類型為可滿足式：(2)(p→q)∧(p→r)219。(p→(q∧r))(4)(p∧216。q)∨(216。p∧q)219。(p∨q)∧216。(p∧q)證明（2）(p→q)∧(p→r)219。(216。p∨q)∧(216。p∨r)219。216。p∨(q∧r))219。p→(q∧r)（4）(p∧216。q)∨(216。p∧q)219。(p∨(216。p∧q))∧(216。q∨(216。p∧q)219。(p∨216。p)∧(p∨q)∧(216。q∨216。p)∧(216。q∨q)219。1∧(p∨q)∧216。(p∧q)∧1 219。(p∨q)∧216。(p∧q)，并求成真賦值(1)(216。p→q)→(216。q∨p)(2)216。(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(216。p→q)→(216。q218。p)219。216。219。219。219。(p218。q)218。(216。q218。p)(216。p217。216。q)218。(216。q218。p)(216。p217。216。q)218。(216。q217。p)218。(216。q217。216。p)218。(p217。q)218。(p217。216。q)(216。p217。216。q)218。(p217。216。q)218。(p217。q)219。m0218。m2218。m3219?！?0,2,3)主合取范式：(216。p→q)→(216。q218。p)219。216。219。(p218。q)218。(216。q218。p)(216。p217。216。q)218。(216。q218。p)219。(216。p218。(216。q218。p))217。(216。q218。(216。q218。p))219。1217。(p218。216。q)219。(p218。216。q)219。 M1219。∏(1)(2)主合取范式為：216。(p→q)217。q217。r219。216。(216。p218。q)217。q217。r 219。(p217。216。q)217。q217。r219。0 ∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式為 0(3)主合取范式為：(p218。(q217。r))→(p218。q218。r)219。216。(p218。(q217。r))→(p218。q218。r)219。219。(216。p217。(216。q218。216。r))218。(p218。q218。r)(216。p218。(p218。q218。r))217。((216。q218。216。r))218。(p218。q218。r))219。1217。1 219。1 1 主析取范式為∑(0,1,2,3,4,5,6,7)第三章部分課后習題參考答案：(2)前提：p174。q,216。(q217。r),r 結論：216。p(4)前提：q174。p,q171。s,s171。t,t217。r 結論：p217。q證明：（2）①216。(q217。r)前提引入 ②216。q218。216。r ①置換 ③q174。216。r ②蘊含等值式 ④r 前提引入 ⑤216。q ③④拒取式 ⑥p174。q 前提引入 ⑦￢p（3）⑤⑥拒取式證明（4）：①t217。r 前提引入 ②t ①化簡律 ③q171。s 前提引入 ④s171。t 前提引入⑤q171。t ③④等價三段論 ⑥（q174。t）217。(t174。q)⑤ 置換 ⑦（q174。t）⑥化簡 ⑧q ②⑥ 假言推理 ⑨q174。p 前提引入 ⑩p ⑧⑨假言推理(11)p217。q ⑧⑩合取15在自然推理系統(tǒng)P中用附加前提法證明下面各推理：4(1)前提：p174。(q174。r),s174。p,q 結論：s174。r 證明①s 附加前提引入 ②s174。p 前提引入 ③p ①②假言推理 ④p174。(q174。r)前提引入 ⑤q174。r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理16在自然推理系統(tǒng)P中用歸謬法證明下面各推理：(1)前提：p174。216。q,216。r218。q,r217。216。s 結論：216。p 證明：①p 結論的否定引入 ②p174。﹁q 前提引入 ③﹁q ①②假言推理 ④￢r218。q 前提引入 ⑤￢r ④化簡律 ⑥r(nóng)217。￢s 前提引入 ⑦r ⑥化簡律 ⑧r217。﹁r ⑤⑦ 合取由于最后一步r217。﹁r 是矛盾式,所以推理正確.第五篇：《離散數(shù)學》圖論部分習題《離散數(shù)學》圖論部分習題，6個3度頂點，其余頂點的度數(shù)均小于3，問G至少有幾個頂點？并畫出滿足條件的一個圖形.（243*6）/2 +6=9 ，其度序列為6；7階無向簡單圖G中最大度≤6 、d…、：不存在以dd…、{d1，d2，…，dn}≥n，n階無向簡單圖G中最大度≤n1 )試畫一個具有5個頂點的自補圖2)是否存在具有6個頂點的自補圖，試說明理由。對于n階圖，原圖與其補圖同構，邊數(shù)應相等，均為(n*(n1)/2)/2，即n*(n1)/4且為整 數(shù)，n=4k或n=4k+1，不存在6階自補圖。(n2且為奇數(shù))階無向簡單圖，證明：(n2且為奇數(shù))，奇度點成對出現(xiàn)。只有2個奇度頂點u和v，如果不連通，在u和v在2個連通分支上，每個分支上僅有一個奇度頂點，與握手引理相矛盾。：1))δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=：δ(G)=min{ d(v)| v206。V } ；κ(G)=min{ |V’| |V’是圖G的點割集} ； λ(G)=min{ |E’| |E’是圖G的邊割集} ？n為奇數(shù)時：：橋的端點是u和v，并且圖各頂點度均為偶數(shù)； 橋為割邊，刪除橋，圖不再連通，u和v應該在2各不同的連通分支上；且u和v度數(shù)變?yōu)槠鏀?shù)；由于其他頂點度數(shù)均為偶數(shù)，則u和v所在的連通分支上只有一個奇度頂點，與握手引理矛盾。：，顯然不是哈密爾頓圖；否則n≥3，則橋的兩個端點u和v至少有一個不是懸掛頂點（容易證明懸掛頂點不是割點）；設u不是懸掛點，則u是割點，存在割點顯然不是哈密爾頓圖。，3個3度頂點，其余頂點全為樹葉，問T有幾片樹葉？X+2*4+3*3=2*（2+3+x1）x=9 ：最大度Δ（T）≥k的樹T至少有k片樹葉。設有n個頂點，其中x片樹葉2*（n1）≥1*K+（nx1）*2+x*1x≥k ，9條邊，+4=3+1n=9。, 有n個頂點、m條邊、f個面，G有k個連通分支。試利用歐拉公式證明:：nm+f=k+1.