(完整版)離散數(shù)學(xué)期末考試試題及答案,推薦文檔

1、離散數(shù)學(xué)試題(b 卷答案 1）一、證明題（10 分）1)(p(qr)(qr)(pr)r證明: 左端(pqr)(qp)r)(pq)r)(qp)r)(pq)r)(qp)r)(pq)(qp)r(pq)(pq)rtr(置換)r2) $x (a(x)b(x) xa(x)$xb(x)證明：$x(a(x)b(x)$x(a(x)b(x)$xa(x)$xb(x)xa(x)$xb(x)xa(x)$xb(x)二、求命題公式(p(qr)(pqr)的主析取范式和主合取范式（10 分）。證明：(p(qr)(pqr)(p(qr)(pqr)（p(qr)）(pqr)(pq)(pr)(pqr)(pqr)(pqr)(pqr)(pq

2、r)(pqr)m0m1m2m7m3m4m5m6三、推理證明題（10 分）1） cd， (cd) e， e(ab)， (ab)(rs)rs證明：(1) (cd)ep(2) e(ab)p(3) (cd)(ab)t(1)(2)，i(4) (ab)(rs)p(5) (cd)(rs)t(3)(4)， i(6) cdp(7) rst(5)，i2) 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

3、(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 人會打籃球，12 人會打排球，6 人會打籃球和排球，5 人會打籃球和網(wǎng)球，還有 2 人會打這三種球。而 6 個(gè)會打網(wǎng)球的人都會打另外一種球， 求不會打這三種球的人數(shù)（10 分）。解：a，b，c 分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。則|a|=12，|b|=6，|c|=14，|ac|=6，|bc|=5，|abc|=2。先求|ab|。6=|（ac）b|=|（ab）（bc）|=|（ab）|

4、+|（bc）|-|abc|=|（ab）|+5-2，|（ab）|=3。于是|abc|=12+6+14-6-5-3+2=20。不會打這三種球的人數(shù) 25-20=5。五、已知 a、b、c 是三個(gè)集合，證明 a-(bc)=(a-b)(a-c) （10 分）。證明：x a-（bc） x ax（bc） x a（xbxc）（x axb）（x axc） x（a-b）x（a-c） x（a-b）（a-c）a-（bc）=（a-b）（a-c）六、已知 r、s 是 n 上的關(guān)系，其定義如下：r=|x，yny=x2，s=| x，yny=x+1。求 r-1、r*s、s*r、r 1，2、s1，2（10 分）。解 ：r-1=|

5、 x，yny=x2 r*s=| x，yny=x2+1s*r=|x，yny=（x+1）2，r 1，2=，s1，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=|xy(modm)是等價(jià)關(guān)系。其中， xy(mod m)的含義是 x-y 可以被 m 整除（15 分）。證明：1）xi，因?yàn)椋▁-x）/m=0，所以 xx(mod m)，即 xrx。2）x，yi，若 xry，則 xy(mod m)，即（x-y）/m=ki，所以（y - x）/m=-k

6、i，所以 yx(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 i，因此 xrz。九、若 f:ab 和g:bc 是雙射，則（gf）-1=f-1g-1（10 分）。證明：因?yàn)?f、g 是雙射，所以 gf：ac 是雙射，所以 gf 有逆函數(shù)（gf）- 1：ca。同理可推 f-1g-1：ca 是雙射。因?yàn)閒-1g-1存在 z（g-1f-1）存在z（fg）gf（gf）-1，所以（gf）-1=f-1g-1。離散數(shù)學(xué)試題(b 卷答案 2）一、證明題（10 分）1)(pq)(p(qr)(pq)

7、(pr)t證明: 左端(pq)(p(qr)(pq)(pr)(摩根律) (pq)(pq)(pr)(pq)(pr)(分配律) (pq)(pr)(pq)(pr) (等冪律)t(代入)2) xy(p(x)q(y) ($xp(x)yq(y)證明：xy(p(x)q(y)xy(p(x)q(y)x(p(x)yq(y)xp(x)yq(y)$xp(x)yq(y)($xp(x)yq(y)二、求命題公式(pq)(pq) 的主析取范式和主合取范式（10 分）解：(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(ppq)(qpq)(pq)m1m0m2m3三、推理證明題（10 分）1)(p(qs)(rp)q

8、rs證明：(1)r (2)rp (3)p (4)p(qs) (5)qs(6)q(7)s(8)rs2) $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)入考場，當(dāng)且

9、僅當(dāng)所有考生提前進(jìn)入考場，考試才能準(zhǔn)時(shí)進(jìn)行。所以，如果考試準(zhǔn)時(shí)進(jìn)行，那么天氣就好（15 分）。解 設(shè) p：今天天氣好，q：考試準(zhǔn)時(shí)進(jìn)行，a(e)：e 提前進(jìn)入考場，個(gè)體域：考生的集合，則命題可符號化為：p$xa(x)，xa(x)q qp。(1)p$xa(x)p(2)pxa(x)t(1)，e(3)xa(x)pt(2)，e(4)xa(x)qp(5)(xa(x)q)(qxa(x)t(4)，e(6)qxa(x)t(5)，i(7)qpt(6)(3)，i五、已知 a、b、c 是三個(gè)集合，證明 a(bc)=(ab)(ac) （10 分）證明：x a（bc） x ax（bc） x a（xbxc）（ xaxb）

10、（xaxc）x（ab）xacx（ab）（ac）a（bc）=（ab）（ac）六、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 滿足：，rr1 且r2，證明 r 是 ab 上的等價(jià)關(guān)系（10 分）。證明 對任意的ab，由 r1 是 a 上的等價(jià)關(guān)系可得r1，由 r2 是b上的等價(jià)關(guān)系可得r2。再由 r 的定義，有

11、，r，所以 r 是自反的。對任意的、ab，若r，則r1 且r2。由 r1 對稱得r1，由 r2 對稱得r2。再由 r 的定義，有，r，即r，所以 r 是對稱的。對任意的、ab，若r且r，則r1 且r2，r1 且r2。由r1、r1 及r1 的傳遞性得r1，由r2、r2 及 r2 的傳遞性得r1。再由r 的定義，有，r，即r，所以 r 是傳遞的。綜上可得，r 是 ab 上的等價(jià)關(guān)系。九、設(shè) f：ab，g：bc，h：ca，證明：如果 hogofia，fohogib，gofohic，則f、g、h 均為雙射，并求出 f1、g1 和 h1（10 分）。解 因 ia 恒等函數(shù)，由 hogofia 可得 f

12、是單射，h 是滿射；因 ib 恒等函數(shù)，由fohogib 可得 g 是單射，f 是滿射；因 ic 恒等函數(shù)，由 gofohic 可得 h 是單射，g 是滿射。從而 f、g、h 均為雙射。由 hogofia，得 f1hog；由 fohogib，得 g1foh；由 gofohic，得 h1gof。離散數(shù)學(xué)試題(b 卷答案 3）一、（10 分）判斷下列公式的類型（永真式、永假式、可滿足式）？(寫過程) 1) p(pqr)2)(qp)p)(pr)3)(pq)r)(pq)r)解：1)重言式；2)矛盾式；3)可滿足式二、（10 分）求命題公式（p(qr)(pqr)的主析取范式，并求成真賦值。解：（p(qr

13、)(pqr)(p(qr)pqrp(qr)pqr(pq)(pr)(pq)r(pq)(pq)(pr)r1(pr)r)1m0m1m2m3m4m5m6m7該式為重言式，全部賦值都是成真賦值。三、（10 分）證明 (pqa)c)(a(pqc)(a(pq)c證明：(pqa)c)(a(pqc)(pqa)c)(a(pqc)(pqa)c)(apq)c)(pqa)(apq)c(pqa)(apq)c(pqa)(apq)c(pqa)(apq)c(a(pq)(pq)c(a(pq)(pq)c(a(qp)(pq)c(a(pq)c四、（10 分）個(gè)體域?yàn)?，2，求x$y（x+y=4）的真值。解：x$y（x+y=4）x（x+1

14、=4）（x+2=4）（1+1=4）（1+2=4） （2+1=4）（2+2=4）（00）（01）010五、（10 分）對于任意集合 a，b，試證明：p(a)p(b)=p(ab)解：xp(a)p(b)，xp(a)且 xp(b)，有 xa 且 xb，從而xab，xp(ab)，由于上述過程可逆，故 p(a)p(b)=p(ab)六、（10 分）已知 a=1，2，3，4，5和 r=， 求 r(r)、s(r)和 t(r)。解：r(r)=，s(r)=，t(r)=，七、（10 分）設(shè)函數(shù) f：rrrr，r 為實(shí)數(shù)集，f 定義為：f()=。1)證明 f 是雙射。解：1），rr，若 f()=f()，即=，則 x1+

15、y1=x2+y2 且x1-y1=x2-y2 得x1=x2，y1=y2 從而 f 是單射。2）rr，由 f()=，通過計(jì)算可得 x=(p+q)/2；y=(p-q)/2；從而的原象存在，f 是滿射。八、（10 分）是個(gè)群，ug，定義 g 中的運(yùn)算“d”為 adb=a*u-1*b，對任意a，bg，求證：也是個(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

16、，adx=a*u-1*x=e，x=u*a-1*u，則 xda=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 如下：01010111110010011111a=00011p=1111100000000001000011111十、（10 分）求葉的權(quán)分別為 2、4、6、8、10、12、14 的最優(yōu)二叉樹及其權(quán)。解：最優(yōu)二叉樹為權(quán)(2+4)4+63+122+(8+10)3+142148離散數(shù)學(xué)試題(b 卷答案 4）一、證明題

17、（10 分）1)(pq)(p(qr)(pq)(pr)t證明: 左端(pq)(p(qr)(pq)(pr)(摩根律) (pq)(pq)(pr)(pq)(pr)(分配律) (pq)(pr)(pq)(pr) ( 等 冪 律 ) 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)二、求命題公式(pq)(pq) 的主析取范式和主合取范式（10 分）解：(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq) (ppq)(qp

18、q)(pq)m1m0m2m3 三、推理證明題（10 分）1)(p(qs)(rp)qrs證明：（1）r附加前提(2)rpp(3)pt(1)(2),i(4)p(qs)p(5)qst(3)(4),i(6)qp(7)st(5)(6),i(8)rscp2) x(p(x)q(x)，xp(x)$x q(x)證明：(1)xp(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 在邊長為 1 的正方形內(nèi)任意放置九個(gè)點(diǎn)，證明其中必存在三個(gè)點(diǎn)，使得由它們組成的三角形（可能是退化的）面積不超過

19、1/8（10 分）。證明：把邊長為 1 的正方形分成四個(gè)全等的小正方形，則至少有一個(gè)小正方形內(nèi)有三個(gè)點(diǎn)，它們組成的三角形（可能是退化的）面積不超過小正方形的一半，即 1/8。五、已知 a、b、c 是三個(gè)集合，證明 a(bc)=(ab)(ac) （10 分）證明：x a（bc） x ax（bc） x a（xbxc）（ xaxb）（xaxc）x（ab）xacx（ab）（ac）a（bc）=（ab）（ac）六、p=a1，a2，an是集合 a 的一個(gè)劃分，定義r=|a、bai，i=1，2，n，則 r 是a 上的等價(jià)關(guān)系（15 分）。證明：aa 必有 i 使得 aai，由定義知 ara，故 r 自反。a,

20、ba，若 arb ，則 a,bai，即 b,aai，所以 bra，故 r 對稱。a,b,ca，若 arb且 brc，則 a,bai 及 b,caj。因?yàn)?ij 時(shí) aiaj=f， 故i=j，即 a,b,cai，所以 arc，故 r 傳遞?？傊?r 是 a 上的等價(jià)關(guān)系。七、若 f:ab 是雙射，則 f-1:ba 是雙射（15 分）。證明:對任意的 xa，因?yàn)?f 是從 a 到 b 的函數(shù)，故存在 yb，使f，f-1。所以,f-1 是滿射。對任意的 xa，若存在 y1,y2b，使得f-1 且f-1,則有f 且f。因?yàn)?f 是函數(shù)，則 y1=y2。所以，f-1 是單射。因此 f-1 是雙射。八、設(shè)

21、是群，和是的子群，證明：若 abg，則 ag或 bg（10 分）。證明 假設(shè) ag 且 bg，則存在 aa，ab，且存在 bb，ba（否則對任意的aa，ab，從而 ab，即 abb，得 bg，矛盾。）對于元素 a*bg，若 a*ba，因 a 是子群，a-1a，從而 a-1 * (a*b)b a，所以矛盾，故 a*ba。同理可證 a*bb，綜合有 a*babg。綜上所述，假設(shè)不成立，得證 ag 或 bg。九、若無向圖 g 是不連通的，證明 g 的補(bǔ)圖g 是連通的（10 分）。證明 設(shè)無向圖 g 是不連通的，其 k 個(gè)連通分支為g1 、g2 、gk 。任取結(jié)點(diǎn)u 、v g，若u 和v 不在圖 g

22、的同一個(gè)連通分支中，則 u ， v 不是圖 g 的邊，因而 u ， v 是圖g 的邊；若u 和v 在圖 g 的同一個(gè)連通分支中，不妨設(shè)其在連通分支gi （1 i k ）中，在不同于gi 的另一連通分支上取一結(jié)點(diǎn) w ，則 u ， w 和 w ， v 都不是圖 g 的邊，因而 u ， w 和 w ， v 都是g 的邊。綜上可知，不管那種情況， u 和v 都是可達(dá)的。由u 和v 的任意性可知， g 是連通的。離散數(shù)學(xué)試題（b 卷答案 5）一、（10 分）求命題公式(pq)(pr)的主合取范式。解：(pq)(pr)（(pq)(pr)）（(pr)(pq)）（(pq)(pr)）（(pr)(pq)）(pq

23、)(pr)(pr)（qp）（qr）(pqr)(pqr)（pqr）（pqr）m1m3m4m5二、（8 分）敘述并證明蘇格拉底三段論解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號化：f（x）：x 是一個(gè)人。g（x）：x 要死的。a：蘇格拉底。命題符號化為x（f（x）g（x），f（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、c 是三個(gè)集合，證明 a(bc)=(ab)(ac) 證明：x a（bc） x ax（bc） x a（xbxc）（ x axb）（x axc） x（ab

24、）x ac x（ab）（ac）a（bc）=（ab）（ac）四、（10 分）已知 r 和s 是非空集合 a 上的等價(jià)關(guān)系，試證：1）rs 是a 上的等價(jià)關(guān)系；2）對 aa，ars=aras。解：xa，因?yàn)?r 和 s 是自反關(guān)系，所以r、s，因而rs，故 rs 是自反的。x、ya，若rs，則r、s，因?yàn)?r 和s 是對稱關(guān)系，所以因r、s，因而rs，故 rs 是對稱的。x、y、za，若rs 且rs，則r、s 且r、s，因?yàn)?r 和 s 是傳遞的，所以因r、s，因而rs，故 rs 是傳遞的?？傊?rs 是等價(jià)關(guān)系。2）因?yàn)?xarsrsrs xarxas xaras 所以ars=aras。五、(1

25、0 分)設(shè) aa，b，c，d，r 是 a 上的二元關(guān)系，且r，求 r(r)、s(r)和 t(r)。解r(r)ria，s(r)rr-1， r2， r3，r4，r2t(r)= uri ，六、(15 分)設(shè) a、b、c、d 是集合，f 是 a 到 b 的雙射，g 是 c 到 d 的雙射，令h：acbd 且ac，h()。證明 h 是雙射。證明：1）先證 h 是滿射。bd，則 bb，dd，因?yàn)?f 是a 到b 的雙射，g 是c 到d 的雙射，所以存在 aa，cc，使得 f(a)=b，f(c)=d，亦即存在ac，使得 h()，所以 h 是滿射。2）再證 h 是單射。、ac，若 h()h()，則 ，所以 f

