離散數(shù)學(xué)期末試卷A卷

1、課程名稱： 離散數(shù)學(xué) 任課教師： 學(xué)號(hào)：姓名： -四川大學(xué)期末考試試題（閉卷）（2014-2015學(xué)年第1學(xué)期）課程號(hào)： 304039040課程名稱： 離散數(shù)學(xué)（A卷） 任課教師： 馮偉森 石兵 周莉 陳瑜 林蘭適用專業(yè)年級(jí)： 2013級(jí)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)： 姓名： 考試須知四川大學(xué)學(xué)生參加由學(xué)校組織或由學(xué)校承辦的各級(jí)各類考試，必須嚴(yán)格執(zhí)行四川大學(xué)考試工作管理辦法和四川大學(xué)考場規(guī)則。有考試違紀(jì)作弊行為的，一律按照四川大學(xué)學(xué)生考試違紀(jì)作弊處罰條例進(jìn)行處理。四川大學(xué)各級(jí)各類考試的監(jiān)考人員，必須嚴(yán)格執(zhí)行四川大學(xué)考試工作管理辦法、四川大學(xué)考場規(guī)則和四川大學(xué)監(jiān)考人員職責(zé)。有違反學(xué)校有關(guān)規(guī)定的，嚴(yán)格按照

2、四川大學(xué)教學(xué)事故認(rèn)定及處理辦法進(jìn)行處理。題 號(hào)一（16%）二（14%）三（10%）四（30%）五（30%）六七八卷面成績得 分閱卷教師閱卷時(shí)間一、單項(xiàng)選擇題（本大題共16小題，每小題1分，共16分）提示：在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分123456789101112131415161. 令R: 小王吃飯；S：小王看電視。則語句“小王一邊吃飯一邊看電視”可以符號(hào)化為（ ）。（A)RS； （B）RS； （C）RS； （D）RS2. 令P(x):x是實(shí)數(shù)，Q(x):x是有理數(shù)。則語句“并非每個(gè)實(shí)數(shù)都是有理數(shù)”可以符號(hào)化為（ ）。

