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

1、離散數(shù)學(xué)試題(B卷答案1）一、證明題（10分）1)(ØP(ØQR)(QR)(PR)ÛR證明: 左端Û(ØPØQR)(QP)R)Û(ØPØQ)R)(QP)R)Û(Ø(PQ)R)(QP)R)Û(Ø(PQ)(QP)RÛ(Ø(PQ)(PQ)RÛTR(置換)ÛR2) $x (A(x)®B(x)Û "xA(x)®$xB(x)證明 ：$x(A(x)®B(x)Û$x(ØA(

2、x)B(x)Û$xØA(x)$xB(x)ÛØ"xA(x)$xB(x)Û"xA(x)®$xB(x)二、求命題公式(P(QR)®(PQR)的主析取范式和主合取范式（10分）。證明：(P(QR)®(PQR)ÛØ(P(QR)(PQR)Û（ØP(ØQØR)）(PQR)Û(ØPØQ)(ØPØR)(PQR)Û(ØPØQR)(ØPØQØR)(&

3、#216;PQØR)(ØPØQØR)(PQR)Ûm0m1m2m7ÛM3M4M5M6三、推理證明題（10分）1） CD， (CD)® ØE， ØE®(AØB)， (AØB)®(RS)ÞRS證明：(1) (CD)®ØE P(2) ØE®(AØB) P(3) (CD)®(AØB) T(1)(2)，I(4) (AØB)®(RS) P(5) (CD)®(RS) T(3

4、)(4)， I(6) CD P(7) RS T(5)，I 2) "x(P(x)®Q(y)R(x)，$xP(x)ÞQ(y)$x(P(x)R(x)證明(1)$xP(x) P(2)P(a) T(1)，ES(3)"x(P(x)®Q(y)R(x) P(4)P(a)®Q(y)R(a) T(3)，US(5)Q(y)R(a) T(2)(4)，I(6)Q(y) T(5)，I(7)R(a) T(5)，I(8)P(a)R(a) T(2)(7)，I(9)$x(P(x)R(x) T(8)，EG(10)Q(y)$x(P(x)R(x) T(6)(9)，I四、某班有

5、25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)（10分）。解：A，B，C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。則|A|=12，|B|=6，|C|=14，|AC|=6，|BC|=5，|ABC|=2。先求|AB|。6=|（AC）B|=|（AB）（BC）|=|（AB）|+|（BC）|-|ABC|=|（AB）|+5-2，|（AB）|=3。于是|ABC|=12+6+14-6-5-3+2=20。不會(huì)打這三種球的人數(shù)25-20=5。五、已知A、B、C是三個(gè)集合，證明A-(BC)=(A-

6、B)(A-C) （10分）。證明：xÎ A-（BC）Û xÎ AxÏ（BC）Û xÎ A（xÏBxÏC）Û（xÎ AxÏB）（xÎ AxÏC）Û xÎ（A-B）xÎ（A-C）Û xÎ（A-B）（A-C）A-（BC）=（A-B）（A-C）六、已知R、S是N上的關(guān)系，其定義如下：R=<x，y>| x，yÎNy=x2，S=<x，y>| x，yÎNy=x+1。求R-1、R*S、S*

7、R、R1，2、S1，2（10分）。解：R-1=<y，x>| x，yÎNy=x2R*S=<x，y>| x，yÎNy=x2+1S*R=<x，y>| x，yÎNy=（x+1）2，R1，2=<1，1>，<2，4>，S1，2=1，4。七、設(shè)R=<a，b>，<b，c>，<c，a>，求r(R)、s(R)和t(R) （15分）。解：r(R)=<a，b>，<b，c>，<c，a>，<a，a>，<b，b>，<c，c>s(

8、R)=<a，b>，<b，c>，<c，a>，<b，a>，<c，b>，<a，c>R2= R5=<a，c>，<b，a>，<c，b>R3=<a，a>，<b，b>，<c，b>R4=<a，b>，<b，c>，<c，c>t(R)=<a，b>，<b，c>，<c，a>，<a，c>，<b，a>，<a，a>，<b，b>，<c，b>，<c，c

9、>八、證明整數(shù)集I上的模m同余關(guān)系R=<x，y>|xºy(mod m)是等價(jià)關(guān)系。其中，xºy(mod m)的含義是x-y可以被m整除（15分）。證明：1）"xI，因?yàn)椋▁-x）/m=0，所以xºx(mod m)，即xRx。2）"x，yI，若xRy，則xºy(mod m)，即（x-y）/m=kI，所以（y - x）/m=-kI，所以yºx(mod m)，即yRx。3）"x，y，zI，若xRy，yRz，則（x-y）/m=uI，（y-z）/m=vI，于是（x-z）/m=（x-y+y-z）/m=u+v

10、I，因此xRz。九、若f:AB和g:BC是雙射，則（gf）-1=f-1g-1（10分）。證明：因?yàn)閒、g是雙射，所以gf：AC是雙射，所以gf有逆函數(shù)（gf）-1：CA。同理可推f-1g-1：CA是雙射。因?yàn)?lt;x，y>f-1g-1Û存在z（<x，z>g-1Ù<z，y>f-1）Û存在z（<y，z>fÙ<z，x>g）Û<y，x>gfÛ<x，y>（gf）-1，所以（gf）-1=f-1g-1。離散數(shù)學(xué)試題(B卷答案2）一、證明題（10分）1)(PQ)Ø

11、;(ØP(ØQØR)(ØPØQ)(ØPØR)ÛT證明: 左端Û(PQ)(P(QR)Ø(PQ)(PR)(摩根律) Û (PQ)(PQ)(PR)Ø(PQ)(PR)(分配律) Û (PQ)(PR)Ø(PQ)(PR) (等冪律) ÛT(代入)2) "x"y(P(x)®Q(y)Û Û($xP(x)®"yQ(y)證明："x"y(P(x)®Q(y)Û&

12、quot;x"y(ØP(x)Q(y)Û"x(ØP(x)"yQ(y)Û"xØP(x)"yQ(y)ÛØ$xP(x)"yQ(y)Û($xP(x)®"yQ(y)二、求命題公式(ØP®Q)®(PØQ) 的主析取范式和主合取范式（10分）解：(ØP®Q)®(PØQ)ÛØ(ØP®Q)(PØQ)ÛØ(PQ

13、)(PØQ)Û(ØPØQ)(PØQ) Û(ØPPØQ)(ØQPØQ)Û(PØQ)ÛM1Ûm0m2m3三、推理證明題（10分）1)(P®(Q®S)(ØRP)QÞR®S證明：(1)R(2)ØRP(3)P(4)P®(Q®S)(5)Q®S(6)Q(7)S(8)R®S2) $x(A(x)®"yB(y)，"x(B(x)®$yC(y

14、)"xA(x)®$yC(y)。證明：(1)$x(A(x)®"yB(y) P (2)A(a)®"yB(y) T(1)，ES(3)"x(B(x)®$yC(y) P(4)"x(B(x)®C() T(3)，ES(5)B()®C() T(4)，US(6)A(a)®B() T(2)，US(7)A(a)®C() T(5)(6)，I(8)"xA(x)®C() T(7)，UG(9)"xA(x)®$yC(y) T(8)，EG四、只要今天天氣不好，

15、就一定有考生不能提前進(jìn)入考場(chǎng)，當(dāng)且僅當(dāng)所有考生提前進(jìn)入考場(chǎng)，考試才能準(zhǔn)時(shí)進(jìn)行。所以，如果考試準(zhǔn)時(shí)進(jìn)行，那么天氣就好（15分）。解 設(shè)P：今天天氣好，Q：考試準(zhǔn)時(shí)進(jìn)行，A(e)：e提前進(jìn)入考場(chǎng)，個(gè)體域：考生的集合，則命題可符號(hào)化為：ØP®$xØA(x)，"xA(x)«QQ®P。(1)ØP®$xØA(x) P(2)ØP®Ø"xA(x) T(1)，E(3)"xA(x)®P T(2)，E (4)"xA(x)«Q P(5)("

16、xA(x)®Q)(Q®"xA(x) T(4)，E(6)Q®"xA(x) T(5)，I(7)Q®P T(6)(3)，I五、已知A、B、C是三個(gè)集合，證明A(BC)=(AB)(AC) （10分）證明：xÎ A（BC）Û xÎ AxÎ（BC）Û xÎ A（xÎBxÎC）Û（ xÎ AxÎB）（xÎ AxÎC）Û xÎ（AB）xÎ ACÛ xÎ（AB）（AC）A（B

17、C）=（AB）（AC）六、A= x1,x2,x3 ，B= y1,y2，R=<x1, y1>,<x2, y2>,<x3, y2>，求其關(guān)系矩陣及關(guān)系圖（10分）。七、設(shè)R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>，求r(R)、s(R)和t(R)，并作出它們及R的關(guān)系圖（15分）。解：r(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,&

18、lt;2,2>,<3,3>,<4,4>,<5,5>s(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>R2=R5=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>R3=<2,1>,<2,5>,<2,4>,<3,4>,&l

19、t;4,4>,<5,2>,<5,4>R4=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>t(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>八、設(shè)R1是A上的等價(jià)關(guān)系，R2是B上的等價(jià)關(guān)系，AÆ且BÆ。關(guān)系R滿足：<<x1

20、，y1>，<x2，y2>>RÛ<x1，x2>R1且<y1，y2>R2，證明R是A×B上的等價(jià)關(guān)系（10分）。證明 對(duì)任意的<x，y>A×B，由R1是A上的等價(jià)關(guān)系可得<x，x>R1，由R2是B上的等價(jià)關(guān)系可得<y，y>R2。再由R的定義，有<<x，y>，<x，y>>R，所以R是自反的。對(duì)任意的<x，y>、<u，v>A×B，若<x，y>R<u，v>，則<x，u>R1且<y，

21、v>R2。由R1對(duì)稱得<u，x>R1，由R2對(duì)稱得<v，y>R2。再由R的定義，有<<u，v>，<x，y>>R，即<u，v>R<x，y>，所以R是對(duì)稱的。對(duì)任意的<x，y>、<u，v>、<s，t>A×B，若<x，y>R<u，v>且<u，v>R<s，t>，則<x，u>R1且<y，v>R2，<u，s>R1且<v，t>R2。由<x，u>R1、<u，s&g

22、t;R1及R1的傳遞性得<x，s>R1，由<y，v>R2、<v，t>R2及R2的傳遞性得<y，t>R1。再由R的定義，有<<x，y>，<s，t>>R，即<x，y>R<s，t>，所以R是傳遞的。綜上可得，R是A×B上的等價(jià)關(guān)系。九、設(shè)f：A®B，g：B®C，h：C®A，證明：如果hogofIA，fohogIB，gofohIC，則f、g、h均為雙射，并求出f1、g1和h1（10分）。解 因IA恒等函數(shù)，由hogofIA可得f是單射，h是滿射；因IB恒等

23、函數(shù)，由fohogIB可得g是單射，f是滿射；因IC恒等函數(shù)，由gofohIC可得h是單射，g是滿射。從而f、g、h均為雙射。由hogofIA，得f1hog；由fohogIB，得g1foh；由gofohIC，得h1gof。離散數(shù)學(xué)試題(B卷答案3）一、（10分）判斷下列公式的類型（永真式、永假式、可滿足式）？(寫(xiě)過(guò)程)1)P®(PQR) 2)Ø(Q®P)ØP)(PR) 3)(ØPQ)®R)®(PQ)R)解：1)重言式；2)矛盾式；3)可滿足式二、（10分）求命題公式（P(QR)®(PQR)的主析取范式，并求成真賦值

24、。解：（P(QR)®(PQR)ÛØ(P(QR)PQRÛØP(ØQØR)PQRÛ(ØPØQ)(ØPØR)(PQ)RÛ(Ø(PQ)(PQ)(ØPØR)RÛ1(ØPØR)R)Û1Ûm0m1m2m3m4m5m6m7該式為重言式，全部賦值都是成真賦值。三、（10分）證明 (PQA)®C)(A®(PQC)Û(A(P«Q)®C證明：(PQA)®

25、;C)(A®(PQC)Û(Ø(PQA)C)(ØA(PQC)Û(ØPØQØA)C)(ØAPQ)C)Û(ØPØQØA)(ØAPQ)CÛØ(ØPØQØA)(ØAPQ)®CÛ(Ø(ØPØQØA)Ø(ØAPQ)®CÛ(PQA)(AØPØQ)®CÛ(A(PQ)(Ø

26、;PØQ)®CÛ(A(PØQ)(ØPQ)®CÛ(A(Q®P)(P®Q)®CÛ(A(P«Q)®C四、（10分）個(gè)體域?yàn)?，2，求"x$y（x+y=4）的真值。解："x$y（x+y=4）Û"x（x+1=4）（x+2=4）Û（1+1=4）（1+2=4）（2+1=4）（2+2=4）Û（00）（01）Û01Û0五、（10分）對(duì)于任意集合A，B，試證明：P(A)P(B)=P(AB)解："x

27、ÎP(A)P(B)，xÎP(A)且xÎP(B)，有xÍA且xÍB，從而xÍAB，xÎP(AB)，由于上述過(guò)程可逆，故P(A)P(B)=P(AB)六、（10分）已知A=1，2，3，4，5和R=<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，求r(R)、s(R)和t(R)。解：r(R)=<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<

28、;3，3>，<4，4>，<5，5>s(R)=<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>t(R)=<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2，4>，<1，4>七、（10分）設(shè)函數(shù)f：R×R®R×R，R為實(shí)數(shù)集，f定義

29、為：f(<x，y>)=<x+y，x-y>。1)證明f是雙射。解：1）"<x1，y1>，<x2，y2>R×R，若f(<x1，y1>)=f(<x2，y2>)，即<x1+y1，x1-y1>=<x2+y2，x2-y2>，則x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2從而f是單射。2）"<p，q>R×R，由f(<x，y>)=<p，q>，通過(guò)計(jì)算可得x=(p+q)/2；y=(p-q)/2；從而<p，q&g

30、t;的原象存在，f是滿射。八、（10分）<G，*>是個(gè)群，uG，定義G中的運(yùn)算“D”為aDb=a*u-1*b，對(duì)任意a，bG，求證：<G， D>也是個(gè)群。證明：1）"a，bG，aDb=a*u-1*bG，運(yùn)算是封閉的。2）"a，b，cG，（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD（bDc），運(yùn)算是可結(jié)合的。3）"aG，設(shè)E為D的單位元，則aDE=a*u-1*E=a，得E=u，存在單位元u。4）"aG，aDx=a*u-1*x=E，x=u*a-1*u，則xDa=u*a-1*u*u-1*a=u=E

31、，每個(gè)元素都有逆元。所以<G， D>也是個(gè)群。九、（10分）已知：D=<V，E>，V=1，2，3，4，5，E=<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>，求D的鄰接距陣A和可達(dá)距陣P。解：1）D的鄰接距陣A和可達(dá)距陣P如下：01010111110010011111A=00011P=1111100000000001000011111十、（10分）求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹(shù)及其權(quán)。解：最優(yōu)二叉樹(shù)為權(quán)(2+4)×4+6×3+1

32、2×2+(8+10)×3+14×2148離散數(shù)學(xué)試題(B卷答案4）一、證明題（10分）1)(PQ)Ø(ØP(ØQØR)(ØPØQ)(ØPØR)ÛT證明: 左端Û(PQ)(P(QR)Ø(PQ)(PR)(摩根律) Û (PQ)(PQ)(PR)Ø(PQ)(PR)(分配律) Û (PQ)(PR)Ø(PQ)(PR) (等冪律) ÛT(代入)2)"x(P(x)®Q(x)"xP(x)

33、9;"x(P(x)Q(x)證明："x(P(x)®Q(x)"xP(x)Û"x(P(x)®Q(x)P(x)Û"x(ØP(x)Q(x)P(x)Û"x(P(x)Q(x)Û"xP(x)"xQ(x)Û"x(P(x)Q(x)二、求命題公式(ØP®Q)®(PØQ) 的主析取范式和主合取范式（10分）解：(ØP®Q)®(PØQ)ÛØ(Ø

34、P®Q)(PØQ)ÛØ(PQ)(PØQ)Û(ØPØQ)(PØQ) Û(ØPPØQ)(ØQPØQ)Û(PØQ)ÛM1Ûm0m2m3三、推理證明題（10分）1)(P®(Q®S)(ØRP)QÞR®S證明：（1）R 附加前提(2)ØRP P(3)P T(1)(2),I(4)P®(Q®S) P(5)Q®S T(3)(4),I(6)Q P(

35、7)S T(5)(6),I(8)R®S CP2) "x(P(x)Q(x)，"xØP(x)Þ$x Q(x)證明：(1)"xØP(x) P(2)ØP(c) T(1),US(3)"x(P(x)Q(x) P(4)P(c)Q(c) T(3),US(5)Q(c) T(2)(4),I(6)$x Q(x) T(5),EG四、例5在邊長(zhǎng)為1的正方形內(nèi)任意放置九個(gè)點(diǎn)，證明其中必存在三個(gè)點(diǎn)，使得由它們組成的三角形（可能是退化的）面積不超過(guò)1/8（10分）。證明：把邊長(zhǎng)為1的正方形分成四個(gè)全等的小正方形，則至少有一個(gè)小正方形內(nèi)有

36、三個(gè)點(diǎn)，它們組成的三角形（可能是退化的）面積不超過(guò)小正方形的一半，即1/8。五、已知A、B、C是三個(gè)集合，證明A(BC)=(AB)(AC) （10分）證明：xÎ A（BC）Û xÎ AxÎ（BC）Û xÎ A（xÎBxÎC）Û（ xÎ AxÎB）（xÎ AxÎC）Û xÎ（AB）xÎ ACÛ xÎ（AB）（AC）A（BC）=（AB）（AC）六、p=A1，A2，An是集合A的一個(gè)劃分，定義R=<a，b>|a

37、、bAi，I=1，2，n，則R是A上的等價(jià)關(guān)系（15分）。證明："aA必有i使得aAi，由定義知aRa，故R自反。"a,bA，若aRb ，則a,bAi，即b,aAi，所以bRa，故R對(duì)稱。"a,b,cA，若aRb 且bRc，則a,bAi及b,cAj。因?yàn)閕j時(shí)AiAj=F，故i=j，即a,b,cAi，所以aRc，故R傳遞。總之R是A上的等價(jià)關(guān)系。七、若f:AB是雙射，則f-1:BA是雙射（15分）。證明:對(duì)任意的xA，因?yàn)閒是從A到B的函數(shù)，故存在yB，使<x,y>f，<y,x>f-1。所以,f-1是滿射。對(duì)任意的xA，若存在y1,y2B，

38、使得<y1,x>f-1且<y2,x>f-1,則有<x,y1>f且<x,y2>f。因?yàn)閒是函數(shù)，則y1=y2。所以，f-1是單射。因此f-1是雙射。八、設(shè)<G，*>是群，<A，*>和<B，*>是<G，*>的子群，證明：若ABG，則AG或BG（10分）。證明 假設(shè)AG且BG，則存在aÎA，aÏB，且存在bÎB，bÏA（否則對(duì)任意的aÎA，aÎB，從而AÍB，即ABB，得BG，矛盾。）對(duì)于元素a*bÎG，若a*bÎA

39、，因A是子群，a-1ÎA，從而a-1 * (a*b)b ÎA，所以矛盾，故a*bÏA。同理可證a*bÏB，綜合有a*bÏABG。綜上所述，假設(shè)不成立，得證AG或BG。九、若無(wú)向圖G是不連通的，證明G的補(bǔ)圖是連通的（10分）。證明 設(shè)無(wú)向圖G是不連通的，其k個(gè)連通分支為、。任取結(jié)點(diǎn)、G，若和不在圖G的同一個(gè)連通分支中，則，不是圖G的邊，因而，是圖的邊；若和在圖G的同一個(gè)連通分支中，不妨設(shè)其在連通分支（1）中，在不同于的另一連通分支上取一結(jié)點(diǎn)，則，和，都不是圖G的邊，因而，和，都是的邊。綜上可知，不管那種情況，和都是可達(dá)的。由和的任意性可知，是連通

40、的。離散數(shù)學(xué)試題（B卷答案5）一、（10分）求命題公式Ø(PQ)«Ø(ØP®R)的主合取范式。解：Ø(PQ)«Ø(ØP®R)Û（Ø(PQ)®Ø(ØP®R)）（Ø(ØP®R)®Ø(PQ)）Û（(PQ)(ØPØR)）（(PR)(ØPØQ)）Û(PQ)(ØPØR)Û(PØR)（QØP）

41、（QØR）Û(PQØR)(PØQØR)（ØPQR）（ØPQØR）ÛM1M3M4M5二、（8分）敘述并證明蘇格拉底三段論解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號(hào)化：F（x）：x是一個(gè)人。G（x）：x要死的。A：蘇格拉底。命題符號(hào)化為"x（F（x）®G（x），F(xiàn)（a）ÞG（a）證明：（1）"x(F(x)®G(x) P（2）F(a)®G(a) T(1),US（3）F(a) P（4）G(a) T(2)(3),I三、（8分）已知A、B

42、、C是三個(gè)集合，證明A(BC)=(AB)(AC)證明：xÎ A（BC）Û xÎ AxÎ（BC）Û xÎ A（xÎBxÎC）Û（ xÎ AxÎB）（xÎ AxÎC） Û xÎ（AB）xÎ AC Û xÎ（AB）（AC） A（BC）=（AB）（AC）四、（10分）已知R和S是非空集合A上的等價(jià)關(guān)系，試證：1）RS是A上的等價(jià)關(guān)系；2）對(duì)aA，aRS=aRaS。解："xA，因?yàn)镽和S是自反關(guān)系，所以<x,x

43、>R、<x,x>S，因而<x,x>RS，故RS是自反的。"x、yA，若<x,y>RS，則<x,y>R、<x,y>S，因?yàn)镽和S是對(duì)稱關(guān)系，所以因<y,x>R、<y,x>S，因而<y,x>RS，故RS是對(duì)稱的。"x、y、zA，若<x,y>RS且<y,z>RS，則<x,y>R、<x,y>S且<y,z>R、<y,z>S，因?yàn)镽和S是傳遞的，所以因<x,z>R、<x,z>S，因而<

44、x,z>RS，故RS是傳遞的。總之RS是等價(jià)關(guān)系。2）因?yàn)閤aRSÛ<x,a>RSÛ<x,a>R<x,a>SÛ xaRxaSÛ xaRaS所以aRS=aRaS。五、(10分) 設(shè)Aa，b，c，d，R是A上的二元關(guān)系，且R<a，b>，<b，a>，<b，c>，<c，d>，求r(R)、s(R)和t(R)。解 r(R)RIA<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<

45、c，c>，<d，d>s(R)RR-1<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>R2<a，a>，<a，c>，<b，b>，<b，d>R3<a，b>，<a，d>，<b，a>，<b，c>R4<a，a>，<a，c>，<b，b>，<b，d>R2t(R)<a，b>，<b，a>，<b，c>，<c，d>，&

46、lt;a，a>，<a，c>，<b，b>，<b，d>，<a，d>六、(15分) 設(shè)A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C®B×D且"<a,c>A×C，h(<a,c>)<f(a),g(c)>。證明h是雙射。證明：1）先證h是滿射。"<b,d>B×D，則bB，dD，因?yàn)閒是A到B的雙射，g是C到D的雙射，所以存在aA，cC，使得f(a)=b，f(c)=d，亦即存在<a,c>A×

47、C，使得h(<a,c>)<f(a),g(c)><b,d>，所以h是滿射。2）再證h是單射。"<a1,c1>、<a2,c2>A×C，若h(<a1,c1>)h(<a2,c2>)，則<f(a1),g(c1)><f(a2),g(c2)> ，所以f(a1)f(a2)，g(c1)g(c2)，因?yàn)閒是A到B的雙射，g是C到D的雙射，所以a1a2，c1c2，所以<a1,c1><a2,c2>，所以h是單射。綜合1）和2），h是雙射。七、(12分)設(shè)<G，*

48、>是群，H是G的非空子集，證明<H，*>是<G，*>的子群的充要條件是若a，bÎH，則有a*b-1ÎH。證明：Þ "a,bH有b-1H，所以a*b-1H。Ü"aH，則e=a*a-1H a-1=e*a-1H a,bH及b-1H，a*b=a*（b-1）-1HHÍG且HF,*在H上滿足結(jié)合律 <H，*>是<G，*>的子群。八、（10分）設(shè)G=<V，E>是簡(jiǎn)單的無(wú)向平面圖，證明G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。解：設(shè)G的每個(gè)結(jié)點(diǎn)的度數(shù)都大于等于6，則2|E|=Sd(v

49、)6|V|，即|E|3|V|，與簡(jiǎn)單無(wú)向平面圖的|E|3|V|-6矛盾，所以G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。九.G=<A,*>,A=a,b,c,*的運(yùn)算表為：(寫(xiě)過(guò)程，7分) （1）G是否為阿貝爾群？（2）找出G的單位元；（3）找出G的冪等元（4）求b的逆元和c的逆元解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b) (b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c) 所以G是阿貝爾群 （2）因?yàn)閍*a=a a*b=b*a=b a*c=c*a=c 所以G的單位元是a （3）

50、因?yàn)閍*a=a 所以G的冪等元是a （4）因?yàn)閎*c=c*b=a，所以b的逆元是c且c的逆元是b 十、(10分)求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹(shù)及其權(quán)。解：最優(yōu)二叉樹(shù)為權(quán)148 離散數(shù)學(xué)試題（B卷答案6）一、（20分）用公式法判斷下列公式的類型：(1)(ØPØQ)®(P«ØQ)(2)(P¯Q)®(PØ(QØR)解：（1）因?yàn)?ØPØQ)®(P«ØQ)ÛØ(ØPØQ)(PØQ)(&#

51、216;PQ)Û(PQ)(PØQ)(ØPQ)ÛÛ所以，公式(ØPØQ)®(P«ØQ)為可滿足式。（2）因?yàn)?P¯Q)®(PØ(QØR)ÛØ(Ø( PQ)(PØQR)Û(PQ)(PØQR)Û(PQP)(PQØQ)(PQR)Û(PQ)(PQR)Û(PQ(RØR)(PQR)Û(PQR)(PQØR)(PQR)ÛÛ所以

52、，公式(P¯Q)®(PØ(QØR)為可滿足式。二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：每個(gè)科學(xué)家都是勤奮的，每個(gè)勤奮又身體健康的人在事業(yè)中都會(huì)獲得成功。存在著身體健康的科學(xué)家。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。解：論域：所有人的集合。()：是勤奮的；()：是身體健康的；()：是科學(xué)家；()：是事業(yè)獲得成功的人；()：是事業(yè)半途而廢的人；則推理化形式為：()®()，()()®()，()()()()下面給出證明：(1)()() P(2)()() T(1)，ES(3)()®() P(4)()®() T

53、(1)，US(5)() T(2)，I(6)() T(4)(5)，I(7)() T(2)，I(8)()() T(6)(7)，I(9)()()®() P(10)()()®() T(9)，Us(11)() T(8)(10)，I(12)() T(11)，EG(13)()() T(12)，I三、（10分）設(shè)AÆ，1，1，B0，0，求P(A)、P(B)0、P(B)ÅB。解 P(A)Æ，Æ，1，1，Æ，1，Æ，1，1，1，Æ，1，1P(B)0Æ，0，0，0，00Æ，0，0，0，0P(B)Å

54、BÆ，0，0，0，0Å0，0Æ，0，0，0，0四、（15分）設(shè)R和S是集合A上的任意關(guān)系，判斷下列命題是否成立？(1)若R和S是自反的，則R*S也是自反的。(2)若R和S是反自反的，則R*S也是反自反的。(3)若R和S是對(duì)稱的，則R*S也是對(duì)稱的。(4)若R和S是傳遞的，則R*S也是傳遞的。(5)若R和S是自反的，則RS是自反的。(6)若R和S是傳遞的，則RS是傳遞的。解 (1)成立。對(duì)任意的，因?yàn)镽和S是自反的，則<，>R，<，>S，于是<，>R*S，故R*S也是自反的。(2)不成立。例如，令1，2，R<1，2>，

55、S<2，1>，則R和S是反自反的，但R*S<1，1>不是反自反的。(3)不成立。例如，令1，2，3，R<1，2>，<2，1>，<3，3>，S<2，3>，<3，2>，則R和S是對(duì)稱的，但R*S<1，3>，<3，2>不是對(duì)稱的。(4)不成立。例如，令1，2，3，R<1，2>，<2，3>，<1，3>，S<2，3>，<3，1>，<2，1>，則R和S是傳遞的，但R*S<1，3>，<1，1>，<2，

56、1>不是傳遞的。(5)成立。對(duì)任意的，因?yàn)镽和S是自反的，則<，>R，<，>S，于是<，>RS，所以RS是自反的。五、（15分）令Xx1，x2，xm，Yy1，y2，yn。問(wèn)(1)有多少個(gè)不同的由X到Y(jié)的函數(shù)？(2)當(dāng)n、m滿足什么條件時(shí)，存在單射，且有多少個(gè)不同的單射？(3)當(dāng)n、m滿足什么條件時(shí)，存在雙射，且有多少個(gè)不同的雙射？解 (1)由于對(duì)X中每個(gè)元素可以取Y中任一元素與其對(duì)應(yīng)，每個(gè)元素有n種取法，所以不同的函數(shù)共nm個(gè)。(2)顯然當(dāng)|m|n|時(shí)，存在單射。由于在Y中任選m個(gè)元素的任一全排列都形成X到Y(jié)的不同的單射，故不同的單射有m!n(n1)(

57、nm1)個(gè)。(3)顯然當(dāng)|m|n|時(shí)，才存在雙射。此時(shí)Y中元素的任一不同的全排列都形成X到Y(jié)的不同的雙射，故不同的雙射有m!個(gè)。六、（5分）集合X上有m個(gè)元素，集合Y上有n個(gè)元素，問(wèn)X到Y(jié)的二元關(guān)系總共有多少個(gè)？解 X到Y(jié)的不同的二元關(guān)系對(duì)應(yīng)X×Y的不同的子集，而X×Y的不同的子集共有個(gè)，所以X到Y(jié)的二元關(guān)系總共有個(gè)。七、（10分）若<G，*>是群，則對(duì)于任意的a、bG，必有惟一的xG使得a*xb。證明 設(shè)e是群<G，*>的幺元。令xa1*b，則a*xa*(a1*b)(a*a1)*be*bb。所以，xa1*b是a*xb的解。若x¢G也是a*

58、xb的解，則x¢e*x¢(a1*a)*x¢a1*(a*x¢)a1*bx。所以，xa1*b是a*xb的惟一解。八、（10分）給定連通簡(jiǎn)單平面圖G<V，E，F(xiàn)>，且|V|6，|E|12。證明：對(duì)任意fF，d(f)3。證明 由偶拉公式得|V|E|F|2，所以|F|2|V|E|8，于是2|E|24。若存在fF，使得d(f)3，則3|F|2|E|24，于是|F|8，與|F|8矛盾。故對(duì)任意fF，d(f)3。離散數(shù)學(xué)試題（B卷答案7）一、（15分）設(shè)計(jì)一盞電燈的開(kāi)關(guān)電路，要求受3個(gè)開(kāi)關(guān)A、B、C的控制：當(dāng)且僅當(dāng)A和C同時(shí)關(guān)閉或B和C同時(shí)關(guān)閉時(shí)燈亮。設(shè)F表

59、示燈亮。(1)寫(xiě)出F在全功能聯(lián)結(jié)詞組­中的命題公式。(2)寫(xiě)出F的主析取范式與主合取范式。解 (1)設(shè)A：開(kāi)關(guān)A關(guān)閉；B：開(kāi)關(guān)B關(guān)閉；C：開(kāi)關(guān)C關(guān)閉；F(AC)(BC)。在全功能聯(lián)結(jié)詞組­中：ØAÛØ(AA)ÛA­AACÛØØ( AC)ÛØ( A­C)Û(A­C)­(A­C) ABÛØ(ØAØB)ÛØ( A­A)(B­B)Û( A

60、3;A)­(B­B)所以FÛ(A­C)­(A­C)(B­C)­(B­C)Û(A­C)­(A­C)­(A­C)­(A­C)­(B­C)­(B­C)­(B­C)­(B­C)(2)FÛ(AC)(BC) Û(A(BØB)C)(AØA)BC)Û(ABC)(AØBC)(ABC)(ØABC)&

61、#219; 主析取范式Û 主合取范式二、（10分）判斷下列公式是否是永真式？(1)($xA(x)®$xB(x)®$x(A(x)®B(x)。(2)("xA(x)®"xB(x)®"x(A(x)®B(x)。解 (1)($xA(x)®$xB(x)®$x(A(x)®B(x)Û(Ø$xA(x)$xB(x)®$x(A(x)®B(x)ÛØ(Ø$xA(x)$xB(x)$x(ØA(x)B(x)Û(

62、$xA(x)Ø$xB(x)$xØA(x)$xB(x)Û($xA(x)$xØA(x)$xB(x)(Ø$xB(x)$xØA(x)$xB(x)Û$x(A(x)ØA(x)$xB(x)ÛT 所以，($xA(x)®$xB(x)®$x(A(x)®B(x)為永真式。(2)設(shè)論域?yàn)?，2，令A(yù)(1)T；A(2)F；B(1)F；B(2)T。則"xA(x)為假，"xB(x)也為假，從而"xA(x)®"xB(x)為真；而由于A(1)®B(1

63、)為假，所以"x(A(x)®B(x)也為假，因此公式("xA(x)®"xB(x)®"x(A(x)®B(x)為假。該公式不是永真式。三、（15分）設(shè)X為集合，AP(X)ÆX且AÆ，若|X|n，問(wèn)(1)偏序集<A，Í>是否有最大元？(2)偏序集<A，Í>是否有最小元？(3)偏序集<A，Í>中極大元和極小元的一般形式是什么？并說(shuō)明理由。解 偏序集<A，Í>不存在最大元和最小元，因?yàn)閚2。考察P(X)的哈斯圖，最底層

64、的頂點(diǎn)是空集，記作第0層，由底向上，第一層是單元集，第二層是二元集，由|X|n，則第n1層是X的n1元子集，第n層是X。偏序集<A，Í>與偏序集<P(X)，Í>相比，恰好缺少第0層和第n層。因此<A，Í>的極小元就是X的所有單元集，即x，xX；而極大元恰好是比X少一個(gè)元素，即Xx，xX。四、（10分）設(shè)A1，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(

65、R)RIA<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>s(R)RR1<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>，