1、離散數(shù)學(xué)綜合復(fù)習(xí)資料一、判斷題1 A、B、C是任意命題公式，如果AÙCÛBÙC，一定有AÛB。（ ）2設(shè)<A，*>是一個(gè)代數(shù)系統(tǒng)，且集合A中元素的個(gè)數(shù)大于1。如果該代數(shù)系統(tǒng)中存在幺元e和零元q，則e¹q。（ ）3 A、B、C為任意集合，已知AÈB=AÈC，必須有B=C。（ ）4 自然數(shù)集是可數(shù)的。（ ）5 命題聯(lián)結(jié)詞Ø，Ù，Ú是最小聯(lián)結(jié)詞組。（ ）6 有理數(shù)集是可數(shù)的。（ ）7 交換群必是循環(huán)群。（ ）8 圖G的鄰接矩陣A，Al中的i行j列表示結(jié)點(diǎn)vi到vj長度為l路的數(shù)目。（ ）二

2、、解答題1 求命題公式Ø(P®Q)的主析取范式。2 舉出A=a,b,c上的二元關(guān)系R和S滿足： （1）R既不是自反的又不是反自反的，既是對稱的又是反對稱的；（2）S既不是對稱的又不是反對稱的，是傳遞的。3 以下哪些是函數(shù)？哪些是入射？哪些是滿射？對任意一個(gè)雙射，寫出它們的逆函數(shù)。（1） f: N®Q, f(x) = 1/x（2） f: R´R®R´R, f(x,y)=<y+1,x+1>4 判斷下列代數(shù)系統(tǒng)是否是群，并說明理由：(1) <R，->：實(shí)數(shù)集關(guān)于減法； (2) <I，+>：整數(shù)集關(guān)于加法；

3、5.構(gòu)造一非空偏序集，它存在一子集有上界，但沒有最小上界。它還有一子集，存在最大下界但沒有最小元。d ° b°°e°c°a6.畫一個(gè)有歐拉回路，但沒有漢密爾頓回路的圖。7.將下列命題符號(hào)化（1）如果張三和李四都不去，她就去。（ØPÙØQ）®R）（2）今天要么是晴天，要么是雨天。（P"Q）v4V5v1v2v30 1 0 0 01 0 1 0 00 1 0 0 00 0 0 0 10 0 0 1 0A(G)=8.設(shè)G=<V,E>，V=V1,V2,V3,V4的鄰接矩陣：（1）試畫出該圖。（

4、2）V2的入度d-(V2)和出度d+(V2)是多少？（3）利用鄰接矩陣的性質(zhì)求從V1到V2長度為3的路有幾條？9.將下列命題符號(hào)化（1）除非你走否則我留下。（2）我們不能邊看電視邊看報(bào)。10.設(shè)集合A有m個(gè)元素，B有n個(gè)元素，則A到B的關(guān)系有多少個(gè)？A到B的函數(shù)有多少個(gè)？11.設(shè)有一組權(quán)3、4、13、5、6、12，（1）求相應(yīng)的最優(yōu)樹（要求構(gòu)造的過程中，每個(gè)分支點(diǎn)的左兒子的權(quán)小于右兒子的權(quán)）。（2）設(shè)上述權(quán)值分別對應(yīng)英文字母b、d、e、g、o、y，試根據(jù)求得的最優(yōu)樹構(gòu)造前綴碼，并對二進(jìn)制序列譯碼。三、證明題1 設(shè)R,S是A上的等價(jià)關(guān)系，證明RÇS也是A上的等價(jià)關(guān)系。2 設(shè)f和g都是群

5、<A，*>到<B，>的同態(tài)，令H=x|xÎA，f(x)=g(x)，試證：<H，*>是<A，*>的子群。3 當(dāng)且僅當(dāng)連通圖的每條邊均為割邊時(shí)，該連通圖才是一棵樹。4 f是群<G,°>到群<G,*>的同態(tài)映射，e是G中的幺元?jiǎng)t，f的同態(tài)核K=x|xÎG且f(x)=e構(gòu)成的代數(shù)系統(tǒng)<K,°>是<G,°>的子群。5 證明當(dāng)且僅當(dāng)G的一條邊e不包含在G的回路中時(shí)，e才是G的割邊。6 設(shè)f是從A到B的一個(gè)函數(shù)，定義A上的關(guān)系R：aRb當(dāng)且僅當(dāng)f(a)=f(b)，

