2007广东工业大学 离散数学A.doc

6、下面等式中唯一的恒等式是 [ ] 　　A. (A∪B∪C)-(A∪B)=C B. A⊕A=A 　　C. A-(B×C)=(A-B)×(A-C) D. A×(B-C)=(A×B)-(A×C) 7、设R为实数集，定义* 运算如下：a*b=|a+b+ab|，则 * 运算满足 [ ] 结合律 B. 交换律 C. 有幺元 D. 幂等律 8、对于集合A＝｛0、1、2、3、4、5、6、7、8、9、10｝，不封闭的二元运算是[ ] A x*y=max(x,y) B x*y=x－y C x*y=(x+y)mod 9 D x*y=min(x,y) 二、填空题(本大题共10小题，每空3分，共24分) 9、含n个命题变项的重言式的主合取范式为_________________________。 10、设个体域为整数集合Z，命题Vxヨy(x+y=3)的真值为___________。 11、以1，1，1，2，2，3为度数序列的非同构的无向树共有___________棵。 12、已知n阶无向简单图G有m条边，则G的补图G有__________条边。 13、设R={{1}, 1，1, {1}，2, {3}，{3}, {2}}，则domR⊕ranR=_____________________。 14. 设A={1, 2, 3, 4}，则A上有____________个不同的双射函数。 15. 设σ=(1345)(2678)是8元置换，则σ-1=___________。 16、集合A＝｛1、2、3、4｝上的恒等关系是_________________________。 三、 简答及证明(本大题共6小题，每小题10分，共60分) 17、(10分)设G为n(n≥3)阶无向简单图，证明G或G的补图必连通。 18、(10分)设A，B，C为集合，证明： A∩(B－C)=(A－C)∩(B－C) 19、(10分)右图是偏序图X，≤的哈斯图 1)X和≤的集合表达式 2)指出偏序集的极大元、极小元、最大元、最小元 20、(10分)设Z为整数集，在Z上定义二元运算*如下： (x，y(Z，x*y＝x＋y－2 请证明（Z，*） 是群。 21、(10分)在命题逻辑中构造下面推理的证明。 　　前提：p→s，q→r，┐r，p∨q 结论：r 22、(10分) 用狄克斯特洛算法求下图中从a到f的最短 通路。（写出求解过程） 课程名称: 离散数学A卷标准答案 一、单项选择题(本大题共8小题，每小题2分，共16分) 1 2 3 4 5 6 7 8 A A C C D D B B 二、填空题(本大题共8小题，每空3分，共24分) 1.无（或没有，或空） 2. 1（或T，或真） 3. 2 4. [n(n-1)/2]-m 5. {2,{2}} 6. 4!（或24） 7. 24（或16） 8.{(1,1),(2,2),(3,3),(4,4)} 三、(10分) 证明：如果图G是连通图，问题得证。 2分 如果G不是连通图，不妨设图G由K个连通分支G1,G2,…,Gk构成。现证G的补图是 连通图。 2分 在补图中任取两点u和v，由于补图和原图有相同的顶点，所以u和v也是图G的点。 下面分两种情况讨论。 1. u和v分别是不同的连通分支Gi和Gj的点（见下图1）。易知，连接u和v的边在补图中， 即在补图中，u和v之间有通路相连。 3分 图1 图2 2. u和v是同一连通分支Gi中的点（见上图2）。则可在另一连通分支Gj中任取一点x， 易见边ux和边vx是补图中的边，由此可知点u和v之间在补图中 有通路uxv相连。 3分 综上所述，补图是连通图。证毕。 四、(10分) 证明：①￢s