離散數(shù)學(xué)練習(xí)題及答案

一、填空題1、集合的表示方法有兩種：法和法。請把“奇整數(shù)集合”表示出來{}。1、列舉；描述；2、無向連通圖G含有歐拉回路的充分必要條件是不含有奇數(shù)度結(jié)點.2*、連通有向圖D含有歐拉回路的充分必要條件是D中每個結(jié)點的入度＝出度.3、設(shè)R是集合A上的等價關(guān)系，則R所具有的關(guān)系的三個特性是、自反性、對稱性、傳遞性.4、有限圖G是樹的一個等價定義是：連通無回路（或任一等價定義）.5、設(shè)N(x)：x是自然數(shù)，Z(y)；y是整數(shù)，則命題“自然數(shù)都是整數(shù)，而有的整數(shù)不是自然數(shù)”符號化為x(N(x)Z(x))x(Z(x)N(x))6、在有向圖的鄰接矩陣中，第i行元素之和,第j列元素之和分別為、結(jié)點vi的出度和結(jié)點vj的入度．7、設(shè)A，B為任意命題公式，C為重言式，若，那么命題是重言式的真值是1．8、命題公式的主析取范式為PQ．設(shè)圖G＝<V，E>和G＝<V,E>,若，則G是G的真子圖，若V=V,EE，則G是G的生成子圖.10、在平面圖中,則＝2E,其中ri(i=1,2,…,r)是G的面．11、設(shè)，則從A到B的所有映射是11、1={（a，1），（b，1）}；2={（a，2），（b，2）}；3={（a，1），（b，2）}；4={（a，2），（b，1）}12、表達(dá)式xyL（x，y）中謂詞的定義域是{a，b，c}，將其中的量詞消除，寫成與之等價的命題公式為12、（L（a，a）L（a，b）L（a，c））（L（b，a）L（b，b）L（b，c））（L（c，a）L（c，b）L（c，c））12*、設(shè)個體域D＝{a,b},公式消去量詞化為(G(a)(H(a,a)H(a,b)))(G(b)(H(b,a)H(b,b)))13、含有三個命題變項P，Q，R的命題公式PQ的主析取范式是14、設(shè)R，S都是集合A上的等價關(guān)系，則對稱閉包s(RS)=RS15、設(shè)G是連通平面圖，v,e,r分別表示G的結(jié)點數(shù)，邊數(shù)和面數(shù)，則v,e和r滿足的關(guān)系式是16、設(shè)G是n個結(jié)點的簡單圖，若G中每對結(jié)點的度數(shù)之和≥n，則G一定是哈密頓圖.17、一個有向樹T稱為根樹，若，其中，稱為樹根，稱為樹葉.若有向圖T恰有一個結(jié)點的入度為0，其余結(jié)點入度為1；入度為0的結(jié)點；出度為0的結(jié)點.18、圖的通路中邊的數(shù)目稱為.結(jié)點不重復(fù)的通路是通路.邊不重復(fù)的通路是通路.通路長度；初級；簡單.19、設(shè)A和B為有限集，|A|=m，|B|=n，則有個從A到B的關(guān)系，有個從A到B的函數(shù)，其中當(dāng)m￡n時有個入射，當(dāng)m=n時，有個雙射。19、20、集合（是/不是）可數(shù)的。是21、設(shè)上的整除關(guān)系在上定義兩個二元運算和：對任意，，。請?zhí)羁眨ㄔ跈M線上填是或不是）：=1\*GB3①是=2\*GB3②是=3\*GB3③是=4\*GB3④不是=1\*GB3①代數(shù)系統(tǒng)格。=2\*GB3②代數(shù)系統(tǒng)有界格。=3\*GB3③代數(shù)系統(tǒng)有補格。=4\*GB3④代數(shù)系統(tǒng)分配格。二、單項選擇題（選擇一個正確答案的代號，填入括號中）1、設(shè)命題公式G=（PQ），H=P（QP），則G與H的關(guān)系是（A）。A．GHB．HGC．G=HD．以上都不是2、下列命題公式等值的是(C)3、設(shè)V＝{a,b,c,d},與V能構(gòu)成強連通圖的邊集E＝(A) (A){<a,b>,<a,c>,<d,a>,<b,d>,<c,d>}(B){<a,d>,<b,a>,<b,c>,<b,d>,<d,c>}(C){<a,c>,<b,a>,<b,c>,<d,a>,<d,c>}(D){<a,d>,<b,a>,<b,d>,<c,d>,<d,c>}4、設(shè)L(x)：x是演員，J(x)：x是老師，A(x,y)：x佩服y.那么命題“所有演員都佩服某些老師”符號化為(B) (A)(B) (C)(D)5、在由3個元素組成的集合上，可以有(D)種不同的關(guān)系。 (A)3 (B)8 (C)9(D)5126、設(shè)S1=,S2={},S3=P({}),S4=P()則命題為假的是(A)． (A)(B)(C)(D)7、設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r=(A)．(A)e－v＋2(B)v＋e－2(C)e－v－2(D)e＋v＋28、下列命題正確的是（A）。A．{}=B．{}=C．{a}{a，b，c}D．{a，b，c}9、設(shè)A,B,C都是集合，如果AC＝BC，則有(C) (A)A＝B(B)AB(C)當(dāng)A－C＝B－C時,有A=B(D)當(dāng)C=U時,有AB10、設(shè)是布爾代數(shù)，，則下式不成立的是(D)11、下面給出的一階邏輯等價式中，（A）是錯的。x（A（x）B（x））=xA（x）xB（x）AxB（x）=x（AB（x））x（A（x）B（x））=xA（x）xB（x）xA（x）=x（A（x））三、多重選擇題(每道小題都可能有一個以上的正確選項，須選出所有的正確選項，不答不得分，多選、少選或選錯都將按比例扣分。)命題公式 (P∧(P→Q))→Q是_____式。(1)重言(2)矛盾(3)可滿足(4)非永真的可滿足2、給定解釋I=(D,)=(整數(shù)集，{f(x,y):f(x,y)=x-y；g(x,y):g(x,y)=x+y；P(x,y):x<y})，下列公式中_____在解釋I下為真。(1)P(f(x,y),g(x,y))(2)xyP(f(x,y),g(x,y))(3)xy(P(x,y)→P(f(x,y),x))(4)xyP(f(x,y),g(x,y))3、Ａ是集合，=10，則=_____。(1)100(2)99(3)2048(4)1024(5)5124、集合Ａ={x|x是整數(shù)，<30}，Ｂ={x|x是質(zhì)數(shù)，x<20}，C={1,3,5}，則①=_____;②=_____;③=_____;④=_____。(1){1,2,3,5}(2)(3){0} (4){1,3,5,7,11,13,17,19}(5){1,3,5,7}(6){7,11,13,17,19}5、設(shè)A、B、C是集合，下列四個命題中，_____在任何情況下都是正確的。若AB且B∈C，則A∈C(2)若AB且B∈C，則AC若A∈B且BC，則AC(4)若A∈B且BC，則A∈C6、設(shè)集合Ａ={a,b,c,d,e,f,g}，Ａ的一個劃分={{a,b},{c,d,e},{f,g}}，則所對應(yīng)的等價關(guān)系有_____個二元組。(1)14(2)15(3)16(4)17(5)8(6)49(7)5127、S={1,2,3,4,5,6,7,8,9,10,11,12}，≤是S上的整除關(guān)系。S的子集Ｂ＝{2,4,6｝，則在<S，≤>中，Ｂ的最大元是_____；Ｂ的最小元是_____；Ｂ的上確界是_____；Ｂ的下確界是_____。(1)不存在的(2)36(3)24(4)12(5)6(6)1(7)28、設(shè)有有限布爾代數(shù)(B,+,*,’,0,1)，則=_____能成立。(1)1(2)2(3)3(4)4(5)5(6)8(7)99、G={0,1,2,…,n}，n∈N，定義為模n加法，即xy=(x+y)modn，則代數(shù)系統(tǒng)(G，)_____。(1)是半群但不是群(2)是無限群(3)是循環(huán)群(4)是變換群(5)是交換群10、僅有一個結(jié)點的圖稱為()，當(dāng)然也是() (1)零圖(2)平凡圖(3)補圖(4)子圖1.1、3。2.4。3.4。4.1；4；2；2。5.4。6.4。7.1；7；4；7。8.2、4、6。 9.3、5。10.2；1。四、化簡解答題第1題圖1、(1)設(shè)圖G(如第1題圖)，作圖G的嵌入圖，說明圖G是平面圖.第12題答案圖圖G的嵌入圖，如第12題答案圖.故圖G為平面圖(4分)(2)在具有n個頂點的完全圖Kn中刪去多少條邊才能得到樹？解：n個頂點的完全圖Kn中共有條邊，n個頂點的樹應(yīng)有條邊，于是，刪去的邊有：。2、判別謂詞公式的類型.2、設(shè)I為任意一個解釋，D為I的個體域.若在解釋I下，該公式的前件為0，無論如何取值，為1； 若在解釋I下，該公式的前件為1，則使得為1，它蘊含著為1為1，由y的任意性，必有為1，于是為1.所以，是永真式．3、化簡集合表達(dá)式：((ABC)(AC))－((C(C－B)－A)3、((ABC)(AC))－((C(C－B)～A)＝(AC)－（C～A）(兩次用吸收律)=((AC)(～CA)=(A～C)(C～C)A(AC)=(A～C)A=A4、判斷下列哪些運算結(jié)果是對的？哪些是錯的？請將錯誤的運算結(jié)果更正過來．(1)(2)(3)(4)（5） （6） （7） （8）4、(1)對．(2)錯．應(yīng)為．(3)對．(4)錯．應(yīng)為{}（5）錯．應(yīng)為 （6）錯．應(yīng)為(或或A－AB) （7）錯．應(yīng)為，即（8）對．5、將命題公式化為只含和的盡可能簡單的等值式．5、（優(yōu)先級有誤）不惟一.v1v1e1 e5v2e6 v5e7 e4e2 e8v3 v4e3v3e3v4第12題圖6、設(shè)圖G如右圖.已知通路(1)v1e5v5e7v2e2v3(2)v5e6v2e2v3e3v4e8v2e7v5(3)v2e7v5e6v2(4)v1e1v2e2v3e3v4e8v2e6v5試回答它們各是簡單通路、簡單回路、初級通路還是初級回路?6、(1)初級通路；(2)簡單回路；(3)初級回路；(4)簡單通路.7、試問n取何值時，無向完全圖Kn，存在一條歐拉回路？7、由于Kn有n個結(jié)點，并且每個結(jié)點的度數(shù)均為n－1，于是，當(dāng)n為奇數(shù)時，Kn的每個結(jié)點的度數(shù)都是偶數(shù)，所以存在一條歐拉回路．8、已知(L，*，)是格，且二元運算*和滿足分配律，a,b,cL，化簡表達(dá)式 ((a*b)(a*c))*((a*b)(b*c))解答：((a*b)(a*c))*((a*b)(b*c))＝(a*b)((a*c)*(b*c))(分配律)=(a*b)((a*b)*c)(冪等律)=a*b(吸收律)9、化簡。9、====R10、試將一階邏輯公式化成前束范式。解：11、指出有向圖D(如下圖)中各圖是強連通，單側(cè)連通還是弱連通？(1)(2)(3)(4)(5)(1)(2)(3)(4)(5)aabced12、找出無向圖G（如右圖所示）中的一個點割集，三條邊和四條邊的邊割集各一個．11、強連通圖為：圖(1),(4),(5)；單側(cè)連通圖為：如圖(1),(2),(4),(5)；弱連通圖為：圖(1)～(5).3.點割集：{a,c,d}(不惟一)三條邊的邊割集：{(b,c),(c,e),(c,d)}(不惟一)四條邊的邊割集：{(a,b),(a,d),(d,e),(c,e)}(不惟一)13、答案圖如下圖的虛線圖.13、求圖13圖G的對偶圖.14、給定三個圖如下圖所示，試判斷它們是否為歐拉圖、哈密頓圖、或平面圖？并說明理由．a(chǎn)bcdefg圖G1圖G2圖G3圖6－7圖6－714、圖G1是歐拉圖，因為每個結(jié)點度數(shù)均為偶數(shù)． 圖G2是哈密頓圖，存在哈密頓回路，如cdgfebac．(不惟一) 圖G3是平面圖．可以改畫成可平面圖，如圖．五、計算題1、設(shè)R和S是集合上的關(guān)系，其中，試求：（1）寫出R和S的關(guān)系矩陣；（2）計算。1、解：（1）（2）={<1，3>，<2，4>}={<1，1>，<1，2>，<1，3>，<2，3>，<2，4>，<3，4>，<4，4>}={<1，1>，<3，1>，<3，2>，<4，3>}={<3，1>，<4，2>}設(shè)A={a，b，c，d}，R1，R2是A上的關(guān)系，其中R1={（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，d）}，R2={（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）}。畫出R1和R2的關(guān)系圖；判斷它們是否為等價關(guān)系，是等價關(guān)系的求A中各元素的等價類。2、解：R1和R2的關(guān)系圖如下：（略）由關(guān)系圖可知，R1是等價關(guān)系。R1不同的等價類有兩個，即{a，b}和{c，d}。由于R2不是自反的，所以R2不是等價關(guān)系。3、設(shè)集合A＝{1,2,3,4,6,8,12}，R是A上的整除關(guān)系，畫出偏序集(A,R)的哈斯圖；寫出A的子集{2,4,6,8}的上界，下界，最小上界，最大下界；(3)寫出集合A的最大元，最小元，極大元，極小元。集合A＝{1,2,3,4,6,8,12}(1)半序集(A,R)的哈斯圖112483612(2)子集{2,4,6,8}無上界，下界是1,2，無最小上界，最大下界是2.(3)A無最大元，最小元是1，極大元是8,12，極小元是1。4、用迪克斯特拉算法求下面有限權(quán)圖中從A到B的最短路，要求用圖示給出求解過程，并計算它們的權(quán)值。AAB142241631892(本題12分)求有限權(quán)圖的最短路ABAB1AB12ABAB122AB1422ABAB14221AB142212A到B的最短路的權(quán)值為6.145892106735、已知帶權(quán)小生成樹，并計算該生成樹的權(quán)．6、設(shè)簡單連通無向圖G有12條邊，G中有1度結(jié)點2個，2度結(jié)點2個，4度結(jié)點3個，其余結(jié)點度數(shù)不超過3．求G中至少有多少個結(jié)點．試作一個滿足該條件的簡單無向圖．圖55、做法如下：=1\*GB3①選邊1；=2\*GB3②選邊2；10673458921=3\*GB3③選邊3；=4\*GB3④選邊5；10673458921⑤選邊7最小生成樹為{1,2,3,5,7}．如圖4中粗線所示．權(quán)數(shù)為18．圖46、設(shè)圖G有x個結(jié)點，有握手定理 21+22+34＋3（x223）122x9圖G至少有9個結(jié)點．滿足條件的圖如圖所示．7、求命題公式的主合取范式.7、7*、求┐(P→Q)(P→┐Q)的主合取范式并給出所有使命題為真的賦值。解答：原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))(┐(P∧┐Q)∨(P∧┐Q))(P∧Q)∨(P∧┐Q)P∧(Q∨┐Q)P∨(Q∧┐Q)(P∨Q)∧(P∨┐Q)命題為真的賦值是P=1,Q=0和P=1,Q=18、求格的表達(dá)式的對偶式，并計算當(dāng)a,b,c的真值分別為0,1,1時對偶式的真值．8、的對偶式為對偶式的真值為9、設(shè)．9、,,－1＝10、重新排列1，2，3，4，5，6，7，8，9使得有4個數(shù)在原來位置上，其它5個數(shù)不在原來位置上，有多少種排法？解答：這是有4個數(shù)不動，5個數(shù)的錯位排列問題。4個數(shù)沒有預(yù)先指定，故有種可能。5個數(shù)的錯位排列，為所求為11、試畫所有不同構(gòu)的四階無向樹(四個結(jié)點)．12.求從1到500的整數(shù)中，能被3或5除盡的數(shù)的個數(shù)。12.解：設(shè)A為從1到500的整數(shù)中，能被3除盡的數(shù)的集合。B為從1到500的整數(shù)中，能被5除盡的數(shù)的集合。則|A|=[500/3]=166（[x]表示不超過x的最大整數(shù)）|B|=[500/5]=100|A∩B|=[500/（3*5）]=33……（1分）由包含排斥原理：|A∪B|=|A|+|B|-|A∩B|=166+100-33=233即從1到500的整數(shù)中，能被3或5除盡的數(shù)有233個?！?分）13、畫圖。對于下圖，利用克魯斯克爾算法求一棵最小生成樹。13、最小生成樹為14、求帶權(quán)2、3、5、7、11、13的最優(yōu)二叉樹。14、解23571113所求最優(yōu)二叉樹為55711131071113171113172441六、證明題1、試構(gòu)造推理證明.1..①RS[前提引入]=2\*GB3②S[前提引入]③R[①，②析取三段論]④(PQ)R[前提引入]⑤(PQ)[③,④拒取式]⑥[⑤置換]2、證明命題公式與有相同的主析取范式．2、方法1．因為兩命題公式等值，由主合取范式的惟一性，可知兩命題公式的主合取范式是相同．方法2． 因為它們的主合取范式相同，可知它們的主析取范式也相同．3、設(shè)G為9個結(jié)點的無向圖，每個結(jié)點的度數(shù)不是5就是6，試證明G中至少有5個度數(shù)為6的結(jié)點，或者至少有6個度數(shù)為5的結(jié)點。證明：由握手定理的推論，G中度數(shù)為5的結(jié)點個數(shù)只能是0,2,4,6,8五種情況；此時，相應(yīng)的結(jié)點度數(shù)為6的結(jié)點個數(shù)分別為9，7，5，3，1個，以上五種對應(yīng)情況(0,9),(2,7),(4,5),(6,3),(8,1)，每對情況，兩數(shù)之和為9，且滿足第2個數(shù)大于或等于5，或者第1個數(shù)大于或等于6，意即滿足至少有度數(shù)為6的結(jié)點5個，或者至少有度數(shù)為5的結(jié)點6個。4、試證明（A~B）（~AB）=（AB）（~A~B）證明：5、設(shè)，其中Q是有理數(shù)集，證明(Q.，+，×)是域，＋和×分別是數(shù)的加法和乘法.證明且惟一，故運算＋是Q()上的二元運算，加法滿足結(jié)合律、交換律..Q()的0元是0＋0.,即存在逆元.所以(Q(),＋)是交換群.且惟一，故×是Q()上的二元運算.容易驗證×在Q()上滿足交換律、結(jié)合律.Q()的單位元是1＋0.任給非0元(a,b至少一個不為0)，運算×在Q()上非0元存在逆元.所以(Q()－{0}，×)是交換群.可以驗證，運算＋對×滿足分配律.所以(Q()，＋，×)是域.6、設(shè)G是圖，無回路，但若外加任意一條邊于G后，就形成一回路.試證明G必為樹.證明由樹的定義可知，只需證G連通即可.任取不相鄰兩點u,v,由題設(shè)，加上邊<u,v>就形成一回路，于是去掉邊<u,v>,從u到v仍有路u,…,v，即u,v連通，由u,v的任意性可知，G是連通的，故G必是樹.7、設(shè)G是平面圖，并且G的所有面的次數(shù)均為3，證明其中e是G的邊數(shù).v是G的結(jié)點數(shù).7、因為G的所有面的次數(shù)為3，因此對G的任意面r，有 deg(r)=3從而，又根據(jù)定理6，G的所有面的次數(shù)之和等于其邊數(shù)的2倍，即即代入歐拉公式，8、設(shè)G是連通簡單平面圖，則G至少有一個度數(shù)不超過5的結(jié)點．（提示：用反證法）8、因為G是連通簡單平面圖，它的每個面至少有3條邊，所以有，即（其中r，e分別為圖G的面數(shù)和邊數(shù)） 假設(shè)結(jié)論不成立，則每個結(jié)點的度數(shù)都大于等于6．則有，即有（其中v是圖G的結(jié)點數(shù)）由歐拉公式：2==0矛盾．所以G中至少有一個結(jié)點的度數(shù)小于或等于5．9、證明：偶數(shù)階群中階為2的元素的個數(shù)一定是奇數(shù)。證：由群的元素的階的有關(guān)知識，任一個群中階為1的就只有單位元一個，階大于2的元素是成雙成對出現(xiàn)的，其余的元素就是階為2的元素。故階大于2的元素有偶數(shù)個。由于這是一個偶數(shù)階群，而奇數(shù)加上一個偶數(shù)還是奇數(shù)，一個偶數(shù)減去一個奇數(shù)仍是奇數(shù)，故階為2的元素一定是奇數(shù)。我們用綜合法得出了整個推理過程。10、設(shè)群<G,*>除單位元外每個元素的階均為2，則<G,*>是交換群。10、設(shè)<G，*>為一群。證明：若對任意a?G有a2=e，e為幺元，則G為阿貝爾群。證明：對任一aG，由已知可得a*a=e，即a-1=a。對任意a,bG，因為a*b=(a*b)-1=b-1*a-1=b*a，所以運算*滿足交換律。從而＜G,*＞是交換群。10*、設(shè)<G，*>為一群。證明：若對任意a，b?G有(a*b)2=a2*b2，則G為阿貝爾群。10*、證：對任意a,b?G，(a*b)2=(a*b)*(a*b)=a*(b*a)*b又由題設(shè)(a*b)2=a2*b2=(a*a)*(b*b)=a*(a*b)*b……（2分）從而a*(b*a)*b=a*(a*b)*b。兩邊同時左乘a-1，右乘b-1得：a*b=b*a……（3分）因此，*運算滿足交換律，故<G,*>為阿貝爾群。11、在一個群<G,*>中，若A和B都是G的子群。若AB=G，則A=G或B=G。證明：用反證法證明。若AG且BG，則有aA,aB且bB,bA。因為A，B都是G的子群，故a,bG，從而a*bG。因為aA,所以aA。若a*bA,則b=a*(a*b)A，這與aB矛盾。從而a*bA。同理可證a*bB。綜合可得a*bAB=G，這與已知矛盾。從而假設(shè)錯誤，得證A=G或B=G。12、任一有限半群一定在等冪元。證明：設(shè)<S,*>是一個有限半群。任取aS，由于*滿足結(jié)合律，我們有{a,a,a,…,a,…}S因為S是有限集合，故a,a,a,…,a,…不可能兩兩不同。從而一定存在正整數(shù)k,m,1k<m使得a=a令p=m-k，則由于*滿足結(jié)合律，a=a=a*a。對任意正整數(shù)qk，有a=a*a=（a*a）*a=a*a（#）若p=q，則元素a就是一個等冪元。否則因為p1，故存在正整數(shù)n滿足npk。故利用（#）可得a=a*a=a*(a*a)=a*a=a*(a*a)=a*a=……=a*a故a就是S的一個等冪元。13、設(shè)是有限字母表，給定代數(shù)系統(tǒng)，其中是串的連接運算。對于任一串，建立到的映射，。證明是到的一個滿同態(tài)，且當(dāng)時，是同構(gòu)映射。13、證明對于中任意兩字符串和，因為，所以，對于任一正整數(shù)，取，則，所以，，是到的一個滿同態(tài)。當(dāng)時，設(shè)，，，是雙射，因此，是一個同構(gòu)映射。14、設(shè)R，S為A上的兩個等價關(guān)系，且RíS。定義A/R上的關(guān)系R/S：<[x],[y]>?R/S當(dāng)且僅當(dāng)<x，y>?S證明：R/S為A/R上的等價關(guān)系。14、證明：S為A上的等價關(guān)系，那么對任意x有<x,x>?S，所以<[x],[x]>?R/S，R/S是自反的；……（2分）若<[x],[y]>?R/S，則<x,y>?S，由S對稱知<y,x>?S，所以<[y],[x]>?R/S，R/S是對稱的；……（3分）若<[x],[y]>?R/S，<[y],[z]>?R/S，則<x,y>?S，<y,z>?S，由S傳遞知<x,z>?S，所以<[