一、单项选择题：（每小题1分，本大题共15分）
1．设a=，下面（ ）集合等于a 。
a、，，下列各式中是错的。
ab、a；c、}ad、a 。
3．六阶群的子群的阶数可以是。
a、1，2，5； b、2，4； c、3，6，7； d、2，3 。
4．设，下列各式中是正确的。
a、 domsb ； b、domsa； c、ransa； d、doms rans = s
5．设集合，则空关系不具备的性质是。
a、自反性； b、反自反性； c、对称性； d、传递性。
6．下列函数中是入射函数。
a、世界上每个人与其年龄的序偶集； b、、世界上每个人与其性别的序偶集；
b、 一个作者的专著与其作者的序偶集； d、每个国家与其国旗的序偶集。
7．是群，则对。
a、满足结合律、交换律b、有单位元，可结合；
c、有单位元、可交换d、每元有逆元，有零元。
8．下面（ d ）哈斯图所描述的偏序关系构成分配格。
9．下列中的运算符都是可交换的。
a、； b、； c、； d、。
10．设g是n个结点、m条边和r个面的连通平面图，则m等于。
a、n+r-2 ； b、n-r+2 ； c、n-r-2 ； d、n+r+2 。
11．n个结点的无向完全图的边数为。
a、； b、； c、； d、。
12．下列图中是根树。
a、；b、；
c、；d、。
13．设p：2×2=5，q：雪是黑的，r：2×4=8，s：太阳从东方升起，下列命题的真值为真。
a、； b、； c、； d、。
14．下面命题公式是重言式。
ab、； c、； d、。
15．设l(x)：x是演员，j(x)：x是老师，a(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为。
ab、；c、； d、。
二、填空题：（每空1分，本大题共15分）
1．设，则 （r为实数集），。
（1）说明是否构成群； （2）在中解方程。
4．将公式划为只含有联结词的等价公式。
五、证明题：（共30分）
1．设，在上定义关系当且仅当，证明是上的等价关系，并求出。
2．用cp规则证明，，
3．将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。
5．证明：若t是有n个结点的完全二叉树，则t有片叶子。
一、单项选择题：
二、填空题：
1．；。2．；。3．以主对角线为对称的元素不能同时为1；
两个不同结点间的定向弧线，不可能成对出现。4．满射；入射。
三、判断改正题：
1．× 若，则不一定。 2．√
3．× b的极大元但可以不唯一。 4．√
5．× 运算*不一定可结合6．× 有限整环一定是域，但反之不成立。
7．× 有割点的连通图不可能是汉密尔顿图。 8．√
9．× 无多重边和自环的图是简单图。 10．√
四、简答题：
1．解：若是自反的，则也是自反的。因为。
自反，，从而 ，即也是自反的。
若是对称的，但不一定是对称的。
如：a = 则是对称的，但不是对称的。
2．要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得：
其最小生成树为：
其树权即最小造价为：1+2+3+5+7=18。
3．解：（1）1），即运算*是封闭的。
而。即*可结合。
3）设s关于*有幺元e，则。
而 。4）设有逆元。则，即 ，，即 s中任意元都有逆元，综上得出，构成群。
2）由，。4．解：原式。
五、证明题：
1．证明：1）即r自反。
即，即r对称。
从而 ，即 r传递。
综上得出，r是等价关系。
且。2．证明：（1） bp(附加前提)
（2p3t(1)(2)i
4) at(3)i
5p6t(4)(5)i
7) ct(6)i
8p9t(7)(8)i
(10t(9)e
(11) et(10)i
(12cp
离散数学试卷A
2011 2012 课程名称 离散数学考试时间120分钟 一 填空题 每空2分，共16分 1 已知个体域是 p 1,1 1 p 1,2 1,p 2,1 0,p 2,2 0,则公式xy p x，y 的真值为。2 公式 x p x y q x,y 的前束范式为。3 设二元关系f g a 则fdom f。...
离散数学试卷
一 判断题。1.设g为无向图，若g中恰好n个结点，n 1条边，则g必为一棵树。2.若a b，则p a p b 3.设g为无向图，若g无回路，则g必为一棵树。4.设a，b是集合，若a b，则p a p b 5.无向图g是欧拉图当且仅当g连通且具有零个或两个奇数度结点。6.设a,b是任意集合，则 a b...
离散数学试卷 A
2014 2015学年第二学期。每题10分，共100分，答案一律写在答题纸上 1.化为主析取范式与主合取范式。2.证明 3.甲 乙 丙 丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的 1 甲和乙只有一人参加 2 丙参加，丁必参加 3 乙或丁至多参加一人 4 丁不参加，...