課程名稱：離散數(shù)學(xué) 任課教師： 學(xué)號： 姓名： 本題NUMPAGES8頁，本頁為第2頁教務(wù)處試題編號：注：試題字跡務(wù)必清晰，書寫工整。本題NUMPAGES8頁，本頁為第4頁教務(wù)處試題編號：四川大學(xué)期末考試試題（閉卷）（2014-2015學(xué)年第1學(xué)期）課程號：304039040 課程名稱：離散數(shù)學(xué)（A卷）任課教師：馮偉森石兵周莉陳瑜林蘭 適用專業(yè)年級：2013級計算機科學(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)格按照《四川大學(xué)教學(xué)事故認(rèn)定及處理辦法》進(jìn)行處理。題號一（16%）二（14%）三（10%）四（30%）五（30%）六七八卷面成績得分閱卷教師閱卷時間一、單項選擇題（本大題共16小題，每小題1分，共16分）提示：在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分12345678910111213141516令R:小王吃飯；S：小王看電視。則語句“小王一邊吃飯一邊看電視”可以符號化為（）。（A)R∨S；（B）R∧S；（C）R→S；（D）～R∨～S令P(x):x是實數(shù)，Q(x):x是有理數(shù)。則語句“并非每個實數(shù)都是有理數(shù)”可以符號化為（）。（A）～x(R(x)Q(x))；（B）～(R(x)Q(x))；（C）～x(R(x)∧Q(x))；（D）～x(R(x)∨Q(x))下列公式中，（）是永真公式。（A）R→S；（B）R∧～R；（C）R∨～R；（D）(R→S)∧(R∧～S)下列公式中（）是等價公式。（A）G∧(H∨S)?(G∨H)∧(G∨S)；（B）G∧(H∨S)?(G∧H)∧(G∧S)；（C）G∧(H∨S)?(G∧H)∨(G∧S)；（D）G∧(H∨S)?(G∨H)∨(G∨S)；公式x((P(x)Q(y，x))zR(y，z))S(x)中，自由變元是()。（A）x和y；（B）y和z；（C）x和z；（D）z或者y設(shè)集合A={1，2，3}，則A上所有非等價關(guān)系數(shù)目為（）。（A）512(B)507(C)508(D)506下列關(guān)于有限集偏序集〈A,≤〉的描述，（）是正確的(A)一定存在最大元 (B)一定存在最小元(C)任意兩元素都存在最大下界(D)一定存在極大元下列說法不正確的是（）(A)任意兩個非空集合之間都可構(gòu)造函數(shù) (B)任意兩個非空集合之間都可構(gòu)造單射函數(shù)(C)任意兩個非空集合之間都可構(gòu)造滿射函數(shù) (D)任意兩個非空集合之間如可構(gòu)造單射函數(shù)，也可構(gòu)造滿射函數(shù)，那么一定可構(gòu)造雙射函數(shù)下列各組數(shù)中，不能構(gòu)成無向圖的點度數(shù)序列的是（）。(A){1，1，2，2，3}(B){1，3，5，7，8}(C){2，2，2，2}(D){2，2，3，8，1}下列說法正確的是（）。(A)樹至少有兩個葉結(jié)點(B)存在既是二部圖又是哈密頓圖的簡單無向圖(C)平面圖滿足歐拉公式n–m+f=2(D)連通無向圖都有非平凡生成樹已知圖G中存在一條歐拉道路，以下說法正確的是（）：（A）圖中沒有奇度數(shù)結(jié)點；（B）圖中只有2個奇度數(shù)結(jié)點；（C）圖中有0個或2個奇度數(shù)結(jié)點；（D）無法確定圖中奇度數(shù)結(jié)點的個數(shù)在實數(shù)集R上，定義代數(shù)系統(tǒng)<R,*>，則關(guān)于“*”運算的下列的運算規(guī)則定義中，（）是可結(jié)合的？(A)a*b=a-b；(B)a*b=max{a,b}；(C)a*b=a+2b；(D）a*b=|a-b|３次對稱群S3的集合中含有（）個元素：（A）2；（B）3；（C）4；（D）6整數(shù)加群<Z,+>是一個無限循環(huán)群，其生成元是（）：（A）-1；（B）0；（C）1；（D）-1和1兩個生成元在代數(shù)系統(tǒng)模7剩余類環(huán)中，零因子的個數(shù)是（）：（A）0個；（B）1個；（C）2個；（D）7個下列哪些代數(shù)系統(tǒng)不是域（）：（A）實數(shù)環(huán)<R,+,×>；（B）有理數(shù)環(huán)<Q,+,×>；（C）整數(shù)環(huán)<Z,+,×>；（D）模7剩余類環(huán)設(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的最小上界和最大下界。解：請利用可達(dá)矩陣求出下圖中的所有強分圖：解：請將下面的有序樹轉(zhuǎn)化為一棵二叉樹。解：求A={1，2，3}上所有既是對稱的，又是反對稱的關(guān)系。解：證明題（本大題共3小題，每題10分，共30分）。請用命題邏輯的推理法則推導(dǎo)：{P→~Q，~P→R，R→~S}S→~Q