南郵離散數(shù)學(xué)綜合練習(xí)期末復(fù)習(xí)題

《離散數(shù)學(xué)》綜合練習(xí)共26頁(yè)第26頁(yè)《離散數(shù)學(xué)》綜合練習(xí)注：此版本的綜合練習(xí)冊(cè)對(duì)應(yīng)教材是《離散數(shù)學(xué)》，辛運(yùn)幃主編，機(jī)械工業(yè)出版社，2014年版，ISBN978-7-111-48204-8第一章命題與命題公式一、選擇題1.下列語(yǔ)句中不是命題的是（）A.3是素?cái)?shù) B.x+y>1C.地球外的星球上也有人 D.雪是黑的2.設(shè)P：我們劃船，Q：我們跳舞，命題“我們不能既劃船又跳舞”符號(hào)化為（）A.PQ B.┐（P∧Q）C.┐P∧┐Q D.┐P∧Q3.令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為（）A.P┐QB.P∨┐Q C.P∧Q D.P∧┐Q4.設(shè)P：天下大雨，Q：他乘公共汽車上班。命題“只有天下大雨，他才乘公共汽車上班”符號(hào)化為（）A.PQ B.QP C.PQ D.PQ5.下面聯(lián)結(jié)詞集中，不屬于聯(lián)結(jié)詞的極小全功能集的是（）A.{，} B.{↓}C.{} D.{，，}6.下面聯(lián)結(jié)詞不滿足交換律的是（）A. B. C. D.二、填空題1.在命題邏輯中，具有唯一的陳述句稱為命題。2.在命題中，有些命題是基本的、原始的，它不能再被分割成為更小的命題，這些命題稱為。3.在重言式中,不論公式中的分量作怎樣的指派，其真值永遠(yuǎn)為。4.在矛盾式中,不論公式中的分量作怎樣的指派，其真值永遠(yuǎn)為。第二章命題邏輯的推理理論一、填空題1.在命題邏輯中，一個(gè)由n個(gè)命題變?cè)鶚?gòu)成的公式共有_________個(gè)大項(xiàng)。2.在命題邏輯中，一個(gè)由n個(gè)命題變?cè)鶚?gòu)成的公式共有_________個(gè)小項(xiàng)。二、計(jì)算題1．設(shè)P、Q、R為原子命題，試求命題公式的主析取范式。2．設(shè)P、Q、R為原子命題，試求命題公式的主合取范式。3.設(shè)P、Q、R為原子命題，求命題公式的真值表，并給出其等價(jià)的主析取范式。4.設(shè)P、Q、R為原子命題，求命題公式的真值表，并給出其等價(jià)的主合取范式。5.設(shè)P、Q、R為原子命題，求命題公式的真值表，并給出其等價(jià)的主析取范式。6.設(shè)P、Q、R為原子命題，求命題公式的真值表，并給出其等價(jià)的主合取范式。三、證明題1.符號(hào)化下面的命題并用推理規(guī)則證明其結(jié)論：甲、乙、丙、丁四人參加拳擊比賽，如果甲獲勝，則乙失??；如果丙獲勝，則乙也獲勝；如果甲不獲勝，則丁不失敗。所以如果丙獲勝，則丁不失敗。2.符號(hào)化下面的命題并用推理規(guī)則證明其結(jié)論：如果2是偶數(shù)，則2不能整除7；或者5不是質(zhì)數(shù)，或者2整除7；5是質(zhì)數(shù)。因此2不是偶數(shù)。3.符號(hào)化下面的命題并用推理規(guī)則證明其結(jié)論：如果廠方拒絕增加工資，那么罷工就不會(huì)停止，除非罷工超過(guò)一年并且工廠撤換了廠長(zhǎng)；若廠方拒絕增加工資，而罷工剛開(kāi)始，因此罷工不會(huì)停止。第三章謂詞邏輯一、選擇題1.設(shè)個(gè)體域A={a,b}，公式在A上消去量詞應(yīng)為（）A.P(x)∧S(x)B.P(a)∧P(b)∧S(a)∨S(b)C.P(a)∧S(b)D.P(a)∧P(b)∧(S(a)∨S(b))2.設(shè)論域?yàn)檎麛?shù)集，下列公式中值為真的是（）A. B.C. D.3.設(shè)論域?yàn)檎麛?shù)集，下列公式中值為假的是（）A. B.C. D.4.一階公式x(P(x)∨yR(y))→Q(x)中量詞x的轄域是（）A.(P(x)∨yR(y)) B.P(x)C.x(P(x)∨yR(y)) D.(P(x)∨yR(y))→Q(x)5.謂詞公式(x)P(x,y)∧(x)(Q(x,z)(x)(y)R(x,y,z))中量詞x的轄域是（）A.(Q(x,z)(x)(y)R(x,y,z)) B.Q(x,z)，R(x,y,z)C.Q(x,z)(y)R(x,y,z) D.Q(x,z)6.下面的邏輯等價(jià)式中，不正確的是（）A.A?"xB（x）"x（A?B（x））B."x（A（x）úB（x））"xA（x）ú"xB（x）C.$x（A（x）úB（x））$xA（x）ú$xB（x）D.?"xA（x）$x（?A（x））二、填空題1.謂詞邏輯中的量詞有兩類：全稱量詞和。2.若解釋I的論域D僅包含一個(gè)元素，則在I下真值為。3.設(shè)個(gè)體域?yàn)閧a,b}，則謂詞公式的真值是.4.謂詞公式x（P(x)∨Q（x）），其中P(x)：x＝1,Q（x）：x＝2，當(dāng)個(gè)體域?yàn)閧1，2}時(shí)，該公式的真值為_(kāi)_______。5.謂詞公式x（P(x)∨Q（x）），其中P(x)：x＝1,Q（x）：x＝2，當(dāng)個(gè)體域?yàn)閧0，1，2}時(shí)，其真值為_(kāi)_______。6.謂詞公式，給定解釋I：個(gè)體域?yàn)閷?shí)數(shù)，：x>y，則該公式的真值為。三、證明題1.用推理規(guī)則證明:(A(x)→B(x))A(x)→B(x).2.用推理規(guī)則證明:(┐A(x)→B(x)),┐B(x)A(x).3.符號(hào)化下面的命題并用推理規(guī)則證明其結(jié)論：所有的舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。第四章集合一、選擇題1.為空集，下列式子中正確的是（） A.＝0 B. C.＝{} D.｛｝2.為空集，下列各式中不正確的是（）A. B.C.｛｝ D.{}3.為空集，下列命題正確的是（）A.?{}= B.è{}=C.{a}?{a，b，c} D.?{a，b，c}4.下列各式中不正確的是（）A.{a,b}{a,b,c,{a,b,c}} B.{a,b}{a,b,c,{a,b,c}}C.{a,b}{a,b,{a,b}} D.{a,b}{{a,b}}5.設(shè)A={{1,2,3},{4,5},{6,7,8}}，下列式子中正確的是（）A.1∈A B.{1,2,3}?A C.{{4,5}}?A D.A6.設(shè)A=（空集），B={,{}}，則B－A是（）A.{{}} B.{} C.{,{}} D.二、填空題1.設(shè)集合，，則。2.設(shè)集合，，則。3.設(shè)集合，，則。4.設(shè)集合，，則。 5.設(shè)集合則其冪集＝。 6.設(shè)為空集，則冪集＝。三、計(jì)算題1.設(shè)集合，試計(jì)算集合和。2.設(shè)四、證明題1.設(shè)和為集合A，B的冪集，且，試證明：。2.設(shè)A、B、C為任意三個(gè)集合，證明：(A∩B)×(C∩D)=(A×C)∩(B×D)第五章關(guān)系與函數(shù)一、選擇題1.設(shè)A為集合，|A|=n，則A上的二元關(guān)系數(shù)量是（）A. B. C. D.2.設(shè)|A|=m，|B|=n則從A到B所有的函數(shù)個(gè)數(shù)為（）A.mn B.nmC. D.3.設(shè)集合A上的關(guān)系，則R是（）A.自反關(guān)系 B.傳遞關(guān)系C.對(duì)稱關(guān)系 D.反自反關(guān)系4.設(shè)集合A={1,2,3}，A上的關(guān)系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，則R不具備（）A.自反性 B.傳遞性 C.對(duì)稱性 D.反對(duì)稱性5.設(shè)集合A={1，2，3}，A上的關(guān)系R={<1，1>，<1，2>，<2，2>，<3，3>，<3，2>}，則R不具備（）A.傳遞性 B.對(duì)稱性C.自反性 D.反對(duì)稱性6.設(shè)R是集合A={a,b,c,d}上的二元關(guān)系，R={<a,a>,<a,b>,<a,c>,<a,d>,<c,b>,<d,b>,<d,c>}，則R具有（） A.自反性、反對(duì)稱性 B.反自反性、傳遞性C.自反性、對(duì)稱性 D.反對(duì)稱性、傳遞性7.設(shè)A={a,b,c,d}，A上的等價(jià)關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，則對(duì)應(yīng)于R的A的劃分是（）A.{{a},{b,c},2ag0qyc}B.{{a,b},{c},kk8iiik} C.{{a},,{c},o0wqi2g} D.{{a,b},{c,d}}8.設(shè)為實(shí)數(shù)集，為正實(shí)數(shù)集，,其中，則是（）A.入射 B.滿射 C.雙射 D.不是函數(shù)9.設(shè)是自然數(shù)集，為實(shí)數(shù)集，,其中，則是（）A.入射 B.滿射C.雙射 D.不是函數(shù)10.設(shè)是自然數(shù)集，，其中（即除以5的余數(shù)），則f是（）A.入射 B.滿射C.雙射 D.既不是入射也不是滿射11.下列關(guān)于函數(shù)的描述，正確的是（）A.一個(gè)函數(shù)的反函數(shù)一定存在 B.任意兩個(gè)函數(shù)一定可復(fù)合C.一個(gè)函數(shù)的反函數(shù)一定是雙射 D.映射可以是多對(duì)多的12.下列關(guān)于函數(shù)的描述，正確的是（）A.函數(shù)一定是一對(duì)一的 B.函數(shù)可以是一對(duì)多的C.函數(shù)可以是多對(duì)一的 D.函數(shù)可以是多對(duì)多的二、填空題1.設(shè)集合，則從到共有個(gè)函數(shù)。 2.設(shè)集合，則從到共有個(gè)函數(shù)。3.設(shè)集合，則上共有個(gè)二元關(guān)系。4.設(shè)集合，則上共有個(gè)二元關(guān)系。5.設(shè)集合，則上共有個(gè)二元關(guān)系。6.設(shè)集合，則從到共有個(gè)二元關(guān)系。7.設(shè)Q為全體有理數(shù)集合，R為Q上的二元關(guān)系，且Q，則其逆關(guān)系＝。8．設(shè)R為非空集合A上的等價(jià)關(guān)系的含義是。9．若關(guān)系R是反對(duì)稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中.10．若關(guān)系R是對(duì)稱的，當(dāng)且僅當(dāng)關(guān)系矩陣是.11．若關(guān)系R是自反的，當(dāng)且僅當(dāng)關(guān)系矩陣中.12．若關(guān)系R是反自反的，當(dāng)且僅當(dāng)關(guān)系矩陣中.三、計(jì)算題1.設(shè)，，試計(jì)算：(1)；(2)；(3)。2.設(shè)S={１,２,３,４}，Ａ上的關(guān)系Ｒ＝｛(1,2)，(2,1)，(2,3)，(3,4)｝求(1)RR(2)。3.設(shè)集合A={1，2}，B={0，1}，求：（1）所有A到B的關(guān)系；（2）所有A到B的函數(shù)；（3）所有A到B的雙射。4.設(shè)集合A＝｛1｝，B＝｛a，b｝，C＝｛2,3｝，試計(jì)算集合和。5.集合S={1，2，3，4，5}，找出S上的等價(jià)關(guān)系，此關(guān)系能產(chǎn)生劃分{{1，2}，{3}，{4，5}}，并畫(huà)出關(guān)系圖。6.集合S={1，2，3，4，5}，找出S上的等價(jià)關(guān)系，此關(guān)系能產(chǎn)生劃分{{1}，{2，3}，{4，5}}。7.求集合A={1,2}上的所有等價(jià)關(guān)系。8.設(shè)是集合上的二元關(guān)系，求解R的自反閉包、對(duì)稱閉包和傳遞閉包。9.設(shè)是集合上的二元關(guān)系，求R的自反閉包、對(duì)稱閉包和傳遞閉包。10.設(shè)集合，是上的二元關(guān)系，求R的自反閉包、對(duì)稱閉包和傳遞閉包。第六章代數(shù)系統(tǒng)的一般概念一、選擇題1.設(shè)群G的階是6，H是G的子群，則H的階不可能是（）A.1 B.2 C.3 D.42.設(shè)群G的階是8，H是G的子群，則H的階不可能是（）A.1 B.2 C.3 D.43.設(shè)群G的階是12，H是G的子群，則H的階不可能是（）A.1 B.2 C.4 4.設(shè)群G的階是8，則其中元素的階不可能是（）A.1 B.2C.3 D.45.設(shè)群G的階是6，則其中元素的階不可能是（）A.1 B.2 C.3 D.46.設(shè)群G的階是12，則其中元素的階不可能是（）A.1 B.2C.4 D.87.下列關(guān)于循環(huán)群的描述，錯(cuò)誤的是（）A.循環(huán)群一定是阿貝爾群 B.循環(huán)群的生成元素是唯一的C.循環(huán)群的子群一定是循環(huán)群 D.素?cái)?shù)階群一定是循環(huán)群8.下列關(guān)于群的描述，錯(cuò)誤的是（）A.群中沒(méi)有零元 B.群中沒(méi)有等冪元C.群中每個(gè)元素都有逆元 D.群中滿足消去律9.關(guān)于整環(huán)和域的關(guān)系，下列描述中正確的是（）A.整環(huán)一定是域 B.有限域未必是整環(huán)C.有限整環(huán)一定是域 D.域一定是有限整環(huán)10.下列關(guān)于代數(shù)系統(tǒng)的描述，錯(cuò)誤的是（）A.群一定是半群 B.單元半群中必有等冪元C.階相同的循環(huán)群必同構(gòu) D.兩個(gè)代數(shù)系統(tǒng)同態(tài)必同構(gòu)11.下列關(guān)于群與子群的描述，錯(cuò)誤的是（）A.群的任意兩個(gè)子群的并一定還是子群B.子群一定是群C.子群中任一元素的逆元一定是它在群中的逆元D.子群中的單位元素一定是群中的單位元素12.設(shè)為阿貝爾群，，的階分別為3和5，則的階為（）A.3 B.5 C.8 D.15二、填空題1.設(shè)（G，*）為群，則其平凡子群是G和。2.設(shè)A={a，b，c，d}，A上二元運(yùn)算如下：*abcdabcdabcdbcdacdabdabc那么代數(shù)系統(tǒng)<A，*>的單位元是。3.設(shè)(G,*)是一個(gè)群，若a,b,x∈G，ax=b，則x=_____________。4.如果同構(gòu)的群認(rèn)為相同，那么4階的群共有。5.如果同構(gòu)的群認(rèn)為相同，那么3階的群共有。6.4階群必是Klein四元群或。7.設(shè)群中元素a的階為12，則a4的階為。8.設(shè)群中元素a的階為6，則a4的階為。9.設(shè)群中元素a的階為12，則a8的階為。10.設(shè)為阿貝爾群，，的階分別為4和5，則的階為。11.設(shè)為阿貝爾群，，的階分別為4和8，則的階為。12.設(shè)為阿貝爾群，，的階分別為4和6，則的階為。13.設(shè)（Z10，+，）為模10的環(huán)，則元素[9]的乘法逆元[9]-1=。14.設(shè)（Z10，+，）為模10的環(huán)，則元素[7]的乘法逆元[7]-1=。15.設(shè)（Z5，+，）為模5的環(huán)，則元素[3]的乘法逆元[3]-1=。16.設(shè)（Z5，+，）為模5的環(huán)，則元素[4]的乘法逆元[4]-1=。17.設(shè)（Z7，+，）為模7的環(huán)，則元素[4]的乘法逆元[4]-1=。18.設(shè)（Z7，+，）為模7的環(huán)，則元素[3]的乘法逆元[3]-1=。三、計(jì)算題1.設(shè)<Z6,+6>是一個(gè)群，這里+6是模6加法，Z6={[0]，[1]，[2]，[3]，[4]，[5]}，試求出每個(gè)元素的階數(shù)，并判斷其是否為循環(huán)群。2.設(shè)是4階群，其運(yùn)算表如下，試求出每個(gè)元素的階數(shù)，并判斷其是否為循環(huán)群。abcdabcdabcdbcdacdabdabc3.設(shè)A={1，2}，A上所有函數(shù)的集合記為AA,是函數(shù)的復(fù)合運(yùn)算，試給出AA上的復(fù)合運(yùn)算的運(yùn)算表，并指出AA中是否有幺元，哪些元素有逆元？4.有理數(shù)集Q上的二元運(yùn)算*定義如下:對(duì)任意的<a,b>,<x,y>∈Q×Q，有<a,b>*<x,y>=<ax,ay+b>問(wèn)運(yùn)算*有沒(méi)有單位元和零元，如果有，求出*的單位元和零元。5.設(shè)A={a,b,c}上的二元運(yùn)算*如下表所示。（1）判斷*是否滿足交換律，結(jié)合律和冪等律；（2）求關(guān)于*的單位元,零元及每個(gè)可逆元的逆元。 題5表*abcaabcbbbcccbc6.設(shè)A={a,b,c}上的二元運(yùn)算*如下表所示。（1）判斷*是否滿足交換律，結(jié)合律和冪等律；（2）求關(guān)于*的單位元,零元及每個(gè)可逆元的逆元。 題6表*abcaabcbbaccccc四、證明題1.設(shè)是一個(gè)獨(dú)異點(diǎn)，且對(duì)于中任意元素，都有，其中是單位元，證明是一個(gè)阿貝爾群。2.設(shè)<A，+，·>是一個(gè)含幺環(huán)，若|A|≥3，且任意都有a·a=a，試證明：<A，+，·>不可能是整環(huán)。3.已知〈A，*〉是群，集合A中元素的個(gè)數(shù)為偶數(shù)，證明：在A中至少存在a≠e，使得a*a=e，其中e為群中的單位元。4.設(shè)(G,)是一個(gè)群，則對(duì)于a,b∈G，必有唯一的x∈G，使得ax=b。5.I上的二元運(yùn)算*定義為：a,bI，a*b=a+b-2。證明：(I,*)為群。6.證明：循環(huán)群的任何子群一定也是循環(huán)群。第七章格與布爾代數(shù)一、選擇題1.設(shè)S={0,1,2,3},≤為小于等于關(guān)系，則{S，≤}是（）A.群 B.環(huán) C.域 D.格2.下列關(guān)于格的描述，正確的是（）A.格中任意兩個(gè)元素都是可比較的 B.格一定滿足反對(duì)稱性C.有補(bǔ)格一定是分配格 D.分配格一定是有補(bǔ)格3.下列關(guān)于格的描述，正確的是（）A．格中滿足分配律B．格中每個(gè)元素都有補(bǔ)元 C．格一定是有界的D．格中滿足對(duì)偶定律4.下面集合（）關(guān)于整除關(guān)系構(gòu)成格。A．{2，3，6，12，24，36}B．{1，2，3，4，6，8，12}C．{1，2，3，5，6，15，30}D．{3，6，9，12}5.設(shè)是格，，則下列選項(xiàng)中錯(cuò)誤的是（）A． Ｂ．C． Ｄ．6．設(shè)是偏序格，其中N是自然數(shù)集合，“≤”是普通的數(shù)間“小于等于”關(guān)系，則有（）A．a(chǎn) B．b C．max{a，b} D．min{a，b}第八章圖一、選擇題1.僅由一個(gè)孤立點(diǎn)組成的圖稱為（）A.二分圖 B.平凡圖 C.多重圖 D.子圖2.在任何圖G=＜V，E＞中，頂點(diǎn)總度數(shù)和邊數(shù)的關(guān)系為（）A. B.C. D.3.設(shè)G為有n個(gè)結(jié)點(diǎn)的無(wú)向完全圖，則G的邊數(shù)為（）A. B.C. D.4.設(shè)圖G的鄰接矩陣為，則G的頂點(diǎn)數(shù)與邊數(shù)分別為（）A.4,5 B.5,6 C.4,10 D.5,85.在任何圖中必定有偶數(shù)個(gè)（）A．度數(shù)為偶數(shù)的結(jié)點(diǎn)B．入度為奇數(shù)的結(jié)點(diǎn)C．度數(shù)為奇數(shù)的結(jié)點(diǎn)Ｄ．出度為奇數(shù)的結(jié)點(diǎn)6.設(shè)無(wú)向圖G有16條邊且每個(gè)頂點(diǎn)的度數(shù)都是2，則圖G有（）個(gè)頂點(diǎn)。A．10 Ｂ．4C．8 Ｄ．16二、填空題1.設(shè)圖G＝<V，E>，若|V|＝1，|E|＝0，則稱圖G為。2.任何(n,m)圖G=(V,E),邊與頂點(diǎn)數(shù)的關(guān)系是。3.5階完全圖的邊共有______。4.4階完全圖的邊共有______。5.n階完全圖的邊共有。6.n階完全圖任一結(jié)點(diǎn)v的度數(shù)d(v)=。三、計(jì)算題1.設(shè)圖G有16條邊，3個(gè)4度結(jié)點(diǎn),4個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)都小于3，問(wèn)G至少有幾個(gè)結(jié)點(diǎn)？2.設(shè)圖G有20條邊，5個(gè)4度結(jié)點(diǎn)，4個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)都小于3，問(wèn)G至少有幾個(gè)結(jié)點(diǎn)？3.設(shè)圖G有18條邊，2個(gè)4度結(jié)點(diǎn)，4個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)都小于3，問(wèn)G至少有幾個(gè)結(jié)點(diǎn)？4.設(shè)圖G有17條邊，3個(gè)4度結(jié)點(diǎn),2個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)都小于3，問(wèn)G至少有幾個(gè)結(jié)點(diǎn)？5.設(shè)圖G有19條邊，4個(gè)4度結(jié)點(diǎn),2個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)都小于3，問(wèn)G至少有幾個(gè)結(jié)點(diǎn)？6.設(shè)圖G有22條邊，4個(gè)4度結(jié)點(diǎn),6個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)都小于3，問(wèn)G至少有幾個(gè)結(jié)點(diǎn)？第九章圖的應(yīng)用一、選擇題1.無(wú)向圖G是歐拉圖，當(dāng)且僅當(dāng)（）A.G的所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)B.G中所有結(jié)點(diǎn)的度數(shù)全為奇數(shù)C.G連通且所有結(jié)點(diǎn)度數(shù)全為奇數(shù)D.G連通且所有結(jié)點(diǎn)度數(shù)全為偶數(shù)2.下列可以一筆畫(huà)出的圖形是（）3.設(shè)G是一個(gè)哈密爾頓圖，則G一定是（） A.歐拉圖 B.樹(shù) C.平面圖 D.連通圖4.設(shè)G是有5個(gè)頂點(diǎn)的完全圖，如果要得到樹(shù)，那么應(yīng)從G中刪去（）A.4條邊 B.6條邊C.8條邊 D.10條邊5.設(shè)圖G是有6個(gè)頂點(diǎn)的連通圖，總度數(shù)為20，則從G中刪去（）A.10條邊 B.5條邊C.3條邊 D.2條邊6.下列關(guān)于樹(shù)的描述，正確的是（）A.樹(shù)是不連通的 B.樹(shù)中增加任意一條邊后必有回路C.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的次數(shù)必定是2 D.樹(shù)中每個(gè)結(jié)點(diǎn)的次數(shù)一定不小于2二、填空題1.設(shè)G是連通平面圖，若G有7個(gè)面15條邊，則G的頂點(diǎn)數(shù)為。2.設(shè)G是連通平面圖，有4個(gè)頂點(diǎn)，4個(gè)面，則G的邊數(shù)為。3.設(shè)G是連通平面圖，若G有8個(gè)頂點(diǎn)12條邊，則G的面數(shù)為。4.設(shè)圖T是一顆(n,m)樹(shù)，則n與m的關(guān)系為。5.樹(shù)的葉是指。 6.經(jīng)連通圖G的每條邊一次而且僅一次的回路稱為G的__________。三、計(jì)算題1.設(shè)樹(shù)T有4個(gè)2度結(jié)點(diǎn)，2個(gè)3度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，其余的都是樹(shù)葉，求T的樹(shù)葉片數(shù)。2.設(shè)樹(shù)T有2個(gè)2度結(jié)點(diǎn)，1個(gè)3度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，其余的都是樹(shù)葉，求T的樹(shù)葉片數(shù)。3.設(shè)樹(shù)T有5個(gè)2度結(jié)點(diǎn)，4個(gè)3度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，其余的都是樹(shù)葉，求T的樹(shù)葉片數(shù)。4.設(shè)樹(shù)T有3個(gè)2度結(jié)點(diǎn)，4個(gè)3度結(jié)點(diǎn)，5個(gè)4度結(jié)點(diǎn)，其余的都是樹(shù)葉，求T的樹(shù)葉片數(shù)。5.設(shè)樹(shù)T有4個(gè)2度結(jié)點(diǎn)，6個(gè)3度結(jié)點(diǎn)，2個(gè)4度結(jié)點(diǎn)，其余的都是樹(shù)葉，求T的樹(shù)葉片數(shù)。6.設(shè)有a、b、c、d、e、f、g七個(gè)人，他們分別會(huì)講的語(yǔ)言如下：a：英，b：漢、英，c：英、西班牙、俄，d：日、漢，e：德、西班牙，f：法、日、俄，g：法、德，能否將這七個(gè)人的座位安排在圓桌旁，使得每個(gè)人均能與他旁邊的人交談？《離散數(shù)學(xué)》綜合練習(xí)參考答案第一章命題與命題公式一、選擇題1.B 2.B 3.D 4.B 5.D 6.B二、填空題1.真值 2.原子命題 3.真 4.假第二章命題邏輯的推理理論一、填空題1. 2.二、計(jì)算題1．解：(主析取范式)2．解：(主合取范式)3.解：的真值表為：故其主析取范式為：4.解：的真值表為：故其主合取范式為：5.解：的真值表為：所以，其主析取范式為：6.解：的真值表為：所以，其主合取范式為：三、證明題1.設(shè)A:甲獲勝,B:乙獲勝,C:丙獲勝,D:丁獲勝則命題化為論證:A→┐B,C→B,┐A→DC→D證明:(1)A→┐BP(2)B→┐AT(1),E(3)┐A→DP(4)B→DT(2)(3),I(5)C→BP(6)C→DT(4)(5),I2.設(shè)P:2是偶數(shù),Q:2整除7,R:5是質(zhì)數(shù)則命題化為論證:P→┐Q,┐R∨Q,R┐P證明:(1)RP(2)┐R∨QP(3)QT(1)(2),I(4)P→┐QP(5)┐PT(3)(4),I3.設(shè)P：廠方拒絕增加工資；Q：罷工停止；R罷工超壺過(guò)一年；S：撤換廠長(zhǎng)則命題化為論證: 證明：① P② P③ T①②I④ P⑤ T④I⑥ T⑤E⑦ T③⑥I第三章謂詞邏輯一、選擇題1.D 2.A 3.D 4.A 5.A 6.B二、填空題1.存在量詞 2.1 3.0 4.1 5.0 6.1三、證明題1.證明:(1)A(x)P(附加前提) (2)A(a)US(1)(3)(A(x)→B(x))P (4)A(a)→B(a)US(3)(5)B(a)T(2)(4),I(6)B(x)UG(5) (7)A(x)→B(x)CP2.證明:(1)(┐A(x)→B(x))P(2)┐A(a)→B(a)US(1) (3)┐B(x)P(4)┐B(a)US(3)(5)A(a)T(2)(4),I(6)A(x)EG(5)3.設(shè)P(x)：x是個(gè)舞蹈者；Q(x)：x很有風(fēng)度；S(x)：x是個(gè)學(xué)生；a：王華上述句子符號(hào)化為：前提：、結(jié)論：證明：① P② P③ US②④ T①I⑤ T③④I⑥ T①I⑦ T⑤⑥I⑧ EG⑦ 第四章集合一、選擇題1.D 2.B 3.A 4.B 5.C 6.C二、填空題1.{{1}} 2. 3.{1} 4. 5. 6. 三、計(jì)算題1.解:由于，故。2.解：， ， 四、證明題1.證明：若，則，所以，；若，則對(duì)任意的,有,所以,又因?yàn)?所以,所以,因此.同理可得,，從而.2.證:任意<x,y>∈(A∩B)×(C∩D)x∈(A∩B)∧y∈(C∩D) x∈A∧x∈B∧y∈C∧y∈D(x∈A∧y∈C)∧(x∈B∧y∈D)<x,y>∈(A×C)∧<x,y>∈(B×D) <x,y>∈(A×C)∩(B×D)所以(A∩B)×(C∩D)=(A×C)∩(B×D).第五章關(guān)系與函數(shù)一、選擇題1.C 2.B 3.B 4.D 5.B 6.D 7.D 8.D 9.A10.D 11.C 12.C二、填空題1.8 2.9 3.24 4.29 5.29 6.26 7.8.R是自反的、對(duì)稱的和傳遞的 9.以主對(duì)角線為對(duì)稱的元素不能同時(shí)為110.對(duì)稱矩陣 11.主對(duì)角線上的所有元素都為1 12.主對(duì)角線上的所有元素都為0三、計(jì)算題1.解： (1)= (2) (3)，所以2.解：（1）RR={(1,1)，(1,3)，(2,2)，(2,4)} （2）R-1=｛(2,1)，(1,2)，(3,2)，(4,3)｝ 3.解：A×B={<1,0>,<1,1>,<2,0>,<2,1>}（1）所有A到B的關(guān)系為的每一個(gè)元素,分別為：，{<1,0>},{<1,1>},{<2,0>},{<2,1>}，{<1,0>,<1,1>},{<1,0>,<2,0>},{<1,0>,<2,1>},{<1,1>,<2,0>},{<1,1>,<2,1>},{<2,0>,<2,1>}，{<1,0>,<1,1>,<2,0>},{<1,0>,<1,1>,<2,1>},{<1,0>,<2,0>,<2,1>},{<1,1>,<2,0>,<2,1>}，{<1,0>,<1,1>,<2,0>,<2,1>}；（2）所有A到B的函數(shù)為{<1,0>,<2,0>},{<1,0>,<2,1>}，{<1,1>,<2,0>},{<1,1>,<2,1>}；（3）所有A到B的雙射為{<1,0>,<2,1>},{<1,1>,<2,0>}。4.解：＝{<1,a,2>,<1,a,3>,<1,b,2>,<1,b,3>}(2分)={}{<a,a,1>,<a,b,1>,<b,a,1>,<b,b,1>}。(3分)5.解：R1={1,2}×{1,2}={(1,1),(1,2),(2,1),(2,)}R2={3}×{3}={(3,3)}R3={4,5}×{4,5}={(4,4),(4,5),(5,4),(5,5)}R=R1R2R3={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4),(4,5),(5,4),(5,5)}關(guān)系圖為：6.解：R1={1}×{1}={(1,1)} R2={2，3}×{2，3}={(2,2),(2,3),(3,2),(3,3)} R3={4,5}×{4,5}={(4,4),(4,5),(5,4),(5,5)}所以，所求的等價(jià)關(guān)系為： R=R1R2R3={(1,1),(2,2),(2,3),(3,2),(3,3),(4,4)(4,5),(5,4),(5,5)}7.解：A上的每一個(gè)劃分對(duì)應(yīng)A上的一個(gè)等價(jià)關(guān)系,所以只要找出A上的所有的劃分即可.A上的劃分有:{1}∪{2}和{1,2}， 所以A上的所有等價(jià)關(guān)系有：； 8.解：自反閉包對(duì)稱閉包傳遞閉包9.解：自反閉包對(duì)稱閉包 傳遞閉包10.解：自反閉包 對(duì)稱閉包 傳遞閉包第六章代數(shù)系統(tǒng)的一般概念一、選擇題1.D 2.C 3.D 4.C 5.D 6.D 7.B 8.B 9.C10.D 11.A 12.D二、填空題1.({e},*) 2.a 3.ab 4.2個(gè) 5.1個(gè) 6.循環(huán)群7.3 8.3 9.3 10.20 11.8 12.1213.[9] 14.[3] 15.[2] 16.[4] 17.[2] 18.[5] 三、計(jì)算題1.解：[0]是單位元，其階數(shù)為1；[1]2=[2]，[1]3=[3]，[1]4=[4]，[1]5=[5]，[1]6=[0]，所以[1]的階數(shù)為6；[2]2=[4]，[2]3=[0]，所以[2]的階數(shù)為3；[3]2=[0]，所以[3]的階數(shù)為2；[4]2=[2]，[4]3=[0]，所以[4]的階數(shù)為3；[5]2=[4]，[5]3=[3]，[5]4=[2]，[5]5=[1]，[5]6=[0]，所以[5]的階數(shù)為6；由上可知，該群是循環(huán)群，[1]，[5]都是其生成元。2.解：是單位元，其階數(shù)為1； ，故的階數(shù)為4； ，故的階數(shù)為2；，故的階數(shù)為4。由上可知，該群是循環(huán)群，都是其生成元。3.解：因?yàn)閨A|=2，所以A上共有22=4個(gè)不同函數(shù)。令，其中：為AA中的幺元，和有逆元。4.解：任意<a,b>∈Q×Q，設(shè)<a,b>*<x,y>=<a,b>，即<ax,ay+b>=<a,b>,得ax=a,且ay+b=b,解得:x=1,y=0. 因?yàn)閷?duì)任意<a,b>∈Q×Q,有<1,0>∈Q×Q,使得<a,b>*<1,0>=<a,b>和<1,0>*<a,b>=<a,b>所以,<1,0>是單位元。 任意<a,b>∈Q×Q,設(shè)<a,b>*<x,y>=<x,y>,即<ax,ay+b>=<x,y>,得ax=x,且ay+b=y,此方程并非對(duì)所有得有理數(shù)a,b都有解,因此,無(wú)零元.5.解：(1)*不滿足交換律、結(jié)合律，但滿足冪等律.(2)a是關(guān)于*的單位元,無(wú)零元a為可逆元，其逆元為a,b和c都不可逆。6.解：(1)*滿足交換律、結(jié)合律，但不滿足冪等律.(2)a是關(guān)于*的單位元，c是關(guān)于*的零元，a為可逆元，其逆元為a,b為可逆元，其逆元為b，c不可逆。四、證明題1.證明：對(duì)于中任意元素，由條件知道，因此存在逆元，此逆元是其自身，因此是一個(gè)群。 對(duì)于中任意元素和，設(shè)，有，因是群，所以，由于每一元素以其自身為逆元，于是即，是可交換的，所以是一個(gè)阿貝爾群。2.證：反證法：反設(shè)<A，+，·>是整環(huán)， 因?yàn)閷?duì)任意都有a·a=a，且|A|≥3，所以且。即有且，這與整環(huán)中無(wú)零因子矛盾。 所以<A，+，·>不可能是整環(huán)。3.證：對(duì)于任意的,均有它的逆元,使得 由于互為逆元的兩個(gè)不相等的元素是成對(duì)出現(xiàn)的，而且集合A中元素的個(gè)數(shù)為偶數(shù)，群中有唯一的幺元，因此，至少有一個(gè)元素是以自身為逆元的。 即必存在，使得4.證明：因?yàn)閍-1*b∈G，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以對(duì)于a,b∈G，必有x∈G，使得ax=b。 若x1,x2都滿足要求。即ax1=b且ax2=b。故ax1=ax2