【正文】 , 有n個(gè)頂點(diǎn)、m條邊、f個(gè)面，G有k個(gè)連通分支。，3個(gè)3度頂點(diǎn)，其余頂點(diǎn)全為樹葉，問T有幾片樹葉？X+2*4+3*3=2*（2+3+x1）x=9 ：最大度Δ（T）≥k的樹T至少有k片樹葉。V } ；κ(G)=min{ |V’| |V’是圖G的點(diǎn)割集} ； λ(G)=min{ |E’| |E’是圖G的邊割集} ？n為奇數(shù)時(shí)：：橋的端點(diǎn)是u和v，并且圖各頂點(diǎn)度均為偶數(shù)； 橋?yàn)楦钸叄瑒h除橋，圖不再連通，u和v應(yīng)該在2各不同的連通分支上；且u和v度數(shù)變?yōu)槠鏀?shù)；由于其他頂點(diǎn)度數(shù)均為偶數(shù)，則u和v所在的連通分支上只有一個(gè)奇度頂點(diǎn)，與握手引理矛盾。只有2個(gè)奇度頂點(diǎn)u和v，如果不連通，在u和v在2個(gè)連通分支上，每個(gè)分支上僅有一個(gè)奇度頂點(diǎn)，與握手引理相矛盾。對(duì)于n階圖，原圖與其補(bǔ)圖同構(gòu)，邊數(shù)應(yīng)相等，均為(n*(n1)/2)/2，即n*(n1)/4且為整 數(shù)，n=4k或n=4k+1，不存在6階自補(bǔ)圖。﹁r ⑤⑦ 合取由于最后一步r217。q 前提引入 ⑤￢r ④化簡(jiǎn)律 ⑥r(nóng)217。p 證明：①p 結(jié)論的否定引入 ②p174。216。r218。216。r)前提引入 ⑤q174。p 前提引入 ③p ①②假言推理 ④p174。p,q 結(jié)論：s174。(q174。p 前提引入 ⑩p ⑧⑨假言推理(11)p217。q)⑤ 置換 ⑦（q174。t）217。t 前提引入⑤q171。r 前提引入 ②t ①化簡(jiǎn)律 ③q171。q ③④拒取式 ⑥p174。216。216。r)前提引入 ②216。q證明：（2）①216。t,t217。p,q171。r),r 結(jié)論：216。q,216。1 219。r))219。(p218。216。((216。q218。p218。q218。r))218。q218。p217。219。q218。(q217。216。q218。(q217。r219。q)217。(p217。q217。p218。216。q217?！?1)(2)主合取范式為：216。q)219。(p218。216。1217。q218。q218。p))217。(216。(216。q218。q)218。p217。q218。q)218。219。p)219。p→q)→(216。m3219。m0218。(p217。216。q)218。p217。216。q)218。p)218。q217。p)218。(216。216。p)(216。(216。216。p)(216。(216。(p218。219。216。q218。(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(216。p→q)→(216。(p∨q)∧216。1∧(p∨q)∧216。p)∧(216。p)∧(p∨q)∧(216。p∧q)219。p∧q))∧(216。p∧q)219。p→(q∧r)（4）(p∧216。216。p∨q)∧(216。(p∧q)證明（2）(p→q)∧(p→r)219。p∧q)219。(p→(q∧r))(4)(p∧216。p∨p∨q∨r219。p∨r)219。(216。p)0000000000所以公式類型為永真式（5）公式類型為可滿足式（方法如上例）（6）公式類型為永真式（方法如上例）第二章部分課后習(xí)題參考答案，對(duì)不是重言式的可滿足式，(1)216。p(p→q)→(216。p216。q)（6）((p→q)∧(q→r))→(p→r)答：（4）pqp→q216。(216。q→216?！贝穑簆: p是無理數(shù)q: 3是無理數(shù)0r: 2是無理數(shù)s: 6能被2整除t: 6能被4整除0命題符號(hào)化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。并且，如果3是無理數(shù)，則2也是無理數(shù)。0→0219。q)219。0(4)（216。q∧r）?(p∧q∧﹁r)219。0.（3）（216。（0?1）∧(1∨1)219。 0∨(0∧1)219。H(a)5合取I(a)8假言推論第四篇：離散數(shù)學(xué)課后習(xí)題答案第一章部分課后習(xí)題參考答案 設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。H(a)174。H(x)174。G(x))前提引入F(a)174。H(x)174。設(shè)F(x):x是科學(xué)工作者，G(x)：x是刻苦鉆研的，H(x):x是聰明的，I(x):x在事業(yè)中獲得成功前提 x(F(x)174。F(x)8UG ，構(gòu)造下列推理的證明（個(gè)體域?yàn)槿祟惣希好總€(gè)科學(xué)工作者都是刻苦鉆研的，每個(gè)刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。G(c)UI216。G(x))前提引入F(c)174。H(c)UI G(c)4析取三段論x(F(x)174。H(c)UI x(G(x)218。xF(x)證明：1 $216。H(x)),$216。（個(gè)體域?yàn)槿祟惣希┰O(shè)F(x):x喜歡步行，G(x)：x喜歡騎自行車，H(x):x喜歡乘汽車 前提 x(F(x)174。每個(gè)人或者喜歡騎自行車或者喜歡乘汽車。216。(216。216。(216。216。(216。H(y)UI 216。H(x)), 前提引入4(F(y)218。H(y)UI x((F(x)218。H(x))前提引入I(y)174。G(x)))證明：1 x(I(x)174。(216。216。G(x))174。H(x))結(jié)論 $x(G(x)217。（1）設(shè)F(x):x是有理數(shù)，G(x)：x實(shí)數(shù)，H(x):x是整數(shù)前提 x(F(x)174。虛數(shù)不是實(shí)數(shù)。有的有理數(shù)是整數(shù)。G(a)前提引入216。G(x))前提引入F(a)174。G(a)，結(jié)論 216。G(6)1UI F(6)前提引入 G(6)3假言推理(2)設(shè)F(x):x是大學(xué)生，G(x)：x是勤奮的，a 王曉山 前提 x(F(x)174。G(x)),F(6)結(jié)論 G(6)證明：1 x(F(x)174。王曉山不勤奮，所以王曉山不是大學(xué)生。所以6能被2整除。F(x))8UG ，構(gòu)造下面推理的證明：(1)偶數(shù)都能被2整除。F(y)7假言三段論 9 x(G(x)174。H(y)5UI 8 G(y)174。F(y)4UI 6 x(G(x)174。F(x))H(y)174。H(x)174。216。H(x))置換原則 3 x(216。H(x))前提引入 2 x216。F(x))證明：1 216。H(x))結(jié)論 x(G(x)174。$x(F(x)217。設(shè)F(x):x是烏鴉，G(x)：x是北京鴨，H(x):x是白色的。G(c)UIG(c)5析取三段論$xG(x)EG ，構(gòu)造下面推理的證明：沒有白色的烏鴉，北京鴨都是白色的。F(c)2EIx(F(x)218。xF(x)附加前提引入$x216。G(x))前提引入F(y)174。xF(x)174。xG(x)（2）前提：x(F(x)218。G(x))EI，構(gòu)造下列推理的證明（可以使用附加前提證明法）：（1）前提：x(F(x)174。xG(x)換名規(guī)則$yx(F(x)174。G(x))證明：1$xF(x)174。F(x))UG，構(gòu)造下列推理的證明：前提：$xF(x)174。F(y)5假言三段論x(H(x)174。F(y)3置換H(y)174。G(y)2UI G(y)174。216。G(x))前提引入x(H(x)174。證明：1 x(F(x)174。①UI 前提引入 ③UI ②⑤假言推理 前提引入 ⑥UI ⑤⑦拒取式 ⑧UG 并且說，由附加前提證明法可知，推理正確，請(qǐng)指出以上證明的錯(cuò)誤。F(y)⑨x216。216。216。G(x))④H(y)174。F(x))。G(x))結(jié)論：x(H(x)174。216。G(x))為假。顯然在以上解釋下xF(x)174。G(x))。xG(x)185。xG(x)為真，而使得x(F(x)174。R(y)UI xR(x)前提引入R(y)5UI 216。G(y)218。216。G(y)UI x(216。G(c)4UI6F(c)5析取三段論$xF(x)6EG(4)證明：1 x(F(x)218。F(c)2UIx(F(x)218。$xF(x)前提引入x216。R(c)6合取$x(F(x)217。R(c))UI G(a)217。I(a))前提引入 F(c)EI F(c)174。R(x)))x(G(a)217。x(F(x)174。217。G(a))174。H(x)),$x216。R(c)UI F(c)218。R(y)2假言推理F(c)EI(F(c)218。R(y))前提引入y((F(y)218。y((F(y)218。216。G(x)),x(216。G(x)),216。R(x))),$xF(x)結(jié)論：$x(F(x)217。R(y)),$xF(x)結(jié)論：$xR(x)（2）前提：x(F(x)174。y((F(y)218。G(y)滿足要求（4）這里，使F(a)為真的a不一定使G(a)為真，同樣的，使G(b)為真的b不一定使F(b)為真（5）這里，c為個(gè)體常項(xiàng)，不能對(duì)F(c)174。$yG(y)也應(yīng)該先化成前束范式才能消去量詞，其前束范式為x$y(F(x)174。G(x))，因?yàn)榱吭~轄域(F(y)174。$xG(x)219。G(x))①UG規(guī)則解：（1）對(duì)F(x)174。G(x))①EG規(guī)則（5）①