千里之行，始于足下。第2頁(yè)/共2頁(yè)精品文檔推薦離散數(shù)學(xué)期末考試試題及答案離散數(shù)學(xué)試題(B卷答案1）

一、證明題（10分）

1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R

證明:左端?(?P∧?Q∧R)∨((Q∨P)∧R)

?((?P∧?Q)∧R))∨((Q∨P)∧R)

?(?(P∨Q)∧R)∨((Q∨P)∧R)

?(?(P∨Q)∨(Q∨P))∧R

?(?(P∨Q)∨(P∨Q))∧R

?T∧R(置換)?R

2)?x(A(x)→B(x))??xA(x)→?xB(x)

證明：?x(A(x)→B(x))??x(?A(x)∨B(x))

??x?A(x)∨?xB(x)

???xA(x)∨?xB(x)

??xA(x)→?xB(x)

二、求命題公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。

證明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R))

?（?P∧(?Q∨?R)）∨(P∧Q∧R)

?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R)

?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R)

?m0∨m1∨m2∨m7

?M3∨M4∨M5∨M6

三、推理證明題（10分）

1）C∨D，(C∨D)→?E，?E→(A∧?B)，(A∧?B)→(R∨S)?R∨S證明：(1)(C∨D)→?EP

(2)?E→(A∧?B)P

(3)(C∨D)→(A∧?B)T(1)(2)，I

(4)(A∧?B)→(R∨S)P

(5)(C∨D)→(R∨S)T(3)(4)，I

(6)C∨DP

(7)R∨ST(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

四、某班有25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不可能打這三種球的人數(shù)（10分）。

解：A，B，C分不表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。則|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=5，|A∩B∩C|=2。

先求|A∩B|。

∵6=|（A∪C）∩B|=|（A∩B）∪（B∩C）|=|（A∩B）|+|（B∩C）|-|A∩B∩C|=|（A∩B）|+5-2，∴|（A∩B）|=3。

于是|A∪B∪C|=12+6+14-6-5-3+2=20。不可能打這三種球的人數(shù)25-20=5。

五、已知A、B、C是三個(gè)集合，證明A-(B∪C)=(A-B)∩(A-C)（10分）。

證明：∵x∈A-（B∪C）?x∈A∧x?（B∪C）

?x∈A∧（x?B∧x?C）

?（x∈A∧x?B）∧（x∈A∧x?C）

?x∈（A-B）∧x∈（A-C）

?x∈（A-B）∩（A-C）

∴A-（B∪C）=（A-B）∩（A-C）

六、已知R、S是N上的關(guān)系，其定義如下：R={|x，y∈N∧y=x2}，S={|x，y∈N∧y=x+1}。求R-1、R*S、S*R、R{1，2}、S[{1，2}]（10分）。

解：R-1={|x，y∈N∧y=x2}

R*S={|x，y∈N∧y=x2+1}

S*R={|x，y∈N∧y=（x+1）2}，R{1，2}={，}，S[{1，2}]={1，4}。

七、設(shè)R={，，}，求r(R)、s(R)和t(R)（15分）。

解：r(R)={，，，，，}

s(R)={，，，，，}

R2=R5={，，}

R3={，，}

R4={，，}

t(R)={，，，，，，，，，}

八、證明整數(shù)集I上的模m同余關(guān)系R={|x≡y(modm)}是等價(jià)關(guān)系。其中，x≡y(modm)的含義是x-y能夠被m整除（15分）。

證明：1）?x∈I，因?yàn)椋▁-x）/m=0，因此x≡x(modm)，即xRx。

2）?x，y∈I，若xRy，則x≡y(modm)，即（x-y）/m=k∈I，因此（y-x）/m=-k∈I，因此y≡x(modm)，即yRx。

3）?x，y，z∈I，若xRy，yRz，則（x-y）/m=u∈I，（y-z）/m=v∈I，于是（x-z）/m=（x-y+y-z）/m=u+v∈I，所以xRz。

九、若f:A→B和g:B→C是雙射，則（gf）-1=f-1g-1（10分）。

證明：因?yàn)閒、g是雙射，因此gf：A→C是雙射，因此gf有逆函數(shù)（gf）-1：C→A。同理可推f-1g-1：C→A是雙射。

