《离散数学》作业参考答案

离散数学作业参考答案一、选择或填空：1 B C D 2 A， F B，F C，F D，T3 2n-2 4 IA5 单位元，1 6 A 7 A D8 (1) PQ (2) PQ 9 偶数 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)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)(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)(PQR)(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）（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）（4）(EF)D 前提（5）(EF) （3），（4）（6）EF （5）（7） E （6）（8） E 前提（9） EE （7），（8）5A(BC)，C(DE)，F(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） 四、设，是三个集合，证明1(AB)(AC)=A(BC)证明： (A-B)(A-C)=(A)(A) =A()=A= A-(BC)2AB=AC，B=C，则C=B证明：B=B(A)=(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(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 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、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设e和0是关于A上二元运算*的单位元和零元，如果|A|1，则e0。证明：用反证法证明。假设e=0。对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元，则a=a*e=a*0=0。即A的所有元素都等于0,这与已知条件|A|1矛盾。从而假设错误。2任一图中度数为奇数的结点是偶数个。证明：设G=V,E是任一图。设|V|=n。由欧拉握手定理可得 deg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。3设群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|。再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+|E|2。所以|E|3|V|6。5单位元有惟一逆元。证明：设是一个群，e是关于运算的单位元。若e1,e2都是e的逆元，即e1*e=e且e2*e=e。因为e是关于运算的单位元，所以e1=e1*e=e=e2*e=e2。即单位元有惟一逆元。6设是一个群，则对于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，必有唯一的xG，使得ax=b。7代数系统是一个群，则G除单位元以外无其它等幂元。证明：设e是该群的单位元。若a是的等幂元，即a*a=a。因为a*e=a，所以a*a=a*e。由于运算*满足消去律，所以a=e。即G除单位元以外无其它等幂元。8若连通简单无向平面图G有n个结点，m条边，p个面，且每个面至少由k(k3)条边围成，则 mk(2)(2)。证明：设连通简单无向平面图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)m。所以mk(2)(2)。9证明：证明在元素不少于两个的群中不存在零元。证明：（用反证法证明）设在群中存在零元。对aG, 由零元的定义有 a*=。因为是群，所以关于*消去律成立。故a=e。即G中元素都等于单位元，这与|G|2矛盾。10素数阶循环群的每个非单位元都是生成元。证明：设是p阶循环群，p是素数。对G中任一非单位元a。设a的阶为k,则k1。由拉格朗日定理，k是p的正整因子。因为p是素数，故k=p。即a的阶就是p，即群G的阶。故a是G的生成元。11设G=V,E是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。证明：（用反证法证明）设|V|=n，则|E|=n-1。由欧拉握手定理可得 deg(v)=2|E|=2n-2。因为G连通，所以vV，deg(v)1。假设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证明在一个群中单位元是惟一的。证明：设e1,e2都是群G,*的单位元, 则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个结点的连通图中恰有n-1 条边，则图中至少有一个结点度数为1。证明：（用反证法证明）设G=V,E有n-1条边且|V|=n-1。由欧拉握手定理可得 deg(v)=2|E|=2n-2。因为G是连通图，所以G中任一结点的度数都大于等于1。假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故deg(v)2n2n-2。得出矛盾。16、设e和0是关于A上二元运算*的单位元和零元，如果|A|1，则e0.证明：（用反证法证明）假设e=0.对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元，则a=a*e=a*0=0. 即A的所有元素都等于0,这与已知条件|A|1矛盾.从而假设错误. 即e0.17、设T=是一棵树，若|V|1，则T中至少存在两片树叶.证明：（用反证法证明）设|V|=n.因为T=V,E是一棵树，所以|E|=n-1.由欧拉握手定理可得 deg(v)=2|E|=2n-2.假设T中最多只有1片树叶，则deg(v) 2(n-1)+12n-2.得出矛盾。18、若n阶连通图中恰有n-1 条边，则图中至少有一个顶点度数为1.证明：（用反证法证明）设G=有n-1条边且|V|=n.由欧拉握手定理可得 deg(v)=2|E|=2n-2.因为G是连通图，所以G中任一顶点的度数都大于等于1.假设G中不存在度数为1 的顶点，则G中任一顶点的度数都大于等于2. 故deg(v) 2n2n-2.得出矛盾. 19、证明对于连通无向简单平面图，当边数e30时，必存在度数4的顶点.证明：若顶点个数小于等于3时，结论显然成立.当顶点多于3 个时，用反证法证明.