國(guó)家開(kāi)放大學(xué)電大本科《離散數(shù)學(xué)》期末試題題庫(kù)及答案（試卷號(hào)：1009）

國(guó)家開(kāi)放大學(xué)電大本科《離散數(shù)學(xué)》期末試題題庫(kù)及答案(試卷號(hào)：1009)題庫(kù)一一、單項(xiàng)選擇題(每小題3分，本題共15分)TOC\o"1-5"\h\z若集合A={1,2.3},則下列表述正確的是( )■{1.2.3IGA B.C.U，2,3}UA D.U.2}￡A設(shè)人=U，2,3}.B=U,2?3,4}.A到B的關(guān)系R=(Vh?y>K6A6B,工>、},則R=( ).<<1.2>.<2.3>){<1,1>.<1.2>,<1.3>,<1,4>,<|,5>}{<!.!>.<2.!>}{<2,]>.<3.1>.<3.2>)TOC\o"1-5"\h\z無(wú)向圖G的邊數(shù)是10,則圖G的結(jié)點(diǎn)度數(shù)之和為( )?10 B.20C.30 D.5如圖一所示，以下說(shuō)法正確的是(e是割點(diǎn){a,e}是點(diǎn)割集{b.e}是點(diǎn)割集0是點(diǎn)割集5-設(shè)個(gè)體域?yàn)檎麛?shù)集，則公式Vx3y(x4-^=2)的解釋可為().任意整數(shù)，，對(duì)任意整數(shù)、満足工+、=2對(duì)任意整數(shù)工,存在整數(shù)'滿足工+>=2存在一整數(shù)上.對(duì)任意整數(shù)>満足z+y=2存在一整數(shù)工，有整數(shù)jy満足工+'=2答案：C 2.D 3.B 4.A 5.B二、填空題(每小題3分.本題共15分)設(shè)集合A={】，2,3},B=(2,3,4),C={3,4,5},則BU(A-C〉等于 設(shè)A=<1,2},B=(2,3},C=(3,4),從A到B的函數(shù)/=(<1,2>,<2,3>}.從B到C的函數(shù)g={V2,3>,V3,4>),則Ran(g*/)等于兩個(gè)圖同構(gòu)的必要條件包括結(jié)點(diǎn)數(shù)相等、邊數(shù)相等與 設(shè)G是連通平面圖.v.e.r分別表示G的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)”值為5,e值為4則r的值為設(shè)個(gè)體域。=（1,2,3?4},則謂詞公式（3z）AGr）消去量詞后的等值式為答案:”，2,3,4}（3,4}度數(shù)相同的結(jié)點(diǎn)數(shù)相等1A⑴VA（2）VA（3）VA（4）三、邏輯公式翻譯（每小題6分，本題共12分）將語(yǔ)句“昨天下雨，今天仍然下雨，”翻譯成命題公式.將語(yǔ)句“若不下雨，我們就去參加比賽，”翻譯成命題公式.答案：TOC\o"1-5"\h\z設(shè)P：昨天下雨,Q：今天下雨. （2分）則命題公式為：PAQ. （6分）設(shè)P：下雨,Q：我們?nèi)⒓颖荣? （2分）則命題公式為：。P-*Q.（或P） （6分）四、判斷說(shuō)明題（判斷各題正誤，并說(shuō)明理由，每小題7分.本題共14分）若圖G是一個(gè)歐拉圖，則圖G中存在歐拉路.無(wú)向圖G的結(jié)點(diǎn)數(shù)比邊數(shù)多1,則G是樹(shù).答案：TOC\o"1-5"\h\z正確. （3分）因?yàn)槿魣DG是一個(gè)歐拉圖，則圖中存在歐擊回路. （5分）按定義知，歐拉回路也是歐拉路. （7分）誤- （3分）反例:如圖G的結(jié)點(diǎn)數(shù)比邊數(shù)多1,但不是樹(shù).Ao五、計(jì)算題（每小題12分，本題共36分）設(shè)集合A={1,2,3,4）上的關(guān)系：R={V1,2>,V2,3>,V3,4>）,S=（V1,1>,V2,2>,V3,3>},試計(jì)算（DR-Si （2）R-*i （3）r（RnS）.圖G=VV,E>,其中（a,8,c,d},E=（（a,6）,（a,c）,（a,d）,（6,c）,3,對(duì)應(yīng)邊的權(quán)值依次為1、1、5、2、3及4,請(qǐng)畫(huà)出G的圖形、寫(xiě)出G的鄰接矩陣并求出G權(quán)最小的生成樹(shù)及其權(quán)值.求「（PVQ）VR的析取范式與主合取范式?答案:答案:(4分)《2)人一B= <8分)(3)AXB=(<a,?>.<a.b>,<b,a>,<b,b>,<c^a>.<c,b>,<d,a>,<d,b>}(12分)16.（I）G的圖形表示如圖一所示:《16.（I）G的圖形表示如圖一所示:《3分）（6分）（6分）deg(v,)=3.deR(vj)?2tdcg(vj)=3.deR(v,)=2補(bǔ)圖如圖二所示：（9分）《12《12分）（6分）圖二17用Kruskal算法求產(chǎn)生的最小生成樹(shù).步51為:w(vt.v?)=l.ijr,=viv>w(vj.v?)w3.選e,?x/>sw(vt.)=4.選ej=VgVrw(vttvf)~9,選e,w(v4.v$)?18.選et=x/<v?w(v>,vt)—22.選r?=V|U,最小生成構(gòu)如圖三所示:圖三 <9分）批小位成樹(shù)的段C（T）=}+3+4+9+18+22=57. H2分,六、證明題（本題共8分）1&設(shè)a.b,c均為任意集合，試證明:An（B-o=（AnB）-（Anc）.答案：證明：TOC\o"1-5"\h\z設(shè)x6A.則Vz,x>6AXA. （1分）因AXA^BXB.故Vx.x>6BXB,jaiJ有;（3 分）因此ASB. （5分）設(shè) （6分）因AXA=BXB，故Vx.x>6AXA,則冇工€人，因此（7分）故得人=& （8分）題庫(kù)二一、單項(xiàng)選擇題（每小題3分，本題共15分）設(shè)人=<】.3,5,7,9）,8=<2,4.6},人到B的關(guān)系R=?x.y>|x-y=]}.fliJR=（ ）.A.{<1.2>.<2.3>,<3.4>} B. {<1,2>,<3.4>.<5.6>）C.<<1.1>.<2.2>,<3,6>} D. {<3.2>.<5.4>,<7.6>}若集合A={a,b,c}.則下列表述正確的是（ ）.A.（a B. （a}€AC.（a.6）6A D. 06A設(shè)個(gè)體域?yàn)榧希?.2.3.4,5）.則公式（▼工）（3y）Gr+y=5）的解釋可為（ ）.存在一整數(shù)工有整數(shù)y滿足x+y=5對(duì)任一整數(shù)z存在整數(shù)y満足工+、=5存在一整數(shù)工對(duì)任意整數(shù)'満足z+y=5任一務(wù)數(shù)工對(duì)任意務(wù)數(shù)v滿足x+v=5

