春離散數(shù)學試卷B

1、本大題 得分本大題 得分A. 1.本大題 得分題號-一一-二三四五六七總分應(yīng)得分16154425100實得分評卷人：一、單項選擇題(本大題共8小題，每題2分，共16分) 在每題列出的四個備選項中只有一個 是符合題目要求的，請將其代碼填入題后的括號內(nèi)。錯選、多項選擇或未選均無分。1. 以下說法中，不正確的選項是(D ).A. 10階4-正那么圖的邊數(shù)等于20.B. 圖G連通的充分必要條件是P(G)=1.C. n階無向簡單圖中，完全圖的邊數(shù)最多.D. 一個圖中偶度頂點的個數(shù)一定是奇數(shù)2. A = n,以下式子中，正確的選項是(D ).A. A A 2n。 B. P(A A)n2.C. |P(A A

2、)|22n. D. |P(A A)|2n3. H=x,y,z,H 上的關(guān)系 R=<x,z>是(C ).A.自反關(guān)系、反對稱關(guān)系和傳遞關(guān)系.B.自反關(guān)系、對稱關(guān)系和傳遞關(guān)系.C.反自反關(guān)系、對稱關(guān)系和傳遞關(guān)系.D.反自反關(guān)系、反對稱關(guān)系和傳遞關(guān)系4. 一階謂詞邏輯中，公式B不含 x,以下式子中成立的是(C ).A.x( (x)x (x)B.x( (x)x (x)C.x( (x)x (x)D.x(x)x (x)A .兩個素數(shù)的差是奇數(shù).B. 如果6是素數(shù)，那么66也是素數(shù).C.兩個素數(shù)的差是偶數(shù).D. 兩個素數(shù)的差是偶數(shù)嗎？6. R是非空集合H上的關(guān)系，那么以下說法中不正確的選項是(

3、C ). A . R是自反的 Ih R B. R是對稱的 R的關(guān)系矩陣是對稱的.C. R不是反自反的 R是自反的. D. R是傳遞的 R2 R7. 以下說法中，不正確的為(D ).A.無向6階完全圖的邊數(shù)是奇數(shù).B. 在任何圖中，所有頂點的度數(shù)之和一定是偶數(shù).C. 圖G不連通的充分必要條件是其連通分支數(shù)P(G) >2.D. 二部圖中的圈都是奇圈.8. 含2個變項的命題公式pV q的全部成真指派有( C )個B. 2. C. 3.D. 4.二、填空題(本大題共5小題，每題3分，共15分)在每題的空格內(nèi)填上正確答案。錯填、不填均無分。1. 設(shè)全集 E=1 , 2, 3, 4, 5，A=1，4

4、，B=1 ,5 ,2，貝卜A A B= 2,5.2. 令p:我?guī)?q:下雨，那么命題只有下雨我才帶傘可符號化為：q_.3. 令F(x): x是飛機；G(y): y是汽車；H (x, y): x比y快。那么命題 飛機都比汽車快可符號化為：一-/x-/y( F(x)八G(y) -_ H(x, y).4. 非空集合A上的關(guān)系R如果滿足條件IA R_,那么R是自反關(guān)系5. 給出如以下圖G.:那么有 d(C)= 3, (G)=_, P(G)=2.三、計算題(本大題共2小題，第1小題20分，第2小題24 分，共44分).5.以下語句中，一定是真命題的有(B ).得分1 寫出(n pVq-r)類型p的真值

5、表和所有成假指派，并確定公式的pqrn pn pV q(n pV qr(n p V q r)p00011010011110010110101111101000011101001111001001110111真值表得分 |2.設(shè) A=a,b,c,d,e,R=I aU <a,b>,va,c>,va,d>,va,e>,vb,e>,<c,e>,vd,e>.2(1) .計算 s(R)與 R;(8 分)(2) .簡要說明R是偏序關(guān)系,并畫出R的哈斯圖；(8)成假指派：(1) .S(R)=RUR-1= I aUP,q,r成假指派 <0,0,1>

6、;,<0,1,1>,v1,1,0>va,b>,vb,a>,va,c>,<c,a>,va,d>,vd,a>,va,e>,ve,a>,vb,e>,ve,b>,vc,e>,ve,c>,<d,e>,<e,d>.(n p V qr)p為可滿足式R°=IaR1=R)o R=R= IaU <a,b>,<a,c>,<a,d>,<a,e>,<b,e>,<c,e>,<d,e>R =Ro R= I aU

7、<a,b>,va,c>,va,d>,va,e>,vb,e>,<c,e>,vd,e>(3) .指出A的最大元、最小元、極大元、極小元；(4分)(4) .A的子集B=a,b，求B的上界、下界、上確界、下確界 。(4分)(2) Ia R R 自反R n R1包含Ia R反對稱R。R包含R R傳遞B ) 第2頁(共4頁)所以R為偏序關(guān)系本大題 得分四、證明題本大題共2小題，第1小題15分，第2小題10分，共25分.得分1.證明:3.A的最大元：e證明：過程見P480例15 2題最小元：a極大元：e極小元：a4B的上界：b,e下界：a上確界：b下確界：a得分5就是6.證明G中至少有52.設(shè)9階無向圖G中，每個頂點的度數(shù)不是 個6度頂點或至少有6個5度頂點.130頁第2題證明：有握手定理，9個頂點情況有:10個5