离散数学复习题含答案.doc

离散数学复习题一、选择题：（每小题只选一个答案，每题2分，5题共10分）1设A= 1,2,3，4,5，6,7,8 ，下述选项正确的是（ C ） （A）1A （B）1,2,3 A （C）4,5 A （D） A2设命题公式，H= Q，则G与H的关系是 ( A )。(A) (B) (C) (D) 以上都不是.3若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为 ( B )(A) PQ (B) PQ (C) PQ (D) PQ4集合A=1,2,10上的关系R=(x , y) | x+y=10,xA,yA,则R的性质为 ( B )A.自反的 B.对称的 C.传递的，对称的 D.反自反的，传递的5一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条 ( B )A.汉密尔顿回路 B.欧拉回路C.汉密尔顿通路 D.初级回路二、填空题：（每小题2分，10题共20分）6设R是集合A上的等价关系，则R所具有的关系的三个特性是 自反性、对称性、传递性 7设A是集合，且A = 1, 2，则A上的全关系AA= （1, 1），（1,2），（2,1），（2,2） 8设,的真值为F，的真值为T ，则命题的 真值是 T .9设A=a,b,c,则A的幂集P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c 。10设A=1,2,B=a,b则AB= (1,a),(1,b),(2,a),(2,b) .11A,B是集合，且|A|=m,|B|=n,则A,B之间存在双射的充分必要条件是 m=n 。12判断一个语句是否为命题，首先要看它是否为 陈述句 ，然后再看它是否具有唯一的 真值 。13设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x) (M(x)D(x) ,其中量词(x)的辖域是 M(x)D(x) 。14设G是一个无向图，恰包含G的每条边一次的简单路称为 欧拉 路。15在树中,度为1的点称为 树叶 。三、判断题：（每题1分，5题共5分）16有的群没有单位元。 ( x ) 17A，B是集合，则命题A B和AB可能同时成立。 ( ) 18平面上的直线间的平行关系是等价关系。 ( )19若两图的结点数和边数相等则两图同构。 ( x ) 20R,S是集合A上的二元关系，则RS=SR. ( x )四、解析题：21.设集合A=a,b,c,d上关系R=(a,b),(b,a),(b,c),(c,d) （1) 写出关系R的矩阵；（2）用矩阵运算求出R的自反、对称闭包；解：（1）R的矩阵为 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0（2）自反闭包： 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1对称闭包： 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 022 对于 3个集合A,B,C,其容斥定理为： |ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|，试问：X是由从1到250的正整数构成的集合，X中有多少个元素能被2,3,5中任意一个整除？解：设A表示X中能被2整除的元素构成的集合； 设B表示X中能被3整除的元素构成的集合； 设C表示X中能被5整除的元素构成的集合|A|=250/2=125 |B|=250/3=83 |C|=250/5=50 |AB|=250/(2*3)=41 |AC|=250/(2*5)=25 |BC|=250/(3*5)=16 |ABC|=250/(2*3*5)=8|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|= 18423.设集合A1, 2, 3, 4, 6, 8, 12，R是A上的整除关系(1) 画出偏序集(A, R)的哈斯图；(2) 写出A的子集2, 4, 6, 8的上界，下界，最小上界，最大下界；写出集合A的最大元，最小元，极大元，极小元。解：集合A1, 2, 3, 4, 6, 8, 12(1) 偏序集(A, R)的哈斯图12483612(2) 子集2, 4, 6, 8无上界，下界是1,2，无最小上界，最大下界是2.(3) A无最大元，最小元是1，极大元是8, 12，极小元是1。24. 证明（）， 。证明：（） （） D(附加前提)（） Q及()(）（）（） （） Q及(3)(4) （） （） Q及(5)(6)（） D及(2)(7)推理规则： 在推导过程中，前提在任何时候都可引用。推理规则Q： 在推导过程中，可随时引用前面某些公式演绎出来的逻辑结果。推理规则D： 如果需要演绎出的公式具有PQ的形式，则可将P做为附加前题使用，设法演绎出Q来。25. 用推理法求(pq)(pq)的主析取范式、主合取范式。解：（1）(pq)(pq) (pq)(pq)(pq) (pq)(pq)(pq) （主析取范式） q(pq) （析取范式） pq （合取范式、主合取范式）26. 用迪克斯特拉算法求下面权图中点u到v之间的最短路径。(注：图形不一定遵循三角形2边之和大于第3边，直线只代表路径)uv124572361解：(1)设S0=u,S0=u1,u2,u3,u4,v,d(u,S0)=min1,4=1,d(u,u1)=1, P1=uu1，u1如下图所标.(2)S1=u,u1,S1=u2,u3,u4,v,d(u,S1)=min4,1+2,1+5,1+7=3,d(u,u2)=3,P2=uu1u2，u2如下图所标.(3)S2=u,u1,u2,S2=u3,u4,v,d(u,S2)=min3+1,1+5,1+7=4,d(u,u3)=4,P3=uu1u2u3, u3如下图所标.(4)S3=u,u1,u2,u3,S3=u4,v,d(u,S3)=min4+3,4+6,1+5,1+7=7,d(u,u4)=7, P4=uu1u2u3u4, u4如下图所标.(5)S4=u,u1,u2,u3,u4,S4=v,d(u,S4)=min7+2,4+6,1+5+3+2,1+7+2=9, d(u,v)=9, P5=uu1u2u3u4v所以最短路径为uu1u2u3u4v，距离为9.V1V2V3V427.设有向图G=（V，E）如右图所示：（1）写出图