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

離散數(shù)學考前綜合復習資料離散數(shù)學考前綜合復習資料/離散數(shù)學考前綜合復習資料《離散數(shù)學》綜合復習資料一、判斷題1．A、B、C是任意命題公式，如果ACBC，一定有AB。（）2．設(shè)<A，*>是一個代數(shù)系統(tǒng)，且集合A中元素的個數(shù)大于1。如果該代數(shù)系統(tǒng)中存在幺元e和零元，則e。（）3．A、B、C為任意集合，已知AB=AC，必須有B=C。（）自然數(shù)集是可數(shù)的。（）命題聯(lián)結(jié)詞{，，}是最小聯(lián)結(jié)詞組。（）有理數(shù)集是可數(shù)的。（）交換群必是循環(huán)群。（）圖G的鄰接矩陣A，Al中的i行j列表示結(jié)點vi到vj長度為l路的數(shù)目。（）二、解答題求命題公式(PQ)的主析取范式。舉出A={a,b,c}上的二元關(guān)系R和S滿足：

（1）R既不是自反的又不是反自反的，既是對稱的又是反對稱的；

（2）S既不是對稱的又不是反對稱的，是傳遞的。以下哪些是函數(shù)？哪些是入射？哪些是滿射？對任意一個雙射，寫出它們的逆函數(shù)。f:NQ,f(x)=1/xf:RRRR,f(x,y)=<y+1,x+1>判斷下列代數(shù)系統(tǒng)是否是群，并說明理由：

(1)<R，->：實數(shù)集關(guān)于減法；(2)<I，+>：整數(shù)集關(guān)于加法；5.構(gòu)造一非空偏序集，它存在一子集有上界，但沒有最小上界。它還有一子集，存在最大下界但沒有最小元。ddbeca6.畫一個有歐拉回路，但沒有漢密爾頓回路的圖。7.將下列命題符號化

（1）如果張三和李四都不去，她就去。（（PQ）R）

（2）今天要么是晴天，要么是雨天。（PQ）v4V5v1v2v301000

10100

01000

00001

00010A(G)=8.設(shè)G=<V,E>，V={V1,V2,V3,V4}的鄰接矩陣：

（1）試畫出該圖。

v4V5v1v2v301000

10100

01000

00001

00010A(G)=9.將下列命題符號化

（1）除非你走否則我留下。（2）我們不能邊看電視邊看報。10.設(shè)集合A有m個元素，B有n個元素，則A到B的關(guān)系有多少個？A到B的函數(shù)有多少個？11.設(shè)有一組權(quán)3、4、13、5、6、12，

（1）求相應(yīng)的最優(yōu)樹（要求構(gòu)造的過程中，每個分支點的左兒子的權(quán)小于右兒子的權(quán)）。

（2）設(shè)上述權(quán)值分別對應(yīng)英文字母b、d、e、g、o、y，試根據(jù)求得的最優(yōu)樹構(gòu)造前綴碼，并對二進制序列10001011譯碼。三、證明題設(shè)R,S是A上的等價關(guān)系，證明RS也是A上的等價關(guān)系。設(shè)f和g都是群<A，*>到<B，eq\o\ac(○,*)>的同態(tài)，令H={x|xA，f(x)=g(x)}，

試證：<H，*>是<A，*>的子群。當且僅當連通圖的每條邊均為割邊時，該連通圖才是一棵樹。f是群<G,°>到群<G’,*>的同態(tài)映射，e’是G’中的幺元則，f的同態(tài)核K={x|xG且f(x)=e’}構(gòu)成的代數(shù)系統(tǒng)<K,°>是<G,°>的子群。證明當且僅當G的一條邊e不包含在G的回路中時，e才是G的割邊。設(shè)f是從A到B的一個函數(shù)，定義A上的關(guān)系R：aRb當且僅當f(a)=f(b)，證明：R是A上的等價關(guān)系。代數(shù)系統(tǒng)<I,+>是一個群，設(shè)B={x|x=5n,nI}，證明：<B,+>是<I,+>的子群。連通圖至少有一棵生成樹

《離散數(shù)學》綜合復習資料答案一、判斷題題號12345678答案╳√╳√╳√╳√二、解答題1、求命題公式(PQ)的主析取范式。解：(PQ)(PQ)PQ解：（1）R={<a,a>,<b,b>}S={<a,a>,<b,b><a,b>,<b,a><a,c>}3、以下哪些是函數(shù)？哪些是入射？哪些是滿射？對任意一個雙射，寫出它們的逆函數(shù)。f:NQ,f(x)=1/xf:RRRR,f(x,y)=<y+1,x+1>解：（1）不是函數(shù)，在x=0時無定義。函數(shù)，雙射，f-1(x,y)=<y-1,x-1>4、判斷下列代數(shù)系統(tǒng)是否是群，并說明理由：

(1)<R，->：實數(shù)集關(guān)于減法；(2)<I，+>：整數(shù)集關(guān)于加法；解：（1）+在R上是封閉的，不可結(jié)合

