中南大學(xué)離散考試試卷

中南大學(xué)考試試卷2009--2010學(xué)年一學(xué)期期末考試試題時(shí)間100分鐘離散數(shù)學(xué)課程48學(xué)時(shí)3學(xué)分考試形式：閉卷判斷（本大題共10小題，每小題1分，共10分）（）1．ρ(A)ρ(B)<=>A是B的子集（）2．Q∧R∨P∧R∨T∧?P∧R的對(duì)偶式為Q∨R∧P∨R∧F∨?P∨R（）3．設(shè)Ａ和Ｂ是兩個(gè)命題公式，若Ａ=＞B且B是重言式，則A是重言式。（）4．R和S都是集合A上的關(guān)系，若R和S是自反的，則RS是自反的。（）5．設(shè)A、B和C是集合，若A∩B=A∩C，且，則B=C。（）6．若R和S都是集合A上的二元關(guān)系，則dom(R)∪dom(S)=dom(R∪S)。（）7．<A;R>是全序集，則A的任何非空子集必有唯一極小元。（）8．有限集上的全序關(guān)系必是良序關(guān)系。（）9．連通的4度正則圖一定沒(méi)有橋。（）10.設(shè)無(wú)向圖G具有割點(diǎn)，則G中一定不存在哈密爾頓通路。單項(xiàng)選擇（本大題共6小題，每小題2分，共12分）（）1．若公式A(P,Q,R)的主合取范式為∏（0，1，4，5），則下列公式哪個(gè)是A(P,Q,R)的主析取范式 ①∑（0，1，4，5）②∏（0，1，4，5）③∑（2，3，6，7）④∏（2，3，6，7）（）2．設(shè)∏1和∏2都是非空集合A的劃分，則下列集合哪個(gè)必定是A的劃分 ①∏1∪∏2②∏1∩∏2③∏1—∏2④（∏1∩（∏2—∏1））∪∏2（）3．設(shè)A-B=，則下列命題中正確的是 ①B=②B≠③AB ④BA（）4．設(shè)R是集合A上的偏序關(guān)系，R-1是R的逆關(guān)系，則R∪R-1是 ①偏序關(guān)系 ②等價(jià)關(guān)系 ③非自反關(guān)系 ④非傳遞關(guān)系（）5．若f、g是A上的雙射，則 ①是雙射 ②-1 =f-1g-1 ③④以上答案都不對(duì)（）6．任何無(wú)向圖中結(jié)點(diǎn)間的可達(dá)關(guān)系是 ①偏序關(guān)系 ②等價(jià)關(guān)系 ③全序關(guān)系 ④擬序關(guān)系填空（本大題共9小題，每空2分，共24分）若簡(jiǎn)單連通平面圖G有4個(gè)結(jié)點(diǎn)，3個(gè)面，則G有______條邊。下圖G最少需要_____種顏色進(jìn)行點(diǎn)著色。若用謂詞R(x)表示“x是實(shí)數(shù)”，L(x,y)表示“x<y”，那么命題“對(duì)于任意實(shí)數(shù)x和y，若x<y，則必存在實(shí)數(shù)z使得x<z且z<y”的謂詞表達(dá)式為：_________________。給定論域D={1,2}和謂詞P：。則公式的真值為_____。若A是n元集合（n>0），則有______個(gè)不同的A上的即對(duì)稱又反對(duì)稱的關(guān)系。一棵樹有兩個(gè)2度頂點(diǎn)，一個(gè)3度頂點(diǎn)，三個(gè)4度頂點(diǎn)，則該樹有______片樹葉ebebcad則A的最大元是________；A的最小元是________；A的極大元是________；A的極小元是________；設(shè)N是自然數(shù)集合，f和g是N到N的函數(shù)，f(n)=2n+1,g(n)=n2，則復(fù)合函數(shù)(n)=______集合Ａ={1,2,3,4,5}上的等價(jià)關(guān)系Ｒ=將導(dǎo)致集合Ａ的劃分，即商集Ａ/Ｒ={{1,2},{3},{4,5}}。計(jì)算與作圖（共36分）(8分)設(shè)Ａ={2,3,12,18,24,30,36,72}，｜為自然數(shù)的整除關(guān)系。畫出<Ａ;｜>的Ｈasse圖，并求{12,24,36}的上、下確界。010010010010110(8分)設(shè)集合A={a,b,c,d}上的關(guān)系R的關(guān)系矩陣M(R)=分別作出R2，r(R)，sr(R)和tsr(R)的關(guān)系矩陣。(12分)有8種化學(xué)品a,b,c,d,e,f,g,h要放進(jìn)貯藏室保管.下列各對(duì)化學(xué)品不能貯藏在同一室內(nèi):a-c,a-f,a-h,b-d,b-f,b-h,c-d,c-g,d-e,d-g,e-f,e-g,f-g,g-h(5分)畫一個(gè)圖表示這些化學(xué)品不能混放的情況，并對(duì)你的圖加以文字說(shuō)明；(4分)貯藏這8種化學(xué)藥物至少需要幾個(gè)房間.一個(gè)房間最多貯藏多少種化學(xué)品，請(qǐng)寫出一種方案；(3分)假如每種化學(xué)品的專家一定熟悉與該種化學(xué)品不能混放的化學(xué)品的特性(例如化學(xué)品a的專家熟悉化學(xué)品c,f,h),則至少需要聘任多少位專家,才能使每種化學(xué)品都有對(duì)其特性熟悉的人，請(qǐng)給出一種聘任方案。證明（本大題共3小題，每小題6分，共18分）用形式推理的標(biāo)準(zhǔn)格式證明：,判斷是否是重言式，并說(shuō)明理由。證明:任意一場(chǎng)聚會(huì),至少有兩個(gè)人與相同數(shù)目的人握過(guò)手。

