山东师范大学硕士研究生入学考试试题
考试科目：离散数学
注意事项：1.本试卷共8道大题(共计11个小题),满分150分；
2.本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划；
3.必须用蓝、黑钢笔或圆珠笔答题，其它均无效。
4.考试结束后将本卷装入试题袋内，不得带走，否则以违纪论处。***************************************
1.(20分)设A={4,|ieJ}是一个集合族，B是一个集合，试判断下面四个集合
(①B((2)(3)(4)间的包含或相等关系并给与证明.
2.(20分)设A={a,b,c},p(A)为A的幂集，(1)试证(p(A),三〉为偏序集。
(2)画出它的哈斯(Hasse)图
(3)求出{a},{c}}的上界、下界、上确界和下确界。
3.(20分)设A={x|x∈I,1≤x≤9},,其中I为正整数集合，在A×A上定义如下关系：
R:(a,b),(c,d)∈R当且仅当a+d=b+c。
试证明R为A×A上的等价关系，并写出(2,5)的等价类。
4.(20分)1)求下式的主析取范式：
(PvQ)人(QvR)^(-PvR)
2)用逻辑推理规则证明：
Vx(P(x)vQ(x))→VxP(x)v3xQ(x)。
5.(15分)设(H,)和(K,o〉是群〈G,o)的两个子群，令HK={hok|h∈H,k∈K},求证：(HK,o)是(G,o)的子群的充分必要条件是HK=KH。
6.(15分)设f:X→Y,g:Y→X,试证：若g。f为X上的恒等函数，则f是入射，g是满射。
7.(20分)试分析图G与其补图G间连通性的关系，并证明你的结论。
8.(20分)G为m条边的连通平面图，其每个面至少由k条边围成(k≥3),试证其点数不少于
第页共1页
山东师范大学
硕士研究生入学考试试题
考试科目：离散数学
注意事项：1.本试卷共8道大题(共计个小题),满分150分；
2.本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划：
3.必须用蓝、黑钢笔或圆珠笔答题，其它均无效。
4.考试结束后将本卷装入试题袋内，不得带走，否则以违纪论处。
**率***率*率率率****率******************
1.(20分)已知
,并证明你的结论。
2.(15分)设∑为26个英文字母构成的集合，A为∑上的所有有限字符串的集合，B为由0和1构成的无限序列的集合，试问A与B是否等势，并证明你的结论。
3.(25分)设A={2,3,4,6,8,12},R为A上的整除关系，B={2,3},C={8,12}。
①试证R为A上的偏序关系
②画出〈A,R)的哈斯(Hasse)图
③给出B和C的上界、下界、上确界和下确界。
4.(20分)设{A,*〉为半群。今有如下两个条件：
(1)〈A,*)满足消去律；
(2)对Va,b∈A,方程a*x=b与y*a=b有解。
试说明上述各条件分别是〈A,*〉为群的哪种条件(指充分必要条件、充分条件和必要条件)?并证明你的结论。
5.(15分)求(P→QR)へ(-P→(一Q-R))的主析取范式。
6.(20分)先符号化下列命题，然后推证其结论。
“若任意有理数都是实数，必有如下结论：即对任意的x,如果任意一个有理数都与x同类，则必有一个实数与x同类。”
7.(15分)在n个乒乓球队员中安排比赛，已经赛完n+1场(每两人比赛算一场),试证明至少有一个队员参加过至少3场比赛。
8.(20分)试分析图G与其补图G之间连通性的关系，并证明你的结论。
第1页(共1页)
山东师范大学
硕士研究生入学考试试题
考试科目：离散数学
注意事项：1.本试卷共10道大题(共计26个小题),满分150分；
2.本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划：
3.必须用蓝、黑钢笔或圆珠笔答题，其它均无效。
**本*本*******************************