【正文】 Ai162。為Ai或Ai)的集合稱為由AA2和i=13A3產(chǎn)生的小項(xiàng)。試證由AA2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個(gè)劃分。證明小項(xiàng)共8個(gè)，設(shè)有r個(gè)非空小項(xiàng)ss…、sr(r≤8)。對(duì)任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個(gè)成立，取Ai162。為包含元素a的Ai或Ai，則a∈IAi162。，i=13即有a∈Usi，于是U205。Usi。又顯然有Usi205。U，所以U＝Usi。i=1i=1i=1i=1rrrr任取兩個(gè)非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個(gè)Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝198。綜上可知，{s1，s2，…，sr}是U的一個(gè)劃分。五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的219。R*R205。R。證明(5)若R是傳遞的，則∈R*R222。$z(xRz∧zSy)222。xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R205。R。反之，若R*R205。R，則對(duì)任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)。證明對(duì)G的邊數(shù)m作歸納法。當(dāng)m＝0時(shí)，由于G是連通圖，所以G為平凡圖，此時(shí)n＝1，r＝1，結(jié)論自然成立。假設(shè)對(duì)邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G162。，并設(shè)其結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n162。、m162。和r162。對(duì)e分為下列情況來討論：若e為割邊，則G162。有兩個(gè)連通分支G1和G2。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n162。＝n，m1＋m2＝m162。＝m－1，r1＋r2＝r162。＋1＝r＋1。由歸納假設(shè)有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。若e不為割邊，則n162。＝n，m162。＝m－1，r162。＝r－1，由歸納假設(shè)有n162。－m162。＋r162。＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。由數(shù)學(xué)歸納法知，結(jié)論成立。七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則：(1)fog是A到C的函數(shù)；(2)對(duì)任意的x∈A，有fog(x)＝f(g(x))。證明(1)對(duì)任意的x∈A，因?yàn)間：A→B是函數(shù)，則存在y∈B使∈g。對(duì)于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復(fù)合關(guān)系的定義，由∈g和∈f得∈g*f，即∈fog。所以Dfog＝A。對(duì)任意的x∈A，若存在yy2∈C，使得、∈fog＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因?yàn)間：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個(gè)元素對(duì)應(yīng)C中惟一的元素。綜上可知，fog是A到C的函數(shù)。(2)對(duì)任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝fog。又因fog是A到C的函數(shù)，則可寫為fog(x)＝f(g(x))。八、（15分）設(shè)是的子群，定義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是無理數(shù)。并且，如果3是無理數(shù)，則2也是無理數(shù)。另外，只有6能被2整除，6才能被4整除?！贝穑簆: p是無理數(shù)q: 3是無理數(shù)0r: 2是無理數(shù)s: 6能被2整除t: 6能被4整除0命題符號(hào)化為： 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）公式類型為永真式（方法如上例）第二章部分課后習(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所以公式類型為永真式(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,