2007_-_离散数学AB.docVIP

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的最短 通路。（写出求解过程） 7、任何图中必定有偶数个： [ ] A、度数为偶数的结点 B、入度为偶数的结点 C、度数为奇数的结点 D、出度为奇数的结点 8、在右图描述的偏序集中，{b, c, d}的上确界是 [ ] A、{a, b} B、{b} C、{a} D、{f} 二、填空题(本大题共10小题，每空3分，共24分) 9、 两个重言式的析取是_____________ 式， 一个重言式和一个永假式的合取式是_____________ 式。 10、公式 ┐(P∨Q) ←→(P∧Q) 的主析取范式是_____________。 11、令A = {(}，则A的子集是_____________ 12、((x)(P(x)∨( y)R(y))→Q(x))中(x)的辖域是_____________。 13、在代数系统Z, + 中，Z是整数集合，+运算是普通加法，则((2)(3 = _____________。 14、设 A={a, b}，则 P (A)= _____________ 15、已知 Π={{a}{b, c}}是A={a, b, c}的一个划分，由 Π决定的 A上的一个等价关系是_____________。 16、已知群 G的阶是 8，G只能有_____________阶非平凡子群。 三、 简答及证明(本大题共6小题，每小题10分，共60分) 17、(10分) 设A，B，C为集合，证明A∩(B－C)=(A－C)∩(B－C) 18、(10分)已知带权图G，如题图所示．试求图G的最小生成树，并计算该生成树的权。 19、(10分)集合Ａ＝｛111、122、341、456、