因?yàn)椤蔲-1g-1?存在z（∈g-1∧∈f-1）?存在z（∈f∧∈g）?∈gf?∈（gf）-1，因此（gf）-1=f-1g-1。

離散數(shù)學(xué)試題(B卷答案2）

一、證明題（10分）

1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T

證明:左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律)

?((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律)

?((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(等冪律)

?T(代入)

2)?x?y(P(x)→Q(y))??(?xP(x)→?yQ(y))

證明：?x?y(P(x)→Q(y))??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)

??(P∨Q)∨(P∨?Q)

?(?P∧?Q)∨(P∨?Q)

?(?P∨P∨?Q)∧(?Q∨P∨?Q)

?(P∨?Q)

?M1

?m0∨m2∨m3

三、推理證明題（10分）

1)(P→(Q→S))∧(?R∨P)∧Q?R→S

證明：(1)R

(2)?R∨P

(3)P

(4)P→(Q→S)

(5)Q→S

(6)Q

(7)S

(8)R→S

2)?x(A(x)→?yB(y))，?x(B(x)→?yC(y))?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(c))T(3)，ES

(5)B(b)→C(c)T(4)，US

(6)A(a)→B(b)T(2)，US

(7)A(a)→C(c)T(5)(6)，I

(8)?xA(x)→C(c)T(7)，UG

(9)?xA(x)→?yC(y)T(8)，EG

四、只要今天天氣不行，就一定有考生別能提早進(jìn)入考場(chǎng)，當(dāng)且僅當(dāng)所有考生提早進(jìn)入考場(chǎng)，考試才干準(zhǔn)時(shí)舉行。因此，假如考試準(zhǔn)時(shí)舉行，這么天氣就好（15分）。

解設(shè)P：今天天氣好，Q：考試準(zhǔn)時(shí)舉行，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)→PT(2)，E

(4)?xA(x)?QP

(5)(?xA(x)→Q)∧(Q→?xA(x))T(4)，E

(6)Q→?xA(x)T(5)，I

(7)Q→PT(6)(3)，I

五、已知A、B、C是三個(gè)集合，證明A∩(B∪C)=(A∩B)∪(A∩C)（10分）

證明：∵x∈A∩（B∪C）?x∈A∧x∈（B∪C）?x∈A∧（x∈B∨x∈C）?（x∈A∧x∈B）∨（x∈A∧x∈C）?x∈（A∩B）∨x∈A∩C?x∈（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）

六、A={x1,x2,x3}，B={y1,y2}，R={,,}，求其關(guān)系矩陣及關(guān)系圖（10分）。

七、設(shè)R={,,,,,}，求r(R)、s(R)和t(R)，并作出它們及R的關(guān)系圖（15分）。

解：r(R)={,,,,,,,,

,,}

s(R)={,,,,,,,,}

R2=R5={,,,,,,}

R3={,,,,,,}

R4={,,,,,,}

t(R)={,,,,,,,,,}

八、設(shè)R1是A上的等價(jià)關(guān)系，R2是B上的等價(jià)關(guān)系，A≠?且B≠?。關(guān)系R滿(mǎn)腳：，>∈R?∈R1且∈R2，證明R是A×B上的等價(jià)關(guān)系（10分）。

證明對(duì)任意的∈A×B，由R1是A上的等價(jià)關(guān)系可得∈R1，由R2是B上的等價(jià)關(guān)系可得∈R2。再由R的定義，有，>∈R，因此R是自反的。

對(duì)任意的、∈A×B，若R，則∈R1且∈R2。由R1對(duì)稱(chēng)得∈R1，由R2對(duì)稱(chēng)得∈R2。再由R的定義，有，>∈R，即R，因此R是對(duì)稱(chēng)的。

對(duì)任意的、、∈A×B，若R且R，則∈R1且∈R2，∈R1且∈R2。由∈R1、∈R1及R1的傳遞性得∈R1，由∈R2、∈R2及R2的傳遞性得∈R1。再由R的定義，有，>∈R，即R，因此R是傳遞的。

綜上可得，R是A×B上的等價(jià)關(guān)系。

九、設(shè)f：A→B，g：B→C，h：C→A，證明：假如hgf＝IA，fhg＝IB，gfh＝IC，則f、

