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

1、系 專業(yè) 年級 班級 學(xué)號 姓名 裝訂線泉州師院2009-2010學(xué)年度第一學(xué)期2008級計(jì)算機(jī)離散數(shù)學(xué)期中試卷題 序一二三四五 總分成 績簽 名得 分評卷人一、單項(xiàng)選擇題:（20%，每空2分） 1設(shè)A=a,a，下列命題錯誤的是（ B ）。AaP(A) BaP(A)CaP(A) DaP(A)2、假定全集E1,2,3,4,5,6,7,8,9,10,A=3,4,5，B2,3,4,7,8,9，則AB的位串是（D）。A01 B00 C00 D003、下列文氏圖陰影部分所表示的集合是( A )。A. (A-(BC)(BC)-A) B. (A-(BC)(BC)-A)C. (A-(BC)(BC)-A) D.

2、 (A-(BC)(BC)-A)4設(shè)p：你主修計(jì)算機(jī)科學(xué)，q：你是新生， r：你可以從校園網(wǎng)訪問因特網(wǎng)。只有你主修計(jì)算機(jī)科學(xué)或不是新生，你才可以從校園網(wǎng)訪問因特網(wǎng)。可符號化為( C )。 ArpqBrpq CrpØqDrpØq 5下列是兩個命題變元p，q的極小項(xiàng)是（ A ）Apq BpqCppqDppq6、下列等值式不正確的是（ C ）A(x)A(x)AB(x)(BA(x)B(x)A(x)C(x)(A(x)B(x)(x)A(x)(x)B(x)D(x)(y)(A(x)B(y)( x)A(x)(y)B(y)7、若s=1,2,3,4，S上關(guān)系R的關(guān)系圖為：則R具有（ B ）性質(zhì)。A

3、、自反性 B、自反性、對稱性C、反自反性、反對稱性 D、自反性、對稱性、傳遞性8設(shè)A=a,b,c,d，A上的等價關(guān)系R=<a,b>,<b,a>,<c,d>,<d,c>IA，則對應(yīng)于R的A的劃分是（ D ）Aa,b,c,dBa,b,c,dCa,b,c,dDa,b,c,d 9、設(shè)A=1，2，3，則A上的二元關(guān)系有（ C ）個。 A. 23 B. 32 C. D. 10下列函數(shù)是雙射的為（ A ），其中：I整數(shù)集，E偶數(shù)集， N自然數(shù)集，R實(shí)數(shù)集。A. f : IE , f (x) = 2x B. f : NNN, f (n) = <n , n+

4、1> C. f : RI , f (x) = x D. f :IN, f (x) = | x |得 分評卷人二填空題（20%，每題2分） 1集合的表示法有 列舉法、描述法 。3令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為 pØq 。4復(fù)合命題(pØq)(ØpØq)是_ 永真_式（永真式或永假式或可滿足式）。5令謂詞P(x,y)表示”x愛y”,個體域是全世界所有人的集合，用P(x,y)、量詞和邏輯詞符號化“所有人都愛某些人”： "x$yP(x,y) 。6$xF(x)Ù"xG(x)的前束范式是

5、 $y"x F(y)Ù G(x) 。7設(shè)A=a,b,c,d,下列左圖所示關(guān)系矩陣所表示的關(guān)系R= <a,a>,<a,b>,<b,a>,<b,d>,<c,b>,<c,c>,<d,c> 。8、設(shè)某偏序集的哈斯圖如下列右圖，該偏序集的拓?fù)渑判驗(yàn)?1,5,3,2,7,9,6,4,8 。9、設(shè)f：NN，且，則f(1,3,4,6= 1,2,3 。 10、給定函數(shù)f：SS,S=0,1,f(x)=x/2+1/4,f是_單射_(滿射或單射或雙射或都不是)。得 分評卷人三、計(jì)算題（20%，每題5分） 1、問A(

6、BÅC)=(AB)Å(AC)嗎為什么解：上式不成立。設(shè)A=1,2,3,B=2,3,4,C=3,4,5有：A(BÅC)= 1,2,32,5=1,2,3,5(AB)Å(AC)= 1,2,3,4Å1,2,3,4,5=52、求公式(pq)r的標(biāo)準(zhǔn)析取范式，再根據(jù)標(biāo)準(zhǔn)析取范式求標(biāo)準(zhǔn)合取范式。解：(pq)rÛ (pÙqÙØr)Ú(pÙqÙr) Ú(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(p&

7、#217;ØqÙr)Ú(pÙqÙr)Û m1Úm3Úm5Ú m6Úm7ÛM0M2M43、設(shè)A=a,b,c,d，其上關(guān)系R=<b,b>，<b,c>，<c,a>，S=<b,a><c,d>,<d,a>，求（1）RS （2）R的對稱閉包及傳遞閉包。 解：(1) RS=<b,a>,<b,d>(2) R的對稱閉包S(R)= <b,b>，<b,c>，<c,a>，<

8、c,b>，<a,c>(3) R的傳遞閉包t(R)= <b,b>，<b,c>，<c,a>，<b,a> 4、設(shè)，偏序集的Hass圖為：求 A中最小元與最大元。 x2,x3,x4的極小元和極大元。 x2,x3的上界與下界。 x3,x4的上確界與下確界。解：A中無最小元，最大元為x1。 x2,x3,x4的極小元為x4，極大元為x2,x3。 x2,x3的上界為x1，下界為x4。 x3,x4的上確界為x3，下確界為x4。得 分評卷人四、證明題（20%，每題5分）1、設(shè)A、B是任意集合，證明： (A-B)(B-A)= (AB)-(AB) 證：

9、=(AB)-(AB)=(AB) (AB)=(AB)(AB)=A(AB)B(AB)=ABBA=(A-B)(B-A)2、證明下列推理：前提：(pÙq) ®r, r®s, ØsÙp結(jié)論：Øq3、設(shè)F，G是任意的關(guān)系，證明：(F°G)-1= G-1°F-14. 任何人如果他喜歡步行，他就不喜歡乘汽車，對于每個人或者喜歡乘汽車或者喜歡騎自行車，有的人不愛騎自行車，因而有的人不愛步行。邏輯推證此結(jié)論的有效性。 (設(shè)個體域是人類)Q(x)：x喜歡步行； S(x)：x喜歡乘汽車 ； R(x)：x喜歡騎自行車。前提："x(

10、Q(x) ®ØS(x), "x(S(x) Ú R(x), $xØR(x)結(jié)論：$xØQ(x)得 分評卷人五、判斷題（20%，每題2分）(在括號中寫“對”或“錯”)1、 gcd(21,7)的值為7，é-2.3ù的值為-2。( 對 )2、 設(shè)A,B,C均為E的子集，則AÍBÛA(B-A)=A。( 錯 ) 3、間接證明法可形式化地表示為：ABÛØBØ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，則Rm°Rn=Rm+n,所以R°R-1=R0=IA. （ 錯）8、一個關(guān)系若是自反的，則必定不是反自反的，若是對稱的，則必定不是反對稱的。( 錯 )9、