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

1、課程名稱： 離散數(shù)學(xué) 任課教師： 學(xué)號：姓名： -四川大學(xué)期末考試試題（閉卷）（2014-2015學(xué)年第1學(xué)期）課程號： 304039040課程名稱： 離散數(shù)學(xué)（A卷） 任課教師： 馮偉森 石兵 周莉 陳瑜 林蘭適用專業(yè)年級： 2013級計算機(jī)科學(xué)與技術(shù)學(xué)號： 姓名： 考試須知四川大學(xué)學(xué)生參加由學(xué)校組織或由學(xué)校承辦的各級各類考試，必須嚴(yán)格執(zhí)行四川大學(xué)考試工作管理辦法和四川大學(xué)考場規(guī)則。有考試違紀(jì)作弊行為的，一律按照四川大學(xué)學(xué)生考試違紀(jì)作弊處罰條例進(jìn)行處理。四川大學(xué)各級各類考試的監(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)行處理。題 號一（16%）二（14%）三（10%）四（30%）五（30%）六七八卷面成績得 分閱卷教師閱卷時間一、單項選擇題（本大題共16小題，每小題1分，共16分）提示：在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分123456789101112131415161. 令R: 小王吃飯；S：小王看電視。則語句“小王一邊吃飯一邊看電視”可以符號化為（ ）。（A)RS； （B）RS； （C）RS； （D）RS2. 令P(x):x是實(shí)數(shù)，Q(x):x是有理數(shù)。則語句“并非每個實(shí)數(shù)都是有理數(shù)”可以符號化為（ ）。

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. 下列公式中（ ）是等價公式。（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上所有非等價關(guān)系數(shù)目為（ ）。（A） 512 (B) 507 (C) 508 (D) 506 7. 下列關(guān)于有限集偏序集A,的描述，（ ）是正確的(A) 一定存在最大元 (B) 一定存在最小元(C) 任意兩元素都存在最大下界 (D) 一定存在極大元8. 下列說法不正確的是（ ）(A)任意兩個非空集合之間都可構(gòu)造函數(shù) (B) 任意兩個非空集合之間都可構(gòu)造單射函數(shù)(C) 任意兩個非空集合之間都可構(gòu)造滿射函數(shù) (D) 任意兩個非空集合之間如可構(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) 樹至少有兩個葉結(jié)點(diǎn) (B) 存在既是二部圖又是哈密頓圖的簡單無向圖 (C) 平面圖滿足歐拉公式 n m + f = 2 (D) 連通無向圖都有非平凡生成樹11. 已知圖G中存在一條歐拉道路，以下說法正確的是（ ）：（A）圖中沒有奇度數(shù)結(jié)點(diǎn)； （B）圖中只有2個奇度數(shù)結(jié)點(diǎn)；（C）圖中有0個或2個奇度數(shù)結(jié)點(diǎn)； （D）無法確定圖中奇度數(shù)結(jié)點(diǎn)的個數(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. 次對稱群S3的集合中含有（ ）個元素：（A）2；（B）3；（C）4； （D）614. 整數(shù)加群<Z,+>是一個無限循環(huán)群，其生成元是（ ）：（A）-1； （B）0； （C）1； （D）-1和1兩個生成元15. 在代數(shù)系統(tǒng)模7剩余類環(huán)中，零因子的個數(shù)是（ ）：（A）0個； （B）1個； （C）2個； （D）7個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)二、多項選擇題（本大題共7小題，每小題2分，共14分）提示：在每小題列出的備選項中有不確定個數(shù)個選項是符合題目要求的，請將其代碼填寫在下表中。錯選、多選、少選或未選均無分。123456789101. 下列語句中，（ ）是命題。 （A）上海不是一個大城市； （B）你去哪里？ （C）4+3=7； （D）不存在最大的質(zhì)數(shù)；（E）請認(rèn)真答題！2. 下列命題中，（ ）是真命題。(A) ,； (B) ,； (C) ； (D) 3. 右圖所示的關(guān)系具有（ ）(A) 自反性

8、(B) 反自反性 (C) 對稱性(D) 反對稱性 (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，+>是含幺半群，也是群； （）只要是半群，就必含有冪等元；（）任何群中只含有一個冪等元。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)系有 個。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上的等價關(guān)系，并且R=IA（1,5）,（5,1）,（2,4）,（4,2）,（

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