g、h均為雙射，并求出f－1、g－1和h－1（10分）。

解因IA恒等函數(shù)，由hgf＝IA可得f是單射，h是滿(mǎn)射；因IB恒等函數(shù)，由fhg＝IB可得g是單射，f是滿(mǎn)射；因IC恒等函數(shù)，由gfh＝IC可得h是單射，g是滿(mǎn)射。從而f、g、h均為雙射。

由hgf＝IA，得f－1＝hg；由fhg＝IB，得g－1＝fh；由gfh＝IC，得h－1＝gf。

離散數(shù)學(xué)試題(B卷答案3）

一、（10分）推斷下列公式的類(lèi)型（永真式、永假式、可滿(mǎn)腳式）？(寫(xiě)過(guò)程)

1)P→(P∨Q∨R)2)?((Q→P)∨?P)∧(P∨R)3)((?P∨Q)→R)→((P∧Q)∨R)

解：1)重言式；2)矛盾式；3)可滿(mǎn)腳式

二、（10分）求命題公式（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)∨(?P∧?R)∨(P∨Q)∨R

?(?(P∨Q)∨(P∨Q))∨(?P∧?R)∨R

?1∨((?P∧?R)∨R)?1

?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7

該式為重言式，全部賦值基本上成真賦值。

三、（10分）證明((P∧Q∧A)→C)∧(A→(P∨Q∨C))?(A∧(P?Q))→C

證明：((P∧Q∧A)→C)∧(A→(P∨Q∨C))?(?(P∧Q∧A)∨C)∧(?A∨(P∨Q∨C))?((?P∨?Q∨?A)∨C)∧((?A∨P∨Q)∨C)

?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C

??((?P∨?Q∨?A)∧(?A∨P∨Q))→C

?(?(?P∨?Q∨?A)∨?(?A∨P∨Q))→C

?((P∧Q∧A)∨(A∧?P∧?Q))→C

?(A∧((P∧Q)∨(?P∧?Q)))→C

?(A∧((P∨?Q)∧(?P∨Q)))→C

?(A∧((Q→P)∧(P→Q)))→C

?(A∧(P?Q))→C

四、（10分）個(gè)體域?yàn)閧1，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））

?（0∨0）∧（0∨1）?0∧1?0

五、（10分）關(guān)于任意集合A，B，試證明：P(A)∩P(B)=P(A∩B)

解：?x∈P(A)∩P(B)，x∈P(A)且x∈P(B)，有x?A且x?B，從而x?A∩B，x∈P(A∩

B)，由于上述過(guò)程可逆，故P(A)∩P(B)=P(A∩B)

六、（10分）已知A={1，2，3，4，5}和R={，，，，}，求r(R)、s(R)和t(R)。

解：r(R)={，，，，，，，，，}

s(R)={，，，，，，，}t(R)={，，，，，，，，，}

七、（10分）設(shè)函數(shù)f：R×R→R×R，R為實(shí)數(shù)集，f定義為：f()=。

1)證明f是雙射。

解：1）?，∈R×R，若f()=f()，即=，則x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2從而f是單射。

2）?∈R×R，由f()=，經(jīng)過(guò)計(jì)算可得x=(p+q)/2；y=(p-q)/2；從而的原象存在，f是滿(mǎn)射。

八、（10分）是個(gè)群，u∈G，定義G中的運(yùn)算“?”為a?b=a*u-1*b，對(duì)任意a，b

∈G，求證：也是個(gè)群。

證明：1）?a，b∈G，a?b=a*u-1*b∈G，運(yùn)就是封閉的。

2）?a，b，c∈G，（a?b）?c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a?（b?c），運(yùn)就是可結(jié)合的。

3）?a∈G，設(shè)E為?的單位元，則a?E=a*u-1*E=a，得E=u，存在單位元u。

4）?a∈G，a?x=a*u-1*x=E，x=u*a-1*u，則x?a=u*a-1*u*u-1*a=u=E，每個(gè)元素都有逆元。

因此也是個(gè)群。

九、（10分）已知：D=，V={1，2，3，4，5}，E={，，，，，}，求D的鄰接距陣A和可達(dá)距陣P。

解：1）D的鄰接距陣A和可達(dá)距陣P如下：

0101011111

0010011111

