苏XI友离散数学模拟试题2.doc
文本预览下载声明
离散数学模拟试题2
单选题(本大题共8小题,每小题2分,共16分)
1.设p:天下大雨,q:我们乘公共汽车。命题“除非天下大雨,否则我们不乘公共汽车。”符号化为 ( )
A. p q B. q p C. p∧q D. q p
2.设N x :x是自然数,H x,y :y是x的后继数。 命题“每个自然数都有后继数.”符号化为( ).
A.?x N x ?y N y ∧H x,y B.?x N x ∧?y N y H x,y C.?x N x ?y N y ∧H x,y D.?x N x ?y N y ∧H x,y 3.设集合A { ,a},下面四个命题为真的是 ( )
A. a A B. A C.{ } A D.{a} A
4.设集合A {a,b,c,d},A上的关系R {〈a,b〉,〈b,a〉, 〈c,d〉,〈d,c〉}∪IA,则下面命题为真的是 ( )
A. R是A上的等价关系 B. R是A上的偏序关系
C. R是A上的全序关系 D. R是A上的全域关系
5.设V 〈N,+〉,其中N为自然数集合,+为数的普通加法。令φ:N→N, φ() 2。下面四个命题为真的是 ( )
A.是满同态 B.是单自同态
C.是自同构 D.是V到自身的映射,但A,B,C都不是
6.设Z是整数集合,∩是Z的幂集P(Z)上的交运算。
令V 〈P(Z);∩〉,则V是 ( )
A.循环群 B. 有限群 C. 无限群 D. 含幺半群
7.设G是有n 个顶点m 条边的无向简单图, 并且m n-1,则有结论 ( )
A. G一定是树 B. G不一定是树 C.G一定不是树 D.G是森林
8.完全图K4是 ( )
A. 欧拉图 B.二部图 C.平面图 D.非平面图
填空题(本大题共8小题,每小题3分,共24分)
1.含n个命题变项的矛盾式的主析取范式为 。
2.设个体域为实数集合R,命题 x y x+y 1 的真值为 。
3.设A {a,b},IA是A上的恒等关系,则商集A/IA 。
4.设S {1,2,3,4},则S上的4元对称群是 阶群。
5.群中唯一的幂等元是 。
6.设Z是整数集合,×是数的乘法运算. 令V 〈Z,×〉,则命题“V是群”的真值为 。
7.两个同构的图的顶点数一定 。
8.设二元正则树T的顶点数为n,则n必为 数。
简答题(本大题共8小题,每小题5分,共40分)
1.用主析取范式法判断命题公式 pq →r的类型。
2.给定解释I如下:D {1,2},P 1,1 P 2,2 0,P 1,2 P 2,1 1。
求 xyP x,y 在解释I下的真值。
3.设A {1,2,3},A上关系R {〈1,1〉,〈1,2〉,〈2,1〉,〈2,2〉,〈3,1〉,〈3,3〉},
写出R的关系矩阵;
画出R的关系图;
并确定R具有哪些性质。
4.设集合A {2,3,5,7,8,12},A上的偏序关系R {〈x, y〉∣x能整除y}。求出集合A的极小元、极大元、最小元、最大元、上界、下界、最小上界、最大下界。
5.设〈L ,∧ ,∨〉是格, a, b∈L ,验证:a∧ b a?a∨b b。
6.设R为实数集合,?定义为:对任意x,yR,有x?y x + y – x y,这里+、-为数的加法和减法运算。验证:〈R,?〉是否为群。
7.画出带权为2,2,5,5,10,11的最优树T,求T对应的前缀码,计算T的权。
8.设10阶平面图G有5个面,求G中的边数。
证明题(本大题共4小题,每小题5分,共20分)
1.在命题逻辑中构造下面推理的证明
前提:q→p, p∨r,q∨s.
结论: r→s .
2.设R是集合A上的关系,证明:R是反自反的当且仅当R∩IA 。
3.设群G中含有2阶元a(即2是使ak e的最小正整数,其中e为单位元),证明与a 可交换的元素构成G的子群。
4.试证明:简单连通无向图G的任何一条边,都是G的某一棵生成树的边。
2
显示全部