2006-2007(上)离散数学试卷(a)
一、判断题：（每小题1分，共6分）
1、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。 （1 ）
2、以下两个谓词公式存在等价关系：。 0 ）
3、若，则1 ）
4、如果一个群不是abel群，那么这个群中的任意两个元素之间的运算都不可交换。 （
5、设无向图g具有割点，则g中一定不存在哈密尔顿通路0 ）
6、如果能将无向图g画在平面上，若边与边之间有交叉，则g必为非平面图。 （1 ）
二、填空题（每空2分，共22分）
1、公式的类型是___重言式___
2、设f(x)：x是人，h(x, y)：x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为。
3、的前束范式是：
4、s，t为集合，为空集，那么的真值为___0___
5、某班有54个学生，其中有29人买了语文参考书，有22人买了数学参考书，有11人两种书都没有买。那么既买了语文书又买了数学书的人有___14___个。
6、设a=，a上关系p=，则。
p 27、设集合a=上定义了两个二元运算和，其运算表如下：
则满**换律且有幺元的是运算有幂等性且不满**换律的运算是。
8、 假定连通平面图有10个顶点，每个顶点的度数皆为2，则该平面图的面数为 2 个。
9、设g1，g2，g3，g4都是4阶3条边的无向简单图，则它们之间至少有__3___个是同构的。
10、图g是由5棵树构成的一森林，g有20个顶点，那么g有___15___条边。
三、解答题（34分）
1、（6分）给定解释如下：
求公式和的值。
2、（6分）设a=，r是a上的二元关系，其关系图如下所示，试用关系矩阵求最小自然数s，t，使s
3、（8分）设代数系统v=< z6, >z6=，为模6乘法。
1）求出所有可逆元素关于运算的逆元。
2）说明v构成什么代数系统。为什么？
5、（4分）求出以2，5，11，23，31，47，59，79为给定权的最优二叉树。
四、证明题（每小题7分，共28分）
1、证明下面的蕴含式（方法不限）：
2、设a，b，c为任意集合，已知，并且，证明：
3、设是任一群，定义为，试证r是g上的等价关系。
4、设g是无向连通简单图，已知δ(g)≥2 。证明：g中存在长度大于等于3的初级回路。
五、应用题（10分）
三人估计比赛结果，甲说“a第一，b第二。”；乙说“c第二，d第四。”；丙说“a第二，d第四。”；结果三人估计的都不全对，但都对了一半，求a、b、c、d的名次。
离散数学试卷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 丁不参加，...