发布时间 : 星期日 文章2002年4月至2011年7月历次自考离散数学试题汇总（打印版） - 图文更新完毕开始阅读7283236bb84ae45c3b358c9c
C.8个 D.9个
8.设A={a,b,c},则A×A中的元素有( )。 A.3个 B.6个 C.8个 D.9个
9.设(G,+,*)是一个除环,则它不满足的运算律是( )。 A.加法交换律 B.乘法交换律 C.乘法消去律 D.加法消去律
10.对于一个代数系统,以下命题成立的是( )。 A.每个元素必有左逆元
B.一个元素有左逆元,则它也是右逆元 C.一个元素的左右逆元不一定相等 D.一个元素的左逆元存在时必唯一
11.若一个代数系统(A,*)满足运算封闭性及结合律,且有幺元,则它是( )。 A.独异点 B.群
C.格 D.布尔代数
12.在有3个结点的图中,奇结点的个数为( )。 A.0 B.1
C.1或3 D.0或2
13.设图G=
14.若图G有一条路经过图中每个结点恰好一次,则G( )。 A.有一条欧拉路 B.是欧拉图 C.有一条汉密尔顿路 D.是汉密尔顿图 二、填空题(每小题2分，共30分)
1.设P:你陪伴我;Q:你代我叫车子;R:我出去.则命题“如果你不陪伴我或不代我叫车子,我就不出去.”的符号化形式为_______。
2.合式公式(P∨┐P)→((Q∧┐Q)∧R)是永_______式。 3.合式公式Q→(P∨(P∧Q))与Q→P的关系是_______。（等价或蕴含选一） 4.设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则命题“小李非常聪明和能干”的为谓词表达式为_______。 5.公式A→(?x)B(x)的前束范式为_______。
6.设论域为集合{a,b,c}，则(?x)P(x)∨(?x)Q(x)?_______。 7.集合A上的关系“?”称为偏序关系，如果?满足_______。 8.设A={a,b,c}，B={a,b,c,d},则A?B=_______。
9.集合A={a,b,c}上的关系R={
10.设A={1,2}，A上的二元运算定义为x*y=min{x,y}，则*的运算表为_______。
11.设A={2,3,6,12}，A上的序关系“?”定义为：x?y当且仅当x整除y.令B={2,3,6}，则B的最小上界是_______，B的极小元是______。 12.整数加群的单位元是_______。
?101???13.设图G的邻接矩阵为?010?，则从结点v1到v3的长度为2的路径数为。
??101??14.若一个连通图G有5个结点，连接每两个结点有一条边，则G一定 平面图。（是或不是选一）
13
15.一颗完全二叉树的高为3，则它至少有_______片树叶，至多有 片树叶。 三、计算题(每小题6分,共24分)
1.求公式A=P∧Q∨R的主合取范式。
2.设集合A{a,b,c,d}，B={1,2,3},C={x,y},A到B的关系为R={
3.设G={a,b}，定义G上的一个二元运算*使(G,*)构成一个群，并验证你的结论。 4.给定一棵树（如图），试分别用中序行遍法、前序行遍法和后序行遍法写出运算表达式。
四、证明题(每小题8分,共32分) 1.用推理规则证明以下蕴含式
┐A→(B∨C)，D∨E，(D∨E)→┐A?B∨C 2.利用推理规则证明
(?x)(M(x)→D(x)),(?x)(S(x)∧M(x))?(?x)(D(x)∧S(x))
3.设正整数的序偶集合为A，在A上定义二元关系R如下：<
4.试证：群(G，*)的两个子群(H1，*),(H2，*)的交H1I H2对一于*还是G的一个子群。
全国2004年4月高等教育自学考试
离散数学试题
课程代码：02324
第一部分 选择题 （共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)
14
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={
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?A,有x*Z=Z*x=Z
B．Z?A，且?x?A有x*Z=Z*x=Z C．Z?A，且?x?A有x*Z=Z*x=x D．Z?A，且?x?A有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}，*是数的乘法运算，
算构成该群的子群的是（ ） A．{R+中的有理数} B．{R+中的无理数} C．{R+中的自然数} D．{1，2，3} 13．设
15
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)等价于命题公式 ；(?x)S(x)等价于命题公式 。 19．设R为A上的关系，则R的自反闭包r(R)= ，对称闭包s(R)= 。
20．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 ，其关系矩阵是 。
21．设
的幺元是 ，零元是 。
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}，试消去给定公式中的量词：(?y)(?x)(x?y?0)。 28．（5分）设A={a,b,c }，P（A）是A的幂集，?是集合对称差运算。已知
中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}?x={b}。 29．（6分）用等值演算法求公式┐(p→q)??(p→┐q)的主合取范式
30．（5分）画出5个具有5个结点5条边的非同构的无向连通简单图。 31．（6分）在偏序集
大元，极小元，最大元，最小元，最小上界和最大下界。
四、证明题（本大题共3小题，第32~33小题每小题6分，第34小题8分，共20分） 32．（6分）用等值演算法证明((q∧s)→r)∧(s→(p∨r))?(s∧(p→q))→r
16