离散数学期末复习题

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是传递的，则R'S是传递的。7.下列关系矩阵所对应的关系具有反对称

3、性的是( B)。一1 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度

4、的分支点各1个，其余顶点均为树叶，则 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

5、.自反性16 .谓词公式(Vx)(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),

6、(3,4),则 R具有(B )A.自反性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_个极小

7、项。2 . 设有集合 A 和 B,其中 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=<1,2>,<3,4>,<2,2>,S=<4,2>,<2,5>,<3,1>,<1,3>,贝U R °S = <1,5>, <2,5>, <3,2> ,S°R=,&

8、lt;1,4>, <3,2>, <4,2> 。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(x),则G的前束范式是 三x(P(x) V Q(x)。三、计算题1 .画出命题公式(P-Q)-(PAi R)的真值表，并求它的主合取范式， 写出相应的成真赋值 和成假赋值。真值表如下表：主合取范式为

9、： 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股和C股的共有9人，买了 A股和C股的共17人，只买A股的共31人，只买B股的共23人。试求：1) 三种股票都买的有几人？2) 买A股、B股和C股的各几人？解：设集合A, B, C分别表示购买 A,B

10、,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)=42因而可得，三种股票都买的有5人。买A股的有63人，买B股的有47人，买C股的有42人。根据题意画出文氏图如下图3. 设集合 A=a, b, c ,d上的二元关系 R=<a, a>

11、, <a,b>, <b, a>, <c,d>,<d, a>,求 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 = : a,b , ： b,a , ： c, d , ： d,a , ： a,a , ；

12、 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）求2,9的最小上界和最大下界。答案：R是A

13、上的偏序关系。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 = v3 V4选 e = v4 V5 选 e

14、 = 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 .解求命题公式(pv<q)T r的主析取范式和主合取范式，并求其成真赋值。答案:(p V q

15、) 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 V r)u(r p Vn q V r) A (n pV qV r) A (n pVn q V r) A (pVn q V r)二 M2 M4 M6=m0mlm3 m5m7其成真赋值为 000, 001, 011, 101, 1118 .求从1到500的整数中，能被 3或5除尽的数的个数。解：设A为从1到500的整数中，能被 3除尽的数的集合。B为从1到500的整数中，能被5除尽的数的集合。则|A|=500/3=16

16、6(x表示不超过x的最大整数)|B|=500/5=100|A A B|=500/ ( 3*5 ) =33由包含排斥原理：|A U B|=|A|+|B|-|A A B|=166+100-33=233即从1到500的整数中，能被 3或5除尽的数有233个。9 .设 A =1,2,3,4, A上二元关系 R=<1,1 A,< 2,3>,< 2,4>,< 3,2> ,< 3, 4> 求其 自反闭包、对称闭包、传递闭包。答案：(计算过程自己补充)自反闭包 r(R) =<1,1.,<2,3,<2,4,：二 3,2/3,42,2j 3,

17、3j4,4 对称I包 s(R) =：二1,1,：二2,3,<2,4,：二3,2,：二 3,4,：二4,24,3传递闭包 t(R) =：二1,12,3,：二2,4, < 3,2, < 3,4/2,2, <3,310 .对集合A中的整除关系画出哈斯图，A=1,2, 3, 4, 6, 8, 12, 14,并求A的极大元、极小元、最小元和最大元。解：首先画出哈斯图(如右图所示)1412极大元最小元最大元极小元：114, 8, 121无在二叉树中1)求带权为2, 3, 5, 7,8的最优二叉树To2)求T对应的二元前缀码。12.13.88V4无向图G如下图所示eeG画出顶点集V1

18、 , V2,V4 的导出子图3)卬3e3写出G的关联矩阵1)2)写出G的关联矩阵。求G中各顶点的度数。解：1）一21010 10110000111.00001 _关联矩阵mg2）求各顶点的度数d(V1)=4 d(V2)=2d(V3)=3d(V4)=13）画出顶点集V1 , V2 , V4 的导出子图V1四、证明题1 .在谓词逻辑中，将下列命题推理符号化并给出形式证明：任何人，如果他喜欢步行，他就不喜欢乘汽车。每一个人或者喜欢乘汽车，或者喜欢骑自行车。并非每个人都喜欢骑自行车。因此，有的人不爱步行。(个体域为人类集合)解：设F(x):x喜欢步行，G(x) : x喜欢乘汽车，H(x):x喜欢骑自行车 则上述推理可以符号化为：- x(F(x) -n (G(x),证明：(1) n - xH(x)(2) xn H(x)H(c)(4) Vx(G(x) V H(x)(5) G(c) V H(c)(6) G(c)(7) - x(F(x) -n (G(x)(8) F(c) -(G(c)(9) n F(c)(10) xn F(x)Vx(G(x) V H(x), n VxH(x) |PT(1),ET(2),ITx n F(x)P T(4),I T(3)(5),IPT,I T(6)(8),I T(9),I2 .在谓词逻辑中，将下列命题推理符号化并给出形式证明：如果一个人怕困难，那