6、證明：R是A上的等價(jià)關(guān)系。7 代數(shù)系統(tǒng)<I,+>是一個(gè)群，設(shè)B=x|x=5n,nÎI，證明：<B,+>是<I,+>的子群。8 連通圖至少有一棵生成樹離散數(shù)學(xué)綜合復(fù)習(xí)資料答案一、判斷題題號(hào)12345678答案二、解答題1、求命題公式Ø(P®Q)的主析取范式。解：Ø(P®Q)ÛØ(ØPÚQ)ÛPÙØQ2、 解：（1）R = <a,a>,<b,b>（2） S=<a,a>,<b,b><a,b&g

7、t;,<b,a><a,c>3、以下哪些是函數(shù)？哪些是入射？哪些是滿射？對任意一個(gè)雙射，寫出它們的逆函數(shù)。（1） f: N®Q, f(x) = 1/x（2） f: R´R®R´R, f(x,y)=<y+1,x+1>解：（1）不是函數(shù)，在x=0時(shí)無定義。（2） 函數(shù)，雙射，f-1(x,y)=<y-1,x-1>4、判斷下列代數(shù)系統(tǒng)是否是群，并說明理由：(1) <R，->：實(shí)數(shù)集關(guān)于減法； (2) <I，+>：整數(shù)集關(guān)于加法；解：（1）+在R上是封閉的，不可結(jié)合所以<R，->不是

8、群；（2）+在I上是封閉的，可結(jié)合的，幺元是0，I中任意元素x的逆元為-x，所以<I，+>是群；5、構(gòu)造一非空偏序集，它存在一子集有上界，但沒有最小上界。它還有一子集，存在最大下界但沒有最小元。解：右圖所示哈斯圖表示一個(gè)偏序集，其中：子集B=b，c有上界d，e但沒有最小上界，同時(shí)子集B=b，c有最大下界a，但沒有最小元。 6、畫一個(gè)有歐拉回路，但沒有漢密爾頓回路的圖。解：7、將下列命題符號(hào)化（1）如果張三和李四都不去，她就去。（ØPÙØQ）®R）（2）今天要么是晴天，要么是雨天。（P"Q）v4V5v1v2v30 1 0 0 01 0

9、 1 0 00 1 0 0 00 0 0 0 10 0 0 1 0A(G)=8、解：（1）如右上圖（2）d-(V2)=2，d+(V2)=2（3）因?yàn)閍(3)12=2，所以V1到V2長度為3的路有2條。9將下列命題符號(hào)化（1）除非你走否則我留下。（ØP®Q）（2）我們不能邊看電視邊看報(bào)。（Ø（PÙQ)）10設(shè)集合A有m個(gè)元素，B有n個(gè)元素，則A到B的關(guān)系有多少個(gè)？A到B的函數(shù)有多少個(gè)？解：1）A到B的關(guān)系有2mn個(gè)。2）A到B的函數(shù)有nm個(gè)。 11設(shè)有一組權(quán)3、4、13、5、6、12，（1）求相應(yīng)的最優(yōu)樹（要求構(gòu)造的過程中，每個(gè)分支點(diǎn)的左兒子的權(quán)小于右兒子

10、的權(quán)）。（2）設(shè)上述權(quán)值分別對應(yīng)英文字母b、d、e、g、o、y，試根據(jù)求得的最優(yōu)樹構(gòu)造前綴碼，并對二進(jìn)制序列譯碼。解：（1）見下頁（2）將上面的最優(yōu)樹的每個(gè)分枝點(diǎn)引出的兩條邊，左側(cè)邊標(biāo)0，右側(cè)邊標(biāo)1，得到一個(gè)b、d、e、g、o、y對應(yīng)的前綴碼000，001，11，010，011，10。對二進(jìn)制序列譯碼為goodbye。34567111912132544 0 1 0 1 0 10 1 0 1 y eb d g o三、證明題1.設(shè)R,S是A上的等價(jià)關(guān)系，證明RÇS也是A上的等價(jià)關(guān)系。證明：a)自反性：對任意aÎA，因?yàn)?lt;a,a>ÎA,<a,a>

