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

1、離散數(shù)學(xué)綜合復(fù)習(xí)資料參考答案一、判斷題1命題邏輯中任何命題公式的主析取范式如果存在一定是唯一的。（ ）2A、B、C是任意集合，如果AÍB及BÎC，則AÍC。（ ）3整數(shù)集是不可數(shù)集。（ ）4代數(shù)系統(tǒng)<S,*>中，如果二元運算*是封閉的、可結(jié)合的，則<S,*>是半群。（ ）5任意平面圖最多是四色的。（ ）6A、B是任意命題公式，如果ØAÛØB，一定有AÛB。（ ）7R是集合A上的二元關(guān)系，若R是反自反的，則Rc也是反自反的。（ ）8、命題邏輯中任何命題公式的主合取范式一定存在。（ ）9、A、B、C為任意

2、集合，已知AÇB=AÇC，必須有B=C。（ ）10、自然數(shù)集合是無限的。（ ）11、命題聯(lián)結(jié)詞Ø，Ù，Ú是最小聯(lián)結(jié)詞組。（ ）12、任一無限集必含有可數(shù)子集。（ ）13、有限整環(huán)必是域。（ ）二、基本題1 判斷公式(P®Q)®(ØQ®ØP)的類型（重言式、矛盾式、可滿足）2 設(shè)A=1,1，計算P(A)-Æ 3 設(shè)樹T有17條邊，除樹根外有12片樹葉，4個4度結(jié)點，1個3度結(jié)點，求樹根的度數(shù)。4 設(shè)P：“天下雨”，Q：“他騎自行車上班”，R：“他乘公共汽車上班”，試符號化下列命題：1）除

3、非下雨，否則他就騎自行車上班2）他或者騎自行車上班，或者乘公共汽車上班5 判斷公式Ø (P«Q)®Ø (PÙQ)的類型（重言式、矛盾式、可滿足）6 設(shè)代數(shù)系統(tǒng)<A,*>，其中A=a,b,c，*是A上的二元運算，運算表如下表，求該代數(shù)系統(tǒng)的幺元，所有可逆元素的逆元。*eabeeabaabebbea7 設(shè)樹T有17條邊，有12片樹葉，2個3度結(jié)點，求4度結(jié)點數(shù)。8 設(shè)A=1,2，試構(gòu)成集合P(A)´A。9. 設(shè)*運算是有理數(shù)集Q上的二元運算，對于任意的a,bÎQ，a*b=a+b-a´b，問運算*是否可交換、

4、可結(jié)合的？v1v2v4v310.試求下面有向圖的強(qiáng)分圖、單側(cè)分圖和弱分圖。11、將下列命題符號化（1）他即聰明又用功。（PÙQ）（2）僅當(dāng)你走我才留下。（Q ® P）（3）所有老的國家選手都是運動員。（("x)(R(x)®Q(x)）（4）某些教練是年老的，但是健壯的。（($x)(P(x)ÙQ(x) ÙR(x)） 12、設(shè)A是一個非空集合，*是A上的二元運算，對于任意a,bÎA，有a*b=b，判定*運算是否可結(jié)合的、可交換？v1v3v2v5v413、試求下面有向圖的強(qiáng)分圖、單側(cè)分圖和弱分圖三、證明題1 設(shè)<G,*>

5、是一個獨異點，并且對于G中的每一個元素x都有x*x=e，其中e是幺元，證明<G,*>是一個阿貝爾群。2 設(shè)G是具有n個結(jié)點的簡單無向圖，如果G中每對結(jié)點的度數(shù)之和均大于等于n-1，那么G是連通的。3 試用推理規(guī)則證明：A ®B，(ØBÚC) ÙØC，Ø(Ø AÙD)Þ Ø D4 若集合A上的關(guān)系R和S是自反、對稱和傳遞的，試證明RÇS也是自反、對稱和傳遞的。5 證明任何圖中，度數(shù)為奇數(shù)的結(jié)點必定是偶數(shù)個。6 試證明：A ®(BÙC),(E®&#

6、216;F)®ØC,B®(AÙØS)ÞB®E7 若R是集合A上的相容關(guān)系，試證明RC也是A上的相容關(guān)系。8 證明任意一棵無向樹至少有兩片樹葉（退化樹除外）離散數(shù)學(xué)綜合復(fù)習(xí)資料參考答案一、判斷題題目12345678910答案×××× 題目111213答案×二、基本題1、解：原式ÛØ (ØPÚQ) Ú(QÚØP) Û(PÙØQ) Ú(QÚØP) 

7、19;(PÙØQ) ÚØ (ØQÙP) Û(PÙØQ) ÚØ (PÙØQ)ÛT所以公式為重言式2、解：P(A)=Æ,1,1, 1,1 P(A)-Æ= Æ,1,1, 1,1-Æ=1,1, 1,13、解：設(shè)樹根的度數(shù)為x，因為有17條邊，所以結(jié)點數(shù)=17+1=18，由握手定理得： 12*1+4*4+1*3+1*x=2*17解得x=3所以樹根度數(shù)為3。4、解：1) ØP®Q 2) Q Ñ R

