《離散數(shù)學(xué)》總復(fù)習(xí) 3

1、adfadffd,,《離散數(shù)學(xué)》總復(fù)習(xí),adfadffd,第一部分 數(shù)理邏輯。包括命題邏輯和謂詞邏輯。,一、離散數(shù)學(xué)的主要內(nèi)容有哪些？,離散數(shù)學(xué)的主要內(nèi)容可以分為四個部分：,第二部分 集合論。包括集合、關(guān)系和函數(shù)。,第三部分 代數(shù)系統(tǒng)。包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)。,第四部分 圖論。包括圖的基本概念，幾種特殊的圖。,adfadffd,二、考試,1、題型 考試試題的題型有：單項選擇題，10道題，占10分。填空題，

2、共10個空，占10分。計算題，共4小題，占20分。證明題，共5題，占30分。2、難易程度 考試題的難度不會超過教材、參考書和模擬試題的難度。以簡單題占60%，較難題占30%，難題占10%。 3、考試范圍 考試試題覆蓋《離散數(shù)學(xué)》的全部內(nèi)容。,adfadffd,第一部分 數(shù)理邏輯,一、內(nèi)容提要1、命題及其聯(lián)結(jié)詞（非、與、或、單條件、雙條件）。2、命題公式的析取范式和合取范式（主范式）。3、命題公式間的

3、等價關(guān)系和蘊(yùn)含關(guān)系。4、命題演算的推理理論。5、謂詞公式的有關(guān)概念（量詞、謂詞、變元、真值指派等）6、謂詞公式間的等價關(guān)系和蘊(yùn)含關(guān)系。7、謂詞演算的推理理論。,adfadffd,二、重點(diǎn)和難點(diǎn)1、命題公式間的等價關(guān)系和蘊(yùn)含關(guān)系。2、命題演算的推理理論(包括命題符號化)。3、謂詞公式間的等價關(guān)系和蘊(yùn)含關(guān)系。4、謂詞演算的推理理論(包括命題符號化) 。,adfadffd,三、例題1、證明推理：(?x)(P(x) ?(Q(

4、x)?R(x))), (?x)P(x)?(?x)(P(x)?R(x)) 證：① (?x)P(x) P②P(c) ES, ①③(?x)(P(x) ?(Q(x)?R(x))) P④P(c) ?(Q(c)?R(c))

5、 US, ③⑤Q(c)?R(c) T, ②, ④, I⑥R(c) T, ⑤, I⑦P(c)?R(c) T, ②, ⑥, I⑧(?x)(P(x

6、)?R(x)) EG, ⑦,adfadffd,2、證明推理：?(P?Q)??(R?S), (Q?P)??R, R ? P?Q 證：① R P② (Q?P)??R P③ (Q?P) T,①,②,I④ R?S

7、 T,①,I⑤ ?(P?Q)??(R?S) P⑥ P?Q T,④,⑤,I⑦ P?Q T,③,⑥,I,adfadffd,第二部分 集合論,集合論包括集合、二元關(guān)系和函數(shù)，它們之間的關(guān)系是：二元關(guān)系是一種特殊的集合，集合中的元素都是序偶；函數(shù)是一種特殊的二元關(guān)系。,一、內(nèi)容提要1、集合的兩種表示方法：列舉法和描述法。2、

8、特殊的集合：空集、全集、子集和冪集。3、集合的運(yùn)算：并、交、差和對稱差，各種運(yùn)算的性質(zhì)。4、集合運(yùn)算的基本定律：交換律，結(jié)合律，分配律，吸收律，德.摩根律等。5、有序n元組、n維笛卡爾積。6、關(guān)系的定義：笛卡爾積的子集。,adfadffd,7、關(guān)系的表示方法：集合、矩陣和關(guān)系圖。8、關(guān)系的性質(zhì)：自反性、反自反性、對稱性、反對稱性和傳遞性。9、關(guān)系的運(yùn)算：復(fù)合運(yùn)算、逆運(yùn)算和閉包運(yùn)算。10、特殊的二元關(guān)系及其相關(guān)特性：等價關(guān)系