設(shè)G為連通無(wú)向圖，則( )時(shí),G中存在歐拉回路.A.G存在兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn) B.G存在一個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)C.G不存在奇數(shù)度數(shù)的結(jié)點(diǎn) D.G存在偶數(shù)度數(shù)的結(jié)點(diǎn)n階無(wú)向完全圖K.的邊數(shù)及每個(gè)結(jié)點(diǎn)的度數(shù)分別是( )-A.n(n-l)與，？ B.”(”一1)/2與”一】C.n-】與” D.n(w-l)與”一】答案：1.D 2.A3.B4.C5.B1.D 2.A3.B4.C5.B分評(píng)卷人1 二、填空題(毎小題3分，本題共15分)設(shè)集合A=(x|x是小于4的正整數(shù)}，用集合的列舉法A=設(shè)A=(l,2},B=(a,6},C=(】，2),從A到B的函數(shù)/={<1,a>.<2,6>),從8到C的函數(shù)g=(Va?2>,V6,l>},則復(fù)合函數(shù)g"= 設(shè)G=<V,E>是一個(gè)圖，結(jié)點(diǎn)度數(shù)之和為30,則G的邊數(shù)為9-設(shè)G是具有”個(gè)結(jié)點(diǎn)血條邊A個(gè)面的連通平面圖.則”+4—2=10.設(shè)個(gè)體域D={2,3,4).A(x)為“工小于3”,則謂詞公式(V_r)A(x)的真值為答案:{1.2,3}{<1.2>,<2.1>）15m假（或F,或0）得分評(píng)卷人三、邏輯公式揚(yáng)譯(毎小題6分，本賄共12分)將語(yǔ)句“如果今天下雨，那么明天的比賽就要延期.”翻譯成命題公式.將語(yǔ)句??地球是圓的，太陽(yáng)也是圓的.'‘翻譯成命題公式.答案:答案:答案:11.設(shè)P：今天下雨，Q：明天的比賽就要延煙.（2分）則命題公式為:P-Q.11.設(shè)P：今天下雨，Q：明天的比賽就要延煙.（2分）則命題公式為:P-Q.（6分）12.設(shè)P：地球是圓的，Q：太陽(yáng)是圓的.（2分）則命題公式為:PAQ.(6分)得分評(píng)卷人四、判斷說(shuō)明題（判斷各題正誤，并說(shuō)明理由毎小歷7分，本題共M分）13.設(shè)A={a,6,c,d),R={Va,6>,V6,a>,Va.a>,V6,6>,Vc,c>),則R是等價(jià)關(guān)系.14.(Vx)(P(x)AQ(y))-*R(x)中量詞V的轄域?yàn)?P(x)AQ(v)).答案：13.錯(cuò)誤.（3分）R不是等價(jià)關(guān)系，因R中不含Vd,d>,故不滿足自反性.（7分）14.正確.（3分）轄域?yàn)榫o接屬詞V之后的最小子公式（P（x）AQ（y））.（7分）得分評(píng)卷人五、計(jì)算題（毎小題12分，本題共36分）設(shè)集合A=(a,6,c},B={6.c,^},試計(jì)算(DAUB； (2M-B； (3)AXB.設(shè)G=<V.E>,V=(v1.vi.vj.v*}.E=(Cv,.vjJ.Cv!.vaJ.Cv).v4).(v?.vj).（vj.v*））.試（1）給出G的圖形表示； （2）寫(xiě)岀其鄰接矩陣；（3）求出每個(gè)結(jié)點(diǎn)的度數(shù)； （4）畫(huà)出其補(bǔ)圖的圖形?試?yán)肒ruskal算法求岀如下所示賦權(quán)圖中的煥小生成樹(shù)《安基與出采解少?。?，開(kāi)求此最小生成樹(shù)的權(quán)?V6?4

