1、離散數(shù)學(xué)作業(yè)參考答案一、選擇或填空：1 B C D 2 A， F B，F(xiàn) C，F(xiàn) D，T3 2n-2 4 IA5 單位元，1 6 A 7 A D8 (1) PQ (2) PQ 9 偶數(shù) 10 自反性、對稱性和傳遞性11 1，單位元，0 12 所有邊一次且恰好一次13 B C D E F14 B D 15 5,10 16 D 17 B 18 D19 A 20（1）RR= 1，1，1，3，2，2，2，4（2）-11，2，2，1，3，2，4，321 m=n-1 22 9,3 23 A 24 D25 (1)26 (2) 27 (3)28 (1)29 (1)30 (3)31 (2)32 (3)33 (2

2、)34 (4)35 (2)36 (1)二、求下列各公式的主析取范式和主合取范式解：1 PQ （主合取范式）（P(QQ)）（(PP)Q）(PQ)（PQ）（PQ）（PQ）(PQ)（PQ）（PQ）（主析取范式）2Q( PR)QPR（主合取范式）（Q( PR)）（PQR）（PQR）（PQR）（PQR）（PQR） （PQR）（PQR）（原公式否定的主合取范式）Q( PR)（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（主析取范式）3 PQPQ（主合取范式）(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)（主析取范式）4(PQ)(RP)(PQ)(RP

3、)(PQ)(RP)（析取范式）(PQ(RR)(P(QQ) R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主析取范式）(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）5PQ（主析取范式）(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)（主合取范式）6 Q(PR)QPR（主合取范式）(Q(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR）（原公式否定的主合取范式）Q(PR)(PQR)(PQ

4、R)(PQR)(PQR)（PQR)(PQR)(PQR）（主析取范式）7 (PQ)(PR)(PQ)(PR) (合取范式)(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)(PQ)(PR)(PQ)(PR)P(QR)(合取范式)(P(QQ)(RR)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)三、證明1PQ， PR, QS = RS證明：（1） R 附加前提（2） PR 前提（3） P （1），（2）（4） PQ 前提 （5） Q （3），（4）

5、（6） QS 前提（7） S （5），（6）（8） RS CP，（1），（8）2A(CB)，BA，DC = AD證明：（1） A 附加前提（2） A(CB) 前提（3） CB （1），（2）（4） BA 前提（5） B （1），（4）（6） C （3），（5）（7） DC 前提（8） D （6），（7）（9） AD CP，（1），（8）3PQ，QR，R，SP=S證明：（1） R 前提（2）QR 前提（3）Q （1），（2）（4）PQ 前提（5）P （3），（4）（6）SP 前提（7）S （5），（6）4BD，(EF)D，E=B證明：（1） B 附加前提（2）BD 前提 （3） D （1），（2

6、）（4）(EF)D 前提（5）(EF) （3），（4）（6）EF （5）（7） E （6）（8） E 前提（9） EE （7），（8）5A(BC)，C(DE)，F(xiàn)(DE),A=BF證明： （1） A 前提（2） A(BC) 前提（3）BC （1），（2）（4）B 附加前提（5）C （3），（4）（6）C(DE) 前提（7）DE （5），（6）(8)F(DE) 前提(9)F （7），（8）(10)BF CP，（4），（9） 四、設(shè)，是三個集合，證明1(AB)(AC)=A(BC)證明： (A-B)(A-C)=(A)(A) =A()=A= A-(BC)2AB=AC，B=C，則C=B證明：B=B(A)

7、=(BA)(B) =(CA)(C)=C(A)=C3A(BC)(AB)(AC)證明： (AB)(AC)= (AB) =(AB) （）=(AB)(AB)= AB=A（B）=A（B-C）4A(BC)(AB)C 證明： A(BC)= A=A()=(A)= (A-B)=(A-B)-C5(AB)(AC)=A(BC) 證明：（A-B）(AC)=(A)(A)=(AA)()= A=A(BC)6、A(BC)，C(DE)，F(xiàn)(DE),A BF.證明： (1) A 前提(2) A(BC) 前提 (3) BC （1），（2）(4) B 附加前提 (5) C （3），（4） (6) C(DE) 前提 (7) DE （5）

8、，（6） (8) F(DE) 前提 (9) F （7），（8） (10) BF CP 7、BD，(EF)D，E B.證明：(1) B 附加前提(2) BD 前提 (3) D （1），（2）(4) (EF)D 前提(5) (EF) （3），（4）(6) EF （5）(7) E （6）(8) E 前提(9) EE （7），（8）8 、A(CB)，BA，DC AD.證明：（1） A 附加前提(2) A(CB) 前提 (3) CB （1），（2） (4) BA 前提 (5) B （1），（4） (6) C （3），（5） (7) DC 前提 (8) D （6），（7） (9) AD CP，（1），（8

9、）9、PQ，QR，RS P.證明、(1) P 附加前提 （2） PQ 前提 （3） Q （1），（2） （4） QR 前提 (5) R （3），（4） (6 ) RS 前提 （7） R （6） （8） RR （5），（7）五、證明1設(shè)e和0是關(guān)于A上二元運算*的單位元和零元，如果|A|1，則e0。證明：用反證法證明。假設(shè)e=0。對A的任一元素a，因為e和0是A上關(guān)于二元運算*的單位元和零元，則a=a*e=a*0=0。即A的所有元素都等于0,這與已知條件|A|1矛盾。從而假設(shè)錯誤。2任一圖中度數(shù)為奇數(shù)的結(jié)點是偶數(shù)個。證明：設(shè)G=V,E是任一圖。設(shè)|V|=n。由歐拉握手定理可得 deg(v)=2|

10、E|可得，圖中所有結(jié)點度數(shù)之和是偶數(shù)。顯然所有偶數(shù)度結(jié)點的度數(shù)之和仍為偶數(shù)，從而所有奇數(shù)度結(jié)點的度數(shù)之和也是偶數(shù)。因此，圖中度數(shù)為奇數(shù)的結(jié)點一定為偶數(shù)個。3設(shè)群G,*除單位元外每個元素的階均為2，則G,*是交換群。證明：對任一aG，由已知可得a*a=e，即a-1=a。對任一a,bG，因為a*b=(a*b)-1=b-1*a-1=b*a，所以運算*滿足交換律。從而G,*是交換群。4在一個連通簡單無向平面圖G=V,E,F中若|V|3，則 |E|3|V|6。證明：因為|V|3，且G=V,E,F是一個連通簡單無向平面圖，所以對任一fF，deg(f)3。由公式deg(f)=2|E|可得，2|E|3|F|。

11、再由歐拉公式|V|-|E|+|F|=2可得|V|-|E|+|E|2。所以|E|3|V|6。5單位元有惟一逆元。證明：設(shè)是一個群，e是關(guān)于運算的單位元。若e1,e2都是e的逆元，即e1*e=e且e2*e=e。因為e是關(guān)于運算的單位元，所以e1=e1*e=e=e2*e=e2。即單位元有惟一逆元。6設(shè)是一個群，則對于a,bG，必有唯一的xG，使得ax=b。證明：因為a-1*bG，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以對于a,bG，必有x=a-*bG，使得ax=b。若x1,x2都滿足要求。即ax1=b且ax2=b。故ax1=ax2。由于*滿足消去律，故x1=x2。從而對于a,bG，

12、必有唯一的xG，使得ax=b。7代數(shù)系統(tǒng)是一個群，則G除單位元以外無其它等冪元。證明：設(shè)e是該群的單位元。若a是的等冪元，即a*a=a。因為a*e=a，所以a*a=a*e。由于運算*滿足消去律，所以a=e。即G除單位元以外無其它等冪元。8若連通簡單無向平面圖G有n個結(jié)點，m條邊，p個面，且每個面至少由k(k3)條邊圍成，則 mk(2)(2)。證明：設(shè)連通簡單無向平面圖G=V,E,F，則|V|=n,|E|=m,|F|=p。由已知對任一fF,deg(f)k。由公式deg(f)=2|E|可得，2|E|k|F|。再由歐拉公式|V|-|E|+|F|=2可得|V|-|E|+|E|2。即k(n-2)(k-2

13、)m。所以mk(2)(2)。9證明：證明在元素不少于兩個的群中不存在零元。證明：（用反證法證明）設(shè)在群中存在零元。對aG, 由零元的定義有 a*=。因為是群，所以關(guān)于*消去律成立。故a=e。即G中元素都等于單位元，這與|G|2矛盾。10素數(shù)階循環(huán)群的每個非單位元都是生成元。證明：設(shè)是p階循環(huán)群，p是素數(shù)。對G中任一非單位元a。設(shè)a的階為k,則k1。由拉格朗日定理，k是p的正整因子。因為p是素數(shù)，故k=p。即a的階就是p，即群G的階。故a是G的生成元。11設(shè)G=V,E是一個連通且|V|=|E|+1的圖，則G中有一個度為1的結(jié)點。證明：（用反證法證明）設(shè)|V|=n，則|E|=n-1。由歐拉握手定理

14、可得 deg(v)=2|E|=2n-2。因為G連通，所以vV，deg(v)1。假設(shè)G中沒有1片樹葉，則deg(v)2n2n-2。得出矛盾。12給定連通簡單無向平面圖G=，且|V|=6, |E|=12, 則對于任意fF, deg(f)=3。證明：因為|V|=63，且G=V,E,F是一個連通簡單無向平面圖，所以對任一fF，deg(f)3。由歐拉公式|V|-|E|+|F|=2可得|F|=8。再由公式deg(f)=2|E|，deg(f)=24。因為對任一fF，deg(f)3，故要使上述等式成立， 對任一fF，deg(f)=3。13證明在一個群中單位元是惟一的。證明：設(shè)e1,e2都是群G,*的單位元,

15、則e1=e1*e2=e2。 所以單位元是惟一的。14在一個群G,*中，若G中的元素a的階是k，即 | a |=k，則a-1的階也是k。證明：因為| a |=k，所以ak=e。即（a-1）k=(ak)-1=e。從而a-1的階是有限的，且|a-1|k。同理可證，a的階小于等于|a-1|。故a-1的階也是k。15若n個結(jié)點的連通圖中恰有n-1 條邊，則圖中至少有一個結(jié)點度數(shù)為1。證明：（用反證法證明）設(shè)G=V,E有n-1條邊且|V|=n-1。由歐拉握手定理可得 deg(v)=2|E|=2n-2。因為G是連通圖，所以G中任一結(jié)點的度數(shù)都大于等于1。假設(shè)G中不存在度數(shù)為1 的結(jié)點，則G中任一結(jié)點的度數(shù)都

16、大于等于2.故deg(v)2n2n-2。得出矛盾。16、設(shè)e和0是關(guān)于A上二元運算*的單位元和零元，如果|A|1，則e0.證明：（用反證法證明）假設(shè)e=0.對A的任一元素a，因為e和0是A上關(guān)于二元運算*的單位元和零元，則a=a*e=a*0=0. 即A的所有元素都等于0,這與已知條件|A|1矛盾.從而假設(shè)錯誤. 即e0.17、設(shè)T=是一棵樹，若|V|1，則T中至少存在兩片樹葉.證明：（用反證法證明）設(shè)|V|=n.因為T=V,E是一棵樹，所以|E|=n-1.由歐拉握手定理可得 deg(v)=2|E|=2n-2.假設(shè)T中最多只有1片樹葉，則deg(v) 2(n-1)+12n-2.得出矛盾。18、若n階連通圖中恰有n-1 條邊，則圖中至少有一個頂點度數(shù)為1.證明：（用反證法證明）設(shè)G=有n-1條邊且|V|=n.由歐拉握手定理可得 deg(v)=2|E|=2n-2.因為G是連通圖，所以G中任一頂點的度數(shù)都大于等于1.假設(shè)G中不存在度數(shù)為1 的頂點，則G中任一頂點的度數(shù)都大于等于2. 故deg(v) 2n2n-2.得出矛盾. 19、證明對于連通無向簡單平面圖，當邊數(shù)e30時，必存在度數(shù)4的頂點.證明：若頂點個數(shù)小于等于3時，結(jié)論顯然成立.當頂點多于3 個時，用反證法證明.