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

PAGE第4頁共17頁離散數(shù)學(xué)試題及答案一、填空題1設(shè)集合A,B，其中A＝{1,2,3},B={1,2},則A-B＝_____{3}______________; (A)-(B)＝____{{3}，{1，3}，{2,3},{1,2,3}}__________.2.設(shè)有限集合A,|A|=n,則|(A×A)|=___2^(n^2)________.3.設(shè)集合A={a,b},B={1,2},則從A到B的所有映射是____A1={(a,1),(b,1)},A2={(a,2),(b,2)},A3={(a,1),(b,2)},A4={(a,2),(b,1)},______________________,其中雙射的是______A3,A4__________.4.已知命題公式G＝(PQ)∧R，則G的主析取范式是____P∧Q∧R(m5)____.5.設(shè)G是完全二叉樹，G有7個(gè)點(diǎn)，其中4個(gè)葉點(diǎn)，則G的總度數(shù)為___12______，分枝點(diǎn)數(shù)為_______3_________.6設(shè)A、B為兩個(gè)集合,A={1,2,4},B={3,4},則從AB＝______{4}______;AB＝____{1,2,3,4}_________;A－B＝______{1,2}_______.7.設(shè)R是集合A上的等價(jià)關(guān)系，則R所具有的關(guān)系的三個(gè)特性是______自反性____________,_________對(duì)稱性_________,_________傳遞性_____________.8.設(shè)命題公式G＝(P(QR))，則使公式G為真的解釋有_____（1,0,0）__________，______(1,0,1)________,________(1,1,0)________.9.設(shè)集合A＝{1,2,3,4},A上的關(guān)系R1={(1,4),(2,3),(3,2)},R1={(2,1),(3,2),(4,3)},則 R1R2=___{(1,3),(2,2),(3,1)}____,R2R1=_____{(2,4),(3,3),(4,2)}_____, R12=_______{(2,2),(3,3)}_________.10.設(shè)有限集A,B，|A|=m,|B|=n,則||(AB)|=______2^(m*n)___________.11設(shè)A,B,R是三個(gè)集合，其中R是實(shí)數(shù)集，A={x|-1≤x≤1,xR},B={x|0≤x<2,xR},則A-B=_____{x|-1≤x<0,x∈R}_______,B-A=______{x|1<x<2,x∈R}_____,A∩B=______{x|0≤x≤1,x∈R}__________,.13.設(shè)集合A＝{2,3,4,5,6}，R是A上的整除，則R以集合形式(列舉法)記為___________________{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}_________.14.設(shè)一階邏輯公式G=xP(x)xQ(x)，則G的前束范式是_____yx(P(y)Q(x))_____________.15.設(shè)G是具有8個(gè)頂點(diǎn)的樹，則G中增加__21___條邊才能把G變成完全圖。16.設(shè)謂詞的定義域?yàn)閧a,b},將表達(dá)式xR(x)→xS(x)中量詞消除，寫成與之對(duì)應(yīng)的命題公式是________(R(a)∧R(b))→(S(a)∨S(b))______________________.17.設(shè)集合A＝{1,2,3,4}，A上的二元關(guān)系R＝{(1,1),(1,2),(2,3)},S＝{(1,3),(2,3),(3,2)}。則RS＝_______{(1,3),(2,2)}________________,R2＝_____________{(1,1),(1,2),(1,3)}_______________.二、選擇題 1設(shè)集合A={2,{a},3,4}，B={{a},3,4,1}，E為全集，則下列命題正確的是(C)。 (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不具備(D). (A)自反性 (B)傳遞性 (C)對(duì)稱性 (D)反對(duì)稱性1234563設(shè)半序集(A,≤)關(guān)系≤的哈斯圖如下所示，若A的子集B={2,3,4,5},則元素6為B123456 (A)下界 (B)上界 (C)最小上界(D)以上答案都不對(duì)4下列語句中，(B)是命題。 (A)請(qǐng)把門關(guān)上(B)地球外的星球上也有人(C)x+5>6(D)下午有會(huì)嗎？5設(shè)I是如下一個(gè)解釋：D＝{a,b},則在解釋I下取真值為1的公式是(D). (A)xyP(x,y)(B)xyP(x,y) (C)xP(x,x)(D)xyP(x,y).6.若供選擇答案中的數(shù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(diǎn)的度，能畫出圖的是(C). (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).7.設(shè)G、H是一階邏輯公式，P是一個(gè)謂詞，G＝xP(x),H＝xP(x),則一階邏輯公式GH是(C). (A)恒真的(B)恒假的 (C)可滿足的(D)前束范式.8設(shè)命題公式G＝(PQ)，H＝P(QP)，則G與H的關(guān)系是(A)。abf(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));P(a,f(a))∧P(b,f(b))=P(3,f(3))∧P(2,f(2)) =P(3,2)∧P(2,3) =1∧0 =0.xyP(y,x).xyP(y,x)=x(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.設(shè)集合A＝{1,2,4,6,8,12}，R為A上整除關(guān)系。畫出半序集(A,R)的哈斯圖；寫出A的最大元，最小元，極大元，極小元；無最大元，最小元1，極大元8,12;極小元是1.寫出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.B無上界，無最小上界。下界1,2;最大下界2.6.設(shè)命題公式G=(P→Q)∨(Q∧(P→R)),求G的主析取范式。7.(9分)設(shè)一階邏輯公式：G=(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.G=(xP(x)∨yQ(y))→xR(x) =(xP(x)∨yQ(y))∨xR(x) =(xP(x)∧yQ(y))∨xR(x) =(xP(x)∧yQ(y))∨zR(z) =xyz((P(x)∧Q(y))∨R(z))9.設(shè)R是集合A={a,b,c,d}.R是A上的二元關(guān)系,R={(a,b),(b,a),(b,c),(c,d)},求出r(R),s(R),t(R)；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)}；畫出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))G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3＝(3,6,7)H=(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)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7＝(3,6,7)G,H的主析取范式相同，所以G=H.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)}.(1)試寫出R和S的關(guān)系矩陣；計(jì)算R?S,R∪S,R－1,S－1?R－1.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→Q,R→S,P∨R}蘊(yùn)涵Q∨S。證明：{P→Q,R→S,P∨R}蘊(yùn)涵Q∨S(1)P∨R P(2)R→P Q(1)(3)P→Q P(4)R→Q Q(2)(3)(5)Q→R Q(4)(6)R→S P(7)Q→S Q(5)(6)(8)Q∨S Q(7)設(shè)A,B為任意集合，證明：(A-B)-C=A-(B∪C).證明：(A-B)-C=(A∩~B)∩~C =A∩(~B∩~C) =A∩~(B∪C) =A-(B∪C)(本題10分)利用形式演繹法證明：{A∨B,C→B,C→D}蘊(yùn)涵A→D。證明：{A∨B,C→B,C→D}蘊(yùn)涵A→D(1)A D(附加)(2)A∨B P(3)B Q(1)(2)(4)C→B P(5)B→C Q(4)(6)C Q(3)(5)(7)C→D P(8)D Q(6)(7)(9)A→D D(1)(8)所以{A∨B,C→B,C→D}蘊(yùn)涵A→D.4.(本題10分)A,B為兩個(gè)任意集合，求證：A－(A∩B)=(A∪B)－B.證明：A－(A∩B)=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所以：A－(A∩B)=(A∪B)－B.離散數(shù)學(xué)試題（A卷及答案）一、（10分）某項(xiàng)工作需要派A、B、C和D4個(gè)人中的2個(gè)人去完成，按下面3個(gè)條件，有幾種派法？如何派？(1)若A去，則C和D中要去1個(gè)人；(2)B和C不能都去；(3)若C去，則D留下。解設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：ACD，(B∧C)，CD必須同時(shí)成立。因此(ACD)∧(B∧C)∧(CD)(A∨(C∧D)∨(C∧D))∧(B∨C)∧(C∨D)(A∨(C∧D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)F∨F∨(A∧C)∨F∨F∨(C∧D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F(A∧C)∨(B∧C∧D)∨(C∧D∧B)∨(C∧D)(A∧C)∨(B∧C∧D)∨(C∧D)T故有三種派法：B∧D，A∧C，A∧D。二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會(huì)議的每個(gè)成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。解：論域：所有人的集合。()：是專家；()：是工人；()：是青年人；則推理化形式為：(()∧())，()(()∧())下面給出證明：(1)()P(2)(c)T(1)，ES(3)(()∧())P(4)(c)∧(c)T(3)，US(5)(c)T(4)，I(6)(c)∧(c)T(2)(5)，I(7)(()∧())T(6)，EG三、（10分）設(shè)A、B和C是三個(gè)集合，則AB(BA)。證明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))(BA)。四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{<2，1>，<2，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，1>，<5，4>，<5，5>}。五、（10分）R是非空集合A上的二元關(guān)系，若R是對(duì)稱的，則r(R)和t(R)是對(duì)稱的。證明對(duì)任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。因R與IA對(duì)稱，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對(duì)稱的。下證對(duì)任意正整數(shù)n，Rn對(duì)稱。因R對(duì)稱，則有xR2yz(xRz∧zRy)z(zRx∧yRz)yR2x，所以R2對(duì)稱。若對(duì)稱，則xyz(xz∧zRy)z(zx∧yRz)yx，所以對(duì)稱。因此，對(duì)任意正整數(shù)n，對(duì)稱。對(duì)任意的x、y∈A，若xt(R)y，則存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，t(R)是對(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是單射。綜上可得，f－1：B→A是雙射。七、（10分）設(shè)<S，*>是一個(gè)半群，如果S是有限集，則必存在a∈S，使得a*a＝a。證明因?yàn)?lt;S，*>是一個(gè)半群，對(duì)任意的b∈S，由*的封閉性可知，b2＝b*b∈S，b3＝b2*b∈S，…，bn∈S，…。因?yàn)镾是有限集，所以必存在j＞i，使得＝。令p＝j(luò)－i，則＝*。所以對(duì)q≥i，有＝*。因?yàn)閜≥1，所以總可找到k≥1，使得kp≥i。對(duì)于∈S，有＝*＝*(*)＝…＝*。令a＝，則a∈S且a*a＝a。八、（20分）（1）若G是連通的平面圖，且G的每個(gè)面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點(diǎn)數(shù)n有如下關(guān)系：m≤(n－2)。證明設(shè)G有r個(gè)面，則2m＝≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤(n－2)。（2）設(shè)平面圖G＝<V，E，F(xiàn)>是自對(duì)偶圖，則|E|＝2(|V|－1)。證明設(shè)G*＝<V*，E*>是連通平面圖G＝<V，E，F(xiàn)>的對(duì)偶圖，則G*G，于是|F|＝|V*|＝|V|，將其代入歐拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。離散數(shù)學(xué)試題（B卷及答案）一、（10分）證明(P∨Q)∧(PR)∧(QS)S∨R證明因?yàn)镾∨RRS，所以，即要證(P∨Q)∧(PR)∧(QS)RS。(1)R附加前提(2)PRP(3)PT(1)(2)，I(4)P∨QP(5)QT(3)(4)，I(6)QSP(7)ST(5)(6)，I(8)RSCP(9)S∨RT(8)，E二、（15分）根據(jù)推理理論證明：每個(gè)考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個(gè)體域：人的集合，則命題可符號(hào)化為：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。(1)x(P(x)Q(x))P(2)x(P(x)∨Q(x))T(1)，E(3)x(P(x)∧Q(x))T(2)，E(4)P(a)∧Q(a)T(3)，ES(5)P(a)T(4)，I(6)Q(a)T(4)，I(7)x(P(x)(A(x)∨B(x))P(8)P(a)(A(a)∨B(a))T(7)，US(9)A(a)∨B(a)T(8)(5)，I(10)x(A(x)Q(x))P(11)A(a)Q(a)T(10)，US(12)A(a)T(11)(6)，I(13)B(a)T(12)(9)，I(14)P(a)∧B(a)T(5)(13)，I(15)x(P(x)∧B(x))T(14)，EG三、（10分）某班有25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)。解設(shè)A、B、C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。則：|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不會(huì)打這三種球的共5人。四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如Ai(Ai為Ai或)的集合稱為由A1、A2和A3產(chǎn)生的小項(xiàng)。試證由A1、A2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個(gè)劃分。證明小項(xiàng)共8個(gè)，設(shè)有r個(gè)非空小項(xiàng)s1、s2、…、sr(r≤8)。對(duì)任意的a∈U，則a∈Ai或a∈，兩者必有一個(gè)成立，取Ai為包含元素a的Ai或，則a∈Ai，即有a∈si，于是Usi。又顯然有siU，所以U＝si。任取兩個(gè)非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個(gè)Ai和分別出現(xiàn)在sp和sq中，于是sp∩sq＝。綜上可知，{s1，s2，…，sr}是U的一個(gè)劃分。五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的R*RR。證明(5)若R是傳遞的，則<x，y>∈R*Rz(xRz∧zSy)xRc∧cSy，由R是傳遞的得xRy，即有<x，y>∈R，所以R*RR。反之，若R*RR，則對(duì)任意的x、y、z∈A，如果xRz且zRy，則<x，y>∈R*R，于是有<x，y>∈R，即有xRy，所以R是傳遞的。六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)。證明對(duì)G的邊數(shù)m作歸納法。當(dāng)m＝0時(shí)，由于G是連通圖，所以G為平凡圖，此時(shí)n＝1，r＝1，結(jié)論自然成立。假設(shè)對(duì)邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G，并設(shè)其結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n、m和r。對(duì)e分為下列情況來討論：若e為割邊，則G有兩個(gè)連通分支G1和G2。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n＝n，m1＋m