9、（自反性、對稱性、傳遞性）、偏序關(guān)系（自反性、反對稱性、傳遞性）、等價類、偏序關(guān)系中的特殊元素（極大元、上界等）。11、函數(shù)的定義、函數(shù)的定義域和值域。12、函數(shù)的性質(zhì)：單射、滿射和雙射。13、函數(shù)的運(yùn)算：復(fù)合函數(shù)、逆函數(shù)。14、集合的基數(shù)。,adfadffd,二、重點(diǎn)和難點(diǎn)1、掌握元素與集合之間的關(guān)系，集合與集合之間的關(guān)系。2、運(yùn)用集合運(yùn)算的基本定律去化簡集合表達(dá)式或證明集合等式。3、掌握二元關(guān)系的五個性質(zhì)和二元關(guān)系的運(yùn)

10、算。4、等價關(guān)系的證明、等價類的求解，偏序關(guān)系的特定元素的求解。5、函數(shù)的性質(zhì)，求復(fù)合函數(shù)和逆函數(shù)。,adfadffd,三、例題1、?????? ?????這兩個關(guān)系是否正確？答：正確。在?????中?表示元素；在?????中?表示空集。2、求R={, , }的傳遞閉包。解：R的傳遞閉包={, , , , ,}。注意：求傳遞閉包是一個不斷重復(fù)合并有序?qū)Φ倪^程。有序?qū)ν宦┑簟?、化簡集合表達(dá)式：((A∩B)∪A)⊕((

11、B∩~B)⊕A⊕(B∪~B)) 解： ((A∩B)∪A)⊕((B∩~B)⊕A⊕(B∪~B)) (吸收律和零律) =A⊕?⊕A⊕U (同一律) = A⊕A⊕U (零律) = ?⊕U = U,adfadffd,4、設(shè)集合A＝{a, b, c, d, e}，偏序關(guān)系R的哈斯圖如圖所示，若A的子集B={c, d, e}，求：（1）用列舉法寫出偏序關(guān)系R的集合表達(dá)式；（2）寫出集合B的極大元、極小元、最大元、最小

12、元、上界、下界、上確界、下確界。,,解：（1）R=IA?{, , , , , , }（2）集合B的極大元：c，極小元：d、e，最大元：c，最小元：無，上界：c、a，上確界：c，下界：無，下確界：無。,adfadffd,5、已知f：R?R且f(x)=(x+4)3- 2，已知g：R?R且g(x)=3x+5，求: f與g的合成函數(shù)，并求3在f與g的合成函數(shù)下的函數(shù)值。 解: (1) f°g: R?R，且 (

13、f°g)(x)=g(f(x))=g((x+4)3 - 2)=3((x+4)3 - 2)+5=3(x+4)3-1 (f ° g)(3)=3*(3+4)3-1=1028,adfadffd,第三部分 代數(shù)系統(tǒng),一、內(nèi)容提要1、代數(shù)系統(tǒng)的定義（封閉性）、特殊元素（幺元，零元、逆元、冪等元）。2、代數(shù)系統(tǒng)之間的關(guān)系：子代數(shù)，同態(tài)（單同態(tài)、滿同態(tài)、同構(gòu)）。3、同余關(guān)系的定義和商代數(shù)。4、半群、獨(dú)異點(diǎn)和群的定義及其相互間的

14、關(guān)系。5、群的基本性質(zhì)：消去律、元素的階。6、循環(huán)群的性質(zhì)及生成元。7、子群的定義及判定方法、正規(guī)子群的定義及判定方法、子群的陪集。(拉格朗日定理),adfadffd,8、環(huán)和域的定義。9、子環(huán)的定義及其判定方法。10、格的定義及其性質(zhì)。11、特殊的格：分配格、有界格、有補(bǔ)格、有補(bǔ)分配格。12、布爾代數(shù)及其性質(zhì)。,二、重點(diǎn)和難點(diǎn)1、代數(shù)系統(tǒng)的定義及特異元素，如何證明兩個代數(shù)系統(tǒng)同態(tài)與同構(gòu)。2、循環(huán)群的定義及其性質(zhì)。3

