*密*第页共NUMPAGES2页西南科技大学2008——2009学年第2学期《离散数学(J)》期末考试试卷（B卷）课程代码143140320命题单位计算机学院：数学与算法课程组学院:_______________班级:_____________姓名:_______________学号:____________基础题（共60分）(4分)求下列集合的幂集(1){1，{2，3}}(2){，{}}(6分)判断公式((PQ)(QR))(PR)的类型。(8分)求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式。(8分)设A、B为两个集合，证明A-B=A当且仅当AB=。(8分)假设A={1，2，3}，R是AA上的等价关系，且<<a,b>,<c,d>>Ra*b=c*d.(*代表算数乘)(1)假设I为AA上恒等关系，给出I，并求R-I。(2)求R对应的AA的划分。(10分)设A={0，1，2，3}，RAA，其中R={<x,y>|x=yx+yA}(1)求R的关系矩阵M(R)和关系图G(R)。(2)讨论R的性质。(3)构造R的对称传递闭包。(6分)画出下述偏序集的哈斯图，并指出A的最大元、最小元、极大元、极小元。偏序集为<A,>,其中A={a,b,c,d,e},=IA{<a,b>,<a,c>,<a,d>,<a,e>,<b,e>,<c,e>,<d,e>}(10分)一颗无向树T，有nt个t度顶点，t=2，3，…k，其余顶点都是树叶，问T有几片树叶？西南科技大学2008——2009学年第2学期《离散数学(J)》期末考试试卷（B卷）综合题（共40分）(15分)在自然推理系统F中，构造下面推理的证明：任何自然数都是整数，存在着自然数，所以存在着整数。个体域为实数集R。设F(x)：x为自然数，G(x)：x为整数(10分)在1到10000之间既不是某个整数的平方，也不是某个整数的立方的数有多少个？（要求应用容斥原理求解）(15分)用Dijkstra算法求下图所示有向带权图中v1到其余各顶点的最短路径及其权值。（要求写出计算过程）