離散數(shù)學(xué) 期末復(fù)習(xí)題.doc

四川大學(xué)錦城學(xué)院考試試題 ( 2010 2011學(xué)年 第 二 學(xué)期)課程號(hào)：020255 課序號(hào)： 課程名稱：離散數(shù)學(xué) 任課教師： 成績(jī)：適用專業(yè)年級(jí)：07 計(jì)算機(jī)科學(xué)和軟件 學(xué)生人數(shù)： 印題份數(shù)： 學(xué)號(hào)： 姓名：考 試 須 知四川大學(xué)錦城學(xué)院學(xué)生參加由學(xué)校組織或由學(xué)校承辦的各級(jí)各類考試，必須嚴(yán)格執(zhí)行四川大學(xué)錦城學(xué)院考試工作管理辦法和四川大學(xué)錦城學(xué)院考場(chǎng)規(guī)則。有考試違紀(jì)作弊行為的，一律按照四川大學(xué)錦城學(xué)院學(xué)生考試違紀(jì)作弊處罰條例進(jìn)行處理。四川大學(xué)錦城學(xué)院各級(jí)各類考試的監(jiān)考人員，必須嚴(yán)格執(zhí)行四川大學(xué)錦城學(xué)院考試工作管理辦法、四川大學(xué)錦城學(xué)院考場(chǎng)規(guī)則和四川大學(xué)錦城學(xué)院監(jiān)考人員職責(zé)。有違反學(xué)校有關(guān)規(guī)定的，嚴(yán)格按照四川大學(xué)錦城學(xué)院教學(xué)事故認(rèn)定及處理辦法進(jìn)行處理。一、單項(xiàng)選擇題1. 下列句子是命題的是( )。A.上課了嗎? B.11+1=100。 C.再過10年，我們就能夠上火星了！ D.本語句是假的。2. 設(shè)A=1，2，B=a,b，下列二元關(guān)系R不是A到B的函數(shù)的是( )；A.R=, B.R=,C.R=, D.R=,3. 在自然數(shù)集合N上，下列定義的運(yùn)算中是可結(jié)合的只有( )；A.a*b=a-b B.a*b=max(a,b)C.a*b=a+2b D.a*b=|a-b|4. 設(shè)是環(huán)，則下列正確的是（ ）；A是半群 B是可換群C對(duì)+是可分配的D+對(duì)是可分配的5 . 設(shè)群（G , * ）的階為15，則其真子群的最高階是( )；A.1 B.3C.5 D.156無向圖G=（n, m）是完全圖，則（ ）；A. n=m B. m=n(n-1)C. m=n(n-1)/2 D. m=n(n+1)/27. 圖G= 是一個(gè)（n, m）圖，則所有節(jié)點(diǎn)的次數(shù)之和等于( )；A.2m B. 2nC.m+n D. m-n8. 在公式中變?cè)獄是（ ）；A自由變?cè)?B約束變?cè)狢既是自由變?cè)?，又是約束變?cè)?D既不是自由變?cè)植皇羌s束變?cè)?. 非空集合A上的二元關(guān)系R若是自反、對(duì)稱的和傳遞的，則R是( )；A.偏序關(guān)系B.等價(jià)關(guān)系C.相容關(guān)系D.擬序關(guān)系本題 2 頁，本頁為第 1 頁 教務(wù)部試題編號(hào)： 四川大學(xué)錦城學(xué)院考試試題 10.設(shè)全總個(gè)體域?yàn)檎麛?shù)集，下列謂詞公式中真值為假的是( )。A. B. C. D. 二、填空題1. 集合X=a，b，c上二元關(guān)系R=，則R的自反閉包r(R)= _；2. 設(shè)集合A=a, b, c, 則A的冪集為：_；3設(shè)代數(shù)系統(tǒng)是環(huán)，則代數(shù)系統(tǒng)滿足_；4. 設(shè)群（Z , * ）（Z是整數(shù)集）是一個(gè)循環(huán)群，其生成元是_和_；5. 整數(shù)環(huán)中加法的零元是_，乘法的單位元是_；6. 在一棵內(nèi)向樹中，有且只有一個(gè)結(jié)點(diǎn)的引出次數(shù)為_；7. 把下述命題符號(hào)化：“張三身體好，工作也好?！?； 8. 設(shè)個(gè)體域是0,1,2，則xS(x)等于命題公式 _。三、計(jì)算題1設(shè)X=a，b，c，d，R是X上的二元關(guān)系，R=,。（1）畫出R的關(guān)系圖；（2）寫出R的關(guān)系矩陣。2設(shè)A1，2，3，4，6，12，R為A上整除關(guān)系，試畫的哈斯圖，并求A中的最大元，最小元，極大元，極小元。3求有向圖G的鄰接矩陣，其中Vv1,v2,v3，E(v1,v2), (v2,v3), (v3,v2), (v3,v1)。4. 構(gòu)造命題公式(PQ)(PQ)的真值表，并寫出其主析取范式。5. 求公式 xP(x) yQ(y) 的前束范式。四、應(yīng)用題 判斷下面推理是否正確，并證明你的結(jié)論。我夫人過生日，我送一束鮮花給她，除非我工作忙。今天我沒有送鮮花給夫人，今天是夫人的生日，由此是否可以推得“今天我工作忙”。 本題 2 頁，本頁為第 2 頁 教務(wù)部試題編號(hào)： 一、單項(xiàng)選擇題1. 下列句子是命題的是( )。A. 下雪了嗎? B. 1+1=10。 C. 天氣真好！ D. 我正在說謊。2. 設(shè)A=1，2，B=a,b，下列二元關(guān)系R是A到B的函數(shù)的是( )；A. R=, B. R=,C. R=, D. R=,3. 是整數(shù)加群，其單位元是 ( )；A. 0 B. 1C. -1 D. 任意元4. 設(shè)是域，則下列正確的是（ ）；A是可換群 B是可換單元半群C對(duì)+是可分配的 D每個(gè)元均有逆元5 . 設(shè)有限群（G , * ）的階為7，下列敘述不正確的是( )；A. 有1階子群B. 有7階子群C. 無真子群 D. 有真子群6有向圖G=（n, m）是完全圖，則（ ）；A. n=m B. m=n(n-1)C. m=n(n-1)/2 D. m=n(n+1)/27. 圖G= 是一個(gè)（n, m）連通圖，若要確定它的生成樹，需刪去的邊的數(shù)目是( )；A. n-m B. m-n+1C .m-n-1 D. m-n8. 在公式中變?cè)獄是（ ）；A自由變?cè)?B約束變?cè)狢既是自由變?cè)?，又是約束變?cè)?D既不是自由變?cè)?，又不是約束變?cè)?. 非空集合A上的二元關(guān)系R若是反自反、傳遞的，則R是( )；A.偏序關(guān)系 B.等價(jià)關(guān)系C.相容關(guān)系 D.擬序關(guān)系10.下列等式正確的是( )。A. B. C. D. 二、填空題1. 集合X=1，2，3上二元關(guān)系R=，則R的對(duì)稱閉包s(R)= _；2. 設(shè)集合A=, 則A的冪集為：_；3設(shè)代數(shù)系統(tǒng)是環(huán)，則代數(shù)系統(tǒng)滿足_；（什么定律）4. 模m的剩余類加群是一個(gè)循環(huán)群，其生成元是_；5. 把下述命題符號(hào)化：“說數(shù)理邏輯枯燥無味或毫無價(jià)值，那是不對(duì)的?！?； 三、計(jì)算題1設(shè)X=a，b，c，d，e，R是X上的二元關(guān)系，R=, , , , , ,。（1）畫出R的關(guān)系圖；（2）寫出R的關(guān)系矩陣。2設(shè)A1，2，3，6，12, 18，R為A上整除關(guān)系，試畫的哈斯圖，并求B=2, 3, 6, 12中的最大元，最小元，極大元，極小元。3. 構(gòu)造命題公式(PQ)(PQ)的真值表，（1）求出成真賦值，成假賦值；（2）判斷公式的類型；（3）寫出其主合取范式。4