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

广东工业大学试卷用纸，共5页，第1页学院：专业：班级学号：姓名：装订线广东工业大学考试试卷(A卷)课程名称:离散数学试卷满分100分考试时间:2015年1月12日(第19周星期一)题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、单项选择题(本大题共5小题，每小题4分，共20分)1.幂集P(P(P()))为()(A){{},{,{}}}.(B){,{,{}},{}}.(C){,{,{}},{{}},{}}(D){,{,{}}}.2.设RAA，SAA，则下述结论正确的是().(A)若R和S是自反的，则RS是自反的。(B)若R和S是对称的，则SR是对称的。(C)若R和S是反对称的，则SR是反对称的。(D)若R和S是传递的，则RS是传递的。3.设集合A={1,2,3,4,5}上的关系R={(x,y)|x,yA且x+y=6}，则R的性质是().(A)自反的.(B)对称的.(C)对称的、传递的.(D)反自反的、传递的。4．下列次序集不是偏序集和全序集的是（）。A．,NB．,ZC．}),({aPD．),(NP5.4阶完全无向图4K中含3条边的不同构的生成子图有(A)3(B)4(C)5(D)2广东工业大学试卷用纸，共5页，第2页二、填空题(本大题共5小题，每小题4分，共20分)1.设集合A={a,b,c,d,e}上的的划分S={{a，d}，{b}，{c，e}}，则由划分S所确定的A上的等价关系R=。2.设A={1,2,3,4,5}上的关系R={(1,2),(3,4),(2,2)},S={(4,2),(2,5),(3,1),(1,3)},则SR{},RS{},RR{}。3.令Z(x):x是整数，O(x):x是奇数，则“不是所有整数都是奇数”符号化为()。4.设有向图G=(V,E)，V={v1，v2，v3，v4}，若G的邻接矩阵A=1001001111011010,则v1的出度deg+(v1)=______2__,v1的入度deg-(v1)=_____3___,从v2到v4长度为2的路有_____2___条。5.不同构的5阶无向树有(3)棵，不同构的5阶根树有(9)棵。三、(10分)设集合A={a,b,c},P(A)是集合A的幂集,试画出偏序集,P(A)的哈斯图,并指出子集{{a},{b}}的极大元、极小元、最大元、最小元、上界、下界、最小上界和最大下界。四、(10分)设p,q,r为命题变元，用等值演算法计算(p→q)→r的主合取范式。五、(10分)设R和S是集合A上的对称关系，证明SR对称的充要条件是RSSR.六、(10分)用CP规则证明下列推理.sqpsrqrqp),(),(.七、(10分)用构造法证明：)))()(()((xRyQxPx，)(xxP))()(()(xRxPxyQ.八、(10分)用哈夫曼算法求带权为1,3,5,7，8,11,12的最优二元树并计算此最优树的权。广东工业大学试卷用纸，共5页，第3页学院：专业：班级学号：姓名：装订线广东工业大学考试答题纸课程名称:离散数学试卷满分100分考试时间:2015年1月12日(第19周星期一)题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、单项选择题(本大题共5小题，每小题4分，共20分)12345CABDA二、填空题(本大题共5小题，每小题4分，共20分)1.{(a,a),(b,b),(c,c),(d,d),(e,e),(a,d),(d,a),(c,e),(e,c)}2.{(1,5),(3,2),(2,5)},{(4,2),(3,2),(1,4)},{(1,2),(2,2)}.3.))()((xOxZx.4.3,2,25.3,9三、（10分）解：{}{a,b,c}{a,c}{a,b}{b,c}{b}{c}{a}{Ø}（4分）极大元{a},{b}，极小元{a},{b}，没有最大元和最小元，上界是{a,b},{a,b,c}，下界是，最小上界是{a,b}，最大下界是。（8分）广东工业大学试卷用纸，共5页，第4页极大元{a},{b}，极小元{a},{b}，没有最大元和最小元，上界是{a,b},{a,b,c}，下界是，最小上界是{a,b}，最大下界是。（10分）四、解：rqprqp)()(rqp)(（2分）rqp)()()(rqrp（4分）))(())((rqpprqqp（7分）)()()(rqprqprqp（10分）五、证明：由于R和S是对称的，所以SSRR11,.（1分）()因为RSSR，两边取逆得11)()(RSSR，而（2分）SRSRRS111)(.所以SRSR1)(，因此SR是对称关系.（6分）()由于SR对称，所以SRSR1)(.（8分）而RSRSSR111)(，因而RSSR.（10分）六、证明(1)qP(附加)（1分）(2))(srqP(3)srT(1)(2)I（3分）(4)pP(5)P(6)rqT(4)(5)I（7分）(7)rT(1)(6)I（8分）(8)sT(3)(7)I(9)sqCP（10分）sqpsrqrqp),(),()(rqp广东工业大学试卷用纸，共5页，第5页七、证明(1))(xxPP(2)P(c)US(1)（1分）(3))))()(()((xRyQxPxP(4)))()(()(cRyQcPUS(3)（3分）(5))()(cRyQT(2)(4)I（5分）(6)Q(y)T(5)I(7)R(c)T(5)I(8))()(cRcPT(2)(7)I（7分）(9)))()((xRxPxUG(8)（9分）(10)))()(()(xRxPxyQT(6)(9)I（10分）八、（10分）解：4727201112945137158（8分）权1222)1211(3)875(4)31()(TW（10分）