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

1、離散數(shù)學(xué)試題（A卷答案）一、（10分）求(P¯Q)®(PØ(QØR)的主析取范式解：(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)ÛÛ二、（10分）在某次研討會(huì)的休息時(shí)間，3名與會(huì)者根據(jù)王教授的口音分別作出下述判斷：甲說(shuō)

2、：王教授不是蘇州人，是上海人。乙說(shuō)：王教授不是上海人，是蘇州人。丙說(shuō)：王教授既不是上海人，也不是杭州人。王教授聽(tīng)后說(shuō)：你們3人中有一個(gè)全說(shuō)對(duì)了，有一人全說(shuō)錯(cuò)了，還有一個(gè)人對(duì)錯(cuò)各一半。試判斷王教授是哪里人？解 設(shè)設(shè)P：王教授是蘇州人；Q：王教授是上海人；R：王教授是杭州人。則根據(jù)題意應(yīng)有：甲：ØPQ乙：ØQP丙：ØQØR王教授只可能是其中一個(gè)城市的人或者3個(gè)城市都不是。所以，丙至少說(shuō)對(duì)了一半。因此，可得甲或乙必有一人全錯(cuò)了。又因?yàn)椋艏兹e(cuò)了，則有ØQP，因此，乙全對(duì)。同理，乙全錯(cuò)則甲全對(duì)。所以丙必是一對(duì)一錯(cuò)。故王教授的話符號(hào)化為：(Ø

3、PQ)(QØR)(ØQR)(ØQP)(ØQR)Û(ØPQQØR)(ØPQØQR)(ØQPØQR)Û(ØPQØR)(PØQR)ÛØPQØRÛT因此，王教授是上海人。三、（10分）證明tsr(R)是包含R的且具有自反性、對(duì)稱性和傳遞性的最小關(guān)系。證明 設(shè)R是非空集合A上的二元關(guān)系，則由定理4.19知，tsr(R)是包含R的且具有自反性、對(duì)稱性和傳遞性的關(guān)系。若是包含R的且具有自反性、對(duì)稱性和傳遞性的任意關(guān)系，則

4、由閉包的定義知r(R)Í。由定理4.15和由定理4.16得sr(R)Ís()，進(jìn)而有tsr(R)Ít()。綜上可知，tsr(R)是包含R的且具有自反性、對(duì)稱性和傳遞性的最小關(guān)系。四、（15分）集合Aa，b，c，d，e上的二元關(guān)系R為R<a，a>，<a，b>，<a，c>，<a，d>，<a，e>，<b，b>，<b，c>，<b，e>，<c，c>，<c，d>，<c，e>，<d，d>，<d，e>，<e，e>，

5、(1)寫(xiě)出R的關(guān)系矩陣。(2)判斷R是不是偏序關(guān)系，為什么？解 (1) R的關(guān)系矩陣為：(2)由關(guān)系矩陣可知，對(duì)角線上所有元素全為1，故R是自反的；1，故R是反對(duì)稱的；可計(jì)算對(duì)應(yīng)的關(guān)系矩陣為：由以上矩陣可知R是傳遞的。五、（10分）設(shè)A、B、C和D為任意集合，證明(AB)×C(A×C)(B×C)。證明：因?yàn)?lt;，>(AB)×CÛ(AB)CÛ(AÏB)CÛ(ACÏB)(ACÏC)Û(AC)(ÏBÏC)Û(AC)Ø(BC)Û<

6、;，>(A×C)<，>Ï(B×C)Û<，>(A×C)(B×C)所以，(AB)×C(A×CB×C)。六、（10分）設(shè)f：A®B，g：B®C，h：C®A，證明：如果hogofIA，fohogIB，gofohIC，則f、g、h均為雙射，并求出f1、g1和h1。解 因IA恒等函數(shù)，由hogofIA可得f是單射，h是滿射；因IB恒等函數(shù)，由fohogIB可得g是單射，f是滿射；因IC恒等函數(shù)，由gofohIC可得h是單射，g是滿射。從而f、g、h均為雙射。

7、由hogofIA，得f1hog；由fohogIB，得g1foh；由gofohIC，得h1gof。七、（15分）設(shè)<G，*>是一代數(shù)系統(tǒng)，運(yùn)算*滿足交換律和結(jié)合律，且a*xa*yÞxy，證明：若G有限，則G是一群。證明 因G有限，不妨設(shè)G，。由a*xa*yÞxy得，若xy，則a*xa*y。于是可證，對(duì)任意的aG，有aGG。又因?yàn)檫\(yùn)算*滿足交換律，所以aGGGa。令eG使得a*ea。對(duì)任意的bG，令c*ab，則b*e(c*a)*ec*(a*e)c*ab，再由運(yùn)算*滿足交換律得e*bb，所以e是關(guān)于運(yùn)算*的幺元。對(duì)任意aG，由aGG可知，存在bG使得a*be，再由運(yùn)算