V6?415.解：(1)R?S={<1,2>,<2,3>)?(2)R_,=(<2.1>,<3,2>.<4.3>}；（8分）(3)r(RnS)=(<l.l>.<2,2>.<3,3>,<4,4>}（12分）16.解：（1）G的圖形表示為：%4d:図（3分）15.解：(1)R?S={<1,2>,<2,3>)?(2)R_,=(<2.1>,<3,2>.<4.3>}；（8分）(3)r(RnS)=(<l.l>.<2,2>.<3,3>,<4,4>}（12分）16.解：（1）G的圖形表示為：%4d:図（3分）（2）鄰接矩陣:R)111（6分）（3）粗線與結(jié)點(diǎn)表示的是最小生成樹(shù),%4〃

區(qū):（10分）權(quán)值為9（】2分）17.M：P-*(QAR)BrPV（QAR）析取范式（2分）頃1PVQ)A(nPVR)（5分）<=>(-!PVQ〉V(RA")A("VR)（?分）PVQ)V(RA")A("VR)V(QAiQ)（9分）（11分）（】2分）?(-iPVQVR)A(nPVQV-iR)A(-|PV-iQVR) 主合取范式（11分）（】2分）試證明：P—Q=P—r(P-*rQ).(DiPVQP(l分)(2)PP（附加前提）（3分）(3)QT(l)(2)/（5分）(4)PAQT(2)(3)/(6分)(5)-|(-1PV-iQ)(DiPVQP(l分)(2)PP（附加前提）（3分）(3)QT(l)(2)/（5分）(4)PAQT(2)(3)/(6分)(5)-|(-1PV-iQ)T(4)E（7分）(6)P-n(-1PViQ)CP規(guī)則（8分〉18.證明:說(shuō)明：（1）因證明過(guò)程中.公式引用的次序可以不同，一般引用前提正確得丨分?利用兩個(gè)公式鶴岀有效靖論?dān)Q1或2分，最后得出結(jié)論得2或1分.（2）可以用真值表驗(yàn)證.釆用反證法可參照給分.題庫(kù)三一、單項(xiàng)選擇題（每小題3分，本題共15分）1.設(shè)A=（1,2,3,4},B={2,3,4）,人到B的關(guān)系R=（Vz,y>|工￡A￡B,且工+y=5}.則R=（ ）.A.{<1,2>,<1.3>,<2,3>） B.<<1,4>.<2,3>,<3.2>}C{<],]>,<2,2>,<3.2>> D.{<3,2>,<2.4>?<3,4>}若集合A=S，6,c,d},則下列表述正確的是（ ）?A.06A B.{aIGAC.{a.6.c?c/}EA D.（a設(shè)個(gè)體域?yàn)檎麛?shù)集，則公Vx）（3y）（x-y=2）的解釋可為（ ）.存在一整數(shù)I有整數(shù)〉滿足x-y-2存在一整數(shù)X對(duì)任意整數(shù)y滿足x-y=2對(duì)任一整數(shù)=存在整數(shù)y満足x-y^2任一整數(shù)]對(duì)任意整數(shù)y滿足1一丁=2A.B.C.D.4.n階無(wú)向完全圖K.的邊數(shù)及每個(gè)結(jié)點(diǎn)的度數(shù)分別是（ ）?A.n（n—1）與” B.n3—1）與”一】C.n—】與” Dn（n—1）/2與“一】設(shè)G為連通無(wú)向圖，則（ ）時(shí),G中存在歐拉回路.A.G不存在奇數(shù)度數(shù)的結(jié)點(diǎn)C.G存在兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)5.B.G存在一個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)D.G存在偶數(shù)度數(shù)的結(jié)點(diǎn)答案:I.B2.D3.C1.D5.A二、填空題（每小題3分，本題共15分）設(shè)集合A=（】.2.3）.B=<2.3>,C=（3.4}.則A\J（B-C）= 設(shè)A^{a,b}.B={\,2},C=<a,b}.從A到丿3的函數(shù)/-{<?,1>.<ft.2>}.從/J到。的函數(shù)k=<<1.6>.<2.?>?.則k?/等于 設(shè)G=<V.E>是一個(gè)圖.|E|=10.則G的結(jié)點(diǎn)度數(shù)之和為 設(shè)G是具有"個(gè)結(jié)點(diǎn)，”條邊&個(gè)而的連通平面圖.則〃+4—2=設(shè)個(gè)體域D=?1.2.3'..V.r）為。的2倍大,2"?則側(cè)詞公式《的或值為答案：{1.2,3}?a.b>.<b,a>}20（或：2|E|）9?m10.假（或F.或0）三、邏輯公式翻譯（每小題6分，本題共12分）11-將語(yǔ)句“如果他掌握了計(jì)算機(jī)的用法，那么他就能完成這項(xiàng)工作."翻譯成命題公式.12.將語(yǔ)句“前天下雨，昨天還是下雨.”翻譯成命題公式.答案：TOC\o"1-5"\h\z設(shè)P：他掌握了計(jì)算機(jī)的用法,Q：他能完成這項(xiàng)工作. （2分）則命題公式為:P-*Q. （6分）設(shè)P：前天下雨.Q：昨天還是下雨. （2分）則命題公式為：PAQ. （6分）四、 判斷說(shuō)明題（判斷各題正誤，并說(shuō)明理由.每小題7分，本題共14分）設(shè)A^{a,b.c），R={<a,a>.<b,b>.<c,c>,<a,b>.<6,a>,<b.c>,<c.b>}，則R是等價(jià)關(guān)系?H.<Vx）（P（j）AQ（y）-R（x））中危詞V的鋁域?yàn)椋≒（x）AQ（y））.答案：】3.錯(cuò)誤. 3萬(wàn)丿R不是等價(jià)關(guān)系.因R中包含<a.b>與V6，c>，但不包含V“，c>.故不満足傳遞性?（7分）錯(cuò)誤. （3分）轄域?yàn)榫o接量詞V之后的最小子公式（P（x）AQ（y）-*R（x））. （7分）五、 計(jì)算題（每小題12分，本題共36分）設(shè)集合A—{a.b.c.d}.B—{a.b}?試計(jì)算（1〉八UH； （2）A-B； （3）AXH.

