大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱要課件

1、（1）需要熟練掌握的知識點包括：命題的定義、邏輯聯(lián)結(jié)詞、命題變元、命題公式（合式公式）、永真式、永假式、可滿足式、等價式、蘊涵式、極小項、極大項、主析取范式、主合取范式。第1章命題邏輯重點（2）掌握基本的等價式和蘊涵式，并掌握常用的等價式和蘊涵式的證明方法（替換規(guī)則和推論規(guī)則）。第1章命題邏輯重點（續(xù)）（3）要能準確地求出命題公式的主析取范式和主合取范式。掌握主析取范式和主合取范式與真值表的對應(yīng)關(guān)系，主析取范式和主合取范式的關(guān)系。第1章命題邏輯重點（續(xù)）（4）掌握命題符號化的原則；（5）熟練掌握四個推論規(guī)則（P、T、CP、F）進行有效性論證。第1章命題邏輯重點（續(xù)）第2章謂詞邏輯重點（1）需要

2、熟練掌握的知識點包括：謂詞、全稱量詞(x)、存在量詞 (x) 、個體、個體域、個體變元（約束變元和自由變元）、謂詞公式的解釋（永真、永假、可滿足）、謂詞公式的基本的等價式和蘊涵式。第2章謂詞邏輯重點（續(xù)）（2）在符號化時要特別注意量詞和邏輯聯(lián)結(jié)詞的搭配：全稱量詞對應(yīng)邏輯聯(lián)結(jié)詞“”，存在量詞對應(yīng)邏輯聯(lián)結(jié)詞“”。（3）在謂詞邏輯推理的證明中，要特別注意US，ES，UG，EG規(guī)則成立的條件（用ES規(guī)則指定的個體不能用UG規(guī)則加以推廣）。第三章集合(1)掌握集合的基本概念及其表示，集合之間的關(guān)系（子集 、真子集 ）、元素與集合的關(guān)系（屬于 ）、全集、空集、冪集、笛卡爾乘積等概念。(2)能熟練地證明集合

3、中的相等關(guān)系、包含關(guān)系。(3)掌握集合的五種基本運算：A、A B、A B、A-B、A B及集合運算的基本定律。第四章二元關(guān)系(1)掌握關(guān)系矩陣和關(guān)系圖的表示方法。(2)掌握合成運算、逆運算、閉包運算的概念。(3)熟練掌握關(guān)系的性質(zhì)（自反性、反自反性、對稱性、反對稱性、可傳遞性）及其判別方法。第四章二元關(guān)系（續(xù)）(4)掌握等價關(guān)系（自反、對稱、可傳遞）和偏序關(guān)系（自反、反對稱、可傳遞）的概念及證明。(5)掌握等價關(guān)系和劃分之間的相互關(guān)系。(6)掌握偏序關(guān)系和哈斯圖，并會求極大（小）元、最大（?。┰?、上（下）界、上（下）確界。第四章函數(shù)一、主要內(nèi)容二、本章要點一、主要內(nèi)容1、函數(shù)的基本概念2、函數(shù)

4、的性質(zhì)3、特種函數(shù)4、復(fù)合函數(shù)5、逆函數(shù) 1、函數(shù)的基本概念設(shè)f是從集合X到Y(jié)上關(guān)系，若對任意的xX都存在唯一的yY，使f，則稱關(guān)系f為函數(shù)（或映射），記作：f: XY。(1)對于函數(shù)f: XY，如果x，yf，也寫成y=f(x), 并稱x為自變量，y稱為函數(shù)在x處的值，或稱y為在函數(shù)f的作用下x的像點，相應(yīng)地稱x為y的原像。(2)對于函數(shù)f: XY，則稱X為函數(shù)f的定義域，Y稱為f的陪域；Rf是f的值域。2、函數(shù)的性質(zhì)設(shè)函數(shù)f: XY,則f滿足下面兩個性質(zhì)：(1)任意性：函數(shù)的定義域必須是集合X，即：Df = X；(2)唯一性：對任意的xX，必存在唯一的yY，使f，即：對任意的xX，y，zY，