15、、子群的定義及其判定方法。4、格的定義及其性質(zhì)。,adfadffd,三、例題1、設(shè)R是實(shí)數(shù)集，在R上定義二元運(yùn)算*，?x, y?R，定義x*y=x+y+2xy。試說明*是否滿足結(jié)合律、交換律？是否存在幺元？若存在請求出幺元 。解： ?x,y,z?R，①(x*y)*z=(x+y+2xy)*z=(x+y+2xy)+z+2(x+y+2xy)z=x+(y+z+2yz)+ 2x(y+z+2yz)= x*(y+z+2yz)=x*(y*z)

16、*運(yùn)算可結(jié)合。 ② x*y=x+y+2xy=y*x *運(yùn)算可交換。 ③ 設(shè)幺元為e，?x?R, e*x=x*e=x+e+2xe=x，由x的任意性,得e=0?R,幺元為0。,adfadffd,2. 給定代數(shù)系統(tǒng)U=,V=,W=,設(shè)f: X→Y是從U到V的同態(tài)，g: Y→Z是從V到W的同態(tài)，則g°f: X→Z必是從U到W的同態(tài)。證：對任意的a, b? X，證明： g°f(a°b)=g°f(a)?g°f(b) g°f(a

17、°b)= g(f(a°b)) = g(f(a)*f(b))(f是同態(tài)映射) = g(f(a))?g(f(b))(g是同態(tài)映射) = g°f(a)?g°f(b),adfadffd,3、設(shè)是群，a, b∈G，且(a*b)2=a2*b2，證明a*b=b*a。 證：因為群滿足消去律，所以 (a*b)2=a2*b2?(a*b)*(a*b

18、)=(a*a)*(b*b) (因*可結(jié)合)?a*(b*a)*b= a*(a*b)*b (群滿足左右消去律)? b*a=a*b,adfadffd,4、設(shè)*運(yùn)算是X中的可結(jié)合的二元運(yùn)算，并且對任意的x, y? X, 若x*y=y*x，則x=y。證明：X中的每個元素都是等冪的。證：對任意的x ? X, 要證明x是等冪的，即證明：x*x=x因為：*運(yùn)算是X中

19、的可結(jié)合的二元運(yùn)算所以：x*(x*x)=(x*x)*x由已知：x*y=y*x ? x=y得：x*x=x,adfadffd,5、設(shè)是個代數(shù)系統(tǒng)，使得對任意的a, b, c, d ?A有： a*a=a (a*b)*(c*d) = (a*c)*(b*d) 證明：a*(b*c)=(a*b)*(a*c)證：左式＝a*(b*c) （因為a*a=a） =(a*a)*(b*c)

20、（因為(a*b)*(c*d)=(a*c)*(b*d)） =(a*b)*(a*c)=右式,adfadffd,6、設(shè)Ｘ為集合，證明＜ ρ(X), ∩ ＞與＜ ρ(X), ∪ ＞是同構(gòu)的。證：對任意的S?ρ(X), 設(shè) f(S)=～S（1）來證f是個同態(tài)映射，即證：f(S1∩S2) = f(S1)∪f(S2) ） f(S1∩S2) ＝ ~(S1∩S2) ＝ ~S1∪~S2 ＝ f

21、(S1)∪f(S2)（2）來證f是個雙射函數(shù) 任取S1, S2?ρ(X), 且S1 ≠ S2, f(S1)=～S1, f(S2)=～S2 因為S1 ≠ S2，所以， ～S1 ≠ ～S2，即f(S1) ≠ f(S2)。故f是單射的；又因為f是ρ(X)到ρ(X)的自身的映射，故f是滿射的。即f為雙射。,adfadffd,7、設(shè)是半群，對于A中的每一個元素a和b，若a≠b，則 a*b≠b*a（ a*b=b*a ? a=