8、或 (QÙØR)Ú(ØQÙR)5、解：原式Û(P®Q)Ù (Q®P) ® (ØPÚØQ) ÛØØ(ØPÚQ)Ù (ØQÚP) Ú (Ø PÚØQ)Û (ØPÚQ)Ù (ØQÚP)Ú(Ø PÚØQ)Û(ØPÚQÚ

9、Ø PÚØQ)Ù (ØQÚPÚØ PÚØQ)ÛTÙTÛT所以公式為重言式6、解：幺元為：e，a的逆元為b，b的逆元為a。7、解：設(shè)有x個4度結(jié)點，因為有17條邊，所以結(jié)點數(shù)=17+1=18，由握手定理得：12*1+2*3+x*4=2*17解得：x=4，所以有4個4度結(jié)點。8、解：P(A) = Æ,1,2,1,2P(A)´A=<Æ,1>,<Æ,2>,<1,1>,<1,2>,<

10、2,1>,<2,2>,<1,2,1>,<1,2,2>9、解：因為a*b= a+b-a´b=b+a-b´a=b*a所以運算是可交換的。a*(b*c)=a+(b*c)-a´(b*c)=a+(b+c-b´c)-a´(b+c-b´c)=a+b+c-b´c-a´b-a´c+a´b´c(a*b)*c=(a+b-a´b)+c-(a+b-a´b) ´c=a+b+c-a´b-a´c-b´c+a´

11、;b´ c所以a*(b*c)= (a*b)*c10、解：強(qiáng)分圖由v1,v2,v3,v4導(dǎo)出的子圖單側(cè)分圖由v1,v2,v3,v2,v3,v4導(dǎo)出的子圖弱分圖由v1,v2,v3,v4導(dǎo)出的子圖11、（1）（PÙQ）（2）（Q ® P）（3）（("x)(R(x)®Q(x)）（4）（($x)(P(x)ÙQ(x) ÙR(x)） 12、解：a*(b*c)=a*c=c(a*b)*c=b*c=c所以a*(b*c)= (a*b)*c，即*運算是可結(jié)合的。a<>b時，a*b=b<>a=b*a，所以不可交換13、解：強(qiáng)分

12、圖由v1,v2,v3,v4和v5導(dǎo)出的子圖由v1,v2,v3,v4,v5導(dǎo)出的子圖是單側(cè)分圖，也是弱分圖三、證明題1、 設(shè)<G,*>是一個獨異點，并且對于G中的每一個元素x都有x*x=e，其中e是幺元，證明<G,*>是一個阿貝爾群。證明：<G,*>是獨異點，*運算封閉，且滿足結(jié)合律，且有幺元，只須證<G,*>中每個元素都有逆元，并且*運算滿足交換律。 因為對于G中的每一個元素x都有x*x=e，所以x的逆元就是x，故<G,*>是群。 對于"x,yÎG，則x*yÎG， 所以(x*y)*(x*y)=e，而(x*

13、y)*(y*x)=x*(y*y)*x=x*e*x=x*x=e 故(x*y)*(x*y)= (x*y)*(y*x)，所以x*y=y*x，即*運算滿足交換律。 所以<G,*>是一個阿貝爾群。2、 設(shè)G是具有n個結(jié)點的簡單無向圖，如果G中每對結(jié)點的度數(shù)之和均大于等于n-1，那么G是連通的。證明：假設(shè)G不連通，則G至少有兩個連通分支G1,G2，設(shè)G1中有n1個結(jié)點，G2中有n2個結(jié)點，則n1+n2<=n。從G1和G2中各任取一點u和v，則deg(u)<=n1-1，deg(v)<=n2-1，則deg(u)+deg(v)<=n1-1+n2-1<=n-2，與G中每對