26、(a1)f(a2)，g(c1)g(c2)，因?yàn)?f 是a 到b 的雙射，g 是c 到d 的雙射，所以 a1a2，c1c2，所以，所以 h 是單射。綜合 1）和 2），h 是雙射。七、(12 分)設(shè)是群，h 是g 的非空子集，證明是的子群的充要條件是若 a，bh，則有 a*b-1h。證明： a,bh 有 b-1h，所以 a*b-1h。ah，則 e=a*a-1h a-1=e*a-1ha,bh 及 b-1h，a*b=a*（b-1）-1hhg 且 hf,*在 h 上滿足結(jié)合律是的子群。八、（10 分）設(shè) g=是簡單的無向平面圖，證明 g 至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。解：設(shè) g 的每個(gè)結(jié)點(diǎn)的度數(shù)都大

27、于等于 6，則 2|e|=sd(v)6|v|，即|e|3|v|， 與簡單無向平面圖的|e|3|v|-6 矛盾，所以 g 至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于 5。九.g=,a=a,b,c,*的運(yùn)算表為：(寫過程，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 a*b=b*a=b a

28、*c=c*a=c 所以 g 的單位元是 a（3） 因?yàn)?a*a=a 所以 g 的冪等元是 a（4） 因?yàn)?b*c=c*b=a，所以 b 的逆元是 c 且c 的逆元是 b十、(10 分)求葉的權(quán)分別為 2、4、6、8、10、12、14 的最優(yōu)二叉樹及其權(quán)。解：最優(yōu)二叉樹為權(quán)148離散數(shù)學(xué)試題（b 卷答案 6）一、（20 分）用公式法判斷下列公式的類型：(1)(pq)(pq)(2)(pq)(p(qr)解：（1）因?yàn)?pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq) m1 m2 m3 m 0所以，公式(pq)(pq)為可滿足式。（2）因?yàn)?pq)(p(qr)( pq)(pqr)(pq)

29、(pqr)(pqp)(pqq)(pqr)(pq)(pqr)(pq(rr)(pqr)(pqr)(pqr)(pqr) m 0 m 1 m2 m3 m4 m5 m6 m7所以，公式(pq)(p(qr)為可滿足式。二、（15 分）在謂詞邏輯中構(gòu)造下面推理的證明：每個(gè)科學(xué)家都是勤奮的，每個(gè)勤奮又身體健康的人在事業(yè)中都會獲得成功。存在著身體健康的科學(xué)家。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。解：論域：所有人的集合。q ( x )： x 是勤奮的； h ( x )： x 是身體健康的； s ( x )：x 是科學(xué)家； c ( x )： x 是事業(yè)獲得成功的人； f ( x )： x 是事業(yè)半途而廢

30、的人；則推理化形式為： x ( s ( x ) q ( x )， x ( q ( x ) h ( x ) c ( x )， $ x ( s ( x ) h ( x ) $ x (c ( x ) f ( x )下面給出證明：(1) $ x ( s ( x ) h ( x )p(2) s ( a ) h ( a )t(1)，es(3) x ( s ( x ) q ( x )p(4) s ( a ) q ( a )t(1)，us(5) s ( a )t(2)，i(6) q ( a )t(4)(5)，i(7) h ( a )t(2)，i(8) q ( a ) h ( a )t(6)(7)，i(9) x

31、 ( q ( x ) h ( x ) c ( x )p(10) q ( a ) h ( a ) c ( a )t(9)，us(11) c ( a )t(8)(10)，i(12) $ x c ( x )t(11)，eg(13) $ x ( c ( x ) f ( x )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)b，0，0，0，00，0，0，0，0，0四、（15 分）設(shè) r 和 s 是集合 a 上的任意關(guān)系，判斷下列命題是否成立？(1) 若 r 和 s

32、 是自反的，則 r*s 也是自反的。(2) 若 r 和 s 是反自反的，則 r*s 也是反自反的。(3) 若 r 和 s 是對稱的，則 r*s 也是對稱的。(4)若 r 和 s 是傳遞的，則 r*s 也是傳遞的。(5)若 r 和 s 是自反的，則 rs 是自反的。(6)若 r 和 s 是傳遞的，則 rs 是傳遞的。解(1)成立。對任意的 a a ，因?yàn)?r 和 s 是自反的，則r，s，于是r*s，故 r*s 也是自反的。(2)不成立。例如，令 a 1，2，r，s，則 r 和 s 是反自反的，但 r*s不是反自反的。(3)不成立。例如，令 a 1，2，3，r，s，則 r 和 s 是對稱的，但 r

33、*s，不是對稱的。(4)不成立。例如，令 a 1，2，3，r， s，則 r 和 s 是傳遞的，但r*s，不是傳遞的。(5)成立。對任意的 a a ，因?yàn)?r 和 s 是自反的，則r，s，于是rs，所以 rs 是自反的。五、（15 分）令 xx1，x2，xm，yy1，y2，yn。問(1) 有多少個(gè)不同的由 x 到 y 的函數(shù)？(2) 當(dāng) n、m 滿足什么條件時(shí)，存在單射，且有多少個(gè)不同的單射？(3) 當(dāng) n、m 滿足什么條件時(shí)，存在雙射，且有多少個(gè)不同的雙射？解 (1)由于對 x 中每個(gè)元素可以取 y 中任一元素與其對應(yīng)，每個(gè)元素有 n 種取法， 所以不同的函數(shù)共 nm 個(gè)。(2) 顯然當(dāng)|m|

34、n|時(shí)，存在單射。由于在 y 中任選 m 個(gè)元素的任一全排列都形成 xn到 y 的不同的單射，故不同的單射有cm m!n(n1)(nm1)個(gè)。(3) 顯然當(dāng)|m|n|時(shí)，才存在雙射。此時(shí) y 中元素的任一不同的全排列都形成 x 到y(tǒng) 的不同的雙射，故不同的雙射有 m!個(gè)。六、（5 分）集合 x 上有 m 個(gè)元素，集合 y 上有 n 個(gè)元素，問 x 到 y 的二元關(guān)系總共有多少個(gè)？解 x 到 y 的不同的二元關(guān)系對應(yīng) xy 的不同的子集，而 xy 的不同的子集共有個(gè)2mn ，所以 x 到 y 的二元關(guān)系總共有2mn 個(gè)。七、（10 分）若是群，則對于任意的 a、bg，必有惟一的 xg 使得a*x

35、b。證明設(shè) e 是群的幺元。令 xa1*b，則 a*xa*(a1*b)(a*a1)*be*bb。所以，xa1*b 是 a*xb 的解。若 xg 也是 a*xb 的解，則 xe*x(a1*a)*xa1*(a*x)a1*bx。所以， xa1*b 是 a*xb 的惟一解。八、（10 分）給定連通簡單平面圖 g，且|v|6，|e|12。證明：對任意 ff，d(f)3。證明由偶拉公式得|v|e|f|2，所以|f|2|v|e|8，于是 d ( f ) 2|e|24。若存在 ff，使得 d(f)3，則 3|f|2|e|24，于是|f|8，與f f|f|8 矛盾。故對任意 ff，d(f)3。離散數(shù)學(xué)試題（b

36、卷答案 7）一、（15 分）設(shè)計(jì)一盞電燈的開關(guān)電路，要求受 3 個(gè)開關(guān) a、b、c 的控制：當(dāng)且僅當(dāng) a 和 c 同時(shí)關(guān)閉或 b 和 c 同時(shí)關(guān)閉時(shí)燈亮。設(shè) f 表示燈亮。(1) 寫出 f 在全功能聯(lián)結(jié)詞組中的命題公式。(2) 寫出 f 的主析取范式與主合取范式。解 (1)設(shè) a：開關(guān) a 關(guān)閉；b：開關(guān) b 關(guān)閉；c：開關(guān) c 關(guān)閉；f(ac)(bc)。在全功能聯(lián)結(jié)詞組中：a(aa)aaac( ac)( ac)(ac)(ac) ab(ab)( aa)(bb)( aa)(bb)所以f(ac)(ac)(bc)(bc)(ac)(ac)(ac)(ac)(bc)(bc)(bc)(bc) (2)f(ac

37、)(bc)(a(bb)c)(aa)bc)(abc)(abc)(abc)(abc) m3 m5 m7 m 0 m 1 m 2 m 4 m 6二、（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)($xa(x)$xb(x)$xa(x)$xb(x)($xa(x)$xa(x)$xb(x)($xb(x)$xa(x)$xb(x)$x(a(x)

38、a(x)$xb(x)t所以，($xa(x)$xb(x)$x(a(x)b(x)為永真式。(2)設(shè)論域?yàn)?，2，令 a(1)t；a(2)f；b(1)f；b(2)t。則xa(x)為假，xb(x)也為假，從而xa(x)xb(x)為真；而由于 a(1)b(1)為假， 所以x(a(x)b(x)也為假，因此公式(xa(x)xb(x)x(a(x)b(x)為假。該公式不是永真式。三、（15 分）設(shè) x 為集合，ap(x)x且 a，若|x|n，問(1)偏序集是否有最大元？ (2)偏序集是否有最小元？(3)偏序集中極大元和極小元的一般形式是什么？并說明理由。解 偏序集不存在最大元和最小元，因?yàn)?n2。考察 p(x)

39、的哈斯圖，最底層的頂點(diǎn)是空集，記作第 0 層，由底向上，第一層是單元集，第二層是二元集，由|x|n，則第 n1 層是 x 的 n1 元子集，第 n 層是 x。偏序集與偏序集相比，恰好缺少第 0 層和第 n 層。因此的極小元就是 x 的所有單元集，即x，xx；而極大元恰好是比 x 少一個(gè)元素，即 xx， xx。四、（10 分）設(shè) a1，2，3，4，5，r 是 a 上的二元關(guān)系，且r，求 r(r)、s(r)和 t(r)。解r(r)ria，s(r)rr1，r2， r3， r4，r2 t(r) u ri，。五、（10 分）設(shè)函數(shù) g：ab，f：bc，(1) 若 fog 是滿射，則 f 是滿射。(2) 若 fog 是單射，則 g 是單射。證明 因?yàn)?g：ab，f：bc，由定理 5.5 知，fog 為 a 到 c 的函數(shù)。(1) 對任意的 zc，因 fog 是滿射，則存在 xa 使 fog(x)z，即 f(g(x)z。由g：ab 可知 g(x)b，于是有 yg(x)b，使得 f(y)z。因此，f 是滿射。(2) 對任意的 x1、x2a，若 x1x2，則由 fog 是單射得 fog(x1)fog(x2)，于是 f(g(x1)f(g(x2)，必有 g(x1)g(x2)。所以，g 是單射。六、（10 分）有幺元且滿足消去律的有限半群一定是群。證明設(shè)是一個(gè)有