A=00011P=11111

0000000000

1000011111

十、（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+12×2+(8+10)×3+14×2＝148

離散數(shù)學(xué)試題(B卷答案4）

一、證明題（10分）

1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T

證明:左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律)?((P∨Q)

∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律)?((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(等冪律)?T(代入)

2)?x(P(x)→Q(x))∧?xP(x)??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)??(?P→Q)∨(P∨?Q)??(P∨Q)∨(P∨?Q)?(?P∧?Q)∨(P∨?Q)?(?P∨P∨?Q)∧(?Q∨P∨?Q)?(P∨?Q)?M1?m0∨m2∨m3

三、推理證明題（10分）

1)(P→(Q→S))∧(?R∨P)∧Q?R→S

證明：（1）R附加前提

(2)?R∨PP

(3)PT(1)(2),I

(4)P→(Q→S)P

(5)Q→ST(3)(4),I

(6)QP

(7)ST(5)(6),I

(8)R→SCP

2)?x(P(x)∨Q(x))，?x?P(x)??xQ(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)?xQ(x)T(5),EG

四、例5在邊長(zhǎng)為1的正方形內(nèi)任意放置九個(gè)點(diǎn)，證明其中必存在三個(gè)點(diǎn)，使得由它們組成的三角形（也許是退化的）面積別超過(guò)1/8（10分）。

證明：把邊長(zhǎng)為1的正方形分成四個(gè)全等的小正方形，則至少有一具小正方形內(nèi)有三個(gè)點(diǎn)，它們組成的三角形（也許是退化的）面積別超過(guò)小正方形的一半，即1/8。五、已知A、B、C是三個(gè)集合，證明A∩(B∪C)=(A∩B)∪(A∩C)（10分）

證明：∵x∈A∩（B∪C）?x∈A∧x∈（B∪C）?x∈A∧（x∈B∨x∈C）?（x∈A∧x∈B）∨（x∈A∧x∈C）?x∈（A∩B）∨x∈A∩C?x∈（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）

六、π={A1，A2，…，An}是集合A的一具劃分，定義R={|a、b∈Ai，I=1，2，…，n}，則R是A上的等價(jià)關(guān)系（15分）。

證明：?a∈A必有i使得a∈Ai，由定義知aRa，故R自反。

?a,b∈A，若aRb，則a,b∈Ai，即b,a∈Ai，因此bRa，故R對(duì)稱(chēng)。

?a,b,c∈A，若aRb且bRc，則a,b∈Ai及b,c∈Aj。因?yàn)閕≠j時(shí)Ai∩Aj=Φ，故i=j，即a,b,c∈Ai，因此aRc，故R傳遞。

總之R是A上的等價(jià)關(guān)系。

七、若f:A→B是雙射，則f-1:B→A是雙射（15分）。

證明:對(duì)任意的x∈A，因?yàn)閒是從A到B的函數(shù)，故存在y∈B，使∈f，∈f-1。因此,f-1是滿(mǎn)射。

對(duì)任意的x∈A，若存在y1,y2∈B，使得∈f-1且∈f-1,則有∈f且∈f。因?yàn)閒是函數(shù)，則y1=y2。因此，f-1是單射。

所以f-1是雙射。

八、設(shè)是群，和是的子群，證明：若A∪B＝G，則A＝G或B＝G（10分）。

證明假設(shè)A≠G且B≠G，則存在a∈A，a?B，且存在b∈B，b?A（否則對(duì)任意的a∈A，a∈B，從而A?B，即A∪B＝B，得B＝G，矛盾。）

關(guān)于元素a*b∈G，若a*b∈A，因A是子群，a-1∈A，從而a-1*(a*b)＝b∈A，因此矛盾，故a*b?A。同理可證a*b?B，綜合有a*b?A∪B＝G。

綜上所述，假設(shè)別成立，得證A＝G或B＝G。

九、若無(wú)向圖G是別連通的，證明G的補(bǔ)圖G是連通的（10分）。

證明設(shè)無(wú)向圖G是別連通的，其k個(gè)連通分支為1G、2G、…、kG。任取結(jié)點(diǎn)u、v∈G，若u和v別在圖G的同一具連通分支中，則[u，v]別是圖G的邊，因而[u，v]是圖G的邊