《計算機數(shù)學基礎(1)》離散數(shù)學試題

1、 PAGE PAGE 3計算機數(shù)學基礎(1)離散數(shù)學試題一、單項選擇題(每小題 2 分，共 10 分)命題公式P(PP)的類型是（）（A）永真式（B）矛盾式（C）非永真式的可滿足式析取范式設個體域是整數(shù)集合 代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 是偶數(shù)，命題“不是所有的素數(shù)都不是偶數(shù)”符號化為：設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、出現(xiàn)次數(shù)和自由出現(xiàn)次數(shù)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）等值證明在任何有向完全圖中，所有結點的入度平方之和等于所有結點的出度平方之和計算機數(shù)學基礎(1)離散數(shù)學試題答案一、單項選擇題(每小題 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.奇數(shù)度三、化簡解答題(每小題 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 中粗線所示權數(shù)為 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