一、选择或填空

1．下列公式中哪些是永真式？(        )

A.(┐PQ)→(Q→R)         B.P→(Q→Q)         C.(PQ)→P      D.P→(PQ)

2．设全体域D是正整数集合，确定下列命题的真值：

A.  x y (xy=y)　　(　　)　       　B.  x y(x+y=y)　　(　　)

C.  x y(x+y=x) 　 (　　)　　       D.  x y(y=2x)　　 (　　)

3．有n个结点的树，其结点度数之和是(　　　　)。

4．举出集合A上的既是等价关系又是偏序关系的一个例子。(　　　　)

5．群的等幂元是(　　)，有(　　　)个。

6．下面给出的集合中，哪一个不是前缀码(    )。

A. {a，ab，110，a1b11}             B. {01，001，000，1}

C. {1，2，00，01，0210}            D. {12，11，101，002，0011}

7．下列哪些公式为永真蕴含式？(　　　)

A.Q=>Q→P      B.Q=>P→Q C.P=>P→Q     D.P(PQ)=>P  

8．设P：我生病，Q：我去学校，则下列命题可符号化为(    )。

（1）若我生病，则我不去学校       (2)　当且仅当我生病时，我才不去学校

9．任一有向图中，度数为奇数的结点有(　　　)个。

10．集合A上的等价关系的三个性质是什么？(        )

11．群＜A,*＞的等幂元有(　　　)个，是(　　　)，零元有(　　　)个。

12．一个图的欧拉回路是一条通过图中(      )的回路。

13．设有下列公式，请问哪几个是永真蕴涵式?(         )

A.P=>PQ                   B. PQ=>P C. PQ=>PQ  

D.P(P→Q)=>Q E. (P→Q)=>P F. P(PQ)=>P

14．判断下列命题哪几个为正确？(　　)　

A. {Ф}∈{Ф，{{Ф}}}      B. {Ф}{Ф，{{Ф}}}        C. Ф∈{{Ф}}

D. Ф{Ф}                E. {a,b}∈{a,b,{a},{b}}

15．设a是10阶群的生成元， 则a4是(    )阶元素，a3是(    )阶元素。

16．设G是一个哈密尔顿图，则G一定是(    )。

A. 欧拉图         B.  树      　C. 平面图        D.　连通图  

17．设G是一棵树，则G 的生成树有(     )棵。

A. 0　　          B. 1　       　C. 2　        　D. 不能确定

18．设无向图G有16条边且每个顶点的度数都是2，则图G有(   )个顶点。

A. 10           B. 4          C. 8            D. 16

19．Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：

A. AB，BC=> AC      B. AB，BC=> A∈B    C. A∈B，B∈C=> A∈C

20．设S={１，２，３，４}，Ａ上的关系Ｒ＝｛〈1，2〉，〈2，1〉，〈2，3〉，〈3，4〉｝，求(1)RR  (2)  R-1 。

21．一棵无向树的顶点数n与边数m关系是(　　　　)。

22．设A={3，6，9}，A上的二元运算*定义为：a*b=min{a，b}，则在独异点中，单位元是(    )，零元是(     )。

23．设G是有n个结点m条边的连通平面图，且有k个面，则k等于:

   A. m-n+2        B. n-m-2        C. n+m-2         D. m+n+2。

24．设无向图G有1边且每个顶点的度数都是3，则图G有(   )个顶点。

   A.  10          B. 4            C. 8             D. 12

25、A，B，C是三个集合，则下列哪个推理正确?(       )

(1) AB，BC  AC  

(2) AB，BC  AB  

(3) AB，BC  AC

26、判断下列命题哪个正确?(      )