8、*滿足交換律得b*ae，所以b是a的逆元。由a的任意性知，G中每個(gè)元素都存在逆元。故G是一群。八、（20分）（1）證明在n個(gè)結(jié)點(diǎn)的連通圖G中，至少有n1條邊。證明 不妨設(shè)G是無(wú)向連通圖（若G為有向圖，可略去邊的方向討論對(duì)應(yīng)的無(wú)向圖）。設(shè)G中結(jié)點(diǎn)為、。由連通性，必存在與相鄰的結(jié)點(diǎn)，不妨設(shè)它為（否則可重新編號(hào)），連接和，得邊，還是由連通性，在、中必存在與或相鄰的結(jié)點(diǎn)，不妨設(shè)為，將其連接得邊，續(xù)行此法，必與、中的某個(gè)結(jié)點(diǎn)相鄰，得新邊，由此可見(jiàn)G中至少有n1條邊。（2）給定簡(jiǎn)單無(wú)向圖G<V，E>，且|V|m，|E|n。試證：若n2，則G是哈密爾頓圖。證明 若n2，則2nm23m6 （1）。

9、若存在兩個(gè)不相鄰結(jié)點(diǎn)、使得d()d()m，則有2nm(m2)(m3)mm23m6，與（1）矛盾。所以，對(duì)于G中任意兩個(gè)不相鄰結(jié)點(diǎn)、都有d()d()m。由定理10.26可知，G是哈密爾頓圖。離散數(shù)學(xué)試題（B卷答案）一、（10分）使用將命題公式化為主范式的方法，證明(P®Q)®(PQ)Û(Q®P)(PQ)。證明：因?yàn)?P®Q)®(PQ)ÛØ(ØPQ)(PQ)Û(PØQ)(PQ)(Q®P)(PQ)Û(ØQP)(PQ)Û(PØQ)(Ø

10、QQ)(PP) (PQ)Û(PØQ)PÛ(PØQ)(P(QØQ)Û(PØQ)(PQ)(PØQ)Û(PØQ)(PQ) 所以，(P®Q)®(PQ)Û(Q®P)(PQ)。二、（10分）證明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，則D不愉快。解 設(shè)A：A努力工作；B、C、D分別表示B、C、D愉快；則推理化形式為：A®BC，B®ØA，D®

11、16;CA®ØD(1)A 附加前提(2)A®BC P(3)BC T(1)(2)，I(4)B®ØA P(5)A®ØB T(4)，E(6)ØB T(1)(5)，I(7)C T(3)(6)，I(8)D®ØC P(9)ØD T(7)(8)，I(10)A®ØD CP三、（10分）證明"x"y(P(x)®Q(y)Û($xP(x)®"yQ(y)。"x"y(P(x)®Q(y)Û&qu

12、ot;x"y(ØP(x)Q(y)Û"x(ØP(x)"yQ(y)Û"xØP(x)"yQ(y)ÛØ$xP(x)"yQ(y)Û($xP(x)®"yQ(y)四、（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)

13、97;BÆ，0，0，0，0Å0，0Æ，0，0，0，0五、（15分）設(shè)X1，2，3，4，R是X上的二元關(guān)系，R<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>(1)畫(huà)出R的關(guān)系圖。(2)寫(xiě)出R的關(guān)系矩陣。(3)說(shuō)明R是否是自反、反自反、對(duì)稱、傳遞的。解 (1)R的關(guān)系圖如圖所示：(2) R的關(guān)系矩陣為：(3)對(duì)于R的關(guān)系矩陣，由于對(duì)角線上不全為1，R不是自反的；由于對(duì)角線上存在非0元，R不是反自反的；由

14、于矩陣不對(duì)稱，R不是對(duì)稱的；經(jīng)過(guò)計(jì)算可得，所以R是傳遞的。六、（15分）設(shè)函數(shù)f：R×R®R×R，f定義為：f(<x，y>)<xy，xy>。(1)證明f是單射。(2)證明f是滿射。(3)求逆函數(shù)f1。(4)求復(fù)合函數(shù)f1of和fof。證明 (1)對(duì)任意的x，y，x1，y1R，若f(<x，y>)f(<x1，y1>)，則<xy，xy><x1y1，x1y1>，xyx1y1，xyx1y1，從而xx1，yy1，故f是單射。(2)對(duì)任意的<u，w>R×R，令x，y，則f(<x，

15、y>)<，><u，w>，所以f是滿射。(3)f1(<u，w>)<，>。(4)f1of(<x，y>)f1(f(<x，y>)f1(<xy，xy>)<，><x，y>fof(<x，y>)f(f(<x，y>)f(<xy，xy>)<xyxy，xy(xy)><2x，2y>。七、（15分）給定群<G，*>，若對(duì)G中任意元a和b，有a3*b3(a*b)3，a4*b4(a*b)4，a5*b5(a*b)5，試證<G，*>是Abel群。證明 對(duì)G中任意元a和b。因?yàn)閍3*b3(a*b)3，所以*a3*b3*(a*b)3*，即得a2*b2(b*a)2。同理，由a4*b4(a*b)4可得，a3*b3(b*a)3。由a5*b5(a*b)5可得，a4*b4(b*a)4。于是(a3*b3)*(b*a)(b*a)4a4*b4，即b4*aa*b4。同理可得，(a2*b2)*(b*a)(b*a)3a3*b3，即b3*aa*b3。由于(a*b)*b3a*b4b4*ab*(b3*a)b*(a*b3)(b*a)*b3，故a*b