浙江师范大学《离散数学》考试卷
（2010—2011学年第 1 学期）
考试形式闭卷使用学生软件工程、网络工程09
考试时间120分钟出卷时间2010 年12 月26 日
说明：考生应将全部答案都写在答题纸上，否则作无效处理。
一．选择题（每题2分，共20分）：
1. 设P：我平时认真学习，Q：我通过离散数学考试，则如下哪种说法能符号化为
P→Q：（）
A．除非我平时认真学习，否则我不能通过离散数学考试。
B. 若我平时认真学习，则我通过离散数学考试。
C. 因为我平时不认真学习，所以我没有通过离散数学考试。
D. 我通过离散数学考试仅当我平时认真学习。
2．命题公式P→(P∨Q∨R) 为（）。
A．重言式B．可满足式C．矛盾式D．等值式
3．设集合A={c, {c}}，下列命题错误的是（）。
A. {c}∈P(A)
B. {c}⊆P(A)
C. {{c}}∈P(A)
D. {{c}}⊆P(A)
4. 设f: N N, f(x)=(x) mod 5, 即x除以5的余数，则函数f （）.
A. 仅单射
B. 仅满射
C. 双射
D. 既不单设也不满射
5．下列命题中正确的结论是：（）
A．集合上A的关系如果不是自反的，就一定是反自反的；
B．集合上A的关系如果不是对称的，就一定是反对称的；
C．在任意关系R上，若<a, b>、<b, c>∈R，则必有<a, c>∈R；
D．非空集合A上的恒等关系既是等价关系又是偏序关系
6. 设集合A={a, b, c}，A上的关系R={<a, b>, <a, c>}，则下列结论错误的是：（）
A．R-1 = {<b, a>, <c, a>}； B. r(R) = R；
C．s(R) = {<a, b>, <a, c>, <b, a>, <c, a>}； D. t(R) = R
7．设集合A 和二元运算*，可交换的代数运算是（ ）。
A ．设)(R M A n =，运算*是矩阵的乘法
B ．设||,,},5,4,3,2,1,1{b b a A b a A =*∈∀--=
C ．设b a b a A b a y x P A =*∈∀=,,}),,({
D ．设(),,,23A Z a b A a b a b =∀∈*=+整数集
8．以下命题中不正确的结论是（ ）
A ．循环群必为交换群；
B ．交换群必为循环群；
C ．素数阶群必为循环群；
D ．群的运算满足消去率。
9. 8阶有限群的任何子群一定不是（ ）的。
A. 2阶
B. 3 阶
C. 4 阶
D. 8 阶
10．以下命题中正确的结论是（ ）
A ．n = 2k (k ≥1)时，完全图K n 必为欧拉图；
B ．如果一个连通图的奇度顶点的个数大于2，那么它可能是一个欧拉图；
C ．无向图中，顶点连通关系 ~ 是顶点集V 上的等价关系；
D ．顶点度数列(5, 4, 3, 2, 2)可简单图化。
二．填空题（每题2分，共20分）
11. 设p : 张三的祖籍是山东，q ：张三的祖籍是浙江，则“张三的祖籍是山东或浙
江”可符号化表示为： 。
12．设个体域为D ={a , b }，则公式∃x (F (x ) G (x ) )的量词消去后的公式
为： 。
13. 设A 、B 为集合，|A |=5, |B |=8, |A ⋂B |=3, 则|A ⋃B | = 。
14．设集合A = {a , b , c , d }，A 上的二元关系R = {<a ,b >, <b ,d >, <c ,c >, <c ,d >}，则
R 2= 。
15．设集合S = {a , b , c } 上的二元关系R 的关系矩阵110001001R M ⎛⎫ ⎪= ⎪ ⎪⎝⎭
，则R 具有的
基本性质为 。
16. 设A ={1, 3, 5}，A 上的二元运算*为：a *b =max{a , b }，则在独异点<A ,*>中，单
位元是 ，零元是 。
17. 设a 是8阶群G 的生成元，则a 3是 阶元，a 4是 阶元。
18．设G 是有限群且|G | = 6，H 是G 的子群且|H | = 2，则H 在G 中的右陪集个数
为 。
19．无向图G 有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点，则G
一共有 个顶点。
20．已知下图，它的点连通度)(G κ为 ，边连通度)(G λ为 。
三．计算题（每小题9分，共45分）
21．用等值演算方法求出如下两个公式的主析取范式，并由此判定它们是否等值：
p →q →r 与p →(q →r )
22．设集合A ＝{1, 2, 3, 4}, A 上的二元关系R ={ <1,4>, <2,3>, <3,2>, <4,1> } ⋃ I A ，
通过画出关系图来分析说明R 是否为A 上的等价关系；若为等价关系，则列出所有的等价类。
23．设}12,,2,1{ =A ，≤为整除关系，}4,3,2{=B ，(1)画出偏序集≤><,A 的哈斯图；
（2）找出A 的极大元、极小元、最大元、最小元；（3）在≤><,A 中求B 的上界、下界、最小上界、最大下界。
24．设>=<a G 是18阶循环群，（1）求出G 的所有生成元；（2）求出G 的所有子
群。
25．求如下有向图D 的邻接矩阵()A D ，并求出从顶点v 3到顶点v 4长度分别为1, 2,
3, 4的通路数。
四．证明题（第26题5分，第27题10分，共15分）
26. 设A 、B 、C 为任意集合，证明：A -B -C = A – (B ⋃C )
27. 构造证明：
前提：(U ∨V ∨ R )→(M ∧ N ), U ∨ P , P → (Q ∨ S ) 结论：⌝Q ∧⌝S → N
1v 2v 3v 4
v。