最新2015年7月離散數(shù)學(xué)試題(附答案)

1、1全國(guó) 2015 年 7 月自考試題離散數(shù)學(xué)（附答案）課程代碼：02324一、單項(xiàng)選擇題（本大題共 15 小題，每小題 1 分，共 15 分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在 題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1設(shè) P:他聰明，Q:他用功，命題“他雖聰明但不用功”的符號(hào)化正確的是 （ ）A.PAQ B.PAQC.PQ D.PVQ2.下面聯(lián)結(jié)詞運(yùn)算不可交換的是（）A. AB.C.VD. J3.下列命題公式不是重言式的是（）2A.Q(PVQ)B. (PAQ)P3C.(PAQ)A(PVQ)D. (P-Q) J (PVQ)4 下列等價(jià)式不正確的是()A- x(P

2、(x) Q(x)：= - xP(x) - xQ(x)B- x(P(x) Q(x)：= - xP(x) - xQ(x)Cx(P(x) Q(x)：= xP(x) . -IxQ(x)D-x(P(x) Q)：二-xP(x) QB (x): x 犯錯(cuò)誤，命題“沒(méi)有不犯錯(cuò)誤的人”符號(hào)化為設(shè) A (x) :x 是人,-x(A(x) B(x)B .x(A(x)B(x)x(A(x) B(x)D.x(A(x)B(x)4設(shè) M=x|f1(x)=0,N=x|f2(x)=0，則方程 f1(x) f2(x)=0 的解為(A.MnN B.MUNC . M 二 N D . M-N7.設(shè) A-B=、，貝 9 有()C. AB

3、D . A 二 B8.A ,B 是集合，P( A ),P( B)為其幕集，且 AAB=_ ,則 P(A)AP(B)為()A . 一 B. _ C. 一一 D. r , 一一9.設(shè)集合 A=1 , 2, 3,10，下列定義的運(yùn)算關(guān)于集合 A 是不封閉的是( )A.x*y=maxx,yB.x*y=minx,yC.x*y=GCDx,y,即 x,y 的最大公約數(shù)D.x*y=LCMx,y,即 x,y 的最小公倍數(shù)6.510. 設(shè) H ,K 是群(G,)的子群，下面代數(shù)系統(tǒng)是(G,)的子群的是()A. (HAK,)B. (HUK,)C. (K-H ,) D . (H-K ,)11 設(shè) A=1 , 2, 3

4、, 4, 5 , B=6 , 7, 8, 9, 10，以下關(guān)系是從 A 到 B 的入 射函數(shù)的是（ ）A.f =,B.f =,C.f =,D.f =,12. 設(shè)簡(jiǎn)單圖 G 所有結(jié)點(diǎn)的度數(shù)之和為 12,則 G 一定有（）A . 3 條邊 B . 4 條邊C. 5 條邊 D . 6 條邊13. 下列不一定是樹(shù)的是（）A .無(wú)回路的連通圖 B .有 n 個(gè)結(jié)點(diǎn)，n-1 條邊的連通圖6C.每對(duì)結(jié)點(diǎn)之間都有通路的圖D .連通但刪去一條邊則不連通的圖14下面關(guān)于關(guān)系 R 的傳遞閉包 t(R)的描述最確切的是(A . t(R)是包含 R 的二元關(guān)系 B . t(R)是包含 R 的最小傳遞關(guān)系C. t(R)是

5、包含 R 的一個(gè)傳遞關(guān)系D . t(R)是任何包含 R 的傳遞關(guān)系15.歐拉回路是()A .路徑 B .跡C.既是初級(jí)回路也是跡D .既非初級(jí)回路也非跡、填空題(本大題共 10 小題，每小題 2 分，共 20 分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16 .設(shè) A=1 , 2 , B=2 , 3，則 AA=_ , AB=_ 。17. 設(shè) A=1 , 2, 3, 4上關(guān)系 R=v1,2,v2,4,v3,3,，則 R 的自反閉包r(R)=_，對(duì)稱閉包 S (R) =_ 。18._ 命題公式(PQ)-1P 的成真指派為_(kāi),成假指派為_(kāi) ,v2,4,v3,3,B=v1,3,v2,4, 那

6、 么 dom(AUB)=_ ,ran(AGB)=_ 。23._如下圖的有補(bǔ)格中，c 的補(bǔ)元是, b的補(bǔ)元是_ 。24._在根樹(shù)中，若每一個(gè)結(jié)點(diǎn)的出度_ m 則稱這棵樹(shù)為 m 叉樹(shù)。如果每一個(gè)結(jié)點(diǎn)的出度 _ m 或 0,則稱這棵樹(shù)為完全 m 叉樹(shù)。825.Zn,二是一個(gè)群，其中 Zn=0,1,2,.,n-1,x 二 y=(x+y)mod n,則在 Z6,二中，1 的階是_ , 4 的階是_ 。三、計(jì)算題(本大題共 5 小題，第 26、27 小題各 5 分，第 28、29 小題各 6 分,第 30 小題 8 分，共 30 分)26.構(gòu)造命題公式(P Q J Q R)-PR的真值表。27 若集合 A

7、=1 , 2 , 3的幕集為 P (A),集合 B=0 , 2 , 2的幕集為 P(B),求P(A)nP(B)。28.設(shè) X=1 , 2, 3, 4 , R 是 X 上的二元關(guān)系，只只=,。(1) 畫(huà)出 R 的關(guān)系圖；(2) 寫(xiě)出 R 的關(guān)系矩陣；(3) 說(shuō)明 R 是否具有自反、反自反、對(duì)稱、傳遞性質(zhì)。29.求下列公式的主析取范式和主合取范式：(P-(QAR)入(1P(1Q R)。930.設(shè) A=a,b,c,P(A)是 A 的幕集，R 為 A 上的包含關(guān)系，試給出的哈斯圖，并給出子集a,b,a,c,c的極大元、極小元、最大元、最小元。四、證明題(本大題共 3 小題，第 31、32 小題各 6

8、分，第 33 小題 8 分，共 20分)1 x31 設(shè) H 是形如1的 2X2 階矩陣的集合，H 中定義通常的矩陣乘法運(yùn)算。1 xJ1-x驗(yàn)證 H 是群，1=1。32.設(shè) R 為 NXN 上的二元關(guān)系，一 ：ab：c,d NXN，: a,b R：c,d = b二d,證明 R 為等價(jià)關(guān)系。133 .簡(jiǎn)單圖 G 有 n 個(gè)結(jié)點(diǎn)，m 條邊，設(shè) m2(n-1)(n-2)，證明：G 是連通的。五、應(yīng)用題(本大題共 2 小題，第 34 小題 7 分，第 35 小題 8 分，共 15 分)34. 構(gòu)造下面推理的證明。只要 A 曾到過(guò)受害者房間并且 11 點(diǎn)以前沒(méi)離開(kāi)，A 就犯了謀殺罪。A 曾到過(guò)受 害者房間

9、。如果在 11 點(diǎn)以前離開(kāi)，看門(mén)人會(huì)看見(jiàn)他。看門(mén)人沒(méi)有看見(jiàn)他。所以 A 犯了謀殺罪。35. 在某次國(guó)際會(huì)議的預(yù)備會(huì)中，共有 8 人參加，他們來(lái)自不同的國(guó)家。已知 他們10中任何兩個(gè)無(wú)共同語(yǔ)言的人中的每一個(gè)，與其余有共同語(yǔ)言的人數(shù)之和大于或等于 8，問(wèn)能否將這 8 個(gè)人排在圓桌旁，使其任何人都能與兩邊的人交談。離敬數(shù)學(xué)試題答案及評(píng)分參考第丨頁(yè)（共4頁(yè)）102008 年 7 月自考離散數(shù)學(xué)試題參考答案2008年7月高等教育自學(xué)考試全國(guó)統(tǒng)一命題考試離散數(shù)學(xué)試題答案及評(píng)分參考（課程代碼2324）一、單項(xiàng)選擇題（本大題共15小紙每小國(guó)1分共15分）EB 2. B 3. C 4. A 5. D 6, B

10、7. 8. B 9,D10, A）1. A L2. D 13. C B 15. B二, 填空題（本大題共10小題,每小題2分，共20分16.01.317- , , . pt , , , , , , , 18.00,01,10 II19. jr.y.z xry20. -2% -1-32L02Z 1,2 3.4423. Au 和注fi I2牡衽二25.63三、計(jì)算題本大題共5小題，第26、27少題各5分，第28、29小題各6分.第如小題8分，共犯分】26.解：P Q RPVQQAR PVQ-QARPAIR（PVQTQARI 卩和（1分0 0 0001000 0 100100（】 分）0 1 01

11、r00010 1 111I00（1分）1 0 0100111 0 1r i0001（11 1 0i廠0111 1 1iIL 100（1分）27. ；P（A） =0（訂,卩,3.1,2（2分）P（B） =0,0|212,02,2G2分）則P（A）HP（B） =0（1分）2-解：（1 ） R的關(guān)系圖如圖所示 a離哉數(shù)學(xué)試題答案及評(píng)分參考第2頁(yè)（共4頁(yè)）11子集,At（otc,e的極大元為a,AfaTc；小元為, 訂,無(wú)最大元，無(wú)雖小元。（4分）四、證朋題（本大題共3小題，第322小題各5分，第甜小羈8分，共20分）31證明:因?yàn)閷?duì)于枉意的（:：） JEH 有t X D=（i；）皿H對(duì)運(yùn)算是封閉的,

12、（2分）且因矩陣運(yùn)算墨可結(jié)合的*我們只需說(shuō)明H存在單垃元，每個(gè)元索有逆元即可。 門(mén)分）/I 0顯然（JeHjg單位元.liio-R的關(guān)系矩陣是：；：；：(1分)(I #)(巧由于主對(duì)角統(tǒng)上不全為不是自反的；由于對(duì)角線上存在非零元素，R不是 反自反的迅不是對(duì)稱的川是傳遞的*(4分)29. jg：(lPV(QAR) A(PV(QVR)O(1PVQ)/(1PVR)A(PVQVR)(1PVQ) V(BA1R) A(1PVR V(QAlQ) A(PVQVR) eCiPVQVR)A(lPVQVlR) A(lPVQVR) A(lPVlQVR) A(PV QVR)o 11(0,4,5,6)2(1.2,3.7（

13、弓分心分）2離戰(zhàn)數(shù)學(xué)試題答案及評(píng)分翁考第3頁(yè)（共4頁(yè)）12且毗；）（）（；7）（）（；XH XI：）利 卄 元素都存在逆元&（2分3N證明：因?yàn)镠 eN= R T所以R具有自反性G分）V t,rf eNKNTR =b - d=db= Rt所以R具有對(duì)稱性。（2分）V * t eW x N, R , R =占=也甩=gb wg R ,因此R具有傳邊性心（2分綜上可得R進(jìn)等價(jià)關(guān)系。33一證明：（用反證法兒 假設(shè)G二丈嘰E是不連適的,不妨設(shè)G可分成兩個(gè)不連通部 分G- uy.E】 ,G3其中 | | =Jtj, ! Va|=嗎顯然，叫 +（2分）-由于叫，所以l,i 1 ,2D-IEH IE, |+|EJ莖叢:）畀烏二!（n - ） （n,+如-2）wx（4分）這與假設(shè)相矛盾因此,C是連通的。五、應(yīng)用題（本大題共2小題，第34小題7分，第笳小題8分.共15分）34.解：設(shè)P：A曾到過(guò)受害者房間Q：A 11點(diǎn)以前離開(kāi)犯謀汆罪前提:P/QjR,lQiS結(jié)論哉35-解：設(shè)*個(gè)人分別為叫宀,作無(wú)向簡(jiǎn)單圖G= ,其中V = vlTvJt.Vv.rVe V,且濘丿，若vt與vf有共同語(yǔ)言，就在vitvi之間連無(wú)向邊（記宀人由此可得垃集合E,則G為8