0418歷年真題答案版02324離散數(shù)學(xué)

1、2009 年 4 月高等教育統(tǒng)一命題離散數(shù)學(xué)試題課程代碼：02324一、單項選擇題（本大題共 15 小題，每小題 1 分，共 15 分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1下列為兩個命題變元 P，Q 的小項是（APQù P Cù PQ）Bù PQ Dù PPQ2下列語句中是真命題的是（ A我正在說謊C如果 1+2=3，那么雪是黑的）B嚴禁吸煙D如果 1+2=5，那么雪是黑的3設(shè) P：我們劃船，Q：我們跑步。命題“我們不能既劃船又跑步”符號化為（）Aù Pù Q C

2、ù（P«Q）4命題公式（P（PQ）Q 是（Bù Pù Q Dù（ù Pù Q）B蘊含式D等價式）B001，011，101，110，111D無A式C重言式5命題公式ù（PQ）R 的成真指派是（A000，001，110，C全體指派6在公式（ " x ）F（x，y）（ $ y）G（x，y）中變元 x 是（）A自由變元C既是自由變元，又是約束變元B約束變元D既不是自由變元，又不是約束變元7集合 A=1，2，10上的關(guān)系 R=<x，y>|x+y=10，xA，yA，則 R 的性質(zhì)是（）A自反的C傳遞的、對

3、稱的B對稱的D反自反的、傳遞的8. 若 R 和 S 是集合 A 上的兩個關(guān)系，則下述結(jié)論正確的是（A. 若 R 和S 是自反的，則 RS 是自反的B. 若 R 和S 是對稱的，則 R o S 是對稱的）C若 R 和S 是稱的，則 R o S 是稱的D若 R 和S 是傳遞的，則 RS 是傳遞的9R=<1，4>，<2，3>，<3，1>，<4，3>，則下列不是t（R）中元素的是（）第 1 頁 共 7 頁A<1，1>C<1，3>B<1，2>D<1，4>10設(shè) A=1，2，3，4，5，6，7，8，下列選項正確

4、的是（）B1，2，3 Í ADÆAA1AC4，5 Ì A11在自然數(shù)集 N 上，下列運算是可結(jié)合的是（）Aa * b=a-2bCa * b=-a-b12在代數(shù)系統(tǒng)中，整環(huán)和域的關(guān)系是（ A整環(huán)一定是域C域一定是整環(huán)13下列所示的哈斯圖所對應(yīng)的偏序集中能Ba * b=mina，bDa * b=|a-b|）B域不一定是整環(huán)D域一定不是整環(huán)格的是（）ABCD14. 設(shè) G 為有 n 個結(jié)點的簡單圖，則有（A. (G)n C(G)n）B(G)nD(G)n15具有 4 個結(jié)點的非同構(gòu)的無向樹的數(shù)目是（）A2C4B3D5二、填空題（本大題共 10 小題，每小題 2 分，共 2

5、0 分）請在每小題的空格中填上正確。錯填、不填均無分。16（ " x）（ " y）（P（x，y） Q（y，z） $ xP（x，y）中" x的轄域為。的轄域為， $ x17兩個重言式的析取是式，一個重言式與一個式的析取是式。18. 設(shè) N 是自然數(shù)集合，f 和 g 是 N 到 N 的函數(shù)，且 f（n）=2n+1，g（n）=n2，那么復(fù)合函數(shù)（f o f）（n）= （g o f）（n）= 。19. 設(shè)復(fù)合函數(shù) g o f 是從 A 到 C 的函數(shù)，如果 g o f 是滿射，那么必是滿射，如果第 2 頁 共 7 頁g o f 是入射，那么必是入射。20設(shè) A=1，2，B

6、=2，3，則 A-A=，A-B=。21設(shè) S 是非空有限集，代數(shù)系統(tǒng)<P（S），>中，其中 P（S）為集合 S 的冪集，則 P（S）對運算的元是，零元是。22在<Z6,+ >中，2 的階是 。23設(shè)<A，>是格，其中 A=1，2，3，4，6，8，12，24，為整除關(guān)系，則 3 的補元是。24在下圖中，結(jié)點 v2 的度數(shù)是。é01ù1010025設(shè)圖 D=<V，E>，V=v1，v2，v3，v4，若 D 的鄰接矩陣 A= ê11ú ，則 deg-（v1）1ê1êë10 0ú

7、;1úû0=，從 v2 到 v4 長度為 2 的路有條。三、計算題（本大題共 5 小題，第 26、27 小題各 5 分，第 28、29 小題各 6 分，第 30 小題8 分，共 30 分）26已知 A=Æ，Æ，1，B=Æ，1，1，計算 AB，A+ B，A 的冪集 P（A）。27. 構(gòu)造命題公式（PQ）P）R 的真值表。28. 下圖給出了一個有向圖。（1）求出它的鄰接矩陣 A；（2）求出 A2，A3，A4 及可達矩陣P。29求下列公式的主合取范式和主析取范式：P（ù P（Q（ù QR）30設(shè) A=1，2，3，4，6，8，12，

8、24，R 為 A 上的整除關(guān)系，試畫<A，R>的哈斯圖， 并求 A 中的最大元、最小元、極大元、極小元。四、證明題（本大題共 3 小題，第 31、32 小題各 6 分，第 33 小題 8 分，共 20 分）31在整數(shù)集 Z 上定義： a o b = a + b - 2 , "a, b Î Z ，證明：<Z， o >是一個群。32R 是集合 A 上自反和傳遞的關(guān)系，試證明：R o R=R。33證明：邊 e 是圖 G 的一條割邊，當且僅當圖 G 中不存在包含邊 e 的簡單回路。五、應(yīng)用題（本大題共 2 小題，第 34 小題 6 分，第 35 小題 9 分，共 15 分）第 3 頁 共 7 頁34構(gòu)造下面推理的證明。如果小張和小王去看，則小李也去看。小趙不去看或小張去看。小王去看。所以，當小趙去看時，小李也去。35今有 n 個人，已知他們中任何 2 人的朋友合起來一定包含其余 n-2 人。試證明：（1）當 n3