【正文】 群，定義R＝{|a、b∈G且a1*b∈H}，則R是G中的－一個(gè)等價(jià)關(guān)系，且[a]R＝aH。證明對(duì)于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－若∈R，則a1*b∈H。因?yàn)镠是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－若∈R，∈R，則a1*b∈H，b1*c∈H。因?yàn)镠是G的子群，所以(a1*b)*(b1*c)＝a－－－－－1*c∈H，故∈R。綜上可得，R是G中的一個(gè)等價(jià)關(guān)系。對(duì)于任意的b∈[a]R，有∈R，a1*b∈H，則存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－[a]R205。aH。對(duì)任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH205。[a]R。所以，[a]R－＝aH。第四篇：離散數(shù)學(xué)課后習(xí)題答案第一章部分課后習(xí)題參考答案 設(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是無(wú)理數(shù)。并且，如果3是無(wú)理數(shù)，則2也是無(wú)理數(shù)。另外，只有6能被2整除，6才能被4整除。”答：p: p是無(wú)理數(shù)q: 3是無(wú)理數(shù)0r: 2是無(wú)理數(shù)s: 6能被2整除t: 6能被4整除0命題符號(hào)化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。19．用真值表判斷下列公式的類(lèi)型：（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所以公式類(lèi)型為永真式（5）公式類(lèi)型為可滿足式（方法如上例）（6）公式類(lèi)型為永真式（方法如上例）第二章部分課后習(xí)題參考答案，對(duì)不是重言式的可滿足式，(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所以公式類(lèi)型為永真式(3)Pqrp∨qp∧r（p∨q）→(p∧r)0000000000000 000 10000 101000 1所以公式類(lèi)型為可滿足式：(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)第三章部分課后習(xí)題參考答案：(2)前提：p174。q,216。(q217。r),r 結(jié)論：216。p(4)前提：q174。p,q171。s,s171。t,t217。r 結(jié)論：p217。q證明：（2）①216。(q217。r)前提引入 ②216。q218。216。r ①置換 ③q174。216。r ②蘊(yùn)含等值式 ④r 前提引入 ⑤216。q ③④拒取式 ⑥p174。q 前提引入 ⑦￢p（3）⑤⑥拒取式證明（4）：①t217。r 前提引入 ②t ①化簡(jiǎn)律 ③q171。s 前提引入 ④s171。t 前提引入⑤q171。t ③④等價(jià)三段論 ⑥（q174。t）217。(t174。q)⑤ 置換 ⑦（q174。t）⑥化簡(jiǎn) ⑧q ②⑥ 假言推理 ⑨q174。p 前提引入 ⑩p ⑧⑨假言推理(11)p217。q ⑧⑩合取15在自然推理系統(tǒng)P中用附加前提法證明下面各推理：4(1)前提：p174。(q174。r),s174。p,q 結(jié)論：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 結(jié)論：216。p 證明：①p 結(jié)論的否定引入 ②p174。﹁q 前提引入 ③﹁q ①②假言推理 ④￢r218。q 前提引入 ⑤￢r ④化簡(jiǎn)律 ⑥r(nóng)217。￢s 前提引入 ⑦r ⑥化簡(jiǎn)律 ⑧r217。﹁r ⑤⑦ 合取由于最后一步r217。﹁r 是矛盾式,所以推理正確.第五篇：《離散數(shù)學(xué)》圖論部分習(xí)題《離散數(shù)學(xué)》圖論部分習(xí)題，6個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度數(shù)均小于3，問(wèn)G至少有幾個(gè)頂點(diǎn)？并畫(huà)出滿足條件的一個(gè)圖形.（243*6）/2 +6=9 ，其度序列為6；7階無(wú)向簡(jiǎn)單圖G中最大度≤6 、d…、：不存在以dd…、{d1，d2，…，dn}≥n，n階無(wú)向簡(jiǎn)單圖G中最大度≤n1 )試畫(huà)一個(gè)具有5個(gè)頂點(diǎn)的自補(bǔ)圖2)是否存在具有6個(gè)頂點(diǎn)的自補(bǔ)圖，試說(shuō)明理由。對(duì)于n階圖，原圖與其補(bǔ)圖同構(gòu)，邊數(shù)應(yīng)相等，均為(n*(n1)/2)/2，即n*(n1)/4且為整 數(shù)，n=4k或n=4k+1，不存在6階自補(bǔ)圖。(n2且為奇數(shù))階無(wú)向簡(jiǎn)單圖，證明：(n2且為奇數(shù))，奇度點(diǎn)成對(duì)出現(xiàn)。只有2個(gè)奇度頂點(diǎn)u和v，如果不連通，在u和v在2個(gè)連通分支上，每個(gè)分支上僅有一個(gè)奇度頂點(diǎn)，與握手引理相矛盾。：1))δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=：δ(G)=min{ d(v)| v206。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)楦钸?，刪除橋，圖不再連通，u和v應(yīng)該在2各不同的連通分支上；且u和v度數(shù)變?yōu)槠鏀?shù)；由于其他頂點(diǎn)度數(shù)均為偶數(shù)，則u和v所在的連通分支上只有一個(gè)奇度頂點(diǎn)，與握手引理矛盾。：，顯然不是哈密爾頓圖；否則n≥3，則橋的兩個(gè)端點(diǎn)u和v至少有一個(gè)不是懸掛頂點(diǎn)（容易證明懸掛頂點(diǎn)不是割點(diǎn)）；設(shè)u不是懸掛點(diǎn)，則u是割點(diǎn)，存在割點(diǎn)顯然不是哈密爾頓圖。，3個(gè)3度頂點(diǎn)，其余頂點(diǎn)全為樹(shù)葉，問(wèn)T有幾片樹(shù)葉？X+2*4+3*3=2*（2+3+x1）x=9 ：最大度Δ（T）≥k的樹(shù)T至少有k片樹(shù)葉。設(shè)有n個(gè)頂點(diǎn)，其中x片樹(shù)葉2*（n1）≥1*K+（nx1）*2+x*1x≥k ，9條邊，+4=3+1n=9。, 有n個(gè)頂點(diǎn)、m條邊、f個(gè)面，G有k個(gè)連通分支。試?yán)脷W拉公式證明:：nm+f=k+1.