所以<R，->不是群；（2）+在I上是封閉的，可結(jié)合的，幺元是0，I中任意元素x的逆元為-x，

所以<I，+>是群；5、構(gòu)造一非空偏序集，它存在一子集有上界，但沒有最小上界。它還有一子集，存在最大下界但沒有最小元。解：右圖所示哈斯圖表示一個偏序集，其中：子集B={b，c}有上界d，e但沒有最小上界，同時子集B={b，c}有最大下界a，但沒有最小元。6、畫一個有歐拉回路，但沒有漢密爾頓回路的圖。解：7、將下列命題符號化

（1）如果張三和李四都不去，她就去。（（PQ）R）

（2）今天要么是晴天，要么是雨天。（PQ）v4V5v1v4V5v1v2v301000

10100

01000

00001

00010A(G)=解：（1）如右上圖

（2）d-(V2)=2，d+(V2)=2

（3）因為a(3)12=2，所以V1到V2長度為3的路有2條。9．將下列命題符號化

（1）除非你走否則我留下。（PQ）

（2）我們不能邊看電視邊看報。（（PQ)）10．設(shè)集合A有m個元素，B有n個元素，則A到B的關(guān)系有多少個？A到B的函數(shù)有多少個？

解：1）A到B的關(guān)系有2mn個。 2）A到B的函數(shù)有nm個。11．設(shè)有一組權(quán)3、4、13、5、6、12，

（1）求相應(yīng)的最優(yōu)樹（要求構(gòu)造的過程中，每個分支點的左兒子的權(quán)小于右兒子的權(quán)）。

（2）設(shè)上述權(quán)值分別對應(yīng)英文字母b、d、e、g、o、y，試根據(jù)求得的最優(yōu)樹構(gòu)造前綴碼，并對二進制序列10001011譯碼。

解：（1）見下頁

（2）將上面的最優(yōu)樹的每個分枝點引出的兩條邊，左側(cè)邊標0，右側(cè)邊標1，得到一個b、d、e、g、o、y對應(yīng)的前綴碼{000，001，11，010，011，10}。對二進制序列譯碼為goodbye。3345671119121325440101010101yebdgo三、證明題1.設(shè)R,S是A上的等價關(guān)系，證明RS也是A上的等價關(guān)系。證明：a)自反性：對任意aA，因為<a,a>A,<a,a>S， 所以<a,a>RS，即RS具有自反性。 b)對稱性：對任意a,bA，如果有<a,b>RS，則<a,b>R且<a,b>S。 因為R,S是等價關(guān)系，所以具有對稱性， 所以<b,a>R且<b,a>S。 所以<b,a>RS，即RS具有對稱性。 c)傳遞性：對任意a,b,cA，若有<a,b>,<b,c>RS 則<a,b>,<b,c>R且<a,b>,<b,c>S 則因為R,S是等價關(guān)系，所以具有傳遞性，所以<a,c>R且<a,c>S 所以<a,c>RS，即RS具有傳遞性。 所以RS是A上的等價關(guān)系。2.設(shè)f和g都是群<A，*>到<B，eq\o\ac(○,*)>的同態(tài)，令H={x|xA，f(x)=g(x)}，

試證：<H，*>是<A，*>的子群。證明由定義知HA（1）設(shè)e是<A,*>的幺元，e’是<B,eq\o\ac(○,*)>的幺元，因為f,g都是<A，*>到<B，eq\o\ac(○,*)>的同態(tài)，則f(e)=g(e)=e’，所以eH，所以H；（2）a,bH，有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)eq\o\ac(○,*)f(b-1)=f(a)eq\o\ac(○,*)f(b)-1=g(a)eq\o\ac(○,*)g(b)-1=g(a)eq\o\ac(○,*)g(b-1)=g(a*b-1)所以a*b-1H，所以<H,*>是<A,*>的子群。當且僅當連通圖的每條邊均為割邊時，該連通圖才是一棵樹。證明：必要性：如果圖G是樹，則刪去任一邊后就不連通，故任一邊均為G的割邊。 充分性：任取兩個結(jié)點u,v，圖G連通，則u,v之間有路存在。若u,v間有兩條路，則可組成一個回路，則刪除回路上任一條邊后不改變圖的連通性，這樣該回路上的邊都不是割邊，與前提矛盾，因此任意兩個結(jié)點間恰有一條路，圖G是樹。f是群<G,°>到群<G’,*>的同態(tài)映射，e’是G’中的幺元則，f的同態(tài)核K={x|xG且f(x)=e’}構(gòu)成的代數(shù)系統(tǒng)<K,°>是<G,°>的子群。證明：由定義可知KG，設(shè)G中的幺元為e，則有f(e)=e’，所以eA，即A為非空集合。對于任意的a,bK，有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-1K，因此<K,°>是<G,°>的子群。 證明當且僅當G的一條邊e不包含在G的回路中時，e才是G的割邊。證明：必要性：設(shè)e是圖G的割邊，e關(guān)聯(lián)的兩個結(jié)點是a,b。如果e包含在G的一個回路中，則除了邊e=(a,b)外，a到b還有一條路存

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