《离散数学期末复习题》由会员分享，可在线阅读，更多相关《离散数学期末复习题（12页珍藏版）》请在金锄头文库上搜索。
1、离散数学复习题一、单项选择题1.给定如下4个语句：(1)刘红与魏新是同学。(3)我每天都看新闻联播。其中不是复合命题的是(B)。(2)除非天下雨，否则我就去踢足球。(4)我在说谎。A. (3)B. (1)(3)(4) C. (1)(3)2.下列式子不是 谓词合式公式的是(B)。D. (3)(4)A . (Vx) P(x)一 R(y)B. (Vx) n P (x) =(Vx)(P(x)-Q(x)C. (VX)(3y)(P(x)AQ(y)(3x)R(x)D. (Vx)(P(x,yHQ(x,z)V(5z)R(x,z)3.命题公式(Pt Q)t (-Qvp)中成真赋值的个数为(D)。A. 0 B .
2、1C. 2 D. 34.在下述公式中是重言式为(A)。A. (P Q) (P Q)b. P，QC 7PTQ)AQ； D. Pt(PQ)。5 .谓词公式(寸x)(P(x) V (三y)R(y) 一Q(x)中的 y (A)。A.只是约束变元B.只是自由变元C.既非约束变元又非自由变元D.既是约束变元又是自由变元6 .设R, S是集合A上的关系，则下列说法正确的是(A)。A.若R, S是自反的，则R ：S是自反的；B.若R, S是反自反的，则R二S是反自反的；C.若R, S是对称的，则 R二S是对称的；D.若R, S是传递的，则RS是传递的。7.下列关系矩阵所对应的关系具有反对称性的是( B)。一1
3、 0 1 A.0 11J 0 0_001C.0 0 1J 0 0_10 01B .011-10 11一10 11D .010J0 0_8,下面四组数能构成无向简单图的度数列的有( A)。A. (2, 2, 2, 2, 2)B. (1,1, 2, 2, 3)C. (5, 4, 3, 2, 2)D. (0, 1, 3, 3, 3)9,下列图中是欧拉图的有(A)。D10.设图G的邻接矩阵为01111010011011101 0110110G的顶点数与边数分别为(D)。A. 4, 5 B, 5, 6 C. 4, 10D. 5, 811 . 一棵无向树T有4度、3度、2度的分支点各1个，其余顶点均为树叶
4、，则 T中有(C) 片树叶。A. 3B. 4 C, 5 D, 612 .若图G有一条通路经过图中每条边恰好一次，则G (A)。A,有一条欧拉通路B,是欧拉图C,有一条哈密顿通路13 .设P,Q,R是命题公式，则A. PB. Q14 .命题公式(P t Q)tD,是哈密顿图P-R, Q-R, PV Q= (C)。C. RD. n R(-Q v P)中极小项的个数为(D)。A. 0 B. 1 C. 2 D. 315 .设S =1, 2,3 , S上关系R的关系图为 则R具有(D)性质。A.自反性、对称性、传递性B.反自反性、反对称性C.反自反性、反对称性、传递性 D.自反性16 .谓词公式(Vx)
5、(P(x) V (三 y)R(y) 一 Q(x)中的 x (D)。A.只是约束变元B.只是自由变元C,既非约束变元又非自由变元D,既是约束变元又是自由变元17 .设个体域为整数集，则下列公式中值为真的是(B)。A. ( V y)(三x)(x - y=2)B, ( V x)(三y)(x + y=2y)C. ( Vx)(x - y=x)D. ( 5x)( Vy)(x+y=3y)18.设S=1,2, 3,则S的募集的元素的个数有(A)。A. 8个B.6个C. 3个D. 7个19 .设集合 A = 1,2,3,4, A 上的关系 R=(1,1),(2,3),(2,4),(3,4),则 R具有(B )A
6、.自反性B.传递性 C.对称性 D.以上答案都不对20 .下面四组数能构成无向简单图的度数列的有( A)。A. (5, 5, 4, 4, 2, 1) B. (5, 4, 3, 2, 2)C. (3, 3, 3, 1) D. (4, 4, 3, 3, 2, 2)21 .一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是(B)。A. 13B. 14C. 15D . 1622 .若图G有一条通路经过图中每个顶点恰好一次，则G(C)。A.有一条欧拉通路B.是欧拉图C.有一条哈密顿通路D.是哈密顿图二、填空题1 . P H Q的主析取范式中，含有2_个极小项。2 . 设有集合 A 和 B
7、,其中 A =1,2,3, B= 1,2, 则 A - B=3,P(A) - P(B)=3,1,3,2,3,1,2,3。3 .由集合运算的吸收律，AI (AU B) =A, AU(AI B) =A。4 . 给定集合A=1,2,3,4,5,在集合A上定义两种关系：R=,S=,贝U R S = , , ,SR=, , 。5 .设 A=x| 1 Wx E2,xW R , B=x|0 x E5,xW R,则 A-B= x| -1 x 0, A=x|2 x 5o6 .设R是集合A上的等价关系，则 R所具有的关系的三个特性是自反性、对称性和传递 性。7 .设一阶逻辑公式 G = VxP(x)-?3 xQ(
8、x),则G的前束范式是 三x(P(x) V Q(x)。三、计算题1 .画出命题公式(P-Q)-(PAi R)的真值表，并求它的主合取范式， 写出相应的成真赋值 和成假赋值。真值表如下表：主合取范式为： M0 A M1 A M2AM3 A M7成真赋值为：100, 101, 110成假赋值为：000, 001 , 010, 011 , 111PQRP- QPAn R(P-Q)-(PAi R)0001000011000101000111001000111010011101111111002 .今有111人购买A,B,C三种股票，已知只买了一种股票的共75人，买了 A股和B股的共有20人，买了 B股
9、和C股的共有9人，买了 A股和C股的共17人，只买A股的共31人，只买B股的共23人。试求：1) 三种股票都买的有几人？2) 买A股、B股和C股的各几人？解：设集合A, B, C分别表示购买 A,B,C三种股票的人的集合。 所示。设三种股票都买的有 x人，由已知条件填写图中相应区域。I C-(A n B) I = 75-31-23=21由已知条件，可得以下方程：(20-x)+x+(9-x)+(17-x)+31+23+21 = 111解得：x=5故 I A =31+(20-5)+5+(17-5)=63I BI =23+(20-5)+5+(9-5)=47I CI =21+(9-5)+5+(17-5
10、)=42因而可得，三种股票都买的有5人。买A股的有63人，买B股的有47人，买C股的有42人。根据题意画出文氏图如下图3. 设集合 A=a, b, c ,d上的二元关系 R=, , , ,求 R0, R2, r(R), s(R), t(R)的集合表达式。写出R的关系矩阵,Mr一11 00 00 00 0010，MR21 R0一11=M r.M r =1J1 0 01 0 00 0 01 0 0解R0 = IA =二 a,a , : b,b , : c, c ,二 d,d 故 R2 a,a，: a,b，: b,a ，: b,b , c,a，: d,a , ： d,b r(R)=R Ia = :
11、a,b , ： b,a , ： c, d , ： d,a , ： a,a , ； b,b , c,c , d, d 1s(R)=R R =二 a,a ，二 a,b ，二 b,a ，二 a,d , ： d,a , ：c,d ，二 d,c 画出R的关系图（如下图所示），并根据沃舍尔算法画出t（R）的关系图t(R)=：a,a ，二 a,b , b, a ，: b, b , c,a , ： c,b , . c, d , ： d,a ，: d,b 4.设 A = 11,2,3,5,6,9,15,27,36,45上的整除关系R = a1,a2)|a1,a2= Aa整除 a2 t1 ）画出R的哈斯图;2）求
12、2,9的最小上界和最大下界。答案：R是A上的偏序关系。1） R的哈斯图：2） 2,9拍勺最小上界lub12,9 =36，最大下界glb（2,9）=15.如下图所示的赋权图表示某七个城市v1,v2,v3,L L ,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。答案:用Kruskal算法求产生的最优树。算法为:w(v1, v7) =1 w(v7, v2) = 4 w(V7,V3)=9 wMm) =3 w(v4,v5)=17 w(vi , v6 ) = 23 结果如图：选 e ”丫7 选 e =v7 V2 选 e3 =v7 V3 选 e =
13、v3 V4选 e = v4 V5 选 e = v1V6树权C(T)=23+1+4+9+3+17=57 即为总造价6.有向图D如下图所示1）写出D的关联矩阵和邻接矩阵;2）求出各顶点的入度和出度。解：1）写出D的关联矩阵和邻接矩阵一 1-1关联矩阵MD =D 0.0-100-1110000-100 -111一01,邻接矩阵A =0J1000010000102）写出各顶点的出度和入度 出度入度d V) =1 d-(VD =2d (V2) =2 d (V3) =0d 一(V2) = 1d)=1d-M) = 1d (V4) =27 .解求命题公式(pvq)T r的主析取范式和主合取范式，并求其成真赋值。答案:(p V q) r 仁1(p V q )V ru 6 pAn q )V ru (j p V r) A (n q V r)6 p V (n q A q ) Vr) A (n pA p )Vq q