3、 （A）"x(R(x)Q(x)； （B）(R(x)Q(x)； （C）"x(R(x)Q(x)； （D）"x(R(x)Q(x)3. 下列公式中，（ ）是永真公式。（A）RS； （B）RR； （C）RR； （D）(RS) (RS)4. 下列公式中（ ）是等價(jià)公式。（A）G(HS) Û (GH) (GS)； （B）G(HS) Û (GH) (GS)； （C）G(HS) Û (GH)(GS)； （D）G(HS) Û (GH) (GS)；5. 公式"x(P(x)®Q(y，x)Ù $z R(y，z)®

4、;S(x)中，自由變元是( )。（A）x和y ； （B）y和z； （C）x和z； （D）z或者y6. 設(shè)集合A=1，2，3，則A上所有非等價(jià)關(guān)系數(shù)目為（ ）。（A） 512 (B) 507 (C) 508 (D) 506 7. 下列關(guān)于有限集偏序集A,的描述，（ ）是正確的(A) 一定存在最大元 (B) 一定存在最小元(C) 任意兩元素都存在最大下界 (D) 一定存在極大元8. 下列說法不正確的是（ ）(A)任意兩個(gè)非空集合之間都可構(gòu)造函數(shù) (B) 任意兩個(gè)非空集合之間都可構(gòu)造單射函數(shù)(C) 任意兩個(gè)非空集合之間都可構(gòu)造滿射函數(shù) (D) 任意兩個(gè)非空集合之間如可構(gòu)造單射函數(shù)，也可構(gòu)造滿射函數(shù)，

5、那么一定可構(gòu)造雙射函數(shù)9. 下列各組數(shù)中，不能構(gòu)成無向圖的點(diǎn)度數(shù)序列的是（ ）。(A) 1，1，2，2，3 (B) 1，3，5，7，8 (C) 2，2，2，2 (D) 2，2，3，8，110. 下列說法正確的是（ ）。(A) 樹至少有兩個(gè)葉結(jié)點(diǎn) (B) 存在既是二部圖又是哈密頓圖的簡單無向圖 (C) 平面圖滿足歐拉公式 n m + f = 2 (D) 連通無向圖都有非平凡生成樹11. 已知圖G中存在一條歐拉道路，以下說法正確的是（ ）：（A）圖中沒有奇度數(shù)結(jié)點(diǎn)； （B）圖中只有2個(gè)奇度數(shù)結(jié)點(diǎn)；（C）圖中有0個(gè)或2個(gè)奇度數(shù)結(jié)點(diǎn)； （D）無法確定圖中奇度數(shù)結(jié)點(diǎn)的個(gè)數(shù)12. 在實(shí)數(shù)集R上，定義代數(shù)系

6、統(tǒng)<R,*>，則關(guān)于“*”運(yùn)算的下列的運(yùn)算規(guī)則定義中，（ ）是可結(jié)合的？(A) a*b=a-b；(B) a*b=maxa,b；(C) a*b=a+2b；(D） a*b=|a-b|13. 次對(duì)稱群S3的集合中含有（ ）個(gè)元素：（A）2；（B）3；（C）4； （D）614. 整數(shù)加群<Z,+>是一個(gè)無限循環(huán)群，其生成元是（ ）：（A）-1； （B）0； （C）1； （D）-1和1兩個(gè)生成元15. 在代數(shù)系統(tǒng)模7剩余類環(huán)中，零因子的個(gè)數(shù)是（ ）：（A）0個(gè)； （B）1個(gè)； （C）2個(gè)； （D）7個(gè)16. 下列哪些代數(shù)系統(tǒng)不是域（ ）：（A）實(shí)數(shù)環(huán)<R,+,×&

7、gt; ； （B）有理數(shù)環(huán)<Q,+,×> ；（C）整數(shù)環(huán)<Z,+,×>； （D）模7剩余類環(huán)二、多項(xiàng)選擇題（本大題共7小題，每小題2分，共14分）提示：在每小題列出的備選項(xiàng)中有不確定個(gè)數(shù)個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將其代碼填寫在下表中。錯(cuò)選、多選、少選或未選均無分。123456789101. 下列語句中，（ ）是命題。 （A）上海不是一個(gè)大城市； （B）你去哪里？ （C）4+3=7； （D）不存在最大的質(zhì)數(shù)；（E）請(qǐng)認(rèn)真答題！2. 下列命題中，（ ）是真命題。(A) ,； (B) ,； (C) ； (D) 3. 右圖所示的關(guān)系具有（ ）(A) 自反性

8、(B) 反自反性 (C) 對(duì)稱性(D) 反對(duì)稱性 (E)傳遞性4. 下列描述那些是不正確的（）。(A) N,< 是自然數(shù)域上的偏序關(guān)系(B) 2A, Í 一定不是全序集 (C) N, 是自然數(shù)域上的全序集 (D) 2, Í是良序集5. 以下關(guān)于代數(shù)系統(tǒng)描述正確的是（ ）：（A）<2A,>和<2A,>都是含幺半群；（B）<R，+>是含幺半群，也是群； （）只要是半群，就必含有冪等元；（）任何群中只含有一個(gè)冪等元。6. 非平凡無向樹是（ ）。(A) 二部圖(B) 哈密頓圖 (C) 平面圖 (D) 連通圖(E) 歐拉圖7. 下列關(guān)于格的說

9、法正確的是（ ）。(A)偏序格 L, 的Hasse圖是連通圖(B)代數(shù)格 L,中，如果 ab = a,那么 ab = b(C)偏序格 L, 中必有最大元，最小元(D) 偏序格 L, 中必有極大元，極小元3、 填空題（本大題共5小題，每題2分，共10分）。1. 若集合A=1,2,3)，則2A= 。2. 設(shè)集合A和B，則從A到B的不同的二元關(guān)系有 個(gè)。3. 設(shè)1, 2, 3, 4, 5, 6，B=1, 2, 3。從到B的關(guān)系（x , y）|x=2y，則：R= ； R-1= 。4. 設(shè)R是定義在集合A=1,2,3,4,5,6上的等價(jià)關(guān)系，并且R=IA（1,5）,（5,1）,（2,4）,（4,2）,（

10、3,6）,（6,3）。那么，可以由此等價(jià)關(guān)系R對(duì)集合A產(chǎn)生的分劃是： 。5. 素?cái)?shù)階群<G,*>, 其子群為 。四、計(jì)算題（本大題共6小題，每題5分，共30分）。1. 請(qǐng)用公式的等價(jià)變換法求公式（PQ）（PR）的主合取范式。解：2. 設(shè)有謂詞公式"(x)(P(x, f(x) Q(x)，在如下給定解釋下，判斷該公式的真值解釋I指定為：（1）個(gè)體域 D = a,b(2) f(a) = b, f(b) = a（3）P(a,a) = 0, P(a,b) = 1, P(b,a) = 1, P(b,b) = 0（4）Q(a) = 0, Q(b) = 1解：3. 設(shè)<A,R>是一個(gè)偏序集，集合A=1,2,3,4,6,9,24,54，關(guān)系R是A上的整除關(guān)系。 （1）請(qǐng)畫出該偏序關(guān)系的哈斯圖； （2）求集合A中的極大元； （3）設(shè)集合A的子集合B=4,6,9，求集合B的最小上界和最大下界。 解：4. 請(qǐng)利用可達(dá)矩陣求出下圖中的所有強(qiáng)分圖：解：5. 請(qǐng)將下面的有序樹轉(zhuǎn)化為一棵二叉樹。解： 6. 求A=1，2，3上所有既是對(duì)稱的，又是反對(duì)稱的關(guān)系。解：5、 證明題（本大題共3小題，每題10分，共30分）。1. 請(qǐng)