離散數(shù)學(xué)試題及答案

第1頁共17頁離散數(shù)學(xué)試題及答案＝＝AAnpAA_______________._____________,其中雙射的是__________________________.ABABAB____________;AB_____________;A－B＝_____________________.ARAAR3),(3,2)},R1={(2,1),(3,2),(4,3)},則R1?R2=________________________,R2?R1=____________________________,R12=________________________.A-B=__________________________,B-A=__________________________,A∩B=__________________________,.._______________________________________________________xQxG第2頁共17頁16.設(shè)謂詞的定義域?yàn)閧a,b},將表達(dá)式VxR(x)→3xS(x)中量詞消除，寫成與之對(duì)應(yīng)的命題公式是R___________________________________________.二、選擇題1設(shè)集合A={2,{a},3,4}，B={{a},3,4,1}，E為全集，則下列命題正確的是()。(A){2}A(B){a}A(C){{a}}BE(D){{a},1,3,4}仁B.2設(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ì)稱性3設(shè)半序集(A,≤)關(guān)系≤的哈斯圖如下所示，若A的子集B={2,3,4,5},則元B542(A)下界(B)上界(C)最小上界(D)42(A)請(qǐng)把門關(guān)上(B)地球外的星球上也有人(C)x+5>6(D)下午有會(huì)嗎？5設(shè)I是如下一個(gè)解釋：D＝{a,b},則在解釋I下取真值為1的公式是().(A)3xVyP(x,y)(B)VxVyP(x,y)(C)VxP(x,x)(D)Vx3yP(x,y).6.若供選擇答案中的數(shù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(diǎn)的度，能畫出圖的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).是().(A)恒真的(B)恒假的(C)可滿足的(D)前束范式.3頁共17頁(A)G不H(B)H不G(C)G＝H(D)以上都不是.9設(shè)A,B為集合，當(dāng)()時(shí)A－B＝B.(A)A＝B(B)A堅(jiān)B(C)B堅(jiān)A(D)A＝B＝氣.10設(shè)集合A={1,2,3,4},A上的關(guān)系R＝{(1,1),(2,3),(2,4),(3,4)},則R具有()。(A)自反性(B)傳遞性(C)對(duì)稱性(D)以上答案都不對(duì)11下列關(guān)于集合的表示中正確的為()。(A){a}={a,b,c}(B){a}堅(jiān){a,b,c}(C)氣={a,b,c}(D){a,b}={a,b,c}12命題VxG(x)取真值1的充分必要條件是().(C)有某些x，使G(x0)取真值1.(D)以上答案都不對(duì).G頂點(diǎn)，6個(gè)面，則G的邊數(shù)是().(A)9條(B)5條(C)6條(D)11條.14.設(shè)G是5個(gè)頂點(diǎn)的完全圖，則從G中刪去()條邊可以得到樹.(A)6(B)5(C)10(D)4.「01111]15.設(shè)圖G的相鄰矩陣為10100，則G的頂點(diǎn)數(shù)與邊數(shù)分別為().11010110110(A)4,5(B)5,6(C)4,10(D)5,8.三、計(jì)算證明題1.設(shè)集合A＝{1,2,3,4,6,8,9,12}，R為整除關(guān)系。(1)畫出半序集(A,R)的哈斯圖；寫出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；(3)寫出A的最大元，最小元，極大元，極小元。2.設(shè)集合A＝{1,2,3,4}，A上的關(guān)系R＝{(x,y)|x,y=A且x>y},求第4頁共17頁(2)寫出R的關(guān)系矩陣.Dabf(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)32320011試求(1)P(a,f(a))∧P(b,f(b));(2)Vx3yP(y,x).5.設(shè)集合A＝{1,2,4,6,8,12}，R為A上整除關(guān)系。(1)畫出半序集(A,R)的哈斯圖；(2)寫出A的最大元，最小元，極大元，極小元；(3)寫出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.7.(9分)設(shè)一階邏輯公式：G=(VxP(x)∨3yQ(y))→VxR(x)，把G化成前束范式.9.設(shè)R是集合A={a,b,c,d}.R是A上的二元關(guān)系,R={(a,b),(b,a),(b,c),(c,d)},(1)求出r(R),s(R),t(R)；(2)畫出r(R),s(R),t(R)的關(guān)系圖.11.通過求主析取范式判斷下列命題公式是否等價(jià)：(1)G=(P∧Q)∨(P∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(P∧R))13.設(shè)R和S是集合A＝{a,b,c,d}上的關(guān)系，其中R＝{(a,a),(a,c),(b,c),(c,d)},S＝{(a,b),(b,c),(b,d),(d,d)}.5頁共17頁(2)計(jì)算R?S,R∪S,R－1,S－1?R－1.四、證明題{P→Q,R→S,P∨R}蘊(yùn)涵Q∨S。2.設(shè)A,B為任意集合，證明：(A-B)-C=A-(B∪C).4.(本題10分)A,B為兩個(gè)任意集合，求證：A－(A∩B)=(A∪B)－B.一、填空題1.{3};{{3},{1,3},{2,3},{1,2,3}}.2.2n2.3.1={(a,1),(b,1)},2={(a,2),(b,2)},3={(a,1),(b,2)},4={(a,2),(b,1)};3,4.5.12,3.6.{4},{1,2,3,4},{1,2}.7.自反性；對(duì)稱性；傳遞性.8.(1,0,0),(1,0,1),(1,1,0).9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2mn.11.{x|-1≤x<0,xR};{x|1<x<2,xR};{x|0≤x≤1,xR}.13.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.14.3x(P(x)∨Q(x)).15.21.6頁共17頁14316.(R(a)∧R(b))→(S(a)∨S(b)).14317.{(1,3),(2,2)};{(1,1),(1,2),(1,3)}.二、選擇題1.C.2.D.3.B.4.B.5.D.6.C.7.C.8.A.9.D.10.B.11.B.13.A.14.A.15.D三、計(jì)算證明題1)894231(2)B無上界，也無最小上界。下界1,3;最大下界是3.(3)A無最大元，最小元是1，極大元8,12,90+;極小元是1.2.R={(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.1)221|1|1(2)MR=||L100110]03.(1)?t＝(t(x))＝t(x)+3＝2x+3＝2x+3.)?＝((x))＝(x)+3＝(x+3)+3＝x+6,(4)?t＝(t(x))＝t(x)/4＝2x/4=x/2,(5)??t＝?(?t)＝?t+3＝2x/4+3＝x/2+3.第7頁共17頁424.(1)P(a,f(a))∧P(b,f(b))=P(3,f(3))∧P(2,f(2))42=P(3,2)∧P(2,3)=1∧0=0.(2)Vx3yP(y,x)=Vx(P(2,x)∨P(3,x))=(P(2,2)∨P(3,2))∧(P(2,3)∨P(3,3))=(0∨1)∧(0∨1)=1∧1=1.5.(1)(2)無最大(3)B無81 6元8,12;極小元是1.上界，無最小上界。下界1,2;最大下界2.=(P∨Q)∨(Q∧(P∨R))QPR=(P∧Q)∨(Q∧P)∨(Q∧R)PQRPQRPQRPQR(P∧Q∧R)∨(P∧Q∧R)=m3∨m4∨m5∨m6∨m7=x(3,4,5,6,7).8頁共17頁7.G=(VxP(x)∨3yQ(y))→VxR(x)=(VxP(x)∨3yQ(y))∨VxR(x)=(VxP(x)∧3yQ(y))∨VxR(x)=(3xP(x)∧VyQ(y))∨VzR(z)=3xVyVz((P(x)∧Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},s(R)＝R∪R－1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)},t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)關(guān)系圖:adabcr(R)abdabs(R)adabct(R)11.G＝(P∧Q)∨(P∧Q∧R)PQRH=(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)PQR9頁共17頁G,H的主析取范式相同，所以G=H.(1)MR=00000011000]0SM=0S001000]0(2)R?S＝{(a,b),(c,d)},R∪S＝{(a,a),(a,b),(a,c),(b,c),(b,d),(c,d),(d,d)},R－1＝{(a,a),(c,a),(c,b),(d,c)},S－1?R－1＝{(b,a),(d,c)}.四證明題(1)P∨RPR→PQ(1)(3)P→QP(4)R→QQ(2)(3)(6)R→SP(7)Q→SQ(5)(6)(8)Q∨SQ(7)2.證明：(A-B)-C=(A∩~B)∩~C=A∩(~B∩~C)=A∩~(B∪C)=A-(B∪C)10頁共17頁(1)AD(附加)(2)A∨BP(3)BQ(1)(2)(5)B→CQ(4)(6)CQ(3)(5)CDP(8)DQ(6)(7)ADD(1)(8)=A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝∪(A∩~B)＝(A∩~B)＝A－B而(A∪B)－B=(A∪B)∩~B=(A∩~B)∪(B∩~B)=(A∩~B)∪=A－B第11頁共17頁所以：A－(A∩B)=(A∪B)－B.離散數(shù)學(xué)試題(A卷及答案)一、(10分)某項(xiàng)工作需要派A、B、C和D4個(gè)人中的2個(gè)人去完成，按下面3個(gè)A→CD，(B∧C)，C→D必須同時(shí)成立。因此(A→CD)∧(B∧C)∧(C→D)D))DACACDCDBC(C∧D∧B∧D)∨(C∧D∧C)∨(C∧F∨F∨(A∧C)∨F∨F∨(C∧D∧B)∨F∨F∨(C∧D∧B)∨F∨CBCDCDBCDT二、(15分)在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會(huì)議的每個(gè)成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。第12頁共17頁推理化形式為：(1)3xY(x)(2)Y(c)(5)S(c)PPT(6)，EG證明：A仁BVx(x∈A→x∈B)∧3x(x∈B∧x茫A)Vx(x茫A∨x∈B)∧3x(x∈B∧x茫A)(3x(x∈A∧x茫B)∧Vx(x∈A∨x茫B))(3x(x∈A∧x茫B)∧Vx(x∈B→x∈A))5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>}R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，i1第13頁共17頁1>，<5，4>，<5，5>}。五、(10分)R是非空集合A上的二元關(guān)系，若R是對(duì)稱的，則r(R)和t(R)是對(duì)稱RyrRRIAxRyxIAyRIA對(duì)稱，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對(duì)稱的。則xRn+1y3z(xRnz∧zRy)3z(zRnx∧yRz)yRn+1x，所以Rn+1對(duì)稱。因此，對(duì)任意正整數(shù)n，Rn對(duì)稱。六、(10分)若f：A→B是雙射，則f－1：B→A是雙射。證明因?yàn)閒：A→B是雙射，則f－1是B到A的函數(shù)。下證f－1是雙射。對(duì)任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f－1(y)＝x，所以f－1是滿射。對(duì)任意的y1、y2∈B，若f－1(y1)＝f－1(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因?yàn)閒：A→B是函數(shù)，則y1＝y(tǒng)2。所以f－1是單射。證明因?yàn)?lt;S，*>是一個(gè)半群，對(duì)任意的b∈S，由*的封閉性可知，b2＝b*b∈S，b3因?yàn)镾是有限集，所以必存在j＞i，使得bi＝bj。令p＝j(luò)－i，則bj＝bp*bj。所以對(duì)q≥i，有bq＝bp*bq。因?yàn)閜≥1，所以總可找到k≥1，使得kp≥i。對(duì)于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)八、(20分)(1)若G是連通的平面圖，且G的每個(gè)面的次數(shù)至少為l(l≥3)，則G第14頁共17頁m≤lr(2)設(shè)平面圖G＝<V，E，F(xiàn)>是自對(duì)偶圖，則|E|＝2(|V|－1)。第15頁共17頁離散數(shù)學(xué)試題(B卷及答案)一、(10分)證明(P∨Q)∧(P→R)∧(Q→S)S∨R(1)R(3)P6)Q→S(7)S(8)R→SPPP(1)Vx(P(x)→Q(x))(2)Vx(P(x)∨Q(x))(7)Vx(P(x)→(A(x)∨B(x))aAaBaBa(10)Vx(A(x)→Q(x))Qa(12)A(a)PPP第16頁共17頁P(yáng)aBaT(5)(13)，IxPxBxT(14)，EG因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所UUsiiiii=1i=1xr第17頁共17頁七、(10分)設(shè)函數(shù)g：A→B，f：B→C，則：證明(1)對(duì)任意的x∈A，因?yàn)間：A→B是函數(shù)，則存在y∈B使<x，y>∈g。對(duì)于y∈B，因Af(g(x))。G中的一個(gè)等價(jià)關(guān)系，且[a]R＝aH。如果你還不知道讀什么書，或者想尋找下載閱讀更多書籍，就請(qǐng)您打開微信掃一掃，掃描下方二維碼，關(guān)注微信公眾號(hào)：大學(xué)生學(xué)術(shù)墻。微信直接搜索關(guān)注公眾號(hào)：大學(xué)生學(xué)術(shù)墻這里是每一位上進(jìn)的人的家園【大學(xué)生學(xué)術(shù)墻】資料庫里有數(shù)百萬本書籍，此外，關(guān)注微信公眾號(hào)：大學(xué)生學(xué)術(shù)墻，并在后臺(tái)回復(fù)：1.回復(fù)：資料，即可免費(fèi)領(lǐng)取100000G的書籍庫、大學(xué)必備筆記期末試卷、考證資料、四六級(jí)考試、計(jì)算機(jī)二級(jí)考試等資料！2.回復(fù)：電影，即可免費(fèi)在線觀看最新上線的熱門大片！3.回復(fù)：小說，即可免費(fèi)領(lǐng)取數(shù)百萬本著名小說！4.回復(fù)：證券、期貨，即可免費(fèi)