離散數(shù)學(xué)期末試題

1、1離散數(shù)學(xué)考試試題（A卷及答案）一、（10分）求(P?Q)?(P∧?(Q∨?R))的主析取范式解：(P?Q)?(P∧?(Q∨?R))??(?(P∨Q))∨(P∧?Q∧R))?(P∨Q)∨(P∧?Q∧R))?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R)?(P∨Q)∧(P∨Q∨R)?(P∨Q∨(R∧?R))∧(P∨Q∨R)?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)?∧0M1M?∨∨∨∨∨2m3m4m5m6m7m二、（10分）在某

2、次研討會(huì)的休息時(shí)間，3名與會(huì)者根據(jù)王教授的口音分別作出下述判斷：甲說：王教授不是蘇州人，是上海人。乙說：王教授不是上海人，是蘇州人。丙說：王教授既不是上海人，也不是杭州人。王教授聽后說：你們3人中有一個(gè)全說對(duì)了，有一人全說錯(cuò)了，還有一個(gè)人對(duì)錯(cuò)各一半。試判斷王教授是哪里人？解設(shè)設(shè)P：王教授是蘇州人；Q：王教授是上海人；R：王教授是杭州人。則根據(jù)題意應(yīng)有：甲：?P∧Q乙：?Q∧P丙：?Q∧?R王教授只可能是其中一個(gè)城市的人或者3個(gè)城市都不是

3、。所以，丙至少說對(duì)了一半。因此，可得甲或乙必有一人全錯(cuò)了。又因?yàn)?，若甲全錯(cuò)了，則有?Q∧P，因此，乙全對(duì)。同理，乙全錯(cuò)則甲全對(duì)。所以丙必是一對(duì)一錯(cuò)。故王教授的話符號(hào)化為：((?P∧Q)∧((Q∧?R)∨(?Q∧R)))∨((?Q∧P)∧(?Q∧R))?(?P∧Q∧Q∧?R)∨(?P∧Q∧?Q∧R)∨(?Q∧P∧?Q∧R)?(?P∧Q∧?R)∨(P∧?Q∧R)??P∧Q∧?R?T因此，王教授是上海人。三、（10分）證明tsr(R)是包含R

4、的且具有自反性、對(duì)稱性和傳遞性的最小關(guān)系。證明設(shè)R是非空集合A上的二元關(guān)系，則tsr(R)是包含R的且具有自反性、對(duì)稱性和傳遞性的關(guān)系。若是包含R的且具有自反性、對(duì)稱性和傳遞性的任意關(guān)系，則由閉包的定義知r(R)?。則sr(R)RR3射，f是滿射；因IC恒等函數(shù)，由g?f?h＝IC可得h是單射，g是滿射。從而f、g、h均為雙射。由h?g?f＝IA，得f－1＝h?g；由f?h?g＝IB，得g－1＝f?h；由g?f?h＝IC，得h－1＝g?

5、f。七、（15分）設(shè)是一代數(shù)系統(tǒng)，運(yùn)算滿足交換律和結(jié)合律，且ax＝ay?x＝y(tǒng)，證明：若G有限，則G是一群。證明因G有限，不妨設(shè)G＝，，…，。由ax＝ay?x＝y(tǒng)得，若x≠y，則ax≠ay。1a2ana于是可證，對(duì)任意的a∈G，有aG＝G。又因?yàn)檫\(yùn)算滿足交換律，所以aG＝G＝Ga。令e∈G使得ae＝a。對(duì)任意的b∈G，令ca＝b，則be＝(ca)e＝c(ae)＝ca＝b，再由運(yùn)算滿足交換律得eb＝b，所以e是關(guān)于運(yùn)算的幺元。對(duì)任意a∈G

6、，由aG＝G可知，存在b∈G使得ab＝e，再由運(yùn)算滿足交換律得ba＝e，所以b是a的逆元。由a的任意性知，G中每個(gè)元素都存在逆元。故G是一群。八、（20分）（1）證明在n個(gè)結(jié)點(diǎn)的連通圖G中，至少有n－1條邊。證明不妨設(shè)G是無向連通圖（若G為有向圖，可略去邊的方向討論對(duì)應(yīng)的無向圖）。設(shè)G中結(jié)點(diǎn)為、、…、。由連通性，必存在與相鄰的結(jié)點(diǎn)，不妨設(shè)它為（否則可重新編1v2vnv1v2v號(hào)），連接和，得邊，還是由連通性，在、、…、中必存在與或相鄰的

7、結(jié)點(diǎn)，不妨設(shè)為1v2v1e3v4vnv1v2v，將其連接得邊，續(xù)行此法，必與、、…、中的某個(gè)結(jié)點(diǎn)相鄰，得新邊，由此可見G3v2env1v2v1?nv1?ne中至少有n－1條邊。（2）給定簡單無向圖G＝，且|V|＝m，|E|＝n。試證：若n≥＋2，則G是哈密爾頓圖。21?mC證明若n≥＋2，則2n≥m2－3m＋6（1）。21?mC若存在兩個(gè)不相鄰結(jié)點(diǎn)、使得d()＋d()＜m，則有2n＝＜m＋(m－2)(m－3)uvuv??Vwwd)(＋m