<Vj.V*）h試（1）給出G的圖形表示； （2）寫(xiě)岀其鄰接矩陣；（3）求岀每個(gè)結(jié)點(diǎn)的度數(shù)； （4）畫(huà)出其補(bǔ)圖的圖形.試?yán)肒ruskal算法求出如下所示賦權(quán)圖中的最小生成樹(shù)（要求寫(xiě)出求解步驟）.并求此最小生成樹(shù)的杖.答案:15.解：(1)P?S==(<1,2>,<2.3>}?R"=(V2,1>,V3,2>,V4,3>)答案:15.解：(1)P?S==(<1,2>,<2.3>}?R"=(V2,1>,V3,2>,V4,3>)；r(/?AS)={<l.l>.<2,2>,<3,3>.<4.4>}（4分）（8分）（】2分）解：G的圖形表示為:（3分）（3分）鄰接矩陣:（9分）（6（9分）粗線表示的圖是曇小生成樹(shù)，權(quán)為5：（】2（】2分）解:r(PVQ)VRTOC\o"1-5"\h\z■(rpArQ)VR 析取范式 (5分)VR)A(rQVR) 《7分)成(rpvR〉V(QArQ))A(rQVR) (9分)=((”VR)V(QArQ))A((rQVR)V(PA")) (10分)VRVQ)A("VRVrQ)A—QVRVP)/\(rQVRv") ⑴分)<=>(PVrQVR)A(rpVQVR)A(「PV-QV/?>主合取范式(12分)六、證明題(本題共8分)試證明：「PVQnPf-(P-「Q).答案：證明：(1)T-1(P-*Q) P（1分）(2)P-*Q T(1)E(3分)⑶(QfR) P(4分)(4)-iR P（5分）(5)nQ T(3)(4)/（6分）(6)-,P T(2>(5)/說(shuō)明：（8分）（1） 因證明過(guò)程中.公式引用的次序可以不同，一般引用前提正確得1分，利用兩個(gè)公式得岀有效結(jié)論得1或2分，最后得岀結(jié)論縛2或1分?（2） 另?可以用真值表驗(yàn)證.題庫(kù)四一、單項(xiàng)選擇題（每小題3分，本題共15分）若集合A=（1,2,3,4）,B=<1,3,5）,則下列表述正確的是（ >.A=8 B.BUAC.B" D.BQA設(shè)A=（1,2.3},B={2,4.6）,A到B的關(guān)系R={<x,y>12x=y},則 ）.{<],3>.<2,4>,<3.5>}{<2.1>.<4.3>.<6.5>><<1.1>,<2,2>.<3.3>}{<1.2>,<2,4>,<3,6>}TOC\o"1-5"\h\z無(wú)向圖G是棵樹(shù)，邊數(shù)是10,則G的結(jié)點(diǎn)度數(shù)之和是（ ）.A.20 B.9C.10 D.114.下面的推理正確的是()?(l)(Vx)F(i)-*G(x)(2)F(y)fG。)(l)(3x)F(x)-*G(x)(2)F(>)-G(y)C(l)(3x)(F(x)—G(z))(2)F(y)-^G(x)D.(l)(Vz)(F(x)-*G(x))(2)F(y)-^G(y)前提引入U(xiǎn)S（1）.前提引人US（1）.前提引入ES（1）.前提引入U(xiǎn)S⑴.設(shè)個(gè)體域?yàn)檎麛?shù)集，則公式Vx3y（x+y=2）的解粹可為（ ）任一整數(shù)h,對(duì)任意整數(shù)'滿足x+y=2對(duì)任一整數(shù)工，存在整數(shù)y滿足工+、=2存在一整數(shù)］，對(duì)任意整數(shù)y満足工+?=2存在一整數(shù)Z，有整數(shù)y満足x+y-2答案：l.C 2.D 3.A4.D 5.B得分評(píng)卷人 二、填空瓶（毎小題3分，本題共15分）設(shè)集合八=（“’>。）.9=化.。），。=《。日）?則An（BUC）等于設(shè)A=（1.2},B={2,3},C=（3.4）,從人到B的函數(shù)/=（<1.2>.<2.3>）,從H到C的函?Cg=（V2,3>?V3,4>},則Ran（g./）等于設(shè)G是漢密爾頓圖,S是其結(jié)點(diǎn)集的一個(gè)子衆(zhòng)，若S的元素個(gè)數(shù)為6,則在G-S中的連通分支數(shù)不超過(guò)設(shè)G是有8個(gè)結(jié)點(diǎn)的連通圖.結(jié)點(diǎn)的度數(shù)之和為24,則可從G中朋去 條邊后使之變成樹(shù).設(shè)個(gè)體域D=U.2.3.4）.則謂詞公式（Vi）A（工）消去危詞后的等值式為答案；{b.c}（3,4}（或C）8.651O.A(1)AA(2)AA(3)AA(4)

