春离散数学试卷B

1、本大题 得分本大题 得分A. 1.本大题 得分题号-一一-二三四五六七总分应得分16154425100实得分评卷人：一、单项选择题(本大题共8小题，每题2分，共16分) 在每题列出的四个备选项中只有一个 是符合题目要求的，请将其代码填入题后的括号内。错选、多项选择或未选均无分。1. 以下说法中，不正确的选项是(D ).A. 10阶4-正那么图的边数等于20.B. 图G连通的充分必要条件是P(G)=1.C. n阶无向简单图中，完全图的边数最多.D. 一个图中偶度顶点的个数一定是奇数2. A = n,以下式子中，正确的选项是(D ).A. A A 2n。 B. P(A A)n2.C. |P(A A

2、)|22n. D. |P(A A)|2n3. H=x,y,z,H 上的关系 R=<x,z>是(C ).A.自反关系、反对称关系和传递关系.B.自反关系、对称关系和传递关系.C.反自反关系、对称关系和传递关系.D.反自反关系、反对称关系和传递关系4. 一阶谓词逻辑中，公式B不含 x,以下式子中成立的是(C ).A.x( (x)x (x)B.x( (x)x (x)C.x( (x)x (x)D.x(x)x (x)A .两个素数的差是奇数.B. 如果6是素数，那么66也是素数.C.两个素数的差是偶数.D. 两个素数的差是偶数吗？6. R是非空集合H上的关系，那么以下说法中不正确的选项是(

3、C ). A . R是自反的 Ih R B. R是对称的 R的关系矩阵是对称的.C. R不是反自反的 R是自反的. D. R是传递的 R2 R7. 以下说法中，不正确的为(D ).A.无向6阶完全图的边数是奇数.B. 在任何图中，所有顶点的度数之和一定是偶数.C. 图G不连通的充分必要条件是其连通分支数P(G) >2.D. 二部图中的圈都是奇圈.8. 含2个变项的命题公式pV q的全部成真指派有( C )个B. 2. C. 3.D. 4.二、填空题(本大题共5小题，每题3分，共15分)在每题的空格内填上正确答案。错填、不填均无分。1. 设全集 E=1 , 2, 3, 4, 5，A=1，4

4、，B=1 ,5 ,2，贝卜A A B= 2,5.2. 令p:我带伞;q:下雨，那么命题只有下雨我才带伞可符号化为：q_.3. 令F(x): x是飞机；G(y): y是汽车；H (x, y): x比y快。那么命题 飞机都比汽车快可符号化为：一-/x-/y( F(x)八G(y) -_ H(x, y).4. 非空集合A上的关系R如果满足条件IA R_,那么R是自反关系5. 给出如以下图G.:那么有 d(C)= 3, (G)=_, P(G)=2.三、计算题(本大题共2小题，第1小题20分，第2小题24 分，共44分).5.以下语句中，一定是真命题的有(B ).得分1 写出(n pVq-r)类型p的真值

5、表和所有成假指派，并确定公式的pqrn pn pV q(n pV qr(n p V q r)p00011010011110010110101111101000011101001111001001110111真值表得分 |2.设 A=a,b,c,d,e,R=I aU <a,b>,va,c>,va,d>,va,e>,vb,e>,<c,e>,vd,e>.2(1) .计算 s(R)与 R;(8 分)(2) .简要说明R是偏序关系,并画出R的哈斯图；(8)成假指派：(1) .S(R)=RUR-1= I aUP,q,r成假指派 <0,0,1>

6、;,<0,1,1>,v1,1,0>va,b>,vb,a>,va,c>,<c,a>,va,d>,vd,a>,va,e>,ve,a>,vb,e>,ve,b>,vc,e>,ve,c>,<d,e>,<e,d>.(n p V qr)p为可满足式R°=IaR1=R)o R=R= IaU <a,b>,<a,c>,<a,d>,<a,e>,<b,e>,<c,e>,<d,e>R =Ro R= I aU

7、<a,b>,va,c>,va,d>,va,e>,vb,e>,<c,e>,vd,e>(3) .指出A的最大元、最小元、极大元、极小元；(4分)(4) .A的子集B=a,b，求B的上界、下界、上确界、下确界 。(4分)(2) Ia R R 自反R n R1包含Ia R反对称R。R包含R R传递B ) 第2页(共4页)所以R为偏序关系本大题 得分四、证明题本大题共2小题，第1小题15分，第2小题10分，共25分.得分1.证明:3.A的最大元：e证明：过程见P480例15 2题最小元：a极大元：e极小元：a4B的上界：b,e下界：a上确界：b下确界：a得分5就是6.证明G中至少有52.设9阶无向图G中，每个顶点的度数不是 个6度顶点或至少有6个5度顶点.130页第2题证明：有握手定理，9个顶点情况有:10个5