離散數(shù)學考前綜合復習資料

1、離散數(shù)學綜合復習資料一、判斷題1 A、B、C是任意命題公式，如果AÙCÛBÙC，一定有AÛB。（ ）2設<A，*>是一個代數(shù)系統(tǒng)，且集合A中元素的個數(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)結詞Ø，Ù，Ú是最小聯(lián)結詞組。（ ）6 有理數(shù)集是可數(shù)的。（ ）7 交換群必是循環(huán)群。（ ）8 圖G的鄰接矩陣A，Al中的i行j列表示結點vi到vj長度為l路的數(shù)目。（ ）二

2、、解答題1 求命題公式Ø(P®Q)的主析取范式。2 舉出A=a,b,c上的二元關系R和S滿足： （1）R既不是自反的又不是反自反的，既是對稱的又是反對稱的；（2）S既不是對稱的又不是反對稱的，是傳遞的。3 以下哪些是函數(shù)？哪些是入射？哪些是滿射？對任意一個雙射，寫出它們的逆函數(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ù)集關于減法； (2) <I，+>：整數(shù)集關于加法；

3、5.構造一非空偏序集，它存在一子集有上界，但沒有最小上界。它還有一子集，存在最大下界但沒有最小元。d ° b°°e°c°a6.畫一個有歐拉回路，但沒有漢密爾頓回路的圖。7.將下列命題符號化（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.設G=<V,E>，V=V1,V2,V3,V4的鄰接矩陣：（1）試畫出該圖。（

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

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

6、證明：R是A上的等價關系。7 代數(shù)系統(tǒng)<I,+>是一個群，設B=x|x=5n,nÎI，證明：<B,+>是<I,+>的子群。8 連通圖至少有一棵生成樹離散數(shù)學綜合復習資料答案一、判斷題題號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ù)？哪些是入射？哪些是滿射？對任意一個雙射，寫出它們的逆函數(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時無定義。（2） 函數(shù)，雙射，f-1(x,y)=<y-1,x-1>4、判斷下列代數(shù)系統(tǒng)是否是群，并說明理由：(1) <R，->：實數(shù)集關于減法； (2) <I，+>：整數(shù)集關于加法；解：（1）+在R上是封閉的，不可結合所以<R，->不是

8、群；（2）+在I上是封閉的，可結合的，幺元是0，I中任意元素x的逆元為-x，所以<I，+>是群；5、構造一非空偏序集，它存在一子集有上界，但沒有最小上界。它還有一子集，存在最大下界但沒有最小元。解：右圖所示哈斯圖表示一個偏序集，其中：子集B=b，c有上界d，e但沒有最小上界，同時子集B=b，c有最大下界a，但沒有最小元。 6、畫一個有歐拉回路，但沒有漢密爾頓回路的圖。解：7、將下列命題符號化（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）因為a(3)12=2，所以V1到V2長度為3的路有2條。9將下列命題符號化（1）除非你走否則我留下。（ØP®Q）（2）我們不能邊看電視邊看報。（Ø（PÙQ)）10設集合A有m個元素，B有n個元素，則A到B的關系有多少個？A到B的函數(shù)有多少個？解：1）A到B的關系有2mn個。2）A到B的函數(shù)有nm個。 11設有一組權3、4、13、5、6、12，（1）求相應的最優(yōu)樹（要求構造的過程中，每個分支點的左兒子的權小于右兒子

10、的權）。（2）設上述權值分別對應英文字母b、d、e、g、o、y，試根據(jù)求得的最優(yōu)樹構造前綴碼，并對二進制序列譯碼。解：（1）見下頁（2）將上面的最優(yōu)樹的每個分枝點引出的兩條邊，左側邊標0，右側邊標1，得到一個b、d、e、g、o、y對應的前綴碼000，001，11，010，011，10。對二進制序列譯碼為goodbye。34567111912132544 0 1 0 1 0 10 1 0 1 y eb d g o三、證明題1.設R,S是A上的等價關系，證明RÇS也是A上的等價關系。證明：a)自反性：對任意aÎA，因為<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。因為R,S是等價關系，所以具有對稱性，所以<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則因為R,S是等價關系，所以具有傳遞性，所以<a,c>ÎR且<a,c>ÎS所以<a, c>ÎRÇS，即RÇS具有傳遞性。所以RÇS是A上的等價關系。2.設f和g都是群<A，*>到<B，>的同態(tài)，令H=x|xÎA，f(x)=g(x)，試證：<H，*>是<A，*>的子群。證明 由定義知HÍA （1）設e是<

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

15、ÍG，設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 證明當且僅當G的一條邊e不包含在G的回路中時，e才是G的割邊。證明：必要性：設e是圖G的割邊，e關聯(lián)的兩個結點是a,b。如果e包含在G的一個回路中，那么除了邊e=(a,b)外，a到b還有一條路存在，所以刪去e后，a,b之間仍然連通，與e是割邊

16、矛盾。充分性：如果邊e不包含在G的回路中，則連接a,b只有邊e。所以刪除邊e后，a,b不再連通，所以e是G的割邊。6 設f是從A到B的一個函數(shù)，定義A上的關系R：aRb當且僅當f(a)=f(b)，證明：R是A上的等價關系。證明：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上的等價關系。7 代數(shù)系統(tǒng)<I,+>是一個群，設B=x|x=5n,nÎI，證明：<B,+>是<I,+>的子群。證明：由題意知BÍI并且B非空，設"x,yÎB則有x,yÎI，且x=5n1, y=5n2(n1,n2