評(píng)卷人三、邏輯公式舗譯（毎小題6分，本題共12分）將語(yǔ)句“昨天下雨，今天仍然下雨評(píng)卷人三、邏輯公式舗譯（毎小題6分，本題共12分）將語(yǔ)句..我們下午2點(diǎn)或者去禮堂看電影或者去教室看書(shū).“鄱謹(jǐn)飭布頓公才答案：設(shè)P：昨天下雨，Q：今天下雨.則命題公式為：PAQ.設(shè)P：我們下午2點(diǎn)去禮堂看電影.Q：我們下午2點(diǎn)去教室看書(shū).則命題公式為：i（PiQ）.注:或者（rPAQ）V（PAnQ）（2分）（2分）（6分）（2分）（6分）四、判斷說(shuō)明題（判斷各題正誤，并說(shuō)明理由.每小館7分，本題共14 分）不存在集合A與B,使得人￡8與ACB同時(shí)成立.V5（IV4V|圖二如圖二所示的圖G存在一條歐拉回路.V5（IV4V|圖二答案：TOC\o"1-5"\h\z錯(cuò)誤. （3分）例：設(shè)A={a}tB={a,{a}} （5分）則有A6B且人（7分）說(shuō)明：舉岀符合條件的反例均給分.】4.正確. （3分）因?yàn)閳DG為連通的，且其中每個(gè)頂點(diǎn)的度數(shù)均為偶數(shù). （7分）如果具體指岀一條歐拉回路也同樣給分.五、計(jì)算題（毎小館12分，本題共36分）設(shè)A=U,2,3),R=<Vr<y>l工￡人，》€(wěn)人且i+y=4>,S=(V工工￡人，y6人且試求R，S,R-*r(S).0000設(shè)圖G=s<V.E>,V={v1,v：.vj.v.hE=((Vi.v：>.(vi.v.J.Cv,.v.)},試(D畫(huà)岀G的圖形表示；寫(xiě)岀其鄰接矩陣；求岀每個(gè)結(jié)點(diǎn)的度數(shù)；畫(huà)岀圖G的補(bǔ)圖的圖形.求「(PVQ)VR的折取范式與主合取范式?答案：15.(DR=(Vag>,V6./?>,Vc?c>?V』，d>.Va/>?Va?c>?Vu?d>,V/>,d>h ”分)(2)關(guān)系圖(8分)(3)集合B無(wú)最大無(wú)，極大元為b與c.無(wú)上界. (12分)16.解：(】〉關(guān)系圖(6分)⑶de《（s⑶de《（s）=3deg(v?)=2deg(p>)=2deg(s〉=ldeg(v$)=s2（9分）5)補(bǔ)圖（12分）17.P-*(QAW)TOC\o"1-5"\h\z?=>-PV(QAR) (2分)9(rPVQ)A(rPVR〉合取范式 (5分)?(-PVQ)V(RA-R)A(-*PVR) (?分)頃"VQ)V(RAF)A(rpvR〉V(QA-Q) (9分)笊"VQVR)A("VQVrR)A("VRVQ〉A(chǔ)(rpvRVrQ) ⑴分)c=>(~*PVQVR)A(rpVQVrR)A(rpv「QVR)主合取范式 (12分)六、證明題（本題共8分）18,試證明門(mén)PVQ=>P-*(-i(-1PV-iQ)).答案；(Dr—QP（1分）(2)PP（附加前提〉（2分）(3)QT(l)(2)/（4分）(4)PAQT(2)(3)/(5分)(5)r(rPVrQ〉T(4)E(6分)(6)r(PfrQ)T(5)E(7分)(7)Pfr(P—Q)CP規(guī)則（8分）說(shuō)明：因證明過(guò)程中，公式引用的次序可以不同，一般引用前提正確徊1分，利用兩個(gè)公式得岀有效結(jié)論待1或2分，最后得岀結(jié)論得2或1分.另，可以用真值裏驗(yàn)證.題庫(kù)五一、 單項(xiàng)選擇題（每小題3分，本題共15分）若集合A=（1,2,3,4）,則下列表述不正確的是（ ）?1EA B.",2,3}UAC.（1.2.3IEA D.0UA若R和殆是A上的對(duì)稱關(guān)系，則RUR”R,nM，R】一M，RLR中對(duì)稱關(guān)系有（）個(gè).TOC\o"1-5"\h\zA.1 B.2C.3 D.4設(shè)G為連通無(wú)向圖，則（ ）時(shí),G中存在歐拉回路.A.G不存在奇數(shù)度數(shù)的結(jié)點(diǎn) B. G存在偶數(shù)度數(shù)的結(jié)點(diǎn)C.G存在一個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn) D. G存在兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)無(wú)向圖G是棵樹(shù)，邊數(shù)是10,則G的結(jié)點(diǎn)度數(shù)之和是（ ）?A20 B. 9C.10 D. 11設(shè)個(gè)體域?yàn)檎麛?shù)集，則公式Vz3y（z+y=0）的解釋可為（ ）.存在一整數(shù)工有整數(shù)y滿足x+y=0對(duì)任意整數(shù)工存在整數(shù)y滿足x+y=0存在一整數(shù)工對(duì)任意整數(shù)y滿足x+y=0任意整數(shù)工對(duì)任意整數(shù)y滿足工+>=0答案：1C 2.D 3.A 4.A 5.B二、 壊空題（每小題3分，本題共15分）設(shè)A={1.2）.B={1.2.3I.則A到B上不同的函效個(gè)數(shù)為有”個(gè)結(jié)點(diǎn)的無(wú)向完全圖的邊數(shù)為若無(wú)向圖G中存在歐拉路但不存在歐拉回路，則G的奇數(shù)度數(shù)的結(jié)點(diǎn)有個(gè).設(shè)G是有2個(gè)結(jié)點(diǎn)的無(wú)向迷通圖.結(jié)點(diǎn)的度數(shù)之和為30,則從G中刪去條邊后使之變成樹(shù).設(shè)個(gè)體域D=（】，2.3,4},則謂詞公式（日工）人3）消去信詞后的等值式為答案：6.97.”3-1）/2（或C：）8.29.6A（1）VA（2）VA（3）VA（4）三、邏輯公式翻譯（每小題6分，本題共12分）將語(yǔ)句“昨天下雨”翻譯成命題公式.將語(yǔ)句“小王今天上午或者去看電影或者去打球”翻譯成命題公式.答案：設(shè)P：昨天下雨. （2分）則命題公式為：（6分）設(shè)小王今天匕午去宥電影Q：小王今天上午去打球 （2分）則命題公式為：TPiQ）.或者（、PAQ）V（『ArQ） 小4卜）四、判斷說(shuō)明題（判斷各題正誤，并說(shuō)明理由.每小題7分，本題共14分）存在集合人與8,使得A6B與Aai同時(shí)成立完全圖K.是平面圖.答案：TOC\o"1-5"\h\z正確. （3分）例：設(shè) （5分）則Tr4eBM/ACB. （7分）說(shuō)明；舉出符合條件的例均紿分.正確. （3分）完全圖K,是平面圖. （5分）如K,可以如下圖示嵌入平面.五、計(jì)算題（每小題12分，本題共36分）

設(shè)偏序集VA,R>的哈斯圖如下,B為A的于集，其中B={b,c}.試。)寫(xiě)岀R的關(guān)系表達(dá)式;畫(huà)岀關(guān)系R。)寫(xiě)岀R的關(guān)系表達(dá)式;畫(huà)岀關(guān)系R的關(guān)系圖；求岀B的最大元、極大元、上界.設(shè)R]G=<V.E>.V=<vt.v2,vj.,vj>.E={(vj,vj)t(vi.v*)?(vjVi).(vj.v$)}.試(D畫(huà)岀G的圖形表示；(2)寫(xiě)出其鄰接矩陣；(3〉求岀每個(gè)結(jié)點(diǎn)的度數(shù)；(4〉畫(huà)出圖G的補(bǔ)圖的圖形?求PTQAR)的合取范式與主合取范式.答案：解:R=(<1.3>.<2,2>.<3.1>}S={<1,1>,<2.2>.<3.3>}R,=(<3.1>,<2.2>.<1,3>}r(S)={<).!>.<2.2>.<3.3>}說(shuō)明：對(duì)于每?-個(gè)求解項(xiàng)?如果部分正確，可以給對(duì)應(yīng)】分?(3分)(6分)(9分)(12分〉解：(1)(2)鄰接矩陣(3分)ro101(2)鄰接矩陣(3分)ro101(6分)（3）dcg（v,）=2deg（vj）=2deg（m）=Odcg（v?）=2（4〉補(bǔ)圖】7.解：i（PVQ）VRe=＞（nPA-iQ）V/? 析取范式n（rPVR）A（iQVR）D（（iPVR〉V（QAiQ））A（iQVR）?（（-!PVW）V（QAqQ））A（（-iQVR）V（PA-iP））?（-iPVRVQ）A（"VRViQ）A（iQVRVP）A（iQVRV"）（9分）（12分）（5分）（7分）（9分）（10分）（11（9分）（12分）（5分）（7分）（9分）（10分）（11分）（12設(shè)人.B是任意集合.試證明：若AXA=BXB.則人=B.答案：設(shè)S=An（B-C）,T=（AnB）-（AnO.TOC\o"1-5"\h\z若Z6S，則X6A且xeB-C,EPx6A,并且x6B且x^C, （2分）所以xeCAQB）且R《（AnC）,得x6T, （3 分）所以SMT. （4分）反之.若x6T,Ji!iJx6（AnB）且x^（AAC）, （5分）即x6A,x6B,且iRC,則得zCB-C, （6分）即得xeACKB-C）,即工￡S.所以TCS. （7分）因此T=S. （8分）另，可以用恒等式替換的方法證明.題庫(kù)六一、單項(xiàng)選擇題（每小題3分，本題共15分）TOC\o"1-5"\h\z若集合人=(1.2.3.4).則下列表述不正確的足( )?<2,3)6A B. AG{1.2.3,0C.<1.2.3,4)CA D.16A若無(wú)向圖G的結(jié)點(diǎn)度數(shù)之和為2O.JfliJG的邊數(shù)為()?A.10 B.20C.30 D.5無(wú)向圖G是棵樹(shù).結(jié)點(diǎn)數(shù)為10,則G的邊數(shù)為( )?A.5 B.10C.9 D.II設(shè)A(x)：xSA.B(x)：x^學(xué)生.則命題“有的人炬學(xué)生”可符號(hào)化為( )■-?(Vx)(A(x)-*B(x))(3x)(A(x)AB(x))(VzXACx)AB(x))D.-*(lz)(A(x)A-B(x))5.下面的推理正確的是( )?A.(1)(Vj)F(x)-*G(x)前提引入(2)F(y)-^G(y)US(l).B.C1X3x)F(x)-G(x)前提引入U(xiǎn)S(D.C.(1)(3x)(F(x)-*G(x))前提引入(2)F(j?)-*G(x)ES⑴.D.(1)(3x)(F(x)—G(x))前提引入(2)F(y)-G(y)ESQ).答案：1.A2.A3.C 4.B5.D得分評(píng)卷人二、填空題(每小題3分，本題共15分)6.設(shè)集合A=(1,2,3),B={2.3,4).C=<3,4.5},則AU(C-8)等于

設(shè)A=（2,3},B=（1.2}.C=?{3,4}t從A到B的函數(shù)/=（V2,2>,V3,1>>,從B到C的函數(shù)g=（<l.3>.<2.4>},則Dom（g./）等于 .已知圖G中共有1個(gè)2度結(jié)點(diǎn),2個(gè)3度結(jié)點(diǎn).3個(gè)4度結(jié)點(diǎn)，則G的邊數(shù)是 .設(shè)G是連通平面圖.v.e.r分別表示G的結(jié)點(diǎn)數(shù)?邊數(shù)和面效?值為5,e值為4,則r的值為設(shè)個(gè)體域D=H,2.3,4},A（工）為七大于5”，則調(diào)詞公式（V工）AG〉的真值為答案：{1,2,3,5}<2,3}（或A）8.101假（或