22、b ）（1）證明對于A中的一切a，有a*a=a。（2）對于A中任意的a和b， 證明a*b*a=a。（3）對于A中任意的a, b和c，證明a*b*c=a*c。 證：（1） a*a=a 因為是半群，*運(yùn)算可結(jié)合，所以： (a*a)*a=a*(a*a) ? a*a=a,adfadffd,（2）證明：對于A中任意的a和b， 證明a*b*a=a。證：能推出 (a*b*a)*a = a*(a*b*a)即可。(a*b*a)

23、*a（*運(yùn)算可結(jié)合）＝a*b*(a*a)＝ a*b*a （由（1）知）＝(a*a)*b*a（由（1）知）＝ a*(a*b*a)（由提示）即： (a*b*a)*a ＝ a*(a*b*a) 故有 a*b*a ＝ a,adfadffd,（3）對于A中任意的a, b和c，證明a*b*c=a*c。證：能推出(a*b*c)*(a*c) = (a*c)*(a*b*c)即可。(a*b*c)*(a*c) （*運(yùn)算可結(jié)

24、合）=a*b*(c*a*c) （由（2））=a*b*c （由（2））=(a*c*a)*b*c （*運(yùn)算可結(jié)合）=(a*c)*(a*b*c) （由提示）即： (a*b*c)*(a*c) =(a*c)*(a*b*c)故： a*b*c=a*c,adfadffd,8、設(shè)是一個群，b? G，定義函數(shù)f: G→G且給定成：對任意的x? G，f(x)=b°x°b-1。 證明：f是從到的一個同構(gòu)映射。證：（1）顯

25、然與同類型；（2）單射：對任意的x, y?G, 證明：f(x)=f(y) ? x=y f(x)=f(y)? b°x°b-1 = b°y°b-1 （消去律）? x°b-1=y°b-1 （消去律）? x=y,adfadffd,（3）滿射 【f: G→G ，f(x)=b°x°b-1】對任意的y ?G,證明：在G中至少存在一個原像b-1°y°b，使得： f(b-1°y°b)=b°(b

26、-1°y°b)°b-1=(b°b-1)°y°(b°b-1)=e°y°e=y,adfadffd,（4）證明f是個同態(tài)映射（即：運(yùn)算的像=像的運(yùn)算）對任意的x, y? G f(x°y)=b°(x°y)°b-1(由f的定義)= b°(x°e°y)°b-1 (群中存在幺元e) = b°(x°b-1°b°y)°b-1= (b°x°b-1)°(b°y°b-1) (結(jié)合律)=f(x)°f(y) (由f的定義)或

27、： f(x°y) = b°(x°y)°b-1 f(x)°f(y)= (b°x°b-1) °(b°y°b-1 ) （因°可結(jié)合）、 = b°x°(b-1 °b)°y°b-1 = b°x°e°y°b-1 = b°(x°y)°b-1,adfadffd,第四部分 圖論,一、內(nèi)容提要1、圖的基本概念

28、：無向圖、有向圖、簡單圖、結(jié)點(diǎn)的度數(shù)、子圖、補(bǔ)圖、圖的同構(gòu)。2、握手定理：所有結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。3、圖的連通性：割邊、割點(diǎn)、邊割集、點(diǎn)割集。通路、回路、連通分支。4、圖的矩陣表示：鄰接矩陣、關(guān)聯(lián)矩陣。5、歐拉圖和哈密爾頓圖的定義和判定條件。6、樹的定義、性質(zhì)、判定條件和遍歷。7、二部圖和平面圖的定義、性質(zhì)和判定條件,adfadffd,二、重點(diǎn)和難點(diǎn)1、掌握圖的基本概念。2、運(yùn)用握手定理解題。3、利用圖的矩陣

29、求兩個結(jié)點(diǎn)間的通路條數(shù)。4、歐拉圖和哈密爾頓圖的判定。5、樹的遍歷方法。,adfadffd,三、例題1、設(shè)T是完全2杈樹，有t片樹葉，i個分支點(diǎn)，證明: i = t-1 (即：在完全2杈中，分支結(jié)點(diǎn)數(shù)比樹葉數(shù)少1)證：由握手定理知： 2+t+(i+t-1-t) × 3=2m =2(t+i-1) 即：t+3i-1 = 2t + 2i -2 解得： i = t-12、設(shè)T是完全2