14、結(jié)點的度數(shù)之和均大于等于n-1矛盾，所以G是連通的。3、 試用推理規(guī)則證明：A ®B，(ØBÚC) ÙØC，Ø(Ø AÙD)Þ Ø D證明 (1)DP(附加前提) (2) Ø(Ø AÙD) P(3) AÚØDT(2)E (4)AT(3)I (5) A ®B P(6) BT(4)(5)I (7) (ØBÚC) ÙØCP (8) (Ø BÙØC)Ú(Ø

15、 CÙC)T(7)E (9) (Ø BÙØC) T(8)E (10) ØB T(9)I (11) Ø BÙBT(6)(10)I 所以A ®B，(ØBÚC) ÙØC，Ø(Ø AÙD)Þ Ø D4、若集合A上的關(guān)系R和S是自反、對稱和傳遞的，試證明RÇS也是自反、對稱和傳遞的。證明：1）自反性對"aÎA，R,S具有自反性，故<a,a>ÎR，且<a,a>ÎS，

16、所以<a,a>ÎRÇS，即RÇS具有自反性。2）對稱性若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具有對稱性。3）傳遞性若a,b,cÎA，有<a,b>,<b,c>ÎRÇS則<a,b>,<b,c>&

17、#206;R且<a,b>,<b,c>ÎS則因為R,S具有傳遞性，所以<a,c>ÎR且<a,c>ÎS所以<a, c>ÎRÇS，即RÇS具有傳遞性。5、證明任何圖中，度數(shù)為奇數(shù)的結(jié)點必定是偶數(shù)個。證明：設(shè)V1,V2分別是G中奇數(shù)度數(shù)和偶數(shù)度數(shù)的結(jié)點集，則由握手定理，由于是偶數(shù)之和，必為偶數(shù)，而2|E|是偶數(shù)，故得是偶數(shù)，所以|V1|是偶數(shù)。6、試證明：A ®(BÙC),(E®ØF)®ØC,B®(AÙ&

18、#216;S)ÞB®E證明：(1)BP(附加前提)(2) B®(AÙØS)P(3) AÙØST(1)(2)I(4)AT(3)I(5) A ®(BÙC)P(6) BÙCT(4)(5)I(7)CT(6)I(8) (E®ØF)®ØCP(9) Ø(E®ØF)T(7)(8)I(10) Ø(ØEÚØF)T(9)E(11)EÙFT(10)E(12)ET(11)I(13) B®ECP7、若R是集合A上的相容關(guān)系，試證明RC也是A上的相容關(guān)系。證明：（本題答案不唯一）即證明RC具有自反性、對稱性因為R相容關(guān)系，所以R具有自反性、對稱性1）自反性對"aÎA，R具有自反性，故<a,a>ÎR，所以<a,a>ÎRC，即RC具有自反