2004年4月高等教育自学考试全国统一命题考试
离散数学 试题
课程代码2324
第一部分 选择题 （共15分）
一、单项选择题（本大题共15小题，每小题1分，共15分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列是两个命题变元p，q的小项是（ ）
A．p∧┐p∧q B．┐p∨q
C．┐p∧q D．┐p∨p∨q
2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）
A．p→┐q B．p∨┐q
C．p∧q D．p∧┐q
3．下列语句中是命题的只有（ ）
A．1+1=10 B．x+y=10
C．sinx+siny<0 D．x mod 3=2
4．下列等值式不正确的是（ ）
A．┐(
x)A
(
x)┐A
B．(x)(B→A(x))B→(x)A(x)
C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)
D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)
5．谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z)中量词x的辖域是（ ）
A．(x)Q(x,z)→(x)(y)R(x,y,z))
B．Q(x,z)→(y)R(x,y,z)
C．Q(x,z)→(x)(y)R(x,y,z)
D．Q(x,z)
6．设R为实数集，函数f：R→R，f(x)=2x，则f是（ ）
A．满射函数 B．入射函数
C．双射函数 D．非入射非满射
7．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，则对应于R的A的划分是（ ）
A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}
C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}
8．设A={Ø}，B=P(P(A))，以下正确的式子是（ ）
A．{Ø,{Ø}}∈B B．{{Ø,Ø}}∈B
C．{{Ø},{{Ø}}}∈B D．{Ø,{{Ø}}}∈B
9．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ ）
A．(X-Y)-Z=X-(Y∩Z)
B．(X-Y)-Z=(X-Z)-Y
C．(X-Y)-Z=(X-Z)-(Y-Z)
D．(X-Y)-Z=X-(Y∪Z)
10．设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（ ）
A．
有x*Z=Z*x=Z
B．Z
A，且
有x*Z=Z*x=Z
C．ZA，且有x*Z=Z*x=x
D．ZA，且
有x*Z=Z*x=Z
11．在自然数集N上，下列定义的运算中不可结合的只有（ ）
A．a*b=min(a,b)
B．a*b=a+b
C．a*b=GCD(a,b)(a,b的最大公约数)
D．a*b=a(mod b)
12．设R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算，<R+，*>是一个群，则下列集合关于数的乘法运算构成该群的子群的是（ ）
A．{R+中的有理数} B．{R+中的无理数}
C．{R+中的自然数} D．{1，2，3}
13．设<A,*,
>是环，则下列正确的是（ ）
A．<A,>是交换群 B．<A,*>是加法群
C．对*是可分配的 D．*对是可分配的
14．下列各图不是欧拉图的是（ ）
15．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）
A．2个面 B．3个面
C．4个面 D．5个面
第二部分 非选择题（共85分）
二、填空题（本大题共10小题，每空1分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．一公式为 之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为 之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定。
17．前束范式具有形式(Q1V1)(Q2V2)…(QnVn)A，其中Qi(1≤i≤n)为 ，A为 的谓词公式。
18．设论域是{a,b,c}，则(x)S(x)等价于命题公式
；(
)S(x)等价于命题公式
。
19．设R为A上的关系，则R的自反闭包r(R)= ，对称闭包s(R)= 。
20．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 ，其关系矩阵是 。
21．设<S,≤>是一个偏序集，如果S中的任意两个元素都有 和 ，则称S关于≤构成一个格。
22．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统<Z,*>的幺元是 ，零元是 。
23．如下平面图有2个面R1和R2，其中deg(R1)= ，deg(R2)= 。
24．无向图G具有一条欧拉回路，当且仅当G是 ，并且所有结点的度数都是 。
25．在下图中，结点v2的度数是 ，结点v5的度数是 。
三、计算题（本大题共6小题，第26—27小题每小题4分，第28、30小题每小题5分，第29、31小题每小题6分，共30分）
26．（4分）求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函数。
27．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：
。
28．（5分）设A={a,b,c }，P（A）是A的幂集，
是集合对称差运算。已知<P(A),
>是群。在群<P(A),>中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}x={b}。
29．（6分）用等值演算法求公式┐(p→q)
(p→┐q)的主合取范式
30．（5分）画出5个具有5个结点5条边的非同构的无向连通简单图。
31．（6分）在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求集合D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。
四、证明题（本大题共3小题，第32~33小题每小题6分，第34小题8分，共20分）
32．（6分）用等值演算法证明((q∧s)→r)∧(s→(p∨r))(s∧(p→q))→r
33．（6分）设n阶无向树G=<V，E>中有m条边，证明m=n-1。
34．（8分）设P={Ø,{1},{1,2},{1,2,3}}，
是集合P上的包含关系。
（1）证明：<P，>是偏序集。
（2）在（1）的基础上证明<P，>是全序集
五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）
35．（9分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）
36．（6分）设有a,b,c,d,e,f,g等七个人，已知a会讲英语；b会讲英语、汉语；c会讲英、俄语；d会讲日、汉语；e会讲德语、俄语；f会讲法语、日语；g会讲法语、德语。试用图论方法安排园桌座位，使每人都能与其身边的人交谈。