5、有：ff y = z。3、特種函數(shù) 設(shè)函數(shù)f: XY,則：(1)若f(X)=Rf=Y, 則稱f是滿射的；(2)對任意x1,x2X，如果:x1x2f(x)f(y),或:f(x1)=f(x2)x1 =x2； 則稱f是單射的；(3)若f是既是滿射的，又是單射的，則稱f是雙射的。 4、復(fù)合函數(shù)給定函數(shù)f: XY，g: XZ，則：gf=xXzZ(y) (fg)則稱gf為f和g的合成函數(shù)（或復(fù)合函數(shù)）。5、逆函數(shù)如果f是個雙射函數(shù)，則f的逆關(guān)系稱為f的逆函數(shù)（或反函數(shù)），并記作：f1。 相關(guān)定理定理1 設(shè)函數(shù)f: AB，所有從A到B的函數(shù)的集合 f | f: AB，記作BA，如果|A|m, |B|=n,則

6、|BA|nm 。 定理2 設(shè)函數(shù)f: XY，g: YZ，則復(fù)合函數(shù)gf是從XZ上的函數(shù)，并對任意的xX，都有：（gf）（x）= g (f (x) )。 相關(guān)定理（續(xù)）定理3 函數(shù)的復(fù)合運算是可結(jié)合的，即如果f、g和h都是函數(shù)，則有： （gf）h = g(fh) = gfh定理4 設(shè)函數(shù)f: XY，f的逆關(guān)系f 1是從YX上函數(shù)，當且僅當f是個雙射函數(shù)。 二、本章要點1、掌握函數(shù)的定義（任意性、唯一性）:設(shè)f是從集合X到Y(jié)的關(guān)系，即f:XY，若對任意的xX都存在唯一的yY，使 f，或y=f(x)，則稱關(guān)系f為函數(shù)（或映射）注意：函數(shù)和關(guān)系的聯(lián)系和區(qū)別。本章要點（續(xù)）2、掌握合成函數(shù)的概念：設(shè)函數(shù)

