《《离散数学》试题及答案.doc》由会员分享，可在线阅读，更多相关《《离散数学》试题及答案.doc（8页珍藏版）》请在金锄头文库上搜索。
1、离散数学试题及答案一、填空题 1 设集合A，B，其中A1,2，3， B= 1,2， 则A - B_; r(A） - r（B） _ .2。 设有限集合A， A = n， 则 |r（AA） = _.3。 设集合A = a， b, B = 1, 2, 则从A到B的所有映射是_ _, 其中双射的是_.4. 已知命题公式G（PQ)R，则G的主析取范式是_。5。设G是完全二叉树，G有7个点,其中4个叶点,则G的总度数为_,分枝点数为_。6 设A、B为两个集合， A= 1，2,4, B = 3，4， 则从AB_; AB_；AB _ 。7. 设R是集合A上的等价关系,则R所具有的关系的三个特性是_， _, _
2、.8. 设命题公式G(P(QR）),则使公式G为真的解释有_，_, _。9. 设集合A1,2，3，4， A上的关系R1 = （1，4）,（2，3）,(3,2), R1 = (2，1)，（3，2）,(4，3)， 则R1R2 = _,R2R1 =_，R12 =_.10。 设有限集A, B，|A = m, B| = n, 则 |r(AB）| = _。11 设A，B，R是三个集合，其中R是实数集,A = x | 1x1, xR， B = x | 0x 2, xR，则A-B = _ , BA = _ , AB = _ ， .13. 设集合A2, 3, 4， 5， 6，R是A上的整除，则R以集合形式(列举
3、法)记为_ _. 14。 设一阶逻辑公式G = xP（x)$xQ(x)，则G的前束范式是_ _。15。设G是具有8个顶点的树,则G中增加_条边才能把G变成完全图。16。 设谓词的定义域为a， b，将表达式xR（x)$xS(x）中量词消除，写成与之对应的命题公式是_。17. 设集合A1， 2, 3， 4,A上的二元关系R(1,1）,(1，2)，（2,3), S（1，3），(2,3),（3,2).则RS_, R2_.二、选择题1 设集合A=2，a，3，4，B = a,3，4,1，E为全集，则下列命题正确的是（ )。（A）2A (B）aA （C)aBE (D）a，1，3,4B.2 设集合A=1，2,
4、3,A上的关系R（1，1),(2，2),(2，3），（3,2）,(3，3）,则R不具备( ）.（A）自反性(B)传递性（C）对称性（D)反对称性1234563 设半序集(A，)关系的哈斯图如下所示,若A的子集B = 2，3,4,5，则元素6为B的( ).(A)下界 （B)上界(C)最小上界 (D）以上答案都不对4 下列语句中，（ )是命题。（A)请把门关上 （B）地球外的星球上也有人 (C）x + 5 6 （D)下午有会吗？5 设I是如下一个解释：Da，b， 则在解释I下取真值为1的公式是（ ）。(A)$xyP（x,y） （B)xyP(x，y） (C）xP(x,x） (D)x$yP(x,y)。
5、6。 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( )。(A）(1，2，2，3，4,5) （B)(1,2，3,4,5,5) （C）（1,1,1，2，3) （D)（2,3，3，4,5,6）。7。 设G、H是一阶逻辑公式，P是一个谓词，G$xP（x), HxP(x)，则一阶逻辑公式GH是（ ）.（A)恒真的 （B）恒假的 (C）可满足的 （D）前束范式。8 设命题公式G（PQ)，HP(QP),则G与H的关系是( )。（A)GH (B)HG （C)GH (D)以上都不是。9 设A, B为集合，当（ ）时ABB。(A)AB(B）AB(C)BA（D）AB.10 设集合A = 1，2，
6、3，4, A上的关系R（1,1）,(2，3），(2，4),（3,4)， 则R具有（ )。(A)自反性 (B）传递性（C）对称性 (D)以上答案都不对11 下列关于集合的表示中正确的为（ ）。(A)aa,b,c （B）aa，b,c(C)a，b，c （D)a,ba,b，c12 命题xG（x）取真值1的充分必要条件是( )。(A) 对任意x,G（x）都取真值1. （B)有一个x0，使G(x0)取真值1。 (C)有某些x，使G（x0)取真值1. （D)以上答案都不对.13. 设G是连通平面图,有5个顶点，6个面，则G的边数是（ )。(A) 9条 (B） 5条 （C) 6条 (D） 11条.14. 设G
7、是5个顶点的完全图,则从G中删去( ）条边可以得到树。(A)6 （B）5 （C）10 （D)4.15. 设图G的相邻矩阵为，则G的顶点数与边数分别为（ ).(A)4， 5 （B）5， 6 (C)4， 10 (D）5， 8.三、计算证明题1.设集合A1, 2, 3, 4, 6， 8， 9， 12,R为整除关系。(1) 画出半序集(A，R)的哈斯图；(2) 写出A的子集B = 3，6，9,12的上界，下界,最小上界,最大下界；(3) 写出A的最大元,最小元，极大元，极小元.2. 设集合A1, 2, 3, 4，A上的关系R（x,y） x， yA 且 x y， 求 (1) 画出R的关系图；(2) 写出
8、R的关系矩阵.3. 设R是实数集合,s,t,j是R上的三个映射，s（x) = x+3， t（x) = 2x, j（x） x/4，试求复合映射st，ss， sj， jt，sjt。4。 设I是如下一个解释：D = 2, 3， abf （2)f (3）P(2， 2)P(2， 3）P（3， 2)P（3, 3)32320011试求 （1） P(a， f (a)P（b, f （b)）；（2） x$y P （y, x）.5。 设集合A1， 2, 4， 6, 8, 12，R为A上整除关系。(1) 画出半序集(A,R）的哈斯图;(2) 写出A的最大元,最小元，极大元，极小元;(3) 写出A的子集B = 4， 6
9、， 8， 12的上界，下界，最小上界，最大下界.6。 设命题公式G = (PQ)（Q(PR）， 求G的主析取范式。7。 （9分）设一阶逻辑公式：G = （xP（x）$yQ(y)）xR（x），把G化成前束范式。9。 设R是集合A = a， b, c， d。 R是A上的二元关系， R = (a，b), （b,a）, (b，c）, （c,d)，(1) 求出r（R), s(R）， t（R)；(2) 画出r(R), s（R)， t（R）的关系图.11. 通过求主析取范式判断下列命题公式是否等价：（1) G = （PQ）(PQR） (2) H = (P（QR）)(Q（PR)）13. 设R和S是集合Aa,
10、b, c, d上的关系，其中R（a, a)，（a, c）,（b, c）,(c, d), S(a, b)，(b， c），（b， d），(d， d)。(1) 试写出R和S的关系矩阵；（2) 计算RS， RS, R1， S1R1.四、证明题1. 利用形式演绎法证明：PQ, RS, PR蕴涵QS。2。 设A,B为任意集合,证明：(A-B）C = A(BC）。3。 (本题10分）利用形式演绎法证明：AB, CB， CD蕴涵AD。4。 （本题10分）A， B为两个任意集合，求证：A(AB） = （AB）B 。参考答案一、填空题1。 3; 3，1，3,2,3,1，2,3。 2. 。3. a1= (a，1)，
11、 (b,1), a2= （a，2), (b,2）,a3= （a,1）, （b,2)， a4= （a，2)， (b，1）； a3， a4.4. （PQR).5. 12, 3。 6. 4， 1, 2， 3, 4, 1， 2. 7. 自反性;对称性；传递性。8. (1, 0, 0)， （1, 0, 1）， (1， 1, 0）。9. （1，3)，(2，2），（3,1）; （2，4）,（3,3），(4，2）； (2,2),(3,3).10. 2mn.11. x | -1x 0， xR; x | 1 x 2, xR; x | 0x1, xR.12. 12; 6。13. （2， 2),(2， 4)，（2, 6),(3， 3
