广东工业大学离散数学试卷和答案-2015A

广东工业大学试卷用纸，共6页，第1页学院：专业：班级学号：姓名：装订线广东工业大学考试试卷(A卷)课程名称:离散数学试卷满分100分考试时间:2015年1月12日(第19周星期一)题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、单项选择题(本大题共5小题，每小题4分，共20分)1.设A,B,C是集合，则下述论断正确的是().(A)若AB，BC，则AC.(B)若AB，BC，则AC.(C)若AB，BC，则AC.(D)若AB，BC，则AC.2．设N是自然数集，Z是整数集，对于任意xZ,令f:ZN,f(x)=|x|,则f()A．仅是单射B．仅是满射C．是双射D．不是函数3.下列次序集既是偏序集又是全序集和良序集的是（）。A．,NB．,ZC．),(NPD．}),({aP4.一棵树有3个5度结点、1个4度结点、3个2度结点，其它的都是1度节点，那么它的边数是（）(A)19(B)18(C)17(D)20.5.3阶完全无向图3K的不同构的生成子图有()个。(A)2(B)3(C)4(D)5二、填空题(本大题共5小题，每小题4分，共20分)1.设X是非空集合，则X的幂集P(X)关于集合的运算的单位元是，零元是，P(X)关于集合的运算的单位元是，零元是。广东工业大学试卷用纸，共6页，第2页2．集合A={a,b,c,d,e}上的等价关系R={(a，a)，(b，b)，(c，c)，(d，d)，(e，e)，(a，c)，(a，e)，(c，a)，(c，e)，(e，a)，(e，c)}所对应的等价类分别为，R所对应的划分为。3．设A={2，4，5，10，12，20}，R为A上的整除关系，则A的子集B={4，10，12}的极大元为，极小元为，上界为，下界为。4.设有向图G=(V,E)，V={v1，v2，v3，v4}，若G的邻接矩阵A=1001001111011010,则v1的出度deg+(v1)=________,v1的入度deg-(v1)=________,从v2到v4长度为2的路有________条。5.当n时，n阶完全无向图nK是平面图；当n时，nK是Hamilton图，当n为时，nK是欧拉图。三、(12分)设},,,{dcbaA,A上的关系)},(),,(),,(),,(),,(),,(),,(),,(),,{(cdbdadccbcaccabaaaR,1.画出R的关系图RG。2.判断R所具有的性质。3.求出R的关系矩阵RM。4.求)(2RSR和四、(8分)利用等值演算法求(P∧Q)→(P∧Q)的主析取范式。五、(10分)用演绎法证明下述论断的正确性。.,,,,QTRSTSRPQP六、(10分)符合化下列命题，并构造推理证明：有理数都是实数，有些有理数是整数，所以有些实数是整数。七、(10分)计算有13片树叶，分别赋权2，3，5，7，11，13，17，19，23，29，31，37，41的Huffman树。八、(10分)用有序树表示代数式)11/3())/43()2((xba。广东工业大学试卷用纸，共6页，第3页学院：专业：班级学号：姓名：装订线广东工业大学考试答题纸课程名称:离散数学试卷满分100分考试时间:2015年1月12日(第19周星期一)题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、单项选择题(本大题共5小题，每小题4分，共20分)12345CBDAC二、填空题(本大题共5小题，每小题4分，共20分)1.，X；X.，。2.{a,c,e},{b},{d};{{a,c,e},{b},{d}}3.10，12;4，10;无；24.2,3,2.5.4，3，奇数。三、(12分)解1.R的关系图RG如下：广东工业大学试卷用纸，共6页，第4页2.(1)由于Rbb),(，所以R不是自反的。(2)由于Raa),(，所以R不是反自反的。(3)因为Rbd),(，而Rdb),(，因此R不是对称的。(4)因Racca),(),,(，于是R不是反对称的。(5)经计算知RcdbdadccbcaccabaaaRR)},(),,(),,(),,(),,(),,(),,(),,(),,{(，进而R是传递的。综上所述，所给R是传递的。3.R的关系矩阵0111011100000111RM。4.)},(),,(),,(),,(),,(),,(),,(),,(),,{(2cdbdadccbcaccabaaaRRR)},(),,(),,(),,(),,(),,(),,(),,(),,(),,(),,(),,(),,(),,{()(dccddbbddaadcccbbcaccaabbaaaRS四、(8分)解(P∧Q)→(P∧Q)=(P∧Q)∧(P∧Q)=P∧Q=(P∧Q)∧(P∧Q)∧(P∧Q)∧(P∧Q)=(P∧Q)∧(P∧Q)∧(P∧Q)五、(10分)证明PT)1(PTS)2(（1分）)2)(1(,)3(TS（2分）PRS)4(（3分）)4)(3(,)5(TR（4分）PRP)6(（5分）)6)(5(,)7(TP（6分）PQP)8(（7分）)8)(7(,)9(TQ（8分）六、(10分)证令Z(x):x是整数,Q(x):x是有理数,R(x):x是实数))()(())()(()),()((xZxRxxZxQxxRxQx(1)))()((xZxQxP(2))()(cZcQES(1)(3)Z(c)T(2)I(4)Q(c)T(2)I(5)))()((xRxQxP(6))()(cRcQUS(5)广东工业大学试卷用纸，共6页，第5页(7)R(c)T(4)(6)I(8))()(cZcRT(3)(7)I（9）))()((xZxRxEG(8)七、(10分)解：八、(10分)解)11/3())/43()2((xba的有序树表示如下：2389514342536578122233341111175523广东工业大学试卷用纸，共6页，第6页--++2a3/4bx/311-