30、杈樹，有t片樹葉，i個分支點(diǎn)，證明T的邊數(shù)m=2t-2 。證：設(shè)T有m條邊，根據(jù)握手定理可得： 2+t+(i+t-1-t) × 3=2m 即：3i + t - 1=2m, i=t-1 3(t-1)+t-1=2m ? 4t+4=2m解得：m=2t - 2。故結(jié)論成立。,adfadffd,3、在n階簡單有向圖中，完全有向圖的邊數(shù)為n(n-1)。證：完全有向圖中任意兩個結(jié)點(diǎn)

31、間都有方向相反的兩條邊，所以： m=2Cn2=2*n(n-1)/2=n(n-1)4、對于（n, n+1）的圖G，則G中至少有一個點(diǎn)的度大于等于3。證：現(xiàn)假設(shè)圖G中所有結(jié)點(diǎn)的度均小于3, 即≤ 2，由握手定理知：,=2(n+1),矛盾,≤ 2n,又因為,則：,即得：,2(n+1),≤ 2n,adfadffd,5、 設(shè)n階無向圖G有m條邊，其中，nk個結(jié)點(diǎn)的度為k, 其余結(jié)點(diǎn)的度為k+1，證明： nk=n(k+1) - 2m

32、證：由握手定理知： nk× k + (n-nk) × (k+1) = 2m 整理得：nk=n(k+1) - 2m 。 6、一棵樹有2個點(diǎn)的度為2，1 個點(diǎn)的度為3，3個點(diǎn)的度為4，其余結(jié)點(diǎn)的度為1，問該樹有多少度為1的點(diǎn)？解：設(shè)有x個結(jié)點(diǎn)的度為1；則：2 × 2+1 × 3+3 × 4+x × 1=2 ×(2+1+3+x-1)

33、19+x=10+2x解得：x=9,adfadffd,7、證明在完全2杈樹中，邊的總數(shù)m=2(nt-1)證：設(shè)完全2杈樹有m條邊，則有m+1個結(jié)點(diǎn)根結(jié)點(diǎn)的度為2，葉結(jié)點(diǎn)的度為1，其余結(jié)點(diǎn)的度為3，則： 2+nt+(m+1-1-nt)*3=2m 2+nt+3m-3nt = 2m 解得：m=2(nt-1),adfadffd,,3、每個自然數(shù)不是奇數(shù)就是偶數(shù)。如果自然數(shù)是偶數(shù)，當(dāng)且僅當(dāng)它能

34、被2整除。并非每個自然數(shù)都能被2整除。因此，有的自然數(shù)是奇數(shù)?！咎崾荆篜(x)：x是自然數(shù)，Q(x)：x是奇數(shù)，R(x)：x是偶數(shù)，S (x)：x能被2整出】 證:先符號化：(?x)(P(x)→(Q(x)∨R(x)))，(?x)(P(x)∧R(x)?S(x))，?(?x)(P(x)→S(x)) ? (?x)(P(x)∧Q(x)),adfadffd,第二次測試題,1. 設(shè)A={1，2，3，4，6，12}，R為A上的整除關(guān)系，則R為

35、A上的偏序關(guān)系。（1）試畫出R的哈斯圖（2）并給出子集{2，3，6}的最大元和最小元、極大元和極小元、上界和下界、上確界和下確界。2. 設(shè)T是一棵完全k元樹，其中分枝結(jié)點(diǎn)數(shù)為i，葉結(jié)點(diǎn)數(shù)為t。試證明k與分枝結(jié)點(diǎn)數(shù)為i，葉結(jié)點(diǎn)數(shù)為t有如下關(guān)系式成立： （k?1）i = t?13. 使用推論規(guī)則證明下列各題：(1) P→(Q∨R)，Q→?P，S→?R，P ? ?S（用P，T規(guī)則）(2) (?X) ( P(X)∨Q(X) )