《计算机数学基础(1)》离散数学试题

1、 PAGE PAGE 3计算机数学基础(1)离散数学试题一、单项选择题(每小题 2 分，共 10 分)命题公式P(PP)的类型是（）（A）永真式（B）矛盾式（C）非永真式的可满足式析取范式设个体域是整数集合 代xy(xy)(xyx)，下面4 个命题中为真的()(A)P 是真命题(B)P是假命题(C)P 是一阶逻辑公式，但不是命题(D)P 不是一阶逻辑公式设A, B, C 都是集合，如果ACBC，则()(A) AB(B) AB(C) 当ACBC 时有A=B(D)当C=U时, 有AB4. 设集合A，a，则P(A) ()(A ) ,a, ,a(B) , a, , a(C) , a, ,a,A(D )

2、 , a, , a给定无向图如第5 题图所示，下面给出的顶集子集中，不是点割集的为（）b,d(B) (C) a,c(D) 二、填空题(每小题 3 分，共 15 分)fagdcagdce 是偶数，命题“不是所有的素数都不是偶数”符号化为：设A, B 为任意集合，命题AB的真值设AB 为有限集，m,n,那末A 与B 间存在双射，当且仅在有向图的邻接矩阵中，第i 行元素之和与第j 列元素之和分别 无向图G为欧拉图，当且仅当G是连通的，且G中结点三、化简解答每小题8分，共32分)指出谓词公式x( P x) Q x, y) xR x) S x) 中x x 的辖域，并指出该公式的约束变元和自由变元以及约束

3、出现次数和自由出现次数12.化简集合表达式：(ABC)(AB)(B(BC)A)A=0,1,2,3,4A R 为：Rx,yA(x=yx+yA)0 120 12(1) (PQ)(PQ)的成真赋值(2) 已知集合 A 上的二元关系 R14 R R 的关系矩阵第 14 题图1928 24 分)8 5 6 7G15 G 的最小生成树，并计算该生成树的权410315 题图R R *，x,yR，定义x*y=x+y+2xy试说明*是否满足结合律、交换律？是否存在单位元？若存在请求出和满足分配律，a,b,cL，化简表达式(a*b)(a*c)* (a*b)(b*c)五、证明题(第 18 题 10 分，第 19 题

4、 9 分)(P(QR)PQ （PQ）等值证明在任何有向完全图中，所有结点的入度平方之和等于所有结点的出度平方之和计算机数学基础(1)离散数学试题答案一、单项选择题(每小题 2 分，共 10 分)1. A2. B3. C4. D5. A二、填空题(每小题 3 分，共 15 分)6.x(F(x)E(x) 或x（F（x）E（x）7.08.m=n9. 结点 vi的出度与结点 vj的入度10.奇数度三、化简解答题(每小题 8 分，共 32 分)11. x 的辖域为：(P(x)Q(x)xR(x)x 的辖域为：R(x)x 3 1 次y 1 次.12. (ABC)(AB)(B(BC)A)(AB)(BA）=(A

5、B)(BA)=A(BB)=A=A13. 由题设，RI ,A,易知，R 具有自反性和对称性14. (1) (PQ)(PQ)(PQ)(PQ)(PP)QQ可见(PQ)(PQ)的成真赋值为(0,1)，(1,1)(2)R 0 ,0 , 2 , 2 , 0 , 2 , 2 ,0 M R010001四计算题(每小题 8 分，共 24 分)15. 做法如下：1；2；3；5；选边 71,2,3,5,715 中粗线所示权数为 1816. x,y,zR，1925875643第 15 题答案图(x*y)*z=(x+y+2xy)*z=(x+y+2xy)+z+2(x+y+2xy)z=x+(y+z+2yz)+ 2x(y+z+2yz)=x*(y*z) ， x R, x R,单位元0.17. (a*b) (a*c)*(a(*b) (b*c)(配律) =a*b(吸收律)181019918. (QR)PQ( PR) PQ( PPQ)(QP Q ) ( RP Q )( PQ)( PQ)( P QR)P QQ)19. 假设完全有向图D 有n 个结点对任意结点vkD , 有n对于完全有向图，kkndeg )kdeg (vk) n1)于是，k 1k 1nn(deg (vk)2(n1) deg k)2k 1k 1n1)24(n1) deg k