离散数学2012年12月28 日
√√计科21101、21102、信科11001、11002
一二三四五六七八
一、单选题: (2分×10=20分)
1.设p:我们听课,q:我们打球.命题“我们不能既听课又打球”符号化为( ). A．┓p→┓q B．┓p∨┓q C．┓(p→q) D．p↔┓q
2.设个体域A={a,b},公式∀xP(x)∧∃yQ(y)消去量词后为( )
A.P(x)∧Q(y)
B.P(a)∧P(b)∧(Q(a)∨Q(b))
C.P(a)∧Q(b)
D. P(a)∧P(b)∧Q(a)∨Q(b)
3．设A={1,2,3}, 则A上的等价关系有( )
A．3个B．4个C．5个D．6个
4．设Z是整数集，+，·分别是普通加法和乘法，则〈Z，+，·〉是（）A．域B．整环和域C．整环D．含零因子环
5．Q为有理数集，·是普通乘法,则代数系统〈Q，*〉不能构成（）A．群B．独异点C．半群D．交换半群
6．N是自然数集，≤是小于等于关系，则〈N，≤〉是（）
A．有界格B．有补格C．分配格D．有补分配格
7．有限布尔代数的元素个数必定等于（）
A．2n B．2n C．n2D．3n
8．给定下列序列，可构成无向简单图的度数序列的是（）
A．1,1,2,2,3 B．1,1,2,2,2 C．0,1,3,3,3 D．1,3,4,4,5
9．任何无向图中顶点间的连通关系是（）
A．偏序关系B．等价关系C．非偏序关系D．非等价关系10．设D=〈V，E〉为有向图，V={a,b,c,d}，
E={<b,a>,<b,c>,<b,d>,<d,a>,< d,c>},则D是（）
A．强连通图B．单向连通图C．弱连通图D．非连通图
二、求命题公式：┓(p∧q)→r的主析取范式和主合取范式及成真赋值。

(10分)
三．设A={1,2,3,4}上的关系R = I A∪{<1,2>, <1,3>,<1,4>,<2,4>}．
(1)写出R的关系矩阵；(2)求s(R)；(3)R是否为等价关系或偏序关系？（10分）
四.设V1=<R,+>, V2= <R*,⋅>，其中R是实数集，R*= R-{0}，+ 和⋅是普通加法和乘法，令f：R→R*, f(x)=e x，证明f 是V1到V2的单同态。

（10分)
五．下面的无向图是否为二部图？欧拉图？能一笔画吗？它是平面图，请画出它的一个平面嵌入。

（10分)
六、设A={1,2}, ⊕为对称差，则<P(A), ⊕>构成群.（10分)
（1）写出⊕的运算表；（2）求解方程{2}⊕X={1}；（3）求由A={1,2}生成的循环子群。

七.设A={1,2,3,4,6,12}是12的正因子集,≤是整除关系.(10分)
(1)画出偏序集<A,≤>的哈斯图；(2)该偏序集是否构成格？布尔代数？
八.给定有向图D如下,求D中:
（1）v1的出度和入度；（2）长度为4的通路总数；（3）v1到v4长度为3的通路条数；
（4）v
1到v
1
长度为4的回路条数；（5）D的可达矩阵。

（10分)。