2002年4月到2013年7月自考離散數(shù)學(xué)試題有答案合集精心整理推薦

第\*頁全國年月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：一、單項(xiàng)選擇題(本大題共小題，每小題分，共分)在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。.一個(gè)連通的無向圖，如果它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，那么它具有一條().漢密爾頓回路.歐拉回路.漢密爾頓通路.初級(jí)回路.設(shè)是連通簡單平面圖，中有個(gè)頂點(diǎn)個(gè)面，則中的邊是().在布爾代數(shù)中，表達(dá)式(∧)∨(∧∧)∨(∧)的等價(jià)式是()∧(∨).(∧)∨(’∧).(∨)∧(∨∨)∧(∨).(∨)∧(∨).設(shè)是虛數(shù)，·是復(fù)數(shù)乘法運(yùn)算，則<{},·>是群，下列是的子群是().<{},·>.〈{},·〉.〈{},·〉.〈{},·〉.設(shè)為整數(shù)集，為集合，的冪集為()、、為數(shù)的加、減、除運(yùn)算，∩為集合的交運(yùn)算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有().〈，，〉.〈，〉.〈，，〉.〈()，∩〉.下列各代數(shù)系統(tǒng)中不含有零元素的是().〈，*〉是全體有理數(shù)集，*是數(shù)的乘法運(yùn)算.〈(),*〉()是全體階實(shí)矩陣集合，*是矩陣乘法運(yùn)算.〈，〉，是整數(shù)集，定義為,∈.〈，〉，是整數(shù)集，是數(shù)的加法運(yùn)算.設(shè){}，上二元關(guān)系的關(guān)系圖如下：具有的性質(zhì)是.自反性.對(duì)稱性.傳遞性.反自反性.設(shè){}，上二元關(guān)系{〈〉，〈〉,〈〉}，則關(guān)系的對(duì)稱閉包()是()∪∪{〈〉}∩.設(shè){}是上恒等關(guān)系，要使∪{〈〉，〈〉，〈〉，〈〉}∪為上的等價(jià)關(guān)系，應(yīng)取().｛〈〉，〈〉｝.{〈〉，〈〉}.{〈〉，〈〉}.{〈〉，〈〉}.下列式子正確的是().∈..{}.{}∈.設(shè)解釋如下：論域?yàn)閷?shí)數(shù)集，()()<.下列公式在下為真的是().()()()(())→(()()).()(()).()()（(())).()()(()→(())).設(shè)是不含變?cè)墓?，謂詞公式()(()→)等價(jià)于().()()→.()()→()→.()()→().謂詞公式()(())→()()∧()()中變?cè)?).是自由變?cè)皇羌s束變?cè)?既不是自由變?cè)植皇羌s束變?cè)?既是自由變?cè)质羌s束變?cè)?是約束變?cè)皇亲杂勺冊(cè)?若：他聰明；：他用功；則“他雖聰明，但不用功”，可符號(hào)化為()∨∧┐→┐∨┐.以下命題公式中，為永假式的是()→(∨∨).(→┐)→┐.┐(→)∧.┐(∨┐)→(∧┐)二、填空題(每空分，共分).在一棵根樹中，僅有一個(gè)結(jié)點(diǎn)的入度為，稱為樹根，其余結(jié)點(diǎn)的入度均為。{}上二元關(guān)系{〈，〉，〈，〉，〈，〉}，的關(guān)系矩陣中。.設(shè)〈,*〉是群，則那么中除外，不可能有別的冪等元；若〈,*〉有零元，則。.設(shè)為集合，()為的冪集，則〈()，〉是格，若∈(),則最大下界是，最小上界是。.設(shè)函數(shù)→,如果對(duì)中的任意兩個(gè)不同的和，它們的象和也不同，我們說是函數(shù)，如果，則稱是函數(shù)。.設(shè)為非空集合上的等價(jià)關(guān)系，其等價(jià)類記為〔〕?！?，若〈〉∈，則〔〕與〔〕的關(guān)系是，而若〈〉，則〔〕∩〔〕。.使公式()()(()∧())()()∧()()成立的條件是不含有，不含有。.設(shè)()是人，()是要死的，則命題“所有的人都是要死的”可符號(hào)化為(),其中量詞()的轄域是。.若∧∧…∧是，則稱,…是相容的，若∧∧…∧是，則稱,…是不相容的。.判斷一個(gè)語句是否為命題，首先要看它是否為，然后再看它是否具有唯一的。三、計(jì)算題(共分).(分)設(shè)有向圖()如下圖所示，試用鄰接矩陣方法求長度為的路的總數(shù)和回路總數(shù)。.()設(shè){}()是的冪集，是對(duì)稱差運(yùn)算，可以驗(yàn)證<()，>是群。設(shè)是正整數(shù)，求({}{}{}){}{}{}.(分)設(shè){}上偏序關(guān)系{〈，〉，〈，〉，〈，〉，〈，〉，〈，〉，〈，〉，〈，〉}∪;()作出偏序關(guān)系的哈斯圖()令{}，求的最大，最小元，極大、極小元，上界，下確界，下界，下確界。.(分)求┐(→)(→┐)的主合取范式并給出所有使命題為真的賦值。.(分)設(shè)帶權(quán)無向圖如下，求的最小生成樹及的權(quán)總和，要求寫出解的過程。.(分)求公式┐(()()→()())∨()()的前束范式。四、證明題(共分).(分)設(shè)是非平凡的無向樹，中度數(shù)最大的頂點(diǎn)有個(gè)，它們的度數(shù)為(≥),證明中至少有片樹葉。.(分)設(shè)是非空集合，是所有從到的雙射函數(shù)的集合，是函數(shù)復(fù)合運(yùn)算。證明：〈,〉是群。.(分)在個(gè)體域{,…，}中證明等價(jià)式：()(()→())()()→()()五、應(yīng)用題(共分).(分)如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過語言而且學(xué)過語言。只要他學(xué)過語言或者語言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序。請(qǐng)用命題邏輯推理方法，證明該推理的有效結(jié)論。.(分)一次學(xué)術(shù)會(huì)議的理事會(huì)共有個(gè)人參加，他們之間有的相互認(rèn)識(shí)但有的相互不認(rèn)識(shí)。但對(duì)任意兩個(gè)人，他們各自認(rèn)識(shí)的人的數(shù)目之和不小于。問能否把這個(gè)人排在圓桌旁，使得任意一個(gè)人認(rèn)識(shí)其旁邊的兩個(gè)人?根據(jù)是什么?全國年月高等教育自學(xué)考試離散數(shù)學(xué)試題參考答案課程代碼：一、單項(xiàng)選擇題(本大題共小題，每小題分，共分)二、填空題.單位元∩∪.入射滿射.［］［］()().(()→())()→().可滿足式永假式(或矛盾式).陳述句真值三、計(jì)算題.中長度為的路總數(shù)為，長度為的回路總數(shù)為。.當(dāng)是偶數(shù)時(shí)，∈()當(dāng)是奇數(shù)時(shí)，∈()于是：當(dāng)是偶數(shù)，(｛｝｛｝｛｝)｛｝｛｝｛｝(｛｝)｛｝｛｝當(dāng)是奇數(shù)時(shí)，(｛｝｛｝｛｝)｛｝｛｝｛｝｛｝｛｝｛｝(｛｝)｛｝｛｝｛｝｛｝｛｝｛｝｛｝｛｝.()偏序關(guān)系的哈斯圖為()的最大元：無，最小元：無；極大元：，，極小元：，下界：，下確界；上界：無，上確界：無.原式(┐(→)→(→┐))∧((→┐)→┐(→))((→)∨(→┐))∧(┐(→┐)∨┐(→))(┐∨∨┐∨┐)∧(┐(┐∨┐)∨(∧┐))(┐(∧┐)∨(∧┐))(∧)∨(∧┐)∧(∨┐)∨(∧┐)(∨)∧(∨┐)命題為真的賦值是和.令(),()(),()(),()(),()(),()令為上的權(quán)，則<<<<<取的∈的∈的∈的∈的∈,即，的總權(quán)和.原式┐(()→())∨()(換名)┐(()→())∨()┐(()→())∨()(┐(()→())∨()四、證明題.設(shè)中有片樹葉，個(gè)分支點(diǎn)。于是中有個(gè)頂點(diǎn)，有條邊，由握手定理知中所有頂點(diǎn)的度數(shù)之的()。又樹葉的度為，任一分支點(diǎn)的度大于等于且度最大的頂點(diǎn)必是分支點(diǎn)，于是≥·()從而()≥≥.從定義出發(fā)證明：由于集合是非空的，故顯然從到的雙射函數(shù)總是存在的，如上恒等函數(shù)，因此非空()∈,因?yàn)楹投际堑降碾p射函數(shù)，故也是到的雙射函數(shù)，從而集合關(guān)于運(yùn)算是封閉的。()∈,由函數(shù)復(fù)合運(yùn)算的結(jié)合律有()()故運(yùn)算是可結(jié)合的。()上的恒等函數(shù)也是到的雙射函數(shù)即∈,且∈有,故是〈，〉中的幺元()∈,因?yàn)槭请p射函數(shù)，故其逆函數(shù)是存在的，也是到的雙射函數(shù)，且有,因此是的逆元由此上知〈，〉是群.證明()(()→())(┐()∨())(┐()∨())∨(┐()∨())∨…∨(┐()∨()))(┐()∨()∨…∨┐()∨(()∨()∨…∨(())┐(()∧()∧…∧())∨(┐()∨()∨…∨(())┐()()∨()()()()→()()五、應(yīng)用題.令：他是計(jì)算機(jī)系本科生：他是計(jì)算機(jī)系研究生：他學(xué)過語言:他學(xué)過語言:他會(huì)編程序前提：(∨)→(∧),(∨)→結(jié)論：→證①(附加前提)②∨①③(∨)→(∧)(前提引入)④∧②③⑤④⑥∨⑤⑦(∨)→(前提引入)⑧⑤⑥.可以把這個(gè)人排在圓桌旁，使得任一人認(rèn)識(shí)其旁邊的兩個(gè)人。根據(jù)：構(gòu)造無向簡單圖<>,其中{,…，}是以個(gè)人為頂點(diǎn)的集合，中的邊是若任兩個(gè)人和相互認(rèn)識(shí)則在與之間連一條邊?！?)是與相互認(rèn)識(shí)的人的數(shù)目，由題意知∈有()(),于是中存在漢密爾頓回路。設(shè)…是中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。全國年月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：一、單項(xiàng)選擇題(本大題共小題，每小題分，共分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。.下列各圖是平面圖的是().設(shè)是個(gè)頂點(diǎn)的無向簡單圖，則下列說法不正確的是).若是樹，則其邊數(shù)等于.若是歐拉圖，則中必有割邊.若中有歐拉路，則是連通圖，且有零個(gè)或兩個(gè)奇度數(shù)頂點(diǎn).若中任意一對(duì)頂點(diǎn)的度數(shù)之和大于等于，則中有漢密爾頓路.格是分配格的充要條件是不含與下面哪一個(gè)選項(xiàng)同構(gòu)的子格().鏈 .鉆石格.五角格 .五角格與鉆石格.設(shè)<,*>是有限循環(huán)群，則下列說法不正確的是().<,*>的生成元是唯一的.有限循環(huán)群中的運(yùn)算*適合交換律中存在一元素，使中任一元素都由的冪組成.設(shè)是<,*>的生成元，則對(duì)任一正整數(shù)，存在正整數(shù)使.在實(shí)數(shù)集合上，下列定義的運(yùn)算中是可結(jié)合的只有()* ** *.設(shè)群<,*>中的元素個(gè)數(shù)大于，若元素∈的逆元素為∈，則*的運(yùn)算結(jié)果是()中零元素 中幺元.非空集合上的二元關(guān)系若是自反和對(duì)稱的，則是().偏序關(guān)系 .等價(jià)關(guān)系.相容關(guān)系 .擬序關(guān)系.下面的圖是｛｝上關(guān)系的關(guān)系圖(),從()可判斷所具有的性質(zhì)是()。。。.自反，對(duì)稱，傳遞.反自反，非對(duì)稱.反自反，對(duì)稱，非傳遞.反自反，對(duì)稱，反對(duì)稱，傳遞.設(shè)｛，，｝，｛｝，下列二元關(guān)系為到的函數(shù)的是()｛<>,<>,<>｝｛<>,<>｝｛<>,<>,<>,<>｝｛<>,<>,<>,<>｝.設(shè)φ為空集，()是集合的冪集，下列論斷不正確的是().φ∈(φ),φ(φ).{φ}∈（φ），{φ}（φ）.φ∈（（φ）），φ（（φ））.{φ}∈（（φ））,{φ}（（φ））.利用謂詞的約束變?cè)拿?guī)則和自由變?cè)胍?guī)則，可將如下公式：改寫成().....設(shè)論域?yàn)檎麛?shù)集，下列謂詞公式中真值為假的是().....在命題演算中，語句為真為假的一種性質(zhì)稱為().真值 .陳述句.命題 .謂詞.設(shè)：明天天晴；：我去爬山；那么“除非明天天晴，否則我不去爬山。”可符號(hào)化為().....下列命題公式是永真式的是()....二、填空題(本大題共小題，每空分，共分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。.一棵有個(gè)葉結(jié)點(diǎn)的完全二叉樹，有個(gè)內(nèi)點(diǎn)；而若一棵樹有個(gè)結(jié)點(diǎn)度數(shù)為，一個(gè)結(jié)點(diǎn)度數(shù)為，個(gè)結(jié)點(diǎn)度數(shù)為，其余是葉結(jié)點(diǎn)，則該樹有個(gè)葉結(jié)點(diǎn)。.在一棵根樹中，有且只有一個(gè)結(jié)點(diǎn)的入度為，其余所有結(jié)點(diǎn)的入度均為。.設(shè)<,≤>是格，其中一個(gè)命題是≤(∨)∧(∨),則的對(duì)偶命題是(∧)(∧)。.設(shè)是整數(shù)集，是整數(shù)加法運(yùn)算，則<>是群，其幺元是，對(duì)任一整數(shù),其逆元

是。.當(dāng)→是函數(shù)時(shí)，有逆函數(shù)，且。。.設(shè){}{}{}{},則(～∩～)∩,冪集((～∩～)∩)。.設(shè)論域{},則()(),()()()。.使公式()()(()())(()()∨()())成立的條件是不含有，不含有。.由命題變?cè)捌浞穸ㄋM成的有限個(gè)析取式的合取式稱為，由命題變?cè)捌浞穸ㄋM成的有限個(gè)合取式的析取式稱為。.不包含的命題叫做原子命題，包含的命題稱為復(fù)合命題。三、計(jì)算題(本大題共小題，第、小題每小題分，第、小題每小題分，第、小題每小題分，第小題分，共分).用等值演算法，求∨(∧)的主析取范式，并按，，順序，寫成編碼形式。.設(shè){}，給定上二元關(guān)系{<>,<>,<>}，求()()和()。.求公式的前束范式。.對(duì)如下有向圖，求中長度為的路有多少條?其中回路有多少條?.設(shè){}，定義上二元關(guān)系{<>∈且字符串包含于字符串中}，即∪{<>,<>,<>}，可以驗(yàn)證是上偏序關(guān)系。①作出的哈斯圖②向中最少添加幾個(gè)序偶可使之成為等價(jià)關(guān)系?求出該等價(jià)關(guān)系所確定的集合的劃分。.某科研所要從個(gè)項(xiàng)目、、中選擇～個(gè)項(xiàng)目上馬，由于某種原因，立項(xiàng)時(shí)要滿足以下條件：()若上，則也要上；()若上，則不能上；()若不上，則或可以上。請(qǐng)找出所有的立項(xiàng)方案.設(shè)有個(gè)城市，，…，，它們之間有輸油管連通，其布置如下圖()(數(shù)字)中

