《离散数学》题库及答案
一、选择或填空
1．下列公式中哪些是永真式？( )
A.(┐P?Q)→(Q→?R) B.P→(Q→Q) C.(P?Q)→P D.P→(P?Q) 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．群
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?(P?Q)=>?P 8．设P：我生病，Q：我去学校，则下列命题可符号化为( )。
（1）若我生病，则我不去学校 (2) 当且仅当我生病时，我才不去学校 9．任一有向图中，度数为奇数的结点有( )个。 10．集合A上的等价关系的三个性质是什么？( )
11．群＜A,*＞的等幂元有( )个，是( )，零元有( )个。 12．一个图的欧拉回路是一条通过图中( )的回路。 13．设有下列公式，请问哪几个是永真蕴涵式?( )
A.P=>P?Q B. P?Q=>P C. P?Q=>P?Q D.P?(P→Q)=>Q E. ?(P→Q)=>P F. ?P?(P?Q)=>?P 14．判断下列命题哪几个为正确？( )
A. {Ф}∈{Ф，{{Ф}}} B. {Ф}?{Ф，{{Ф}}} C. Ф∈{{Ф}} D. Ф?{Ф} E. {a,b}∈{a,b,{a},{b}}
15．设a是10阶群的生成元， 则a是( )阶元素，a是( )阶元素。 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. A?B，B?C=> A?C B. A?B，B?C=> A∈B C. A∈B，B∈C=> A∈C
20．设S={１，２，３，４}，Ａ上的关系Ｒ＝｛〈1，2〉，〈2，1〉，〈2，3〉，〈3，4〉｝，求(1)R?R (2) R 。
第 1 页 共 14 页
-1
4
3
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有18条边且每个顶点的度数都是3，则图G有( )个顶点。
A. 10 B. 4 C. 8 D. 12 25、A，B，C是三个集合，则下列哪个推理正确?( )
(1) A?B，B?C ? A?C (2) A?B，B?C ? A?B (3) A?B，B?C ? A?C
26、判断下列命题哪个正确?( )
(1) {Ф}?{Ф,{{Ф}}} (2) {Ф}?{Ф,{{Ф}} (3) Ф?{{Ф}} (4) Ф={Ф}
27、设T是一棵树，则T是一个( ).
(1) 欧拉图 (2) 哈密尔顿图 (3) 连通图
28、下列公式中哪个不是蕴涵式?( )
(1) P?P?Q (2) P?Q?P (3) P?Q?P?Q (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条边的连通图
第 2 页 共 14 页
(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． P??Q 2． Q→( P??R) 3． P→Q
4． ?(P→Q) ? (R?P) 5． P?Q 6 Q→(P??R) 7 (P→Q)?(P→R) 三、证明
1．P?Q， P→R, Q→S => R?S
2．A→(C?B)，B→?A，D→?C => A→?D 3．P→Q，?Q?R，?R，?S?P=>?S 4．?B?D，(E→?F)→?D，?E=>?B
5．A→(B→C)，C→(?D?E)，?F→(D??E),A=>B→F 6、A→(B→C)，C→(?D?E)，?F→(D??E),A ? B→F. 7、?B?D，(E→?F)→?D，?E ? ?B. 8、A→(C?B)，B→?A，D→?C ? A→?D.
第 3 页 共 14 页
9、P→?Q，Q??R，R??S ? ?P.
四、设Ａ，Ｂ，Ｃ是三个集合，证明 1．(A－B)∪(A－C)=A－(B∩C) 2．A∩B=A∩C，A∩B=A∩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，则e?0。 2．任一图中度数为奇数的结点是偶数个。
3．设群＜G，＊＞除单位元外每个元素的阶均为2，则＜G，＊＞是交换群。 4．在一个连通简单无向平面图G=〈V，E，F〉中若|V|?3，则 |E|?3|V－6。 5．单位元有惟一逆元。
6．设
8．若连通简单无向平面图G有n个结点，m条边，k个面，且每个面至少由k(k?3)条边围成，则 m?k(ｎ－
2)／(ｋ－2)。
9．证明在元素不少于两个的群中不存在零元。 10．素数阶循环群的每个非单位元都是生成元。
11．设G=〈V，E〉是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。
12．给定无向连通简单平面图G=
14．在一个群〈G，*〉中，若G中的元素a的阶是k，即 | a |=k，则a的阶也是k。 15．若有n个结点的连通图中恰有n-1 条边，则图中至少有一个结点度数为1。 16、设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e?0. 17、设T=
第 4 页 共 14 页
-1
《离散数学》作业参考答案
一、选择或填空：
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) P??Q (2) P??Q 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）R?R={ 〈1，1〉，〈1，3〉，〈2，2〉，〈2，4〉} （2）Ｒ＝｛〈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)
第 5 页 共 14 页
-1
《离散数学》题库及答案
