計(jì)算機(jī)《離散數(shù)學(xué)》期中試卷答案

1、名姓號%學(xué)級、JI班級年彳1業(yè),專系泉州師院2009-2010學(xué)年度第一學(xué)期2008級計(jì)算機(jī)離散數(shù)學(xué)期中試卷題序一二三四五總分成績得分評卷人簽名簽名一、單項(xiàng)選擇題：(20%每空2分)1 .設(shè)A=a,a,下列命題錯誤的是(B )。A. a P(A) B . a P(A)C. a P(A) D . a P(A)2、假定全集 E= 1,2,3,4,5,6,7,8,9,10,A=3,4,5, B= 2,3,4,7,8,9,則 AU B的位串是(D )。A. 01 B . 0011100000 C . 00 D3、下列文氏圖陰影部分所表示的集合是(A )。A. (A-(BUC)U (BUC)-A)B.

2、(A-(BAC)U (BAC)-A)C. (A-(BAC)U (BUC)-A)D. (A-(BUC)U (BAC)-A)4.設(shè)p：你主修計(jì)算機(jī)科學(xué)，q：你是新生，r :你可以從校園網(wǎng)訪問因特網(wǎng)。只有 你主修計(jì)算機(jī)科學(xué)或不是新生，你才可以從校園網(wǎng)訪問因特網(wǎng)?？煞柣癁?(C )。00A. r f pVqC. r 一 p V q5.下列是兩個命題變元A. n pA qC. p An p A q6、下列等值式不正確的是B. r f pA qD. r-pV qp, q的極小項(xiàng)是(A )A.x)A ( x) n AB. ( x)(B-A(x)B-( x)A(x)C. ( x)(A(x) A B(x)(

3、x)A(x) A ( x)B(x)D. (x)(y)(A(x) - B(y)( x)A(x) 一( y)B(y)7、若$=1,2,3,4, S上關(guān)系R的關(guān)系圖為：則R具有(B )性質(zhì)。A自反性B、自反性、對稱性C反自反性、反又稱性D、自反性、對稱性、傳遞性8.設(shè) A=a,b,c,d, A上的等價關(guān)系 R=, U I a,則對應(yīng)于R的A的劃分是(D )A. a,b,c,dB. a,b,c,dC a,b,c,dD. a,b,c,d9、設(shè)A=1 , 2, 3,則A上的二元關(guān)系有(C )個。323 3。2 2A. 2 B. 3 C. 2D. 310.下列函數(shù)是雙射的為(A )，其中：I整數(shù)集，E偶數(shù)集

4、，N 自然數(shù)集,R實(shí)數(shù)集A. f : IE , f (x) = 2x B. f : NNN, f (n) = C. f : RI , f (x) = x D. f :I.填空題(20%每題2分)1.集合的表示法有列舉法、描述法得分評卷人N, f (x) = | x |O12、設(shè)Ai 0, 7 ,i1,2,3,，則 Aii 10 3.令p：今天下雪了， q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化4.復(fù)合命題(p q) V ( p q)是 永真 式(永真式或永假式或可滿足射或都不是)。三、計(jì)算題(20%每題5分)1、問 AU (B C)=(A U B) (AU C)嗎為什么解：上式不成

5、立。設(shè) A=1,2,3,B=2,3,4,C=3,4,5有：AU(BC)= 1,2,3 U2,5=1,2,3,5(A U B) (AU C)= 1,2,3,41,2,3,4,5=55.令謂詞P(x,y)表示“ x愛y”，個體域是全世界所有人的集合，用 P(x,y)、量詞和邏輯詞符號化“所有人都愛某些人”x yP(x,y)xF(x) xG(x)的前束范式是y x F(y)G(x)7 . 設(shè) A=a,b,c,d, 下列左圖所示關(guān)系矩陣所表示的關(guān)系R= ,1MR 08、設(shè)某偏序集的哈斯圖如下列右圖，該偏序集的拓?fù)渑判驗(yàn)?,5,3,2,7,9,6,4,89、設(shè) f : NR N,且 f (x)1,當(dāng)x為

6、奇數(shù)二當(dāng) X為偶數(shù)則 f(1,3,4,6= 1,232、求公式(p A q) V r的標(biāo)準(zhǔn)析取范式，再根據(jù)標(biāo)準(zhǔn)析取范式求標(biāo)準(zhǔn)合取范式。解：(p A q) V r(p q r) (p q r) ( p(p q r) (p q r) (p qr)mm3 m5m6mMA MA Mq r)得分評卷人10、給定函數(shù)f: Sf S,S=0,1,f(x)=x/2+1/4,f是 單射(滿射或單射或雙A中無最小元，最大元為 xlox 2,X3,X4的極小元為x4 ,極大元為x2,x3。x 2,x3的上界為x1 ,下界為x4。x 3,x4的上確界為x3,下確界為x4。3、設(shè) A=a,b,c,d,其上關(guān)系 R= ,

7、 , , S=,求(1) R S(2) R的對稱閉包及傳遞閉包。得分評卷人得分評卷人R S=,(2)R 的對稱閉包 S(R)= , , , , R 的傳遞閉包 t(R)= , , , B)四、證明題(20%每題5分)1、設(shè)A、B是任意集合，證明： (A-B) U(B-A尸(A U B)-(A證：=(A U B)-(A A B)=(A u B) n (A n B)=(A U B) n (A U B)=An (A U B) U Bn (A U B)=An bu Bn a=(A-B) U(B-A)4、設(shè) A xi,x2,x3, x4, 4,偏序集求A中最小元與最大元。x 2,*34的極小元和極大元。

8、x 2,x3的上界與下界。x 3,x4的上確界與下確界。解：A, R 的Hass圖為:2、證明下列推理:前提：(p q)r, rs,結(jié)論：q(pq) r前提引入(2)rs前提引入(pq) s(1)(2)假言二段論(4) sp前提引入(5)P(2)化簡(6) s(2)化簡(7) (Pq)(3)(6)拒取式(8) Pq置換(9) q(5)(8)析取三段論3、設(shè)F, G是任意的關(guān)系，證明：(FG)-1= G-1 F-1證：任取 x, yX, y(F G)y, XF Gt( y,t F t, X G) t( t, yF 1X, tG 1)t(X,tG 1t, yF 1)1 u 1X, y G F前提引

9、入(1) ES規(guī)則前提引入(3)US規(guī)則(2)(4)析取三段論前提引入(6)US規(guī)則拒取式(8)EG規(guī)則歡騎自行車，有的人不愛騎自行車，因而有的人不愛步行。邏輯推證此結(jié)論的有效性。(設(shè)個體域是人類)Q(x) ： X喜歡步行；S(x) ： X喜歡乘汽車； R(x) : X喜歡騎自行車。前提：x(Q(x)S(x), x(S(x) R(x), x R(x)結(jié)論：x Q(x)證： X R(x) R(a) x(S(x) R(x) S(a) R(a)(5)S(a)(6) x(Q(x) S(x)(7)Q(a) S(a) Q(a)(9) x Q(x)4.任何人如果他喜歡步行，他就不喜歡乘汽車，對于每個人或者喜歡乘汽車或者喜得分評卷人五、判斷題（20%每題2分）（在括號中寫“對”或“錯”）1、gcd（21,7）的值為7, 的值為-2。（ 對 ）2、設(shè)A,B,C均為E的子集，則A B AU （B-A尸A。（ 錯）3、間接證明法可形式化地表示為：A-BB- A。（ 對 ）4、對每個最大項(xiàng)而言，只有與下標(biāo)編碼相同的賦值是成假賦值，其余都是成真賦值。（對）5、設(shè)個體域是整數(shù)集Z,則 x y z（x+y=z）的真值為1。（錯 ）6、邏輯公式（xF（x） yG（y）yG（y）不是永真式。（對 ）7、因?yàn)槿鬜是A上的關(guān)系，且 m,n N,則Rf R=RTn,所以R R1=R=IA.（錯