評(píng)分標(biāo)準(zhǔn)判斷(1)T (2)F (3)F (4)T (5)F(6)T (7)F (8)T (9)T (10)F單項(xiàng)選擇1.③ 2.④ 3.③ 4.② 5.① 6.②填空1.5 2.3 3.xy(R(x)∧R(y)∧L(x,y)→z(R(z)∧L(x,z)∧L(z,y)))_或xy(R(x)∧R(y)→(L(x,y)→z(R(z)∧L(x,z)∧L(z,y))))或與之等價(jià)的其他形式。4.T 5.2n 6.9 7.最大元：無(wú)；最小元：a；極大元：b,e,d；極小元：a8.2n2+1 9.{<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,2>,<2,1>,<4,5>,<5,4>}計(jì)算與作圖31231218302436722 （4分）{12,24,36}的上確界：72；下確界：12 （上下確界各2分）2.有右逆無(wú)左逆（2分）g1={<1,a>,<2,c>}；g2={<1,b>,<2,c>}；g3={<1,d>,<2,c>}（每個(gè)2分）010010010110010010010110010111R2= r(R)= 111111111111111111111111sr(R)= tsr(R)=（每個(gè)2分）4.(1)節(jié)點(diǎn)表示化學(xué)藥品，如果兩種藥品不能混放就在其間連一條邊，圖略；或者節(jié)點(diǎn)表示化學(xué)藥品，如果兩種藥品能混放就在其間連一條邊(2)如果是上述第一種畫圖法，即在圖中尋找極大頂點(diǎn)無(wú)關(guān)集；如果是第二種畫圖法，即在圖中尋找極大完全子圖。至少需要3個(gè)房間，每個(gè)房間最多放3中藥品。一種放置方案：{a,b,g},{c,e,h},{d,f}（不唯一）(3)至少需要2人，比如請(qǐng)g和f的專家證明1.,⑴AP(附加前提)⑵A∨B T⑴I⑶(A∨B)(C∧D) P⑷C∧DT⑵⑶I⑸D T⑷I⑹D∨E T⑸I⑺(D∨E)PP⑻PT⑹⑺I⑼AP CP（格式不對(duì)酌情扣分）2.不是永真式，取解釋如下 D={1,2} P(1)P(2)Q(1)Q(2) FTFT 在該解釋下xP(x)為T，xQ(x)為F，所以xP(x)→xQ(x)為F；而(P(1)→Q(1))為T，(P(2)→Q(2))為T，所以x(P(x)→Q(x))為T；綜上該公式不是永真式3.因?yàn)橐粋€(gè)人若與同一人握手多次不會(huì)影響其握手的人數(shù)，所以該問(wèn)題即證任一無(wú)向簡(jiǎn)單圖中必有兩個(gè)點(diǎn)的度相等證明略離散數(shù)學(xué)考試試題（A卷及答案）一、（10分）判斷下列公式的類型（永真式、永假式、可滿足式）？1)((PQ)∧Q)((Q∨R)∧Q)2)((QP)∨P)∧(P∨R)3)((P∨Q)R)((P∧Q)∨R)解：1)永真式；2）永假式；3)可滿足式。二、（8分）個(gè)體域?yàn)閧1，2}，求xy（x+y=4）的真值。解：xy（x+y=4）x（（x+1=4）∨（x+2=4））（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））（0∨0）∧（0∨1）1∧10三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元關(guān)系數(shù)是多少？A到B的函數(shù)數(shù)是多少？解：因?yàn)閨P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元關(guān)系有2mn個(gè)。因?yàn)閨BA|=|B||A|=mn，所以A到B的函數(shù)mn個(gè)。四、（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>,<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分)75個(gè)兒童到公園游樂(lè)場(chǎng)，他們?cè)谀抢锟梢则T旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船，已知其中20人這三種東西都乘過(guò)，其中55人至少乘坐過(guò)其中的兩種。若每樣乘坐一次的費(fèi)用是0.5元，公園游樂(lè)場(chǎng)總共收入70元，求有多少兒童沒(méi)有乘坐過(guò)其中任何一種。解設(shè)、、分別表示騎旋轉(zhuǎn)木馬、坐滑行鐵道、乘宇宙飛船的兒童組成的集合，|∩∩|＝20，|∩|＋|∩|＋|∩|－2|∩∩|＝55，||＋||＋||＝70/0.5＝140。由容斥原理，得|∪∪|＝||＋||＋||―|∩|―|∩|―|∩|＋|∩∩|所以|∩∩|＝75－|∪∪|＝75－(||＋||＋||)＋(|∩|＋|∩|＋|∩|－2|∩∩|)＋|∩∩|＝75－140＋55＋20＝10沒(méi)有乘坐過(guò)其中任何一種的兒童共10人。六、（12分）已知R和S是非空集合A上的等價(jià)關(guān)系，試證：1）R∩S是A上的等價(jià)關(guān)系；2）對(duì)a∈A，[a]R∩S=[a]R∩[a]S。解：x∈A，因?yàn)镽和S是自反關(guān)系，所以<x,x>∈R、<x,x>∈S，因而<x,x>∈R∩S，故R∩S是自反的。x、y∈A，若<x,y>∈R∩S，則<x,y>∈R、<x,y>∈S，因?yàn)镽和S是對(duì)稱關(guān)系，所以因<y,x>∈R、<y,x>∈S，因而<y,x>∈R∩S，故R∩S是對(duì)稱的。x、y、z∈A，若<x,y>∈R∩S且<y,z>∈R∩S，則<x,y>∈R、<x,y>∈S且<y,z>∈R、<y,z>∈S，因?yàn)镽和S是傳遞的，所以因<x,z>∈R、<x,z>∈S，因而<x,z>∈R∩S，故R∩S是傳遞的。總之R∩S是等價(jià)關(guān)系。2）因?yàn)閤∈[a]R∩S<x,a>∈R∩S<x,a>∈R∧<x,a>∈Sx∈[a]R∧x∈[a]Sx∈[a]R∩[a]S所以[a]R∩S=[a]R∩[a]S。七（10分）設(shè)A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×CB×D且<a,c>∈A×C，h(<a,c>)＝<f(a),g(c)>。證明h是雙射。證明：1）先證h是滿射。<b,d>∈B×D，則b∈B，d∈D，因?yàn)閒是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在<a,c>∈A×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的雙射，所以a1＝a2，c1＝c2，所以<a1,c1>＝<a2,c2>，所以h是單射。綜合1）和2），h是雙射。八、（12分）<G,*>是個(gè)群，u∈G，定義G中的運(yùn)算“”為ab=a*u-1*b，對(duì)任意a,b∈G，求證：<G,>也是個(gè)群。證明：1）a,b∈G，ab=a*u-1*b∈G，運(yùn)算是封閉的。2）a,b,c∈G，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc），運(yùn)算是可結(jié)合的。3）a∈G，設(shè)E為的單位元，則aE=a*u-1*E=a，得E=u，存在單位元。4）a∈G，ax=a*u-1*x=E，x=u*a-1*u，則xa=u*a-1*u*u-1*a=u=E，每個(gè)元素都有逆元。所以<G,>也是個(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。解：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)＝148離散數(shù)學(xué)考試試題（B卷及答案）一、（10分）求命題公式(P∧Q)(PR)的主合取范式。解：(P∧Q)(PR)（(P∧Q)(PR)）∧（(PR)(P∧Q)）（(P∧Q)∨(P∧R)）∧（(P∨R)∨(P∨Q)）(P∧Q)∨(P∧R)(P∨R)∧（Q∨P）∧（Q∨R）(P∨Q∨R)∧(P∨Q∨R)∧（P∨Q∨R）∧（P∨Q∨R）M1∧M3∧M4∧M5二、（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、C是三個(gè)集合，證明A∩(B∪C)=(A∩B)∪(A∩C)證明：∵xA∩（B∪C）xA∧x（B∪C）xA∧（xB∨xC）（xA∧xB）∨（xA∧xC）x（A∩B）∨xA∩Cx（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）四、（10分）已知R和S是非空集合A上的等價(jià)關(guān)系，試證：1）R∩S是A上的等價(jià)關(guān)系；2）對(duì)a∈A，[a]R∩S=[a]R∩[a]S。解：x∈A，因?yàn)镽和S是自反關(guān)系，所以<x,x>∈R、<x,x>∈S，因而<x,x>∈R∩S，故R∩S是自反的。x、y∈A，若<x,y>∈R∩S，則<x,y>∈R、<x,y>∈S，因?yàn)镽和S是對(duì)稱關(guān)系，所以因<y,x>∈R、<y,x>∈S，因而<y,x>∈R∩S，故R∩S是對(duì)稱的。x、y、z∈A，若<x,y>∈R∩S且<y,z>∈R∩S，則<x,y>∈R、<x,y>∈S且<y,z>∈R、<y,z>∈S，因?yàn)镽和S是傳遞的，所以因<x,z>∈R、<x,z>∈S，因而<x,z>∈R∩S，故R∩S是傳遞的。總之R∩S是等價(jià)關(guān)系。2）因?yàn)閤∈[a]R∩S<x,a>∈R∩S<x,a>∈R∧<x,a>∈Sx∈[a]R∧x∈[a]Sx∈[a]R∩[a]S所以[a]R∩S=[a]R∩[a]S。五、(10分)設(shè)A＝{a，b，c，d}，R是A上的二元關(guān)系，且R＝{<a，b>，<b，a>，<b，c>，<c，d>}，求r(R)、s(R)和t(R)。解r(R)＝R∪IA＝{<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<c，c>，<d，d>}s(R)＝R∪R-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>，<a，a>，<a，c>，<b，b>，<b，d>，<a，d>}六、(15分)設(shè)A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×CB×D且<a,c>∈A×C，h(<a,c>)＝<f(a),g(c)>。證明h是雙射。證明：1）先證h是滿射。<b,d>∈B×D，則b∈B，d∈D，因?yàn)閒是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在<a,c>∈A×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(