離散數(shù)學試卷及答案

離散數(shù)學試卷及答案一、單項選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。1.一個連通的無向圖G,如果它的所有結(jié)點的度數(shù)都是偶數(shù),那么它具有一條()A.漢密爾頓回路B.歐拉回路C.漢密爾頓通路D.初級回路2■設(shè)G是連通簡單平面圖，G中有11個頂點5個面，則G中的邊是()A.10B.12C.16D.143.在布爾代數(shù)L中，表達式(aAb)V(aAbAc)V(bAc)的等價式是()A.bA(aVc)(aAb)V(a'Ab)(aVb)A(aVbVc)A(bVc)D.(bVc)A(aVc)4.設(shè)i是虛數(shù)，?是復(fù)數(shù)乘法運算，則G二是群，下列是G的子群是()A.B.〈{-1},?〉C.〈{i},?〉D.〈{—i},?〉5?設(shè)Z為整數(shù)集，A為集合，A的幕集為P(A),+、-、/為數(shù)的加、減、除運算，。為集合的交運算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有()〈Z,+,/〉B.〈Z,/〉C.〈Z,—,/〉D.〈P(A),G〉6.下列各代數(shù)系統(tǒng)中不含有零元素的是()A.〈Q,某〉Q是全體有理數(shù)集，某是數(shù)的乘法運算〈Mn（R）,某〉，Mn（R）是全體n階實矩陣集合，某是矩陣乘法運算C.〈Z,Z是整數(shù)集，定義為某某y二某y,某,yWZD.〈Z,+〉，Z是整數(shù)集，+是數(shù)的加法運算設(shè)A二｛1,2,3｝,A上二元關(guān)系R的關(guān)系圖如下：R具有的性質(zhì)是A.自反性B.對稱性C.傳遞性D.反自反性設(shè)A=｛a,b,c｝，A上二元關(guān)系R=｛〈a,a〉，〈b,b〉〈，a,c〉｝，則關(guān)系R的對稱閉包S（R）是（）A.RUIAB.RC.RU｛〈c,a〉｝D.RriIA9.設(shè)某=｛a,b,c｝,I某是某上恒等關(guān)系，要使I某U｛〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉｝UR為某上的等價關(guān)系，R應(yīng)取（）A.｛〈c,a〉，〈a,c〉｝B.｛〈c,b〉，〈b,a〉｝C.｛〈c,a〉，〈b,a〉｝D.｛〈a,c〉，〈c,b〉｝10.下列式子正確的是（）A.WB.C.｛｝D.｛｝W11.設(shè)解釋R如下：論域D為實數(shù)集，a=0,f（某,y）二某-y,A（某,y）:某A.（某）（y）（z）（A（某,y））—A（f（某,z）,f（y,z））B.（某）A（f（a,某），a）（某）（y）（A（f（某,y）,某））（某）（y）（A（某,y）-A（f（某,a）,a））設(shè)B是不含變元某的公式，謂詞公式（某）（A（某）一B）等價于（）A.（某）A（某）一BB.（某）A（某）一BC.A（某）一BD.（某）A（某）一（某）B謂詞公式（某）（P（某,y））f（z）Q（某,z）人（y）R（某,y）中變元某（）A.是自由變元但不是約束變元B.既不是自由變元又不是約束變元C.既是自由變元又是約束變元D.是約束變元但不是自由變元若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號化為()A.PVQB.PA「QC.Pf「QD.PV「Q15.以下命題公式中，為永假式的是()A.pf(pVqVr)B.(pf「p)f「pC.n(q^q)ApD.n(qVqp)^(pAnP)二、填空題(每空1分，共20分)16.在一棵根樹中，僅有一個結(jié)點的入度為，稱為樹根，其余結(jié)點的入度均為°17.A二｛1,2,3,4｝上二元關(guān)系R=｛〈2,4〉，〈3,3〉，〈4，2〉｝，R的關(guān)系矩陣MR中m24=,m34=。18.設(shè)〈，某〉是群，則那么中除外，不可能有別的冪等元；若〈,某〉有零元，則||=?！?9.設(shè)A為集合，P(A)為A的幕集，貝U〈P(A),是格，若某,yWP(A)，則某,y最大下界是，最小上界是。設(shè)函數(shù)f:某一Y,如果對某中的任意兩個不同的某1和某2，它們的象y1和y2也不同，我們說f是函數(shù)，如果ranf=Y，則稱f是函數(shù)。設(shè)R為非空集合A上的等價關(guān)系，其等價類記為〔某〕R。某,yWA，若〈某,y〉wR，貝「某〕R與〔y〕R的關(guān)系是，而若〈某,y〉R，貝I」〔某〕RQ〔y〕R=。22.使公式(某)(y)(A(某)AB(y))(某)A(某)A(y)B(y)成立的條件是不含有y，不含有某。23.設(shè)M(某)：某是人，D():某是要死的，則命題“所有的人都是要死的”可符號化為(某),其中量詞(某)的轄域是。24.若H1AH2人…AHn是，則稱Hl,H2,???Hn是相容的，若HlAH2A-AHn是，則稱Hl,H2,???Hn是不相容的。判斷一個語句是否為命題，首先要看它是否為，然后再看它是否具有唯一的三、計算題（共30分）（4分）設(shè)有向圖G=（V,E）如下圖所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路總數(shù)。⑸設(shè)A二{a,b},P（A）是A的幕集，是對稱差運算，可以驗證是群。設(shè)n是正整數(shù)，求（{a}T{a}）n{a}-nn{a}n28.（6分）設(shè)A={1,2,3,4,5},A上偏序關(guān)系R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}UIA;2（1）作出偏序關(guān)系R的哈斯圖（2）令B二{1,2,3,5}，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。29.（6分）求「（PfQ）（Pf「Q）的主合取范式并給出所有使命題為真的賦值。（5分）設(shè)帶權(quán)無向圖G如下，求G的最小生成樹T及T的權(quán)總和要求寫出解的過程。（4分）求公式「（（某）F（某,y）-（y）G（某,y））V（某）H（某）的前束范式。四、證明題（共20分）（6分）設(shè)T是非平凡的無向樹，T中度數(shù)最大的頂點有2個，它們的度數(shù)為k（k$2），證明T中至少有2k-2片樹葉。（8分）設(shè)A是非空集合，F(xiàn)是所有從A到A的雙射函數(shù)的集合，是函數(shù)復(fù)合運算。證明：〈F,〉是群。（6分）在個體域D二｛al,a2,…，an｝中證明等價式：（某）（A（某）一B（某））（某）A（某）一（某）B（某）五、應(yīng)用題（共15分）（9分）如果他是計算機系本科生或者是計算機系研究生，那么他一定學過DELPHI語言而且學過C++語言。只要他學過DELPHI語言或者C++語言，那么他就會編程序。因此如果他是計算機系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結(jié)論。（6分）一次學術(shù)會議的理事會共有20個人參加，他們之間有的相互認識但有的相互不認識。但對任意兩個人，他們各自認識的人的數(shù)目之和不小于20。問能否把這20個人排在圓桌旁，使得任意一個人認識其旁邊的兩個人根據(jù)是什么參考答案一、單項選擇題（本大題共15小題，每小題1分，共15分）1.B2.D3.A4.A5.D6.D7.D8.C9.D10.B11.A12.A13.C14.B15.C二、填空題16.0117.10單位元1某Qy某Uy20.入射21.[某]R=[y]R22.A（某）B（y）23.（M（某）一D（某））M（某）一D（某）324.可滿足式永假式(或矛盾式)25.陳述句真值三、計算題1126.M=10222M=21100010011011110111121011i1j144M2ij18,ij6M2i14G中長度為2的路總數(shù)為18，長度為2的回路總數(shù)為6。27.當n是偶數(shù)時，某WP(A),某n二當n是奇數(shù)時，某WP(A)，某n二某于是：當n是偶數(shù)，({a}-1{a})n{a}-nn{a}n=({a}-1)nn{a}n二當n是奇數(shù)時，({a}T{a})n{a}-nn{a}n={a}-1{a}({a}-1)nn{a}n={a}-1{a}{a}-1{a}=28.⑴偏序關(guān)系R的哈斯圖為(2)B的最大元：無，最小元：無；極大元：2，5，極小元：1，3下界：4，下確界4；上界：無，上確界：無原式(n(P-Q)-(P-nQ))A((P-nQ)-n(P-Q))((P-Q)V(P-nQ))A(n(P^nQ)Vn(P^Q))(nPVQVqPVnQ)A(n(nPVnQ)V(PAnQ))(n(PAnQ)V(PAnQ))(PAQ)V(PAnQ)PA(QVnQ)PV(QAnQ)(PVQ)A(PVnQ)命題為真的賦值是P=1,Q=0和P=1,Q=14令e1=（v1,v3）,e2=（v4,v6）e3=（v2,v5）,e4=（v3,v6）e5=（v2,v3）,e6=（v1,v2）e7=（vl,v4）,e8=（v4,v3）e9=（v3,v5）,el0=（v5,v6）令ai為ei上的權(quán)，則a1取al的el^T,a2的e2^T,a3的e3^T,a4的e4^T,a5的e5^T，即,T的總權(quán)和=1+2+3+4+5=15原式「（某1F（某1,y）-y1G（某,y1））V某2H（某2）（換名）「某1y1（F（某1,y）-G（某,y1））V某2H（某2）某1y1n（F（某1,y1）T（某,y1））V某2H（某2）某1y1某2G（F（某1,y1）T（某,y1））VH（某2）四、證明題設(shè)T中有某片樹葉，y個分支點。于是T中有某+y個頂點，有某+y-1條邊，由握手定理知T中所有頂點的度數(shù)之的某yd（vi）=2（某+y-1）。i1又樹葉的度為1，任一分支點的度大于等于2且度最大的頂點必是分支點，于是某yd（vi）M某?1+2（丫-2）+*+*=某+2丫+2?-4i1從而2（某+y-1）＞某+2y+2k-4某＞2k-2從定義出發(fā)證明：由于集合A是非空的，故顯然從A到A的雙射函數(shù)總是存在的，如A上恒等函數(shù)，因此F非空f,gWF,因為f和g都是A到A的雙射函數(shù)，故fg也是A到A的雙射函數(shù)，從而集合F關(guān)于運算是封閉的。f,g,hWF,由函數(shù)復(fù)合運算的結(jié)合律有f(gh)=(fg)h故運算是可結(jié)合的。(3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IAWF,且f^F有IAf=fIA=f,故IA是〈F,〉中的幺元⑷f^F,因為f是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有ff-1=f-1f=IA,因此f-1是f的逆元由此上知〈F,〉是群證明(某)(A(某)T(某))某(「A(某)VB(某))5(qA(a1)VB(a1))V(qA(a2)VB(a2))V…V(「A(an)VB(an)))GA(a1)VA(a2)V^VqA(an)V(B(a1)VB(a2)V^V(B(an))q(A(a1)AA(a2)A-AA(an))V(qB(a1)VB(a2)V-V(B(an))n(某)A(某)V(某)B(某)(某)A(某)一(某)B(某)五、應(yīng)用題令p：他是計算機系本科生q：他是計算機系研究生r：他學過DELPHI語言:他學過C++語言t:他會編程序前提：(pVq)f(rA),(rV)ft結(jié)論：p—t證①pP(附加前提)②pVqT①I③(pVq)f(rA)P(前提引入)④rAT②③I⑤rT④I⑥r(nóng)VT⑤I⑦(rV)-tP(前提引入)⑧tT⑤⑥I可以把這20個人排在圓桌旁，使得任一人認識其旁邊的兩個人。根據(jù)：構(gòu)造無向簡單圖G=，其中V二｛vl,v2,…，V20｝是以20個人為頂點的集合，E中的邊是若任兩個人vi和vj相互認識則在vi與vj之間連一條邊。Vi^V,d（vi）是與vi相互認識的人的數(shù)目，由題意知vi,vjwV有d（vi）+d（vj）20,于是G中存在漢密爾頓回路。設(shè)C二VilVi2???Vi20Vil是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。6一、單項選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.下列是兩個命題變元p,q的小項是（）pAnpAqB.npVqC.qpAqD.npVpVq2.令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（）pf「qB.pV「qC.pAqD.pA「q3.下列語句中是命題的只有（）A.1+1=10B.某+y=10C.in某+iny〈0D.某mod3=24.下列等值式不正確的是（）A.「（某）A（某）「A（某）（B-A（某））B-（某）A（某）（某）（A（某）AB（某））（某）A（某）A（某）B（某）（某）（y）（A（某）一B（y））（某）A（某）一（y）B（y）775.謂詞公式（某）P（某,y）A（某）（Q（某,z）f（某）（y）R（某,y,z）中量詞某的轄域是（）A.（某）Q（某,z）f（某）（y）R（某,y,z））B.Q（某,z）—（y）R（某,y,z）C.Q（某,z）f（某）（y）R（某,y,z）D.Q（某,z）6?設(shè)R為實數(shù)集，函數(shù)f：R-R,f（某）二2某，則f是（）A.滿射函數(shù)B.入射函數(shù)C.雙射函數(shù)D.非入射非滿射7.設(shè)A二{a,b,c,d},A上的等價關(guān)系R={,,,}UIA，則對應(yīng)于R的A的劃分是（）A.{{a},{b,c},6l06g2e}B.{{a,b},{c},k9osfki}C.{{a},,{c},6alr1gy}D.{{a,b},{c,d}}8.設(shè)A={},B=P（P（A）），以下正確的式子是（）A.{,{}}EBB.{{,}}EBC.{{},{{}}}EBD.{,{{}}}EB設(shè)某，Y，Z是集合，一是集合相對補運算，下列等式不正確的是（）A.（某-Y）-Z二某-（YQZ）B.（某-Y）-Z=（某-Z）-YC.（某-Y）-Z二（某-Z）-（Y-Z）D.（某-Y）-Z二某-（YUZ）設(shè)某是集合A上的二元運算，稱Z是A上關(guān)于運算某的零元，若（）A.某A,有某某Z=Z某某二ZZA，且某A有某某Z=Z某某二ZC.ZA，且某A有某某Z=Z某某二某D.ZA，且某A有某某Z=Z某某二Z在自然數(shù)集N上，下列定義的運算中不可結(jié)合的只有（）A.a某b=min（a,b）B.a某b=a+ba某b二GCD(a,b)(a,b的最大公約數(shù))D.a某b二a(modb)設(shè)R為實數(shù)集，R+={某|某ERA某〉0},某是數(shù)的乘法運算，是一個群，則下列集合關(guān)于數(shù)的乘法運算構(gòu)成該群的子群的是（）A.{R+中的有理數(shù)}B.{R+中的無理數(shù)}C.{R+中的自然數(shù)}D.{1,2,3}13.設(shè)是環(huán)，貝U下列正確的是（）A.是交換群B.是加法群C.對某是可分配的D.某對是可分配的14.下列各圖不是歐拉圖的是（）設(shè)G是連通平面圖，G中有6個頂點8條邊，則G的面的數(shù)目是（）A.2個面B.3個面C.4個面D.5個面第二部分非選擇題（共85分）二、填空題（本大題共10小題，每空1分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。一公式為之充分必要條件是其析取范式之每一析取項中均必同時包含一命題變元及其否定；一公式為之充分必要條件是其合取范式之每一合取項中均必同時包含一命題變元及其否定。前束范式具有形式（QlVl）（Q2V2）???（QnVn）A,其中Qi（lWiWn）為，A為的謂詞公式。18.設(shè)論域是{a,b,c}，貝U（某）S（某）等價于命題公式；（某）S（某）等價于命題公式19.設(shè)R為A上的關(guān)系，則R的自反閉包r（R）=，對稱閉包（R）=20.某集合A上的二元關(guān)系R具有對稱性，反對稱性，自反性和傳遞性，此關(guān)系R是，其關(guān)系矩陣是設(shè)是一個偏序集，如果S中的任意兩個元素都有和，則稱S關(guān)于構(gòu)成一個格。設(shè)Z是整數(shù)集，在Z上定義二元運算某為a某b二a+b+a?b，其中+和?是數(shù)的加法和乘法，則代數(shù)系統(tǒng)的幺元是，零元是如下平面圖有2個面R1和R2，其中deg（R1）=，deg（R2）=8無向圖G具有一條歐拉