离散数学A卷及答案.doc

课程考试试题学期学年 2011-2012 2 离散数学（A卷） 拟题人: 校对人:拟题学院（系）: 适 用 专 业: 高密校区 2011级计专、软专 （答案写在答题纸上，写在试题纸上无效）一、单项选择题（每小题2分，共20分）1下列为两个命题变元，的最小项的是（）A B C D 2下列语句中是真命题的是（）A我正在说谎B严禁吸烟C如果1+2=3，那么雪是黑的D如果1+2=5，那么雪是黑的3在公式F（x，y） yG（x，y）中变元x是（）A自由变元B约束变元C既是自由变元，又是约束变元D既不是自由变元，又不是约束变元4集合A=1，2，10上的关系R=（x，y）|x+y=10，xA，yA，则R的性质是（）A自反的B对称的C传递的、对称的D反自反的、传递的5设论域为l，2，与公式等价的是( )A.A(1)A(2)B. A(1)A(2)C.A(1)D. A(2)A(1)6. 下列关系矩阵所对应的关系具有反自反性的是（）ABCD7. 在自然数集N上，下列运算是可结合的是（）A B C D 8.设A是奇数集合，下列构成独异点的是( )A. B. C.D. 9. 右图的最大入度是( )A0 B1 C2 D3 第9题图10. 设G为有n个结点的简单图，则有（）A(G)n B(G)n C(G)n D(G)n二、填空题(每空2分，共20分)1设A=1，2，3，4，B=2，4，6，则A-B=_，AB=_。2设S是非空有限集，代数结构（P（S），）中，其中P（S）为集合S的幂集，则P（S）对运算的单位元是_，零元是_。3设fRR,f(x)=x+3,gRR,g(x)=2x+1,则复合函数,。4设有向图G=（V, E）,V=v1,v2,v3,v4,若G的邻接矩阵，则deg-(v1)=_ _,deg+(v4)=_。5给定集合A=1,2,3,4,5，在集合A上定义两种关系：R=（1,2）,（3,4）,（2,2）,S=（4,2）,（2,5），（3,1）,（1,3），则，。三、解答题（6个小题，共60分）1（10分）设A=,，为整除关系。（）画出（A，）的哈斯图；（）求子集，的极大元、极小元、最大元、最小元。2（10分）构造命题公式（PQ）P）R的真值表。3（10分）求命题公式A=P（QP）（PQ）的主析取范式和主合取范式。 4（10分）证明：(AB)，BC, C A.5（10分）设图G有n个结点，n+1条边，证明：G中至少有一个节点度数3。6（10分）用矩阵的方法求下图中节点u1，u5之间长度为2的路的数目。 20112012 学年 2学期 离散数学 （A卷） 试题标准答案拟 题 人： 书写标准答案人： 拟题学院（系）： 高密校区 适用专业： 2011级计专、软专 （答案要注明各个要点的评分标准）一、单项选择题（每小题2分，共20分）1（）2 ()；3（C）；4（）；5. (A) 6（）7 ()；8（）；9（）；10. (). 二、填空题(每空2分，共20分)11，1，； 2, ； 32x+, 2x+； 43,1； 5(1,5),(3,2), (2,5)，(4,2),(3,2), (1,4)三、解答题（6个小题，共60分）1.解：（） 哈斯图： 5分 （），的极大元：，。极小元：。最大元：无。最小元：10分 2. 解： PQPQPQP（PQ）P）R1111111010011 10分3.解：A= P（QP）（PQ） =P（QP）（PQ） =P（QPQ）（PPQ） =P（00） =P5分 所以A的主析取范式P（QQ）（PQ）（PQ）7分A的主合取范式P（QQ）（PQ）（PQ）10分4证明：（）BC 分（）C P（） 分 （）B T (1) (2)I 5分 （）(AB) P 分（）AB （）E 8分（）A T (3) (5)I10分5.证明： 设图有n个节点边数为n+1 1分 假设任意节点其度数，则 5分 又因为节点度数总和等于边数两倍，即 8分 所以，这是个矛盾。故不可能每个节点度数小于等于2，即至少有一节点度数大于等于3 10分6.解： 邻接矩阵 4分 8分所以，图中节点u1，u5之间长度为2的路有条。10分