2008离散数学A2试卷+答案.doc

广东工业大学考试试卷 ( A )课程名称: 离散数学 考试时间: 2007 年 1 月 26 日 (第 21 周 星期五 )题 号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、单项选择题(本大题共8小题，每小题2分，共16分)1、设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”的符号化形式为 A A. pq B. qpC .pq D. pq2、设解释I如下，个体域D=a,b, F(a,a)= F (b,b)=0, F(a,b)=F(b,a)=1，在解释I下，下列公式中真值为1的是 A A. VxyF(x,y) B. xVyF(x,y)C. VxVyF(x,y) D. xyF(x,y)3、设R1、R2为集合A上的任意关系，下列命题为真的是 C 若R1、R2反自反，则R1 R2反自反 B 若R1、R2传递，则R1 R2传递 C 若R1、R2自反，则R1 R2自反 D 若R1、R2对称，则R1 R2对称4、设G为完全二部图K2,3，下面命题中为真的是 C A. G为欧拉图 B. G为哈密尔顿图C. G为平面图 D. G为正则图5、对于任意集合X, Y, Z，则 D A. XY=XZ =Y=Z B. XY=XZ =Y=Z C. XY=XZ =Y=Z D. XY=XZ =Y=Z 学 院： 专 业： 学 号： 姓 名： 装 订 线6、下面等式中唯一的恒等式是 D A. (ABC)-(AB)=C B. AA=AC. A-(BC)=(A-B)(A-C) D. A(B-C)=(AB)-(AC)7、设R为实数集，定义* 运算如下：a*b=|a+b+ab|，则 * 运算满足 B A. 结合律 B. 交换律 C. 有幺元 D. 幂等律8、对于集合A0、1、2、3、4、5、6、7、8、9、10，不封闭的二元运算是 B A x*y=max(x,y) B x*y=xy C x*y=(x+y)mod 9 D x*y=min(x,y)二、填空题(本大题共10小题，每空3分，共24分)9、含n个命题变项的重言式的主合取范式为_无_。10、设个体域为整数集合Z，命题Vxy(x+y=3)的真值为_1_。11、以1，1，1，2，2，3为度数序列的非同构的无向树共有_2_棵。12、已知n阶无向简单图G有m条边，则G的补图G有_条边。13、设R=，则domRranR=_。14. 设A=1, 2, 3, 4，则A上有_4!_个不同的双射函数。15. 设=(1345)(2678)是8元置换，则-1=_。16、集合A1、2、3、4上的恒等关系是_。三、 简答及证明(本大题共6小题，每小题10分，共60分)17、(10分)设G为n(n3)阶无向简单图，证明G或G的补图必连通。第19题图18、(10分)设A，B，C为集合，证明：A(BC)=(AC)(BC)19、(10分)右图是偏序图的哈斯图1)X和的集合表达式2)指出偏序集的极大元、极小元、最大元、最小元20、(10分)设Z为整数集，在Z上定义二元运算*如下： x，yZ，x*yxy2 请证明（Z，*） 是群。21、(10分)在命题逻辑中构造下面推理的证明。前提：ps，qr，r，pq结论：r22、(10分) 用狄克斯特洛算法求下图中从a到f的最短163233516adcebf通路。（写出求解过程）0 课程名称: 离散数学A卷标准答案 一、单项选择题(本大题共8小题，每小题2分，共16分)12345678AACCDDBB二、填空题(本大题共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的点。下面分两种情况讨论。uGivGjxGjuvGi1. 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 P 1分ps P 1分p T 1分pq P 1分q T 1分qr P 1分r T 1分T规则应用正确：2分； P规则应用正确：1分；五、(10分)解：1.Xa,b,c,d,e,f 2分 =(a,b)，(a,c)，(a,d)，(a,e)，(a,f)，(b,e)，(c，e), (c,f)，(d,f)Ix4分，其中错一个、多一个、漏一个元素均扣0.5分，直至4分扣完。 2.极大元e； 1分极小元a； 1分最大元不存在； 1分最小元a。 1分六、(10分)证明： 由已知，运算显然封闭； 2分对x，y，zZ有：(x*y)*z=(x+y-2)*z=(x+y-2)+z-2=x+y+z-4 1分 x*(y*z)=x*(y+z-2)=x+(y+z-2)-2=x+y+z -4 1分所以，*满足结合律；对x Z有：x*2=x+2-2=0， 1分且2*x=2+x-2=0 1分所以，存在单位元：2 对x Z有：x*(4-x)=x+4-x-2=2， 1分且(4-x)*x=4-x+x-2=2 1分所以，对x Z有x的逆元是：4-x 1分由可知，（Z，*）是群。 1分七、(10分)b c d e f5 2分 9 2分7 1分11 1分 1分故a到f的最短通路是a-b-d-c-f（或a-b-d-e-c-f）， 2分其权为10 1分八、(10分)前提：x(F(x)G(x)，x(G(x) H(x)I(x)，F(a)，H(a) 2分结论：I(a) 1分证明：x(F(x)G(x) PF(a)G(