離散數(shù)學(xué)考前綜合復(fù)習(xí)資料

離散數(shù)學(xué)考前綜合復(fù)習(xí)資料離散數(shù)學(xué)考前綜合復(fù)習(xí)資料/離散數(shù)學(xué)考前綜合復(fù)習(xí)資料《離散數(shù)學(xué)》綜合復(fù)習(xí)資料一、判斷題1．A、B、C是任意命題公式，如果ACBC，一定有AB。（）2．設(shè)<A，*>是一個(gè)代數(shù)系統(tǒng)，且集合A中元素的個(gè)數(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é)點(diǎn)vi到vj長(zhǎng)度為l路的數(shù)目。（）二、解答題求命題公式(PQ)的主析取范式。舉出A={a,b,c}上的二元關(guān)系R和S滿足：

（1）R既不是自反的又不是反自反的，既是對(duì)稱的又是反對(duì)稱的；

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

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

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

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

《離散數(shù)學(xué)》綜合復(fù)習(xí)資料答案一、判斷題題號(hào)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ù)？哪些是入射？哪些是滿射？對(duì)任意一個(gè)雙射，寫出它們的逆函數(shù)。f:NQ,f(x)=1/xf:RRRR,f(x,y)=<y+1,x+1>解：（1）不是函數(shù)，在x=0時(shí)無定義。函數(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，->不是群；（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）如果張三和李四都不去，她就去。（（PQ）R）

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

10100

01000

00001

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

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

（3）因?yàn)閍(3)12=2，所以V1到V2長(zhǎng)度為3的路有2條。9．將下列命題符號(hào)化

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

（2）我們不能邊看電視邊看報(bào)。（（PQ)）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)小于右兒子的權(quán)）。

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

解：（1）見下頁

（2）將上面的最優(yōu)樹的每個(gè)分枝點(diǎn)引出的兩條邊，左側(cè)邊標(biāo)0，右側(cè)邊標(biāo)1，得到一個(gè)b、d、e、g、o、y對(duì)應(yīng)的前綴碼{000，001，11，010，011，10}。對(duì)二進(jìn)制序列譯碼為goodbye。3345671119121325440101010101yebdgo三、證明題1.設(shè)R,S是A上的等價(jià)關(guān)系，證明RS也是A上的等價(jià)關(guān)系。證明：a)自反性：對(duì)任意aA，因?yàn)?lt;a,a>A,<a,a>S， 所以<a,a>RS，即RS具有自反性。 b)對(duì)稱性：對(duì)任意a,bA，如果有<a,b>RS，則<a,b>R且<a,b>S。 因?yàn)镽,S是等價(jià)關(guān)系，所以具有對(duì)稱性， 所以<b,a>R且<b,a>S。 所以<b,a>RS，即RS具有對(duì)稱性。 c)傳遞性：對(duì)任意a,b,cA，若有<a,b>,<b,c>RS 則<a,b>,<b,c>R且<a,b>,<b,c>S 則因?yàn)镽,S是等價(jià)關(guān)系，所以具有傳遞性，所以<a,c>R且<a,c>S 所以<a,c>RS，即RS具有傳遞性。 所以RS是A上的等價(jià)關(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(○,*)>的幺元，因?yàn)閒,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)，因?yàn)閒,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,*>的子群。當(dāng)且僅當(dāng)連通圖的每條邊均為割邊時(shí)，該連通圖才是一棵樹。證明：必要性：如果圖G是樹，則刪去任一邊后就不連通，故任一邊均為G的割邊。 充分性：任取兩個(gè)結(jié)點(diǎn)u,v，圖G連通，則u,v之間有路存在。若u,v間有兩條路，則可組成一個(gè)回路，則刪除回路上任一條邊后不改變圖的連通性，這樣該回路上的邊都不是割邊，與前提矛盾，因此任意兩個(gè)結(jié)點(diǎn)間恰有一條路，圖G是樹。f是群<G,°>到群<G’,*>的同態(tài)映射，e’是G’中的幺元?jiǎng)t，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為非空集合。對(duì)于任意的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,°>的子群。 證明當(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是割邊矛盾。充分性：如果邊e不包含在G的回路中，則連接a,b只有邊e。所以刪除邊e后，a,b不再連通，所以e是G的割邊。設(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)自反性：對(duì)任意aA，f(a)=f(a)，所以aRa，即R是自反的。 b)對(duì)稱性：對(duì)任意a，bA，若aRb，即f(a)=f(b)，即f(b)=f(a)，故bRa，即R是對(duì)稱的。 c)傳遞性：對(duì)任意a，b，cA，若aRb，bRc，即f(a)=f(b)，f(b)=f(c) 即f(a)=f(b)=f(c)，故aRc，即R是傳遞的。 所以R是A上的等價(jià)關(guān)系。代數(shù)系統(tǒng)<I,+>是一個(gè)群，設(shè)B={x|x=5n,nI}，證明：<B,+>是<I,+>的子群。證明：由題意知BI并且B非空，設(shè)x,yB則有x,yI，且x=5n1,y=5n2(n1,n2I)，在<