11、ÎS，所以<a,a>ÎRÇS，即RÇS具有自反性。b)對稱性：對任意a,bÎA，如果有<a,b>ÎRÇS，則<a,b>ÎR且<a,b>ÎS。因?yàn)镽,S是等價(jià)關(guān)系，所以具有對稱性，所以<b,a>ÎR且<b,a>ÎS。所以<b,a>ÎRÇS，即RÇS具有對稱性。c)傳遞性：對任意a,b,cÎA，若有<a,b>,<b,c>ÎRÇ

12、;S則<a,b>,<b,c>ÎR且<a,b>,<b,c>ÎS則因?yàn)镽,S是等價(jià)關(guān)系，所以具有傳遞性，所以<a,c>ÎR且<a,c>ÎS所以<a, c>ÎRÇS，即RÇS具有傳遞性。所以RÇS是A上的等價(jià)關(guān)系。2.設(shè)f和g都是群<A，*>到<B，>的同態(tài)，令H=x|xÎA，f(x)=g(x)，試證：<H，*>是<A，*>的子群。證明 由定義知HÍA （1）設(shè)e是<

13、;A,*>的幺元，e是<B,>的幺元， 因?yàn)閒,g都是<A，*>到<B，>的同態(tài)，則f(e)=g(e)=e，所以eÎH，所以H¹Æ； （2）"a,bÎH，有f(a)=g(a)，f(b)=g(b)， 因?yàn)閒,g都是同態(tài)映射，所以f(b)-1=f(b-1)且g(b)-1=g(b-1) 所以f(a* b-1)=f(a)f(b-1)=f(a)f(b)-1= g(a)g(b)-1=g(a)g(b-1)=g(a* b-1) 所以a* b-1ÎH，所以<H,*>是<A,*>的子群。3

14、 當(dāng)且僅當(dāng)連通圖的每條邊均為割邊時(shí)，該連通圖才是一棵樹。證明：必要性：如果圖G是樹，則刪去任一邊后就不連通，故任一邊均為G的割邊。充分性：任取兩個(gè)結(jié)點(diǎn)u,v，圖G連通，則u,v之間有路存在。若u,v間有兩條路，則可組成一個(gè)回路，則刪除回路上任一條邊后不改變圖的連通性，這樣該回路上的邊都不是割邊，與前提矛盾，因此任意兩個(gè)結(jié)點(diǎn)間恰有一條路，圖G是樹。4 f是群<G,°>到群<G,*>的同態(tài)映射，e是G中的幺元?jiǎng)t，f的同態(tài)核K=x|xÎG且f(x)=e構(gòu)成的代數(shù)系統(tǒng)<K,°>是<G,°>的子群。證明：由定義可知K

15、ÍG，設(shè)G中的幺元為e，則有f(e)=e，所以eÎA，即A為非空集合。對于任意的a,bÎK，有f(a)=e，f(b)=e則f(a°b-1)=f(a)*f(b-1)=f(a)*f(b)-1=e*e=e則a°b-1ÎK，因此<K,°>是<G,°>的子群。5 證明當(dāng)且僅當(dāng)G的一條邊e不包含在G的回路中時(shí)，e才是G的割邊。證明：必要性：設(shè)e是圖G的割邊，e關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)是a,b。如果e包含在G的一個(gè)回路中，那么除了邊e=(a,b)外，a到b還有一條路存在，所以刪去e后，a,b之間仍然連通，與e是割邊

16、矛盾。充分性：如果邊e不包含在G的回路中，則連接a,b只有邊e。所以刪除邊e后，a,b不再連通，所以e是G的割邊。6 設(shè)f是從A到B的一個(gè)函數(shù)，定義A上的關(guān)系R：aRb當(dāng)且僅當(dāng)f(a)=f(b)，證明：R是A上的等價(jià)關(guān)系。證明：a)自反性：對任意aÎA，f(a)=f(a)，所以aRa，即R是自反的。b)對稱性：對任意a，bÎA，若aRb，即f(a)=f(b)，即f(b)=f(a)，故bRa，即R是對稱的。c)傳遞性：對任意a，b，cÎA，若aRb，bRc，即f(a)=f(b)，f(b)=f(c)即f(a)=f(b) =f(c)，故aRc，即R是傳遞的。所以R是A上的等價(jià)關(guān)系。7 代數(shù)系統(tǒng)<I,+>是一個(gè)群，設(shè)B=x|x=5n,nÎI，證明：<B,+>是<I,+>的子群。證明：由題意知BÍI并且B非空，設(shè)"x,yÎB則有x,yÎI，且x=5n1, y=5n2(n1,n2