7、f: XY ,g: YZ,則: gf=|xXzZ(y)(yYy=f(x)z=g(y)稱為f和g的合成函數(shù)（復(fù)合函數(shù)）。注意：合成關(guān)系和合成函數(shù)書寫格式的區(qū)別。本章要點（續(xù)）3、掌握反函數(shù)的概念及其存在的條件：設(shè) f: XY是雙射函數(shù)，則f的逆關(guān)系稱f的反函數(shù)，記作f-1注意：只有雙射函數(shù)才有反函數(shù)。本章要點（續(xù)）4、掌握特種函數(shù)的定義（單射、滿射、雙射）及證明：滿射函數(shù)：設(shè)函數(shù)f: XY，若f(X)=Rf=Y（值域陪域）。單射函數(shù)：設(shè)函數(shù)f: XY，對任意x1，x2X，如果： x1x2 f(x1)f(x2)或 f(x1)=f(x2) x1=x2；第五章代數(shù)結(jié)構(gòu)一、主要內(nèi)容二、本章要點一、主要內(nèi)

8、容1. 代數(shù)運算2. 二元運算的性質(zhì) 3二元運算的特異元 4. 可約的或可消去的 5. 代數(shù)系統(tǒng)的概念 6. 同態(tài)與同構(gòu)的概念 7. 代換性質(zhì)和同余關(guān)系8. 商代數(shù)與積代數(shù)9.半群和群1. 代數(shù)運算設(shè)X集合，f是從Xn X上映射，則稱f為集合X中的n元運算。特別是：(1)當n=1時，f：X X稱為集合X中的一元運算；(2)當n=2時，f：XX X稱為集合X中的二元運算。如果對給定的集合中的元素進行運算，從而產(chǎn)生了像點，而該像點又是該集合中的元素，則稱給定的運算對該集合封閉。在上述的代數(shù)運算的定義中蘊含著對集合的封閉性。2. 二元運算的性質(zhì)設(shè)和*為集合X上的二元運算，與這些運算相關(guān)的性質(zhì)有：(1

9、)交換律：x，y，有 xy=yx；(2)結(jié)合律：x,y,z，有:(xy)z=x(yz)；(3)等冪律：x有xx=x； (4)分配律：x,y,z有:x(y*z)=(xy)* (xz) 3二元運算的特異元(1)幺元(2)零元(3)逆元(1)幺元設(shè)*為上的二元運算，則:(1)如果(el)(elX(x)(xXel*x=x)，則稱el為集合X關(guān)于運算*的左幺元；(2)如果(er)(erX(x)(xXx*er=x)，則稱er為集合X關(guān)于運算*的右幺元；(3)如果運算的左幺元和右幺元同時存在，則必有el=er=e，使得對任意的xX，有:x*e=e*x=x并稱e為運算*的幺元且幺元e是惟一的。(2)零元(1)

10、如果(0l)(0l X(x)(xX0l*x=0l)，則稱0l為集合X關(guān)于運算*的左零元；(2)如果(0r)(0r X(x)(xXx*0r=0r)，則稱0r為集合X關(guān)于運算*的右零元；(3)如果運算的左零元和右零元同時存在，則必有0l=0r=0，使得對任意的xX，有:x*0=0*x=0并稱0為運算*的零元。(3)逆元 設(shè)*為上的二元運算，且X中對于運算存在幺元e。令xX。(1)如果(xl)(xlXxl*x=e)，則稱xl是x的左逆元，并稱x是左可逆的；(2)如果(xr)(xrXx*xr=e)，則稱xr是x的右逆元，并稱x是右可逆的；(3)如果元素x既是左可逆的，又是右可逆的，則稱x是可逆的。4.

11、 可約的或可消去的 設(shè)為代數(shù)系統(tǒng)，且aX，如果對任意的x，yX有： （a*x=a*y）（x*a=y*a）x = y則稱a是可約的或可消去的。5. 代數(shù)系統(tǒng)設(shè)X是一個非空集合，為X上的代數(shù)運算構(gòu)成的非空集合，則稱序偶為一個代數(shù)系統(tǒng)（或代數(shù)結(jié)構(gòu)），其中：(1)集合X為代數(shù)系統(tǒng)的定義域。如果X是個有限集合，則稱為有限代數(shù)系統(tǒng)，X=n為代數(shù)系統(tǒng)的階；否則稱為無限代數(shù)系統(tǒng)。(2)=1，2，n為X中的n元運算（n=1，2，3，）構(gòu)成的集合，如果為有限集合，則可將表示為：。6. 同態(tài)與同構(gòu)的概念設(shè)U，V是兩個代數(shù)系統(tǒng)，和*是二元運算，函數(shù)f：XY，如果對任意的x，yX有: f(xy)=f(x)*f(y) (

12、運算的像=像的運算)則稱f是代數(shù)系統(tǒng)U到V同態(tài)映射(簡稱同態(tài))，并稱代數(shù)系統(tǒng)U與V同態(tài)。(1) 如果f是滿射的，則稱f 是從U到V的滿同態(tài)；(2) 如果f是單射的，則稱f 是從U到V的單一同態(tài)；(3) 如果f是雙射的，則稱f 是從U到V的同構(gòu)。(4) 如果U=V，則稱f是從U到U的自同構(gòu)。7. 代換性質(zhì)和同余關(guān)系代換性質(zhì)：給定代數(shù)系統(tǒng)，其中是個二元運算。設(shè)R是X中的等價關(guān)系，如果對任意的x1，x2X和y1，y2X有： (x1Rx2)(y1Ry2)(x1*y1)R(x2*y2)則稱等價關(guān)系E對于運算具有代換性質(zhì)。同余關(guān)系：給定代數(shù)系統(tǒng)U=，且R是集合X中的等價關(guān)系。如果等價關(guān)系R對運算具有代換性

13、質(zhì)，則稱R是代數(shù)系統(tǒng)U中的同余關(guān)系。8. 商代數(shù)與積代數(shù)給定代數(shù)系統(tǒng)U=，其中是個二元運算，R是U中的同余關(guān)系。試構(gòu)成一個新的代數(shù)系統(tǒng)W=，其中(1)X/R=xR xX；(2)對任意的x1,x2X,有x1Rx2R=x1x2R則稱代數(shù)系統(tǒng)W為U的商代數(shù)，簡稱商代數(shù)，并記作U/R。商代數(shù)與積代數(shù)（續(xù)）設(shè)U，V是代數(shù)系統(tǒng)，試構(gòu)成一個新的代數(shù)系統(tǒng)：UV = 其中XY是X和Y的笛卡兒乘積，且運算的定義為：對任意的x1，x2X和y1，y2Y有,則稱UV是U和V的積代數(shù)，U和V是UV的因子代數(shù)。9.半群和群半群：設(shè)是代數(shù)系統(tǒng)，*運算是S上的二元運算，若*運算是可結(jié)合的，則稱為一個半群。群：（1）是代數(shù)系統(tǒng)；

14、（2） “*”運算滿足結(jié)合律；（3）中存在幺元e；（4）中任意一個元素都有逆元素； 則稱代數(shù)系統(tǒng)是群。子群設(shè)是一個群，H是A的非空子集，若也是一個群，則稱是的子群。阿貝爾群和循環(huán)群若群對運算“*”滿足交換律，則稱是阿貝爾群（交換群）。若群中每個元素均是它的某個 元素a的整數(shù)冪，則稱是由a生成的循環(huán)群。a稱為的生成元素。二、本章要點(1)理解代數(shù)運算以及代數(shù)運算的性質(zhì)（結(jié)合律、交換律、分配律、等冪律、消去律）。(2)掌握代數(shù)系統(tǒng)和子代數(shù)系統(tǒng)的定義，理解運算的封閉性。(3)給定集合和運算，會判別運算對該集合是否封閉。本章要點（續(xù)）(4)給定二元運算，說明運算是否滿足交換律、結(jié)合律、等冪律、分配律和

15、消去律。 (5)掌握和理解幺元、零元、逆元的概念,給定個集合和該集合上的二元運算，會求該運算的幺元、零元和逆元。(6)掌握和理解同態(tài)、滿同態(tài)、單一同態(tài)和同構(gòu)的概念和性質(zhì),并會求解（證）相關(guān)問題。(7)掌握半群、獨異點、群、子群的概念及相關(guān)的證明。(8)理解阿貝爾群、循環(huán)群的概念。本章要點（續(xù)）第七章圖論要點1、圖的基本概念：（1）無向圖、有向圖、簡單圖、子圖、真子圖、生成子圖、完全圖、正則圖、零圖、平凡圖、加權(quán)圖、補圖、圖同構(gòu)。（2）鄰接結(jié)點、鄰接邊；（3）無向圖：度的概念；（4）有向圖：出度、入度、度；（5）奇結(jié)點、偶結(jié)點；（6）任何一個(n,m)圖，其度之和等于邊數(shù)的兩倍；（7）任何一個圖G，度為奇數(shù)的結(jié)點個數(shù)一定為偶數(shù)個。圖論要點（續(xù)）2、路徑、回路和圖的連通性：（1）路徑（簡單路徑、基本路徑），回路（簡單回路、基本回路）；（2）可達的概念、連通圖與非連通圖、分支（極大連通子圖）；（3）強連通圖、單向連通圖和弱連通圖，強分支、單