篇一：离散数学期末试卷(A)
>2007 ～ 2008学年第一学期《离散数学》期末试卷（A） 年级专业适用年级专业：2006级软件工程专业
试卷说明：闭卷考试，考试时间120分钟
一、单项选择题（共20小题，每小题1分，共20分）
1．下列语句中只有C
A．今年元旦会下雪。
B．1+1=10。
C．嫦娥一号太棒了！
D．嫦娥奔月的神话已成为现实。
2．p?q的主合取范式是。B
A．(p?q)?(p??q) B．(p??q)?(?p?q)
C．(p?q)?(?p??q)D．(p?q)?(?p?q)
3．与p? q等值的命题公式是。D
A．?p?q B．p??qC．p??qD．?p?q
4．在一阶逻辑中使用的量词只有B
A．1B．2 C．3D．4
5．??xA(x)?C
A．??xA(x)B．?x?A(x)C．?x?A(x)D．?xA(x)
6．若|A|=4，则C
A．4B．8C．16D．64
7．设A、B、C为任意集合，集合的对称差运算不具有的性质是D
A．A?B = B?A B．(A?B)?C = B?(A?C)
班级学号 姓名____________
C．A?A = ? D．A?A = A
8．二元关系是B
A．两个集合的笛卡儿积 B．序偶的集合
C．映射的集合 D．以上都不是
9．下面关于函数的叙述中正确的是D
A．函数一定是满射 B．函数一定是单射
C．函数不是满射就单射D．函数是特殊的关系
10．半群中的二元运算一定满足B
A．交换律 B．结合律 C．分配律 D．幂等律
11．环中有B
A．一B．二C．三 D．四
12．群与独异点的区别是C
A．满足交换律 B．满足结合律
C．每个元素都有逆元 D．满足分配律
13．九阶轮图的点色数是B
A．2B．3 C．4 D．9
14．设N、Q、Z、R分别表示非负整数集、有理数集、整数集和实数集，＋表示数的加法，则下面的代数系统中，不是群。A
A．<N ，＋> B．<Q ，＋>
C．< Z ，＋> D．<R ，＋>
15．简单通路是没有的通路。A
A．重复边 B．重复顶点 C．平行边 D．环
16．设个体域为N（非负整数集），下列公式为真的是。B
A．?y ?x (xy = 1) B．?y ?x (xy = x)
C．?x ?y (x+y=0) D．?x ?y (x > y)
17．非平凡树一定是。B
A．正则图 B．二部图C．欧拉图 D．哈密顿图
18．环<R，+ ，?>中的 ? 运算只要求满足。B
A．交换律 B．结合律C．分配律 D．幂等律
19．集合A上的等价关系与一 一 对应。B
A．集合A的子集 B．集合A的划分
C．集合A到A的双射 D．集合A与A的单射
20．全序关系一定不是A
A．等价关系B．偏序关系 C．线序关系D．整除关系
二、填空题（共10题，每题2分，共20分）
11． 设S(x)：x是计算机学院的学生。L(x)：x学离散数学。
则“计算机学院的学生都要学离散数学。”可符号化为 ：
__ ?x(S(x)?L(x)) _____________________________________。
12． 设A={a,b,c}，A上的等价关系R={<a,b>,<b,a>} ?IA ，
则商集A/R=____ {{a , b} , {c}}
13．设B={?}，则幂集P(B) = ___________ {?,{?}} 。
14．?xA(x) ??yB(x,y)的前束范式是____．?u?v (A(u) ?B(x,v))或 ?x?y(A(x) ?B(u,y))
15．设集合A={0，1}，则A上可定义的二元运算有____16_______个。
16．设A={1，2，3，4}，A上关系R={<1,3>,<3,1>,<4,1>}?IA ，
则t(R)=__ {<1,3>,<3,1>,<4,1>,<4,3>} ?IA
17．设函数f：N?N，f =x -1，函数h：N?N，h(x)=x2+1，
则复合函数f?h (x) = _______(x -1)2+1
18．完全二部图Kr,s（r<s）的最大度?(Kr,s) = ______S____，
最小度?(Kr,s)= _____ r ___。
19．设一棵树有4个2度顶点，3个3度顶点，其余顶点都是1度顶点，
则该树有_______5___片树叶。
20．命题公式?(p?(p?q))的成假赋值是__00，01，10，11
三、运算题（共5小题，每小题8分，共40分）
21．求命题公式?(p??q) ? (q ? r)的主析取范式，并指出其类型。
解：?(p??q) ? (q ? r) ? (?p ? q ) ? (q ? r)
? (?p ? r) ? q ? (?p ?(? q ? q ) ? r) ? ((? p ? p ) ? q ?(? r ? r ) )
? (?p ?? q ? r) ? (?p ? q ? r) ?(?p ? q ? ?r) ?(?p ? q ? r)
?(p ? q ? ?r) ? (p ? q ? r)
? (?p ?? q ? r) ? (?p ? q ? ?r) ?(?p ? q ? r) ? (p ? q ? ?r) ? (p ? q ? r) 该公式是可满足式
22．设A={a,b,c,d,e,f}， A上的偏序关系：
R={<a,b>,<a,d>,<a,c>,<a,f>,<a,e>,<b,d>,<b,e>,<c,e>,<c,f>} ? IA
画出该偏序关系的哈斯图，并求A的极大元、极小元、最大元和最小元。
解：
极大元为d、e、f；极小元为a；无最大元；最小元为a
23．设个体域D={a,b,c}，消去一阶公式 ?x（F(x) ??yG(y)）中的量词 ，并在下述解释下求其真值：F(a)= F(b)=1 , F(c)= 0，G(a)=1， G(b)=G(c)=0。
解：?x（F(x) ??yG(y)）?? xF(x) ??yG(y)
?（F(a) ? F(b) ? F(c)）?（G(a) ? G(b) ? G(c)）
?（1 ? 1 ? 0）?（1 ? 0 ? 0）? 1 ?1?1
24．画一棵叶带权为1、2、3、3、5、6、7的最优二元树T，并计算树权W(T)。
解： W(T) = 71
25．设Z为整数集合，V=< Z , *>，*是二元运算，定义为：
x*y=x+y-xy
说明V是含幺半群而不是群。
解：（1）*运算在Z上封闭：
（2）*运算可结合，对任意a、b、c?Z
a*(b*c) = a*(b+c-bc) = a+ b+c-bc -a(b+c-bc) = a+b+c-ab-ac-bc+abc
(a*b)*c = (a+b-ab)*c = a+b-ab+c- (a+b-ab) c = a+b+c-ab-ac-bc+abc
所以a*(b*c) =(a*b)*c
（3）*运算的幺元是0
（4）任意x?Z，x*1=1*x=1，所以1是零元，它没有逆元。
由上述可知，故< Z , *>是含幺半群而不是群。
四、证明题（共3小题，共20分）
26（10分）．在一阶逻辑中构造下面推理的证明：
前提：?x(F(x) ??G(x)) ，?x (G(x) ? R(x))，?x?R(x)
结论：?x?F(x) （10分）证: ① ?x?R(x)前提引入
② ?R(c)
①EI
③ ?x (G(x) ? R(x)) 前提引入
④ G(c) ? R(c) ③ UI
⑤ G(c) ②④析取三段论
⑥ ?x(F(x) ??G(x)) 前提引入
⑦ F(c) ??G(c)⑥ UI
⑧ ?F(c)⑤ ⑦拒取式
⑨ ?x?F(x) ⑧ EG
27（5分）．证明，若非空集合A上的关系R和S是反对称的，则R?S也是反对称的。
篇二：离散数学试题及答案
一、填空 20% （每小题2分）1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为
“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P
则公式?x?yP(y,x)真值为 。 2、 设S={a1 ，a2 ，?，a8}，Bi是S的子集，则由B31所表达的子集是 。
3、 设A={2，3，4，5，6}上的二元关系R?{?x,y?|x?y?x是质数}，则R=
（列举法）。
R的关系矩阵MR=
。
5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R= ；
A上既是对称的又是反对称的关系R=。 6、设代数系统<A，*>，其中A={a，b，c},
则幺元是；是否有幂等
性 ；是否有对称性。
7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。
9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。 10、公式(P?(?P?Q))?((?P?Q)??R 的根树表示为
。
二、选择 20% （每小题2分）
1、在下述公式中是重言式为（）
A．(P?Q)?(P?Q)；B．(P?Q)?((P?Q)?(Q?P))； C．?(P?Q)?Q； D．P?(P?Q) 。
2、命题公式 (?P?Q)?(?Q?P) 中极小项的个数为（ ），成真赋值的个数为（ ）。
A．0； B．1； C．2；D．3 。 3、设S?{?,{1},{1,2}}，则 2 有（ ）个元素。
A．3； B．6；C．7； D．8 。 4、 设S?{ 1, 2, 3 }，定义S?S上的等价关系
S
R?{??a,b?,?c,d? | ?a,b??S?S,?c,d??S?S,a?d?b?c}则由 R产 生的S?S上一个划分共有（ ）个分块。
A．4； B．5；C．6； D．9 。 5、设S?{ 1, 2, 3 }，S上关系R的关系图为
则R具有（ ）性质。
A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性 。 6、设 ?,? 为普通加法和乘法，则（）?S,?,??是域。 A．S?{x|x?a?b,a,b?Q}B．S?{x|x?2n,a,b?Z}
C．S?{x|x?2n?1,
n?Z} D．S?{x|x?Z?x?0}= N 。
7、下面偏序集（ ）能构成格。
8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。
A．1； B．2； C．3；D．4 。 9、在如下各图中（ ）欧拉图。
是实数集合，“?”为普通乘法，则代数系统<R ，×> 是（）。
、设R
10
A．群； B．独异点；C．半群 。
三、证明 46%
1、 设R是A上一个二元关系，
S?{?a,b?|(a,b?A)?(对于某一个c?A,有?a,c??R且?c,b??R)}试证明若R
是A上一个等价关系，则S也是A上的一个等价关系。（9分）
2、 用逻辑推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）
3、 若f:A?B是从A到B的函数，定义一个函数g:B?2A 对任意b?B有
A
g(b)?{x|(x?A)?(f(x)?b)}，证明：若f是A到B的满射，则g是从B到 2 的
单射。（10分）
4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）
5、 设G是具有n个结点的无向简单图，其边数m?
图（8分）
1
(n?1)(n?2)?2，则G是Hamilton2
四、计算 14%
1、 设<Z6,+6>是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求
出<Z6,+6>的所有子群及其相应左陪集。（7分）
2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）
一、 填空 20%（每小题2分）
1、?P?Q；P?Q 2、T 3、B31?B00011111?{a4,a5,a6,a7,a8} 4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,
?1
??1
4>,<5,5>,<5,6>}；?0
??1?0?1111?
?
1111?
0011?5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>}
?
1111?0000??
1
n(n?1)；图中无奇度结点且连通 2
6、a ；否；有7、Klein四元群；循环群 8、 B 9、10 、
二、
选择 20%（每小题 2分）
三、 证明 46%
1、（9分）
（1） S自反的
?a?A，由R自反，?(?a,a??R)?(?a,a??R)，??a,a??S
（2） S对称的
?a,b?A
?a,b??S?(?a,c??R)?(?c,b??R)
?(?a,c??R)?(?c,b??R)??b,a??S
（3） S传递的
?S定义?R对称?R传递
篇三：离散数学期末试题
"txt">一、（10分）求(P?Q)?(P∧?(Q∨?R))的主析取范式 解：(P?Q)?(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R))?(P∨Q)∨(P∧?Q∧R))
?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R)
?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ?M0∧M1
?m2∨m3∨m4∨m5∨m6∨m7
二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。
王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？
解 设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R
王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：
((?P∧Q)∧((Q∧?R)∨(?Q∧R)))∨((?Q∧P)∧(?Q∧R))
?(?P∧Q∧Q∧?R)∨(?P∧Q∧?Q∧R)∨(?Q∧P∧?Q∧R) ?(?P∧Q∧?R)∨(P∧?Q∧R) ??P∧Q∧?R ?T
因此，王教授是上海人。
三、（10分）证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。
证明 设R是非空集合A上的二元关系，则tsr(R)是包含R的且具有自反性、对称性和传递性的关系。
若R是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)?R。则
'
'
sr(R)?s(R)＝R，进而有tsr(R)?t(R)＝R。
综上可知，ts(原文来自：wWW.DxF5.com 东 星资源网:离散数学期中考试题)r(R)是包含R的且具有自反性、对称性和传递性的最小关系。
四、（15分）集合A＝{a，b，c，d，e}上的二元关系R为R＝{<a，a>，<a，b>，<a，c>，<a，d>，<a，e>，<b，b>，<b，c>，<b，e>，<c，c>，<c，d>，<c，e>，<d，d>，<d，e>，<e，e>}，
(1)写出R的关系矩阵。
(2)判断R是不是偏序关系，为什么？ 解 (1) R的关系矩阵为：
''''
?1
??0
M(R)??0
??0?0?1111?
?
1101?0101?
?
0011?0001??
(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；rij＋rji≤1，故R是反对称的；可计算对应的关系矩阵为：
?1
??0
M(R2)??0
??0?0?
由以上矩阵可知R是传递的。
1111?
?
1101?
0101??M(R)
?
0011?0001??
五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。 证明：因为
<x，y>∈(A－B)×C?x∈(A－B)∧y∈C
?(x∈A∧x?B)∧y∈C
?(x∈A∧y∈C∧x?B)∨(x∈A∧y∈C∧y?C) ?(x∈A∧y∈C)∧(x?B∨y?C) ?(x∈A∧y∈C)∧?(x∈B∧y∈C) ?<x，y>∈(A×C)∧<x，y>?(B×C) ?<x，y>∈(A×C)－(B×C)
所以，(A－B)×C＝(A×C－B×C)。
六、（10分）设f：A?B，g：B?C，h：C?A，证明：如果h?g?f＝IA，f?h?g＝IB，g?f?h＝IC，则f、g、h均为双射，并求出f、g和h。
解 因IA恒等函数，由h?g?f＝IA可得f是单射，h是满射；因IB恒等函数，由f?h?g＝IB可得g是单射，f是满射；因IC恒等函数，由g?f?h＝IC可得h是单射，g是满射。从而f、g、h均为双射。
由h?g?f＝IA，得f＝h?g；由f?h?g＝IB，得g＝f?h；由g?f?h＝IC，得h＝g?f。
－1
－1
－1
－1
－1
－1
七、（15分）设<G，*>是一代数系统，运算*满足交换律和结合律，且a*x＝a*y?x＝y，证明：若G有限，则G是一群。
证明 因G有限，不妨设G＝{a1，a2，…，an}。由a*x＝a*y?x＝y得，若x≠y，则a*x≠a*y。于是可证，对任意的a∈G，有aG＝G。又因为运算*满足交换律，所以aG＝G＝Ga。令e∈G使得a*e＝a。对任意的b∈G，令c*a＝b，则b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由运算*满足交换律得e*b＝b，所以e是关于运算*的幺元。对任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由运算*满足交换律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。
八、（20分）（1）证明在n个结点的连通图G中，至少有n－1条边。
证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。
设G中结点为v1、v2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、…、vn?1中的某个结点相邻，得新边en?1，由此可见G中至少有n－1条边。
2（2）给定简单无向图G＝<V，E>，且|V|＝m，|E|＝n。试证：若n≥Cm?1＋2，则G是哈密尔顿
图。
2证明 若n≥Cm。 ?1＋2，则2n≥m－3m＋6 （1）
2
若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝
w?V
?d(w)＜m＋(m－2)(m－3)＋m＝m－
2
3m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。
离散数考试试题（B卷及答案）
一、（10分）使用将命题公式化为主范式的方法，证明(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。 证明：因为(P?Q)?(P∧Q)??(?P∨Q)∨(P∧Q)
?(P∧?Q)∨(P∧Q)
(Q?P)∧(P∨Q)?(?Q∨P)∧(P∨Q)
?(P∧?Q)∨(?Q∧Q)∨(P∧P) ∨(P∧Q) ?(P∧?Q)∨P
?(P∧?Q)∨(P∧(Q∨?Q)) ?(P∧?Q)∨(P∧Q)∨(P∧?Q) ?(P∧?Q)∨(P∧Q)
所以，(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。
二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。
解 设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为： A?B∨C，B??A，D??CA??D
(1)A 附加前提 (2)A?B∨CP
(3)B∨CT(1)(2)，I (4)B??A P (5)A??B T(4)，E (6)?B T(1)(5)，I (7)CT(3)(6)，I (8)D??C P
(9)?D T(7)(8)，I (10)A??DCP
三、（10分）证明?x?y(P(x)?Q(y))?(?xP(x)??yQ(y))。 ?x?y(P(x)?Q(y))??x?y(?P(x)∨Q(y))
??x(?P(x)∨?yQ(y)) ??x?P(x)∨?yQ(y) ???xP(x)∨?yQ(y) ?(?xP(x)??yQ(y))
四、（10分）设A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。 解 P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}}
P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}}
五、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}
(1)画出R的关系图。 (2)写出R的关系矩阵。
(3)说明R是否是自反、反自反、对称、传递的。 解 (1)R的关系图如图所示： (2) R的关系矩阵为：
?1
??0
M(R)??
1??1?
反自反的；由于矩阵不对称，R不是对称的；
经过计算可得
10111011
0??0? 0??0??
(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是
?1
??0
M(R2)??
1??1?
10111011
0??0?
?M(R)，所以R是传递的。 ?0?0??
六、（15分）设函数f：R×R?R×R，f定义为：f(<x，y>)＝<x＋y，x－y>。 (1)证明f是单射。 (2)证明f是满射。 (3)求逆函数f。
(4)求复合函数f?f和f?f。
证明 (1)对任意的x，y，x1，y1∈R，若f(<x，y>)＝f(<x1，y1>)，则<x＋y，x－y>＝<x1＋y1，x1－y1>，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射。
(2)对任意的<u，w>∈R×R，令x＝
－1－1
u?wu?wu?wu?wu?w
，y＝，则f(<x，y>)＝<＋，－22222
u?w
>＝<u，w>，所以f是满射。 2
(3)f(<u，w>)＝<
－1－1
u?wu?w
，>。 22
－1
－1
(4)f?f(<x，y>)＝f(f(<x，y>))＝f(<x＋y，x－y>)＝<
x?y?x?yx?y?(x?y)
，>＝<x，y>
22
3
3
4
4
4
5
5
5
f?f(<x，y>)＝f(f(<x，y>))＝f(<x＋y，x－y>)＝<x＋y＋x－y，x＋y－(x－y)>＝<2x，2y>。
七、（15分）给定群<G，*>，若对G中任意元a和b，有a*b＝(a*b)，a*b＝(a*b)，a*b＝(a*b)，
3