(1) {Ф}{Ф,{{Ф}}}   (2) {Ф}{Ф,{{Ф}} 

(3) Ф{{Ф}}          (4) Ф={Ф}   

27、设T是一棵树，则T是一个(      ).

(1) 欧拉图  (2) 哈密尔顿图  (3) 连通图

28、下列公式中哪个不是蕴涵式?(       )

(1)  PPQ          (2)  PQP   

(3)  PQPQ      (4)  P(P→Q)Q

39、下面给出的集合中，哪一个不是前缀码(       ).

(1) {a，ab，110，a1b11}     (2) {01，001，000，1}

(3) {1，2，00，01，0210}    (4) {12，11，101，002，0011}

30  6阶有限群的任何子群一定不是(       ).

(1) 2阶　　(2) 3 阶    (3) 4 阶  　(4) 6 阶

31、在有n个顶点的连通图中，其边数(      ).

(1) 最多有n-1条　　(2) 至少有n-1 条

(3) 最多有n条  　　(4) 至少有n 条

32、下列哪一种图不一定是树?(       )

(1) 无简单回路的连通图　   　(2) 有n个顶点n-1条边的连通图    

(3) 每对顶点间都有通路的图 　(4) 连通但删去一条边便不连通的图  

33、下面给出的集合中，哪一个是前缀码?(　　　)

(1) {0，10，110，101111}　　　(2) {01，001，000，1}

(3) {b，c，aa，ab，aba}　　  　 (4) {1，11，101，001，0011}

34、有限布尔代数的元素的个数一定等于(      ).

(1)  偶数　(2)  奇数  (3)  4的倍数  　(4)  2的正整数次幂

35、在自然数集N上，下列哪种运算是可结合的?(      )

(1) a*b=a-b　　(2) a*b=max{a,b}　(3) a*b=a+2b　(4) a*b=|a-b|

36、判断下列命题哪个为真?(      )

(1) A-B=B-A  A=B         (2) 空集是任何集合的真子集

(3) 空集只是非空集合的子集     (4) 若A的一个元素属于B，则A=B

二、求下列各公式的主析取范式和主合取范式

1．　PQ　    

2．  Q→( PR)

3．  P→Q　    

4． (P→Q)  (RP) 

5．　PQ  

6 Q→(PR)

7 (P→Q)(P→R)

三、证明

1．PQ， P→R, Q→S => RS

2．A→(CB)，B→A，D→C => A→D

3．P→Q，QR，R，SP=>S

4．BD，(E→F)→D，E=>B

5．A→(B→C)，C→(DE)，F→(DE),A=>B→F

6、A→(B→C)，C→(DE)，F→(DE),A  B→F.

7、BD，(E→F)→D，E  B.

8、A→(CB)，B→A，D→C  A→D.

9、P→Q，QR，RS  P.

四、设Ａ，Ｂ，Ｃ是三个集合，证明

1．(A－B)∪(A－C)=A－(B∩C) 

2．A∩B=A∩C，∩B=∩C，则C=B

3．A∩(B－C)＝(A∩B)－(A∩C) 

4．A－(B∪C)＝(A－B)－C   

5．(A－B)∩(A－C)=A－(B∪C)　 

五、证明

1．设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e0。

2．任一图中度数为奇数的结点是偶数个。

3．设群＜G，＊＞除单位元外每个元素的阶均为2，则＜G，＊＞是交换群。

4．在一个连通简单无向平面图G=〈V，E，F〉中若|V|3，则 |E|3|V－6。

5．单位元有惟一逆元。

6．设是一个群，则对于a,b∈G，必有惟一的x∈G，使得ax=b。

7．设代数系统是一个群，则G除单位元以外无其它等幂元。

8．若连通简单无向平面图G有n个结点，m条边，k个面，且每个面至少由k(k3)条边围成，则  mk(ｎ－2)／(ｋ－2)。

9．证明在元素不少于两个的群中不存在零元。

10．素数阶循环群的每个非单位元都是生成元。

11．设G=〈V，E〉是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。

12．给定无向连通简单平面图G=，且|V|=6, |E|=12, 则对于任意fF, deg(f)=3。

13．证明在一个群中单位元是惟一的。

14．在一个群〈G，*〉中，若G中的元素a的阶是k，即 | a |=k，则a-1的阶也是k。

15．若有n个结点的连通图中恰有n-1 条边，则图中至少有一个结点度数为1。

16、设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e0.

17、设T=是一棵树，若|V|>1，则T中至少存在两片树叶.

18、若n阶连通图中恰有n-1 条边，则图中至少有一个顶点度数为1.

19、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点.

《离散数学》作业参

一、选择或填空：

1． B C D                               

2． A， F     B，F     C，F     D，T

3． 2n-2                 

4． IA

5． 单位元，1     

6． A 

7． A D

8． (1) PQ      (2) PQ 

9． 偶数      

10． 自反性、对称性和传递性

11． 1，单位元，0      

12． 所有边一次且恰好一次

13． B C D E F

14． B D          

15． 5,10   

16． D          

17． B       

18． D

19． A       

20．（1）RR={ 〈1，1〉，〈1，3〉，〈2，2〉，〈2，4〉}

（2）Ｒ-1＝｛〈1，2〉，〈2，1〉，〈3，2〉，〈4，3〉｝

21． m=n-1   

22． 9,3   

23． A   

24． D

25  (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）（主析取范式）

2．Q→( PR)

QPR（主合取范式）

（Q→( PR)）

（PQR）（PQR）（PQR）（PQR）（PQR） （PQR）（PQR）（原公式否定的主合取范式）

Q→( PR)

（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（主析取范式）

3．  P→QPQ（主合取范式）

(P(QQ))((PP)Q)

(PQ)(PQ)(PQ)(PQ)

(PQ)(PQ)(PQ)（主析取范式）

4．(P→Q)(RP)(PQ)(RP)

(PQ)(RP)（析取范式）

(PQ(RR))(P(QQ) R)

(PQR)(PQR)(PQR)(PQR)

(PQR)(PQR)(PQR)（主析取范式）

((P→Q)(RP))

(PQR)(PQR)(PQR)(PQR)(PQR)

（原公式否定的主析取范式）

(P→Q)(RP)

(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）

5．PQ（主析取范式）

(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 (P→Q)(P→R)

(PQ)(PR) (合取范式)

(PQ(RR)(P(QQ)R)

(PQR)(PQR)(PQR)(PQR)

(PQR)(PQR)(PQR)(主合取范式)

(P→Q)(P→R)

(PQ)(PR)

P(QR)(合取范式)

(P(QQ)(RR))((PP)QR)

(PQR)(PQR)(PQR)(PQR)

(PQR)(PQR)

(PQR)(PQR)(PQR)(PQR)(PQR)

(主析取范式)

三、证明

1．PQ， P→R, Q→S => RS

证明：

（1）   R        附加前提

（2）  P→R        前提

（3）   P      （1），（2）

（4）   PQ       前提    

（5）    Q        （3），（4）

（6）   Q→S       前提

（7）    S        （5），（6）

（8）    RS      CP，（1），（8）

2．A→(CB)，B→A，D→C => A→D

证明：（1）   A       附加前提

（2）A→(CB)    前提

（3）CB        （1），（2）

（4）B→A       前提

（5）B         （1），（4）

（6）  C         （3），（5）

（7）D→C       前提

（8） D        （6），（7）

（9）A→D       CP，（1），（8）

3．P→Q，QR，R，SP=>S

证明：

（1）  R          前提

（2）QR       前提

（3）Q        （1），（2）

（4）P→Q         前提

（5）P        （3），（4）

（6）SP        前提

（7）S        （5），（6）

4．BD，(E→F)→D，E=>B

证明：

（1）  B          附加前提

（2）BD       前提 

（3） D           （1），（2）

（4）(E→F)→D  前提

（5）(E→F)    （3），（4）

（6）EF         （5）

（7）  E           （6）

（8）  E          前提

（9） EE        （7），（8）

5．A→(B→C)，C→(DE)，F→(DE),A=>B→F

证明：

 （1）   A           前提

（2） A→(B→C)    前提

（3）B→C        （1），（2）

（4）B            附加前提

（5）C           （3），（4）

（6）C→(DE)  前提

（7）DE       （5），（6）

(8)F→(DE) 前提

(9)F             （7），（8）

(10)B→F           CP，（4），（9） 

四、设Ａ，Ｂ，Ｃ是三个集合，证明

1．(A－B)∪(A－C)=A－(B∩C)

证明：

 (A-B)(A-C)=(A∩)(A∩) =A∩()=A∩= A-(B∩C)

2．A∩B=A∩C，∩B=∩C，则C=B

证明：

B=B∩(A)=(B∩A)(B∩) =(C∩A)(C∩)=C∩(A)=C

3．A∩(B－C)＝(A∩B)－(A∩C)

证明： 

(A∩B)－(A∩C)= (A∩B) ∩=(A∩B) ∩（）=(A∩B∩)(A∩B∩)

= A∩B∩=A∩（B∩）=A∩（B-C）

4．A－(B∪C)＝(A－B)－C        

证明： 

A－(BC)= A∩=A∩()=(A∩)∩= (A-B)∩=(A-B)-C

5．(A－B)∩(A－C)=A－(B∪C)　  　

证明：

（A-B）∩(A－C)=(A∩)∩(A∩)=(A∩A)∩(∩)= A∩=A－(B∪C)

6、A→(B→C)，C→(DE)，F→(DE),A  B→F.

证明：

 (1)    A           前提

(2)    A→(B→C)   前提

       (3)    B→C        （1），（2）

(4)    B            附加前提

       (5)    C           （3），（4）

       (6)    C→(DE)  前提

       (7)    DE       （5），（6）

       (8)    F→(DE) 前提

       (9)    F             （7），（8）

       (10)   B→F           CP 

7、BD，(E→F)→D，E  B.

证明：

(1)       B            附加前提

(2)     BD         前提 

(3)       D           （1），（2）

(4)     (E→F)→D  前提

(5)     (E→F)    （3），（4）

(6)     EF         （5）

(7)       E            （6）

(8)      E           前提

(9)     EE         （7），（8）

8 、A→(CB)，B→A，D→C  A→D.

证明：

（1）   A            附加前提

(2)    A→(CB)    前提

 (3)    CB        （1），（2）

 (4)    B→A       前提

 (5)    B         （1），（4）

 (6)     C          （3），（5）

 (7)    D→C       前提

 (8)    D         （6），（7）

 (9)   A→D        CP，（1），（8）

9、P→Q，QR，RS  P.

证明、

(1)         P         附加前提

        （2）     P→Q       前提

        （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,b∈G，必有唯一的x∈G，使得ax=b。

证明：

因为a-1*b∈G，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以对于a,b∈G，必有x=a-¹*b∈G，使得ax=b。

若x1,x2都满足要求。即ax1=b且ax2=b。故ax1=ax2。

由于*满足消去律，故x1=x2。

从而对于a,b∈G，必有唯一的x∈G，使得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)2n>2n-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)2n>2n-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)+1>2n-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) 2n>2n-2.

得出矛盾. 

19、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点.

证明：

若顶点个数小于等于3时，结论显然成立.

当顶点多于3 个时，用反证法证明. 记|V|=n,|E|=m,|F|=k.

假设图中所有顶点的度数都大于等于5.

由欧拉握手定理得deg(v)=2|E|得    5n2m.

又因为G=〈V,E,F〉是一个连通简单无向平面图，所以对每个面f，deg(f)3.

由公式deg(f)=2|E|可得，2m3k.

再由欧拉公式|V|-|E|+|F|=2可得2m-m+m=m

从而30m，这与已知矛盾.下载本文