為邊的編號(hào)，括號(hào)內(nèi)數(shù)字為邊的權(quán)，它是兩城市間的矩離，為了保衛(wèi)油管不受破壞，在每段油管間派一連士兵看守，為保證每個(gè)城市石油的正常供應(yīng)最少需多少連士兵看守?輸油管道總長度越短，士兵越好防守。求他們看守管道的最短的總長度。(要求寫出求解過程)四、證明題(本大題共小題，每小題分，共分).證明()(()→())├()()→()().證明當(dāng)每個(gè)結(jié)點(diǎn)的度數(shù)大于等于時(shí)，不存在有條邊的連通簡單平面圖。""年月自考答案離散數(shù)學(xué)""全國年月離散數(shù)學(xué)試題課程代碼：一、單項(xiàng)選擇題（本大題共小題，每小題分，共分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。．下列命題公式為重言式的是（）．→(∨) ．(∨┐)→．∧┐ ．→┐．下列語句中不是命題的只有（）．這個(gè)語句是假的。 ．．飛碟來自地球外的星球。 ．凡石頭都可練成金。．設(shè)：我很累，：我去學(xué)習(xí)，命題：“除非我很累，否則我就去學(xué)習(xí)”的符號(hào)化正確的是（）．┐∧ ．┐→．┐→┐ ．→┐．下列等價(jià)式正確的是（）．┐┐．．┐┐．．在公式中變?cè)牵ǎ杂勺冊(cè)s束變?cè)仁亲杂勺冊(cè)?，又是約束變?cè)炔皇亲杂勺冊(cè)?，又不是約束變?cè)O(shè){，，}，上二元關(guān)系{<，>，<，>，<，>，<，>}，則是（）．自反關(guān)系 ．反自反關(guān)系．對(duì)稱關(guān)系 ．傳遞關(guān)系．設(shè)集合為人的全體，在上定義關(guān)系、為{<，，∈∧是的父親}，{<，>，∈∧是的母親}，那么關(guān)系{<，>，∈∧是的祖母}的表達(dá)式為（）． ．． ．．設(shè)是正整數(shù)集，{(，)，∈∧}，則∩({，，，}×{，，，})（）．．{<，>}．{<，>，<，>} ．{<，>，<，>，<，>}．下列式子不正確的是（）．()() ．()(∪)．()()() ．(∪)()∪．下列命題正確的是（）．{，}{{，}，{，，}，} ．{，}{，{，}，{，，}，}．{，}{{}，{}，{，}}．{，}∈{，，{}，{，，}}．在下列代數(shù)系統(tǒng)中，不是環(huán)的只有（）．<，，*)，其中為整數(shù)集，，*分別為整數(shù)加法和乘法。．(，，*)，其中為有理數(shù)集，，*分別為有理數(shù)加法和乘法。．<，，*>，其中為實(shí)數(shù)集，為實(shí)數(shù)加法，*。．<()，，*>，其中()為實(shí)數(shù)集×階矩陣結(jié)合，，*是矩陣加法和乘法。．下列整數(shù)集對(duì)于整除關(guān)系都構(gòu)成偏序集，而能構(gòu)成格的是（）．{，，，，}．{，，，，}．{，，}．{，，，}．結(jié)點(diǎn)數(shù)為奇數(shù)且所有結(jié)點(diǎn)的度數(shù)也為奇數(shù)的連通圖必定是（）．歐拉圖．漢密爾頓圖．非平面圖．不存在的．無向圖是歐拉圖當(dāng)且僅當(dāng)是連通的且（）．中各頂點(diǎn)的度數(shù)均相等．中各頂點(diǎn)的度數(shù)之和為偶數(shù)．中各頂點(diǎn)的度數(shù)均為偶數(shù)．中各頂點(diǎn)的度數(shù)均為奇數(shù)．平面圖(如下)的三個(gè)面的次數(shù)分別是（）．，，．，，．，，．，，二、填空題（本大題共小題，每小題分，共分） 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。．求一個(gè)公式的主析取或主合取范式的方法，有法和法。．給定謂詞合式公式，其中一部分公式形式為()()或()()，則量詞，后面所跟的稱為，而稱為相應(yīng)量詞的。．設(shè)，，，都是實(shí)數(shù)集，：→，且()→；：→，且()＝()；：→，且()。那么的定義域是，而復(fù)合函數(shù)()()。．集合{，，，}上二元關(guān)系{<，>，<，>，<，>，<，>，<，>，<，>}，則的自反閉包()，對(duì)稱閉包()。．已知<{，，，}，·>(其中，是數(shù)的乘法)是群，則的階是；的階是。．對(duì)代數(shù)系統(tǒng)<，*>，其中*是上的二元運(yùn)算，若，∈，且對(duì)任意的∈，都有**，**，則稱為運(yùn)算“*”的，稱為運(yùn)算“*”的。．設(shè)<，*>是群，則<，*>滿足結(jié)合律和；若｜｜>，中不可能有。．寫出如右有向圖的一條初級(jí)回路：，其長度是。．一個(gè)且的無向圖稱為樹。．在簡單無向圖<，>中，如果中的每個(gè)結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接，則該圖稱為，如果有個(gè)結(jié)點(diǎn)，那么它還是度正則圖。三、計(jì)算題(本大題共小題，第、題各分，第、題各分，第題分，共分)．若集合{，{，}}的冪集為()，集合{，{}}的冪集為()，求()∩()。．構(gòu)造命題公式(→(∧))→┐的真值表。．求圖＝<，>的可達(dá)矩陣，其中＝｛｝＝｛(),(),(),(),(),(),()｝．求下列公式的主析取范式和主合取范式：（∧）∨（┐∧）．設(shè)＝｛，，，，，，｝，為上整除關(guān)系，試畫<，>的哈斯圖，并求中的最大元，最小元，極大元，極小元。四、證明題（本大題共小題，第、小題各分，第題分，共分）．設(shè)是偶數(shù)集，＋和·是數(shù)的加、乘運(yùn)算，證明<，＋，·>是一個(gè)環(huán)。．設(shè)是集合上的二元關(guān)系，證明是上傳遞關(guān)系當(dāng)且僅當(dāng)。．設(shè)是簡單平面圖，有個(gè)頂點(diǎn)條邊，且<，證明中存在一項(xiàng)點(diǎn)，（）≤。五、應(yīng)用題（本大題共小題，第題分，第題分，共分）．判斷下面推理是否正確，并證明你的結(jié)論。 如果小王今天家里有事，則他不會(huì)來開會(huì)。如果小張今天看到小王，則小王今天來開會(huì)了。小張今天看到小王。所以小王今天家里沒事。．有個(gè)村莊，，，…，欲修建道路使村村可通?，F(xiàn)已有修建方案如下帶權(quán)無向圖所示，其中邊表示道路，邊上的數(shù)字表示修建該道路所需費(fèi)用，問應(yīng)選擇修建哪些道路可使得任二個(gè)村莊之間是可通的且總的修建費(fèi)用最低?要求寫出求解過程，畫出符合要求的最低費(fèi)用的道路網(wǎng)絡(luò)圖并計(jì)算其費(fèi)用。年月全國自考離散數(shù)學(xué)試題試卷真題課程代碼：一、單項(xiàng)選擇題（本大題共小題，每小題分，共分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。．下列語句中不是命題的只有（）．雞毛也能飛上天？ ．或重于泰山，或輕于鴻毛。．不經(jīng)一事，不長一智。 ．牙好，胃口就好。．從真值角度看，命題公式的全部類型是（）．永真式 ．永假式．永真式，永假式 ．永真式，永假式，可滿足式．設(shè)（）：是人；（）：要吃飯。用謂詞公式表達(dá)下述命題：所有的人都要吃飯，其中錯(cuò)誤的表達(dá)式是（）． ．． ．．下列公式是前束范式的是（）． ．． ．．設(shè)論域?yàn)檎麛?shù)集，下列真值為真的公式是（）． ．． ．．下列是謂詞演算中的合式公式的是（）． ．． ．（）．（）（）．．．．．（）．下列式子正確的是（）．（－）（∪） ．－（∪）（－）∪．（－）（－） ．（∩）．下列集合對(duì)所給的運(yùn)算是封閉的只有（）．非零整數(shù)集合*上的除法運(yùn)算．全體×實(shí)可逆矩陣集合（）上的矩陣加法和乘法運(yùn)算．全體×實(shí)矩陣集合（）上的矩陣加法和乘法運(yùn)算．{，，…，}，*（，），即，最小公倍數(shù)．設(shè)<，\\(○)，*>是環(huán)，則下列說法不正確的是（）．<，\\(○)>是交換群 ．<，*>是半群．*對(duì)\\(○)是可分配的 ．\\(○)對(duì)*是可分配的．下列四個(gè)格，是分配格的是（）．．．（）．．．下列各圖是無向完全圖的是（）．下列各有向圖是強(qiáng)連通圖的是（）．設(shè)Ｇ是具有個(gè)結(jié)點(diǎn)的無向簡單圖，若在Ｇ中存在一條漢密爾頓路，則Ｇ中每一對(duì)結(jié)點(diǎn)的度數(shù)之和與的關(guān)系為（）．大于 ．大于等于．等于 ．小于．設(shè)連通平面圖Ｇ，共有個(gè)結(jié)點(diǎn)，條邊，個(gè)面，則歐拉證明成立的公式是（）． ．． ．二、填空題（本大題共小題，每小題分，共分） 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。．所謂是指不能再分解的命題，而復(fù)合命題是由一些經(jīng)過聯(lián)結(jié)詞復(fù)合而成的命題。．在命題演算中，兩個(gè)的合取、析取、條件、雙條件均為。．使公式成立的條件是中不含，中不含。．設(shè){，，，}，是上的二元關(guān)系，{<>是素?cái)?shù)}，則;。．設(shè)無向圖Ｇ有個(gè)結(jié)點(diǎn)條邊，每個(gè)結(jié)點(diǎn)的度數(shù)為或，記為度數(shù)等于的結(jié)點(diǎn)數(shù)，則。如果無向簡單圖的結(jié)點(diǎn)的度數(shù)均為相同的偶數(shù)，且，則。．設(shè){，，，，，}，是上的整除關(guān)系，則是上的偏序，其最大元是，極小元是。．設(shè)<>是有界格，,若,則；若,則。．設(shè)是群上的幺元，若且,則。．代數(shù)系統(tǒng)<,。>，其中為命題公式集合，。為析取運(yùn)算，則<，。>中零元素是，幺元是。．樹是不包含的圖。三、計(jì)算題（本大題共小題，第、題各分，第、題各分，第、題各分，共分）．如果論域是集合{}，試消去下面公式中的量詞：．求公式（的主析取范式。．設(shè){}上二元關(guān)系{<>,<>,<>},用關(guān)系矩陣法求最小的自然數(shù)<使。．根據(jù)下列條件如果能畫則請(qǐng)畫出一個(gè)歐拉圖，如果不能畫則請(qǐng)說明理由。（）偶數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊（）奇數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊（）偶數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊（）奇數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊．下列各整數(shù)集合對(duì)于整除關(guān)系“”都構(gòu)成偏序集，判斷哪些偏序集能構(gòu)成格？并說明理由。){}){}){}){,…}．設(shè){，，，，}，等價(jià)關(guān)系{<>,()},寫出各元素的等價(jià)類，并求。四、證明題（本大題共小題，第、題各分，第題分，共分）．用等價(jià)變換法證明：是永真式。．若無向圖是歐拉圖，中是否存在割邊？為什么？．設(shè)是一個(gè)集合，（），是上元素之間的包含關(guān)系，試證明<>是偏序集。（注：（）為的冪集）五、應(yīng)用題（本大題共小題，第題分，第題分，共分）．設(shè)有個(gè)村莊要修路，（）若要使所有村莊之間都有通路，問需在兩村之間至少修幾條路？（）若要使任意兩村莊之間有一條直接的路，則至少修幾個(gè)路？（）若修一條連接所有村莊的環(huán)路，問有多少種修路方案？．設(shè)有推理：()沒有不守信用的人是可信賴的；()有些可以信賴的人是受過教育的人；()因此有些受過教育的人是守信用的。試構(gòu)造推理的證明，要求把推理的前提，結(jié)論符號(hào)化為謂詞形式，并寫出推理過程。（個(gè)體域：人的集合）提示：設(shè)（）表示是守信用的人；（）表示是可信賴的人；（）表示是受過教育的人。""全國年月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：一、單項(xiàng)選擇題（本大題共小題，每小題分，共分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。．下列命題公式中不是重言式的是（）．→(→) ．→(→)．→(→) ．(→(→))(→(→))．下列語句中為命題的是（）．這朵花是誰的？ ．這朵花真美麗?。。@朵花是你的嗎？ ．這朵花是他的。．設(shè)個(gè)體域是整數(shù)集，則下列命題的真值為真的是（）．(·) ．(·≠)．(·) ．(·)．關(guān)于謂詞公式（）()(()∧())∧()(),下面的描述中錯(cuò)誤的是（）．（）的轄域是（）（（）∧()）．是該謂詞公式的約束變?cè)ǎ┑妮犛蚴牵ǎ?．是該謂詞公式的約束變?cè)O(shè)論域{}，與公式（）等價(jià)的命題公式是（）．（）∧（）．（）→（）．（）∨（）．（）→（）．集合{，，}上的下列關(guān)系矩陣中符合等價(jià)關(guān)系條件的是（）．．．．．設(shè){?}，（（）），以下不正確的式子是（）．{{?}，{{?}}，{?，{?}}}包含于．{{{?}}}包含于．{{?，{?}}}包括于 ．{{?}，{{?，{?}}}}包含于．設(shè)是整數(shù)集，{…，，，，，，…}，：→，（），則（）．僅是滿射．僅是入射．是雙射．無逆函數(shù)．設(shè){，，，，}，上二元關(guān)系{〈，〉，〈，〉，〈，〉}，{〈，〉，〈，〉，〈，〉}，則的運(yùn)算結(jié)果是（）．{〈，〉，〈，〉，〈，〉} ．{〈，〉，〈，〉，〈，〉}．{〈，〉，〈，〉，〈，〉} ．{〈，〉，〈，〉，〈，〉}．設(shè)有代數(shù)系統(tǒng)〈，*〉，其中是所有命題公式的集合，*為命題公式的合取運(yùn)算，則的幺元是（）．矛盾式．重言式．可滿足式．公式∧．在實(shí)數(shù)集合上，下列定義的運(yùn)算中不可結(jié)合的是（）．* ．*．* ．*．下列集合關(guān)于所給定的運(yùn)算成為群的是（）．已給實(shí)數(shù)的正整數(shù)次冪的全體，且{，，}，關(guān)于數(shù)的乘法．所有非負(fù)整數(shù)的集合，關(guān)于數(shù)的加法．所有正有理數(shù)的集合，關(guān)于數(shù)的乘法．實(shí)數(shù)集，關(guān)于數(shù)的除法．設(shè)無向圖中有條邊，有一個(gè)度頂點(diǎn)和一個(gè)度頂點(diǎn)，其余頂點(diǎn)度為，則該圖的頂點(diǎn)數(shù)是（）．．．．．下列各圖中既是歐拉圖，又是漢密爾頓圖的是（）．．．．．設(shè)無向圖的邊數(shù)為，結(jié)點(diǎn)數(shù)為，則是樹等價(jià)于（）．連通且．連通且．連通且．每對(duì)結(jié)點(diǎn)之間至少有一條通路二、填空題（本大題共小題，每小題分，共分） 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。．不能再分解的命題稱為，至少包含一個(gè)聯(lián)結(jié)詞的命題稱為。．在命題演算中，五個(gè)聯(lián)結(jié)詞的含義是由其表唯一確定的，而不是由其類似的語言的含義確定。．使公式（）（）（（）→（））（（）（）→（）（））成立的條件是不含有，不含有。．設(shè)為任意集合，請(qǐng)?zhí)钊脒m當(dāng)?shù)倪\(yùn)算符，使式子?；?成立。．設(shè){，，，，}，{〈〉≠∧(∈)∧≡()}，則，。．稱集合是給定非空集合的覆蓋：若{，，…，}，其中，≠?，，，…，，且；進(jìn)一步若，則是集合的劃分。．對(duì)實(shí)數(shù)的普通加法和乘法，是加法的冪等元，是乘法的冪等元。．在代數(shù)系統(tǒng)〈，*〉中，{}，*是上二元運(yùn)算，則該代數(shù)系統(tǒng)的單位元是，零元是。．設(shè)〈，≤〉是偏序集，若中都有最小上界和則稱關(guān)于偏序≤構(gòu)成格。．若一條路中，所有邊均不相同，則此路稱作；若一條路中所有的結(jié)點(diǎn)均不相同，則稱此路為。三、計(jì)算題（本大題共小題，第、小題各分，第、小題各分，第、小題各分，共分）．試畫出結(jié)點(diǎn)數(shù)為的（）強(qiáng)連通圖；（）單向連通圖；（）弱連通圖；（）非連通圖。．設(shè){，，，}，{〈〉∈∧(∨)}，{〈〉∈∧（）}。試求．在全體正整數(shù)集合中規(guī)定∩，∪為：對(duì)任意的∈，∪[]，即求的最小公倍數(shù)；∩()，即求的最大公約數(shù)； 則運(yùn)算∩，∪滿足結(jié)合律，交換律和吸收律，于是〈，∩，∪〉是一個(gè)格。判斷下列集合是否是<，∩，∪>的子格？ ）{，，，，，} ）{，，，，} ）{，，，…，}）{∈}．求命題公式（→）→（∨）的主析取范式。．結(jié)出命題公式（∨(∧)）∧((∨)∧)的二叉樹表示。．設(shè){},{〈〉，〈〉，〈〉，〈〉}，求，()()()的關(guān)系圖。四、證明題（本大題共小題，第、小題各分，第小題分，共分）．設(shè)是非空集合，（）是的冪集，是集合的包含關(guān)系，則〈（），〉是格，證明：〈（），〉是有補(bǔ)格。．設(shè)〈{},*〉是半群，其中*，證明：（）**；（）*。．若一棵樹恰有個(gè)結(jié)點(diǎn)的度數(shù)為，則它必是一條歐拉路。五、應(yīng)用題（本大題共小題，第小題分，第小題分，共分）．設(shè)是整數(shù)集，<，>，＝，≤，≥，≠是Ｉ上的二元關(guān)系，分別表示小于，大于、等于、小于等于，大于等于，不等于，那么這些關(guān)系會(huì)滿足什么性質(zhì)？試填寫下表自反反自反對(duì)稱反對(duì)稱傳遞<>≤≥≠≤∩≥≤∪≥．設(shè)，是整數(shù)集，則： （）對(duì)矩陣的加法和乘法構(gòu)成一個(gè)環(huán)； （）中存在元素是右零因子但不是左零因子。""全國年月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：一、單項(xiàng)選擇題（本大題共小題，每小題分，共分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。．令：今天下雪了，：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為（）．→ ．∨．∧ ．∧．下列命題公式為重言式的是（）．→（∧） ．→（∧）．（∧）→ ．（∨）→．下列個(gè)推理定律中，不正確的是（）．（∧） ．（∨）∧．（→）∧ ．（→）∧．謂詞公式(()∨())→()中量詞的轄域是（）． ．（）．(()∨()) ．(),()．設(shè)個(gè)體域{}，公式()∧()在中消去量詞后應(yīng)為（）．()∧() ．()∧()∧(()∨())．()∧() ．()∧()∧()∨()．下列選項(xiàng)中錯(cuò)誤的是（）．?? ．?∈?．?{?} ．?∈{?}．設(shè){}，上的等價(jià)關(guān)系{<,>,<,>,<,>,<,>}∪，則對(duì)應(yīng)于的的劃分是（）．{{},{,},{}} ．{{,},{},{}}．{{},{},{},{}} ．{{,},{}}．設(shè)為實(shí)數(shù)集，函數(shù)：→，()，則是（）．滿射函數(shù) ．入射函數(shù)．雙射函數(shù) ．非入射非滿射．設(shè)為實(shí)數(shù)集，{∈∧>}，*是數(shù)的乘法運(yùn)算，<，*>是一個(gè)群，則下列集合關(guān)于數(shù)的乘法運(yùn)算構(gòu)成該群的子群的是（）．{中的有理數(shù)} ．{中的無理數(shù)}．{中的自然數(shù)} ．{，，}．下列運(yùn)算中關(guān)于整數(shù)集不能構(gòu)成半群的是（）．{,} ．． ．．設(shè)是整數(shù)集，，分別是普通加法和乘法，則（，，）是（）．域 ．整環(huán)和域．整環(huán) ．含零因子環(huán)．設(shè){,,}，是上的二元關(guān)系，{<,>,<,>,<,>,<,>}，那么是（）．反自反的 ．反對(duì)稱的．可傳遞的 ．不可傳遞的．設(shè)<,>為有向圖，{,,,,,},{<,>,<,>,<,>,<,>,<,>}是（）．強(qiáng)連通圖 ．單向連通圖．弱連通圖 ．不連通圖．在有個(gè)結(jié)點(diǎn)的連通圖中，其邊數(shù)（）．最多有條 ．至少有條．最多有條 ．至少有條．連通圖是一棵樹，當(dāng)且僅當(dāng)中（）．有些邊不是割邊 ．每條邊都是割邊．無割邊集 ．每條邊都不是割邊二、填空題（本大題共小題，每小題分，共分） 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。．任意兩個(gè)不同的小項(xiàng)的合取為式，全體小項(xiàng)的析取式必為式。．公式(()→()∨(,))→()中的自由變?cè)獮?，約束變?cè)獮?。．設(shè)集合{≤≤被整除，∈}{≤≤被整除，∈}，則∩，∪。．設(shè){，，}，：→，：→，{<,>,<>,<>}, {<>,<>,<>}，則，。．設(shè){}，是上的二元關(guān)系，且給定{<>,<>,<>}，則的自反閉包()，對(duì)稱閉包()。．設(shè)為有理數(shù)集，笛卡爾集×，*是上的二元運(yùn)算，<,>,<,>∈,<,>*<,><,>,則*運(yùn)算的幺元是。<,>∈,若≠，則<,>的逆元是。．設(shè)*是集合上的二元運(yùn)算，若運(yùn)算*滿足且存在，則稱<，*>為獨(dú)異點(diǎn)。．令{,,}，<,*>是循環(huán)群，是單位元，則，的階是。．如下無向圖割點(diǎn)是，割邊是。．無向圖具有生成樹，當(dāng)且僅當(dāng)。的所有生成樹中的生成樹稱為最小生成樹。三、計(jì)算題（本大題共小題，第、小題各分，第、小題各分，第小題分，共分）．集合{,,,,}上的二元關(guān)系為 {<>,<>,<>,<>,<>,<>,<>,<>, <>,<>,<>,<>,<>,<>} （）寫出的關(guān)系矩陣； （）判斷是不是偏序關(guān)系，為什么？．利用真值表判斷公式（（∨）∧（→））→（∧）是否為重言式。．給定圖如下所示，（）寫出的可達(dá)矩陣；（）中長度為的路有幾條？．求下列公式的主析取范式和主合取范式：（→）∧（→）．設(shè)為的因子構(gòu)成的集合，×，∈,整除。畫出偏序集<>的哈斯圖，并求中的最大元，最小元，極大元，極小元。五、證明題（本大題共小題，第、小題各分，第小題分，共分）．設(shè)是上的一個(gè)自反關(guān)系，證明：是一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng)若<>∈，<>∈，則<>∈。．設(shè)<，*>是一個(gè)群，∈，定義：**，∈。證明：<,>也是一個(gè)群。．設(shè)圖是具有個(gè)結(jié)點(diǎn)，條邊的無向簡單圖，證明圖是漢密爾頓圖。五、應(yīng)用題（本大題共小題，第小題分，第小題分，共分）．構(gòu)造下面推理的證明。如果今天是星期六，我們就要到頤和園或圓明園去玩。如果頤和園游人太多，我們就不去頤和園玩。今天是星期六，頤和園游人太多，所以我們?nèi)A明園玩。．個(gè)城市用條公路的網(wǎng)絡(luò)連結(jié)。一條公路定義為兩個(gè)城市間的一條不穿過任何中間城市的道路。任意兩個(gè)城市之間至多修一條公路。證明如果>()()，則人們總能通過連結(jié)的公路，在任何兩個(gè)城市間旅行。""全國年月自考離散數(shù)學(xué)試題課程代碼：一、單項(xiàng)選擇題(本大題共小題，每小題分，共分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。.設(shè)：天下大雨：他在室內(nèi)運(yùn)動(dòng),命題“除非天下大雨，否則他不在室內(nèi)運(yùn)動(dòng)”可符合化為（）.∧ .→.→→.下列命題聯(lián)結(jié)詞集合中，是最小聯(lián)結(jié)詞組的是（）.{，} .{，∨，∧}.{，∧} .{∧，→}.下列命題為假命題的是（）.如果是偶數(shù)，那么一個(gè)公式的析取范式惟一.如果是偶數(shù)，那么一個(gè)公式的析取范式不惟一 .如果是奇數(shù)，那么一個(gè)公式的析取范式惟一.如果是奇數(shù)，那么一個(gè)公式的析取范式不惟一.謂詞公式(()∨())→())中變?cè)牵ǎ?自由變?cè)?.約束變?cè)?既不是自由變?cè)膊皇羌s束變?cè)?.既是自由變?cè)彩羌s束變?cè)?若個(gè)體域?yàn)檎麛?shù)減，下列公式中值為真的是（）() .() () .().下列命題中不正確的是（）∈{}{{}} .{}{}{{}} {}∪,則∈且.設(shè){()≤}，{≥},則下列選項(xiàng)正確的是（）.下列表達(dá)式中不成立的是（）∪()(∪)(∪) ∩()(∩)(∩).()×(×)(×) .()×(×)(×).半群、群及獨(dú)異點(diǎn)的關(guān)系是（）.{群}{獨(dú)異點(diǎn)}{半群} .{獨(dú)異點(diǎn)}{半群}{群}.{獨(dú)異點(diǎn)}{群}{半群} .{半群}{群}{獨(dú)異點(diǎn)}.下列集合對(duì)所給的二元運(yùn)算封閉的是（）.正整數(shù)集上的減法運(yùn)算 .在正實(shí)數(shù)的集上規(guī)定為∈.正整數(shù)集上的二元運(yùn)算為() ∈.全體×實(shí)可逆矩陣集合×上的矩陣加法.設(shè)集合{，，}，下列關(guān)系中不是等價(jià)關(guān)系的是（）{<>,<>,<>}{<>,<>,<>,<>,<>} {<>,<>,<>,<>} {<>,<>,<>,<>,<>,<>,<>,<>,<>} .下列函數(shù)中為雙射的是（）：→()() ：→()：→() ：→().設(shè)集合{,}上的關(guān)系如下，具有傳遞性的是（）{<>,<>,<>,<>} {<>,<>} {<>,<>,<>,<>} {<>}.含有個(gè)結(jié)點(diǎn)，條邊的不同構(gòu)的簡單圖有（）個(gè) 個(gè)個(gè) 個(gè).設(shè)的結(jié)點(diǎn)數(shù)大于，<>是強(qiáng)連通圖，當(dāng)且僅當(dāng)（）中至少有一條通路 中至少有一條回路中有通過每個(gè)結(jié)點(diǎn)至少一次的通路 中有通過每個(gè)結(jié)點(diǎn)至少一次的回路二、填空題(本大題共小題，每小題分，共分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。.設(shè){}，{}，則，。.設(shè){}，×，{<>，<>,<>}，則的自反閉包()。對(duì)稱閉包()。.設(shè)、為兩個(gè)命題，德摩根律可表示為，吸收律可表示為。.對(duì)于公式(()∨())，其中()∶()∶,當(dāng)論域?yàn)閧}時(shí)，其真值為,當(dāng)論域?yàn)閧}時(shí)，其真值為。.設(shè)∶→()∶→(),則復(fù)合函數(shù),。個(gè)結(jié)點(diǎn)可構(gòu)成個(gè)不同構(gòu)的簡單無向圖，可構(gòu)成個(gè)不同構(gòu)的簡單有向圖。.無向圖<>如左所示，則的最大度Δ()，的最小度δ()。.設(shè)圖<>{},若的鄰接矩陣，則(),()。.格是分配格，當(dāng)且僅當(dāng)既不含有與同構(gòu)的子格，也不含有與同格的子格。.給定集合{}，在集合上定義兩種關(guān)系：{<>,<>,<>},{<>,<>,<>,<>}，則，。三、計(jì)算題（本大題共小題，第、題各分，第、題各分，第題分，共分）.設(shè){}，上的等價(jià)關(guān)系{<>,<>,<>,<>}∪，畫出的關(guān)系圖，并求出中各元素的等價(jià)類。.構(gòu)造命題公式（∨）（∧）的真值表。.求下列公式的主析取范式和主合取范式：→（（→）∧（∧））.設(shè){,,,,}，為上的關(guān)系，{<,>，<,>，<,>,<,>,<,>,<,>,<,>}∪，試畫<，>的哈斯圖，并求中的最大元，最小元，極大元，極小元。.給定圖如圖所示，（）中長度為的路有幾條？其中有幾條回路？（）寫出的可達(dá)矩陣。四、證明題（本大題共小題，第、題各分，第題分，共分）.設(shè)（，≤）是格，試證明：,,∈,有∧（∨）≥（∧）∨（∧）；∨（∧）≤（∨）∧（∨）。.設(shè)是上的自反和傳遞關(guān)系，如下定義上的關(guān)系，使得,∈，<,>∈<,>∈∧(,)∈。證明是上的等價(jià)關(guān)系。.設(shè)有<,>,的結(jié)點(diǎn)數(shù)，稱該圖為階圖，若從結(jié)點(diǎn)到存在路，證明從到必存在長度小于等于的一條路。五、應(yīng)用題（本大題共小題，第題分，第題分，共分）.構(gòu)造下面推理的證明。每個(gè)喜歡步行的人都不喜歡坐汽車，每個(gè)人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車，因而有的人不喜歡步行。.今要將人分成組（每組個(gè)人）去完成項(xiàng)任務(wù)。已知每個(gè)人至少與其余個(gè)人中的個(gè)人能相互合作。（）能否使得每組的個(gè)人都能相互合作？（）你能給出幾種不同的分組方案？全國年月自考試題離散數(shù)學(xué)（附答案）課程代碼：一、單項(xiàng)選擇題（本大題共小題，每小題分，共分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。．設(shè)：他聰明，：他用功，命題“他雖聰明但不用功”的符號(hào)化正確的是（）．∧ ．∧．→ ．∨．下面聯(lián)結(jié)詞運(yùn)算不可交換的是（）．∧ ．→．∨ ．．下列命題公式不是重言式的是（）．→（∨） ．（∧）→．（∧）∧（∨） ．（→）（∨）．下列等價(jià)式不正確的是（）．．．．．設(shè)（）是人，（）：犯錯(cuò)誤，命題“沒有不犯錯(cuò)誤的人”符號(hào)化為（）． ．（））． ．())．設(shè){()}{()}，則方程()·()的解為（）．∩ ．∪． ．．設(shè)，則有（）． ．≠． ．．，是集合，（），（）為其冪集，且∩，則()∩()為（）． ．{}．{{}} ．{，{}}．設(shè)集合{，，，……，}，下列定義的運(yùn)算關(guān)于集合是不封閉的是（）．*{} ．*{}．*{},即的最大公約數(shù) ．*{},即的最小公倍數(shù)．設(shè)，是群（，）的子群，下面代數(shù)系統(tǒng)是（，）的子群的是（）．（∩，） ．（∪，）．（，） ．（，）．設(shè){，，，，}，{，，，，}，以下關(guān)系是從到的入射函數(shù)的是（）．{<>,<>,<>,<>,<>}．{<>,<>,<>,<>,<>}．{<>,<>,<>,<>}．{<>,<>,<>,<>,<>}．設(shè)簡單圖所有結(jié)點(diǎn)的度數(shù)之和為，則一定有（）．條邊 ．條邊．條邊 ．條邊．下列不一定是樹的是（）．無回路的連通圖 ．有個(gè)結(jié)點(diǎn)，條邊的連通圖．每對(duì)結(jié)點(diǎn)之間都有通路的圖 ．連通但刪去一條邊則不連通的圖．下面關(guān)于關(guān)系的傳遞閉包()的描述最確切的是（）．()是包含的二元關(guān)系 ．()是包含的最小傳遞關(guān)系．()是包含的一個(gè)傳遞關(guān)系 ．()是任何包含的傳遞關(guān)系．歐拉回路是（）．路徑 ．跡．既是初級(jí)回路也是跡 ．既非初級(jí)回路也非跡二、填空題（本大題共小題，每小題分，共分） 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。．設(shè){，}，{，}，則，。．設(shè){，，，}上關(guān)系{<>,<>,<>,<>}，則的自反閉包()，對(duì)稱閉包（）。．命題公式（）→的成真指派為，成假指派為。．公式（）（（）→()）→()(())中的自由變?cè)獮椋s束變?cè)獮?。．設(shè)→()→(),那么復(fù)合函數(shù)，。．有理數(shù)集中的*運(yùn)算定義如下：*，則*運(yùn)算的單位元是，設(shè)有逆元，則其逆元。．設(shè){<>,<>,<>}{<>,<>,<>},那么(∪)(∩)。．如下圖的有補(bǔ)格中，的補(bǔ)元是，的補(bǔ)元是。．在根樹中，若每一個(gè)結(jié)點(diǎn)的出度,則稱這棵樹為叉樹。如果每一個(gè)結(jié)點(diǎn)的出度或，則稱這棵樹為完全叉樹。．<,>是一個(gè)群，其中{,……}()，則在<,>中，的階是，的階是。三、計(jì)算題（本大題共小題，第、小題各分，第、小題各分，第小題分，共分）．構(gòu)造命題公式（）→的真值表。．若集合{，{，}}的冪集為（），集合{{，}，{}}的冪集為（），求()∩()。．設(shè){，，，}，是上的二元關(guān)系，{<>,<>,<>,<>,<>,<>,<>,<>,<>}。（）畫出的關(guān)系圖；（）寫出的關(guān)系矩陣；（）說明是否具有自反、反自反、對(duì)稱、傳遞性質(zhì)。．求下列公式的主析取范式和主合取范式：（→（））（→（→））。．設(shè){}()是的冪集，為上的包含關(guān)系，試給出<()>的哈斯圖，并給出子集{{},{},{}}的極大元、極小元、最大元、最小元。四、證明題（本大題共小題，第、小題各分，第小題分，共分）．設(shè)是形如的×階矩陣的集合，中定義通常的矩陣乘法運(yùn)算。驗(yàn)證是群，。．設(shè)為×上的二元關(guān)系，∈×，證明為等價(jià)關(guān)系。．簡單圖有個(gè)結(jié)點(diǎn)，條邊，設(shè)>()()，證明：是連通的。五、應(yīng)用題（本大題共小題，第小題分，第小題分，共分）．構(gòu)造下面推理的證明。只要曾到過受害者房間并且點(diǎn)以前沒離開，就犯了謀殺罪。曾到過受害者房間。如果在點(diǎn)以前離開，看門人會(huì)看見他?？撮T人沒有看見他。所以犯了謀殺罪。．在某次國際會(huì)議的預(yù)備會(huì)中，共有人參加，他們來自不同的國家。已知他們中任何兩個(gè)無共同語言的人中的每一個(gè)，與其余有共同語言的人數(shù)之和大于或等于，問能否將這個(gè)人排在圓桌旁，使其任何人都能與兩邊的人交談。年月自考離散數(shù)學(xué)試題參考答案全國年月自學(xué)考試離散數(shù)學(xué)試題（附答案）課程代碼：一、單項(xiàng)選擇題（本大題共小題，每小題分，共分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。．下列為兩個(gè)命題變?cè)?，的小?xiàng)是（）．∧∧ ．∨．∧ ．∨∨．下列語句中是真命題的是（）．我正在說謊 ．嚴(yán)禁吸煙．如果，那么雪是黑的 ．如果，那么雪是黑的．設(shè)：我們劃船，：我們跑步。命題“我們不能既劃船又跑步”符號(hào)化為（）．∧ ．∨．（） ．（∨）．命題公式（∧（→））→是（）．矛盾式 ．蘊(yùn)含式．重言式 ．等價(jià)式．命題公式（∧）→的成真指派是（）．，，， ．，，，，．全體指派 ．無．在公式（）（，）→（）（，）中變?cè)牵ǎ杂勺冊(cè)?．約束變?cè)仁亲杂勺冊(cè)?，又是約束變?cè)?．既不是自由變?cè)植皇羌s束變?cè)蟵，，…，}上的關(guān)系{<，>，∈，∈}，則的性質(zhì)是（）．自反的 ．對(duì)稱的．傳遞的、對(duì)稱的 ．反自反的、傳遞的．若和是集合上的兩個(gè)關(guān)系，則下述結(jié)論正確的是（）．若和是自反的，則∩是自反的．若和是對(duì)稱的，則是對(duì)稱的．若和是反對(duì)稱的，則是反對(duì)稱的．若和是傳遞的，則∪是傳遞的．{<，>，<，>，<，>，<，>}，則下列不是（）中元素的是（）．<，> ．<，>．<，> ．<，>．設(shè){{，，}，{，}，{，，}}，下列選項(xiàng)正確的是（）．∈ ．{，，}．{{，}} ．∈．在自然數(shù)集上，下列運(yùn)算是可結(jié)合的是（）． ．{，}． ．．在代數(shù)系統(tǒng)中，整環(huán)和域的關(guān)系是（）．整環(huán)一定是域 ．域不一定是整環(huán)．域一定是整環(huán) ．域一定不是整環(huán)．下列所示的哈斯圖所對(duì)應(yīng)的偏序集中能構(gòu)成格的是（）． ．． ．．設(shè)為有個(gè)結(jié)點(diǎn)的簡單圖，則有（）．Δ()＜ ．Δ()≤．Δ()＞ ．Δ()≥．具有個(gè)結(jié)點(diǎn)的非同構(gòu)的無向樹的數(shù)目是（）． ．． ．二、填空題（本大題共小題，每小題分，共分） 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。．（）（）（（，）（，））∧（，）中的轄域?yàn)?，的轄域?yàn)?。．兩個(gè)重言式的析取是式，一個(gè)重言式與一個(gè)矛盾式的析取是式。．設(shè)是自然數(shù)集合，和是到的函數(shù)，且（），（），那么復(fù)合函數(shù)（）（）（）（）。．設(shè)復(fù)合函數(shù)是從到的函數(shù)，如果是滿射，那么必是滿射，如果是入射，那么必是入射。．設(shè){，}，{，}，則，。．設(shè)是非空有限集，代數(shù)系統(tǒng)<（），∪>中，其中（）為集合的冪集，則（）對(duì)∪運(yùn)算的單位元是，零元是。．在<,\\(○)>中，的階是。．設(shè)<，≤>是格，其中{，，，，，，，}，≤為整除關(guān)系，則的補(bǔ)元是。．在下圖中，結(jié)點(diǎn)的度數(shù)是。．，從到長度為的路有條。三、計(jì)算題（本大題共小題，第、小題各分，第、小題各分，第小題分，共分）．已知{{}，{，}}，{{，}，{}}，計(jì)算∪，\\(○)，的冪集（）。．構(gòu)造命題公式（（∧）→）∨的真值表。．．求下列公式的主合取范式和主析取范式：∨（→（∨（→）））．設(shè){，，，，，，，}，為上的整除關(guān)系，試畫<，>的哈斯圖，并求中的最大元、最小元、極大元、極小元。四、證明題（本大題共小題，第、小題各分，第小題分，共分）．在整數(shù)集上定義：，證明：<，>是一個(gè)群。．是集合上自反和傳遞的關(guān)系，試證明：。．證明：邊是圖的一條割邊，當(dāng)且僅當(dāng)圖中不存在包含邊的簡單回路。五、應(yīng)用題（本大題共小題，第小題分，第小題分，共分）．構(gòu)造下面推理的證明。如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去。．今有個(gè)人，已知他們中任何人的朋友合起來一定包含其余人。試證明：（）當(dāng)≥時(shí)，這個(gè)人能排成一列，使得中間任何人是其兩旁的人的朋友，而兩頭的人是其左邊（或右邊）的人的朋友。（）當(dāng)≥時(shí)，這個(gè)人能排成一圓圈，使得每個(gè)人是其兩旁的人的朋友。年月自考全國離散數(shù)學(xué)參考答案""全國年月自考離散數(shù)學(xué)試題課程代碼：一、單項(xiàng)選擇題(本大題共小題，每小題分，共分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。.下列句子為命題的是().走，看電影去 >.空集是任意集合的真子集 .你明天能來嗎?.下列式子不是謂詞合式公式的是().()(()→()(()∧(，))) .()∧()∨(，).()()→() .()()∧(，).下列式子為重言式的是()→∨ .(﹁∧)∧(∨﹁).﹁() .(∨)(→).設(shè)個(gè)體域?yàn)閷?shí)數(shù)集，特定元素，函數(shù)(，)，特定謂詞(，)為<，下列公式真值為真的是().()()(，((，)，)).()()(﹁((，)，)).()()()((，)→((，)，(，))).()((，)，).對(duì)于公式()()(，)∨(，)∧()(，)，下列說法正確的是()是自由變?cè)?是約束變?cè)?()的轄域是(，)∨(，) .()的轄域是(，).設(shè)論域?yàn)閧，}，與公式()﹁()等價(jià)的是().﹁()∨﹁() .﹁()→﹁().﹁()∧﹁() .()→().設(shè)是正整數(shù)集，：×→，(，)，則().僅是入射 .僅是滿射.是雙射 .不是函數(shù).下列哪個(gè)關(guān)系矩陣所對(duì)應(yīng)的關(guān)系具有自反性(). .. ..設(shè)和是集合上的相容關(guān)系，下列關(guān)系哪個(gè)可能不是相容關(guān)系().在整數(shù)集上，下面哪個(gè)運(yùn)算不是二元運(yùn)算().加法 .減法.乘法 .除法.設(shè)是奇數(shù)集合，×為乘法運(yùn)算，則<，×>是().半群 .群.循環(huán)群 .交換群.下面不滿足結(jié)合律的運(yùn)算是()*(，) *(，)*() *.右圖的最小入度是().下面既是漢密爾頓圖又是歐拉圖的圖形是().一棵樹有個(gè)度點(diǎn)、個(gè)度點(diǎn)、個(gè)度點(diǎn)，其它的都是度，那么它的邊數(shù)是()二、填空題(本大題共小題，每小題分，共分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。.設(shè)命題變?cè)獮椋?，則小項(xiàng)，大項(xiàng)。.置換規(guī)則：在證明的任何步驟上，命題公式中的任何子命題公式都可以，記為規(guī)則。.一個(gè)公式，如果量詞均在全式的，其作用域延伸到整個(gè)公式的，則該公式稱為前束范式。.請(qǐng)用聯(lián)結(jié)詞﹁，∧表示聯(lián)結(jié)詞∨和聯(lián)結(jié)詞：，。.設(shè){，，，}，上的二元關(guān)系{<，>，<，>，<，>}，{<，>，<，>，<，>}，則～，()。.代數(shù)系統(tǒng)<，*，>是整環(huán)，則<，*>是，<，>是，且無零因子。.在實(shí)數(shù)集上定義運(yùn)算，則幺元為，元素的逆元為。.若回路中，除外各不相同，則此回路稱為圈(或初級(jí)回路)。.偶圖記為那么當(dāng)時(shí)，是平面圖，當(dāng)時(shí)，是非平面圖。.若圖中存在，它經(jīng)過圖中所有的邊恰好次，則稱該圖為歐拉圖。三、計(jì)算題(本大題共小題，每小題分，共分).用等值演算求(→)→的主合取范式。.列出(→(∨))(→)的真值表。．設(shè){}，{<，>，<，>，<，>，<，>，<，>}，求的傳遞閉包。.設(shè){，，，，，}，請(qǐng)畫出上整除關(guān)系的哈斯圖，并給出子集{，，，}的下界、下確界、極大元、最大元。.求右圖所示格的所有元子格。.用矩陣的方法求右圖中結(jié)點(diǎn)，之間長為的路徑的數(shù)目。四、證明題(本大題共小題，第小題分，第、小題各分，共分).用推理方法證明：∨，→，→├∨。.設(shè){<，>，∈，為整數(shù)集}，上的關(guān)系{<<，>,<，>>}，證明是等價(jià)關(guān)系。．證明：一個(gè)圖是強(qiáng)連通的，當(dāng)且僅當(dāng)圖中有一個(gè)回路，它至少包含每個(gè)結(jié)點(diǎn)一次。五、綜合應(yīng)用題（本大題共小題，第小題分，第小題分，共分）．符號(hào)化下面命題，并構(gòu)造推理證明：人是要死的，蘇格拉底是人，所以蘇格拉底是要死的。．設(shè)是的有限子集，則<，>是群<，>的子群當(dāng)且僅當(dāng)<，>是群<，>的子代數(shù)。全國年月自學(xué)考試離散數(shù)學(xué)試題課程代碼：一、單項(xiàng)選擇題(本大題共小題，每小題分，共分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均不得分。.下列句子為命題的是().全體起立! .我在說謊 .張三生于年的春天.下列式子不是謂詞合式公式的是().....下列式子為矛盾式的是(). .. ..設(shè)給定賦值如下：個(gè)體域?yàn)樽匀粩?shù)集；特定元素；特定函數(shù)()()；特定謂詞()為。在賦值下，下列公式為真的是().....對(duì)于公式，下列說法正確的是()是自由變?cè)羌s束變?cè)?的轄域是.的轄域是().設(shè)論域?yàn)閧，}，與公式等價(jià)的是()()() .()()() .()().設(shè)是正整數(shù)集合，→，(),則().僅是入射 .僅是滿射.是雙射 .不是函數(shù).下列關(guān)系矩陣所對(duì)應(yīng)的關(guān)系具有反自反性的是(). .. ..設(shè)和是集合上的相容關(guān)系，下列關(guān)于的說法正確的是().一定是相容關(guān)系 .一定不是相容關(guān)系.可能是也可能不是相容關(guān)系 .一定是等價(jià)關(guān)系.設(shè)是奇數(shù)集合，下列構(gòu)成獨(dú)異點(diǎn)的是().<，> .<，>.<，×> .<，÷>.設(shè)是整數(shù)集，下列說法正確的是().<，>有零元 .<，÷>有零元.<，>有幺元 .<，÷>有幺元.下列說法不正確的是().在實(shí)數(shù)集上，乘法對(duì)加法是可分配的.在實(shí)數(shù)集上，加法對(duì)乘法是可分配的.在某集合的冪集上，∪對(duì)∩是可分配的.在某集合的冪集上，∩對(duì)∪是可分配的.右圖的最大入度是().下列可一筆畫成的圖形是().一棵樹有個(gè)度結(jié)點(diǎn)，個(gè)度結(jié)點(diǎn)，其它的都是度結(jié)點(diǎn)，那么這棵樹的結(jié)點(diǎn)數(shù)是()二、填空題(本大題共小題，每小題分，共分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均不得分。.請(qǐng)寫出表示分配律的兩個(gè)命題公式等價(jià)定理。個(gè)命題變?cè)姆Q為大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，但兩者必須。.在謂詞推理過程中，由得到()，其中為論域的某個(gè)個(gè)體，用的是規(guī)則，記為規(guī)則。.請(qǐng)用聯(lián)結(jié)詞，表示聯(lián)結(jié)詞和聯(lián)結(jié)詞：，。.設(shè){，，，}，{，，}，則，。.給出{，}上的一個(gè)等價(jià)關(guān)系，并給出其對(duì)應(yīng)的劃分。.設(shè){，，，}，上的二元關(guān)系{<，>，<，>，<，>}，{<，>，<，>，<，>}，則∩，(—)。.代數(shù)系統(tǒng)<，，。>是域，則和都是交換群。.若圖中存在，它經(jīng)過圖中所有的，則稱該圖為漢密爾頓圖。點(diǎn)完全圖記為，那么當(dāng)時(shí)，是平面圖，當(dāng)時(shí)，是非平面圖。三、計(jì)算題(本大題共小題，每小題分，共分).列出的真值表。.用等值演算求()的主析取范式。.設(shè){}，給定上的二元關(guān)系{<>,<>,<>,<>}，求的傳遞閉包。.求右圖所示格的所有元和元子格。.求<一{}，>的所有生成元及所有階、階子群，其中為模乘法。.用矩陣的方法求右圖中結(jié)點(diǎn)，之間長度為的路徑的數(shù)目。()題四、證明題(本大題共小題，第小題分，第、小題各分，共分).用推理方法證明：。.設(shè)是的非空子集，則<，·>是群<，·>的子群當(dāng)且僅當(dāng)對(duì)任意有·。．證明整數(shù)集上的大于等于關(guān)系“”是一個(gè)偏序關(guān)系。五、綜合應(yīng)用題(本大題共小題，第小題分，第小題分，共分)．將下面命題符號(hào)化，并構(gòu)造推理證明：所有有理數(shù)是實(shí)數(shù)，有些有理數(shù)是整數(shù)，所以有些實(shí)數(shù)是整數(shù)。．某城市擬在六個(gè)區(qū)之間架設(shè)有線電話網(wǎng)，其網(wǎng)點(diǎn)間的距離如下列有權(quán)矩陣給出，請(qǐng)繪出有權(quán)圖，給出架設(shè)線路的最優(yōu)方案，并計(jì)算線路的總長度。年月自考離散數(shù)學(xué)參考答案全國年月自學(xué)考試離散數(shù)學(xué)試題課程代碼：一、單項(xiàng)選擇題（本大題共小題，每小題分，共分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。．下列句子不是命題的是（）．中華人民共和國的首都是北京 ．張三是學(xué)生．雪是黑色的 ．太好了?。铝惺阶硬皇侵^詞合式公式的是（）．（）()→()．()┐（）()(()→())．()()(()∧())→()()．()(()→())∨()()．下列式子為重言式的是（）．(┐∧)→ ．∨∧→┐．∨(∧) ．(┐∨)(→)．在指定的解釋下，下列公式為真的是（）．()(()∨())()(),論域:{}．()(()∧())()(),論域:{}．()(()→())()>(),論域:{}．()(()→())()>(),論域:{}．對(duì)于公式()()(()∧())→()()，下列說法正確的是（）．是自由變?cè)?．是約束變?cè)?)的轄域是(,) ．()的轄域是()(()∧())→()()．設(shè)論域?yàn)閧}，與公式()()等價(jià)的是（）．()∨() ．()→()．()∧() ．()→()．設(shè)是正整數(shù)集，是實(shí)數(shù)集，→,(),則（）．僅是入射 ．僅是滿射．是雙射 ．不是函數(shù)．下列關(guān)系矩陣所對(duì)應(yīng)的關(guān)系具有反對(duì)稱性的是（）． ．． ．．設(shè)和是集合上的相容關(guān)系，下列關(guān)于復(fù)合關(guān)系的說法正確的是（）．一定是等價(jià)關(guān)系 ．一定是相容關(guān)系．一定不是相容關(guān)系 ．可能是也可能不是相容關(guān)系．下列運(yùn)算不滿足交換律的是（）．* ．*()．* ．*．設(shè)是偶數(shù)集合，下列說法正確的是（）．<>是群 ．<,×>是群．<,÷>是群 ．<>,<,×>,<,÷>都不是群．設(shè)*是集合上的二元運(yùn)算，下列說法正確的是（）．在中有關(guān)于運(yùn)算*的左幺元一定有右幺元．在中有關(guān)于運(yùn)算*的左右幺元一定有幺元．在中有關(guān)于運(yùn)算*的左右幺元，它們不一定相同．在中有關(guān)于運(yùn)算*的幺元不一定有左右幺元．題圖的最大出度是（）． ．． ．．下列圖是歐拉圖的是（）．一棵樹的個(gè)度點(diǎn)，個(gè)度點(diǎn)，其它的都是度，那么這棵樹的邊數(shù)是（）． ．． ．二、填空題（本大題共小題，每小題分，共分） 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。．請(qǐng)寫出表示德摩根律的兩個(gè)命題公式等價(jià)定理，。．個(gè)命題變?cè)姆Q為小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，但兩者必須。．前提引入規(guī)則：在證明的任何步驟上都可以，簡稱規(guī)則。．自由變?cè)胍?guī)則是指對(duì)某出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或用與原子公式中所有個(gè)體變?cè)煌膫€(gè)體變?cè)ゴ?，且。．設(shè){}，則(()，×。．設(shè){},上的二元關(guān)系{<>,<>,<>}{<>,<>,<>}，則，()。．設(shè)代數(shù)系統(tǒng)<,·,*>是環(huán)，則<,·>是，<,*>是。．在<{},>中，元素的階為，它生成的子群為，其中為模乘法。．設(shè)<,≤>是一個(gè)，如果中任意兩個(gè)元素都有，則稱<,≤>為格。．若一條中，所有的均不相同，稱為跡。三、計(jì)算題（本大題共小題，每小題分，共分）．給定論域{}，(),(),(),(),(),(),在該賦值下，求式子((())∧(,()))的真值。．請(qǐng)通過等值演算法求┐(∧)→(∨)的主析取范式