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

大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱要大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱要大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱要（2）掌握基本的等價(jià)式和蘊(yùn)涵式，并掌握常用的等價(jià)式和蘊(yùn)涵式的證明方法（替換規(guī)則和推論規(guī)則）。第1章命題邏輯重點(diǎn)（續(xù)）”通過閱讀科技書籍，我們能豐富知識，培養(yǎng)邏輯思維能力；大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱要大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)1（2）掌握基本的等價(jià)式和蘊(yùn)涵式，并掌握常用的等價(jià)式和蘊(yùn)涵式的證明方法（替換規(guī)則和推論規(guī)則）。第1章命題邏輯重點(diǎn)（續(xù)）（2）掌握基本的等價(jià)式和蘊(yùn)涵式，并掌握常用的等價(jià)式和蘊(yùn)涵式的2（3）要能準(zhǔn)確地求出命題公式的主析取范式和主合取范式。掌握主析取范式和主合取范式與真值表的對應(yīng)關(guān)系，主析取范式和主合取范式的關(guān)系。第1章命題邏輯重點(diǎn)（續(xù)）（3）要能準(zhǔn)確地求出命題公式的主析取范式和主合取范式。掌握主3（4）掌握命題符號化的原則；（5）熟練掌握四個(gè)推論規(guī)則（P、T、CP、F）進(jìn)行有效性論證。第1章命題邏輯重點(diǎn)（續(xù)）（4）掌握命題符號化的原則；第1章命題邏輯重點(diǎn)（續(xù)）4第2章 謂詞邏輯重點(diǎn)（1）需要熟練掌握的知識點(diǎn)包括：謂詞、全稱量詞(

x)、存在量詞(

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

、真子集

）、元素與集合的關(guān)系（屬于

）、全集、空集、冪集、笛卡爾乘積等概念。(2)能熟練地證明集合中的相等關(guān)系、包含關(guān)系。(3)掌握集合的五種基本運(yùn)算：~A、A∩B、A∪B、A-B、A⊕B及集合運(yùn)算的基本定律。第三章 集合(1)掌握集合的基本概念及其表示，集合之間的關(guān)系7第四章二元關(guān)系(1)掌握關(guān)系矩陣和關(guān)系圖的表示方法。(2)掌握合成運(yùn)算、逆運(yùn)算、閉包運(yùn)算的概念。(3)熟練掌握關(guān)系的性質(zhì)（自反性、反自反性、對稱性、反對稱性、可傳遞性）及其判別方法。第四章二元關(guān)系(1)掌握關(guān)系矩陣和關(guān)系圖的表示方法。8第四章二元關(guān)系（續(xù)）(4)掌握等價(jià)關(guān)系（自反、對稱、可傳遞）和偏序關(guān)系（自反、反對稱、可傳遞）的概念及證明。(5)掌握等價(jià)關(guān)系和劃分之間的相互關(guān)系。(6)掌握偏序關(guān)系和哈斯圖，并會(huì)求極大（?。┰?、最大（?。┰⑸希ㄏ拢┙?、上（下）確界。第四章二元關(guān)系（續(xù)）(4)掌握等價(jià)關(guān)系（自反、對稱、可傳遞）9第四章 函數(shù)一、主要內(nèi)容二、本章要點(diǎn)第四章 函數(shù)一、主要內(nèi)容10一、主要內(nèi)容1、函數(shù)的基本概念2、函數(shù)的性質(zhì)3、特種函數(shù)4、復(fù)合函數(shù)5、逆函數(shù)

一、主要內(nèi)容1、函數(shù)的基本概念111、函數(shù)的基本概念

設(shè)f是從集合X到Y(jié)上關(guān)系，若對任意的x

X都存在唯一的y

Y，使<x，y>

f，則稱關(guān)系f為函數(shù)（或映射），記作：f:X→Y。(1)對于函數(shù)f:X→Y，如果﹤x，y﹥

f，也寫成y=f(x),

并稱x為自變量，y稱為函數(shù)在x處的值，或稱y為在函數(shù)f的作用下x的像點(diǎn)，相應(yīng)地稱x為y的原像。(2)對于函數(shù)f:X→Y，則稱X為函數(shù)f的定義域，Y稱為f的陪域；Rf是f的值域。1、函數(shù)的基本概念 設(shè)f是從集合X到Y(jié)上關(guān)系，若對任意的x122、函數(shù)的性質(zhì)

設(shè)函數(shù)f:X→Y,則f滿足下面兩個(gè)性質(zhì)：(1)任意性：函數(shù)的定義域必須是集合X，即：Df=X；(2)唯一性：對任意的x

X，必存在唯一的y

Y，使<x，y>

f，即：對任意的x

X，y，z

Y，有：<x，y>

f∧<x，z>

f

y=z。2、函數(shù)的性質(zhì) 設(shè)函數(shù)f:X→Y,則f滿足下面兩個(gè)性質(zhì)：133、特種函數(shù)

設(shè)函數(shù)f:X→Y,則：(1)若f(X)=Rf=Y,則稱f是滿射的；(2)對任意x1,x2

X，如果:x1≠x2

f(x)≠f(y),或:f(x1)=f(x2)

x1=x2；

則稱f是單射的；(3)若f是既是滿射的，又是單射的，則稱f是雙射的。

3、特種函數(shù)設(shè)函數(shù)f:X→Y,則：144、復(fù)合函數(shù)

給定函數(shù)f:X→Y，g:X→Z，則：gｏf=｛<x，z>│x

X∧z

Z∧(

y)(<x，y>f∧<y，z>g)｝則稱gｏf為f和g的合成函數(shù)（或復(fù)合函數(shù)）。4、復(fù)合函數(shù) 給定函數(shù)f:X→Y，g:X→Z，則：155、逆函數(shù)

如果f是個(gè)雙射函數(shù)，則f的逆關(guān)系稱為f的逆函數(shù)（或反函數(shù)），并記作：f–1。

5、逆函數(shù) 如果f是個(gè)雙射函數(shù)，則f的逆關(guān)系稱為f的逆函數(shù)16相關(guān)定理定理1

設(shè)函數(shù)f:A→B，所有從A到B的函數(shù)的集合{f|f:A→B}，記作BA，如果|A|＝m,|B|=n,則|BA|＝nm。

定理2

設(shè)函數(shù)f:X→Y，g:Y→Z，則復(fù)合函數(shù)gｏf是從X→Z上的函數(shù)，并對任意的xX，都有：（gｏf）（x）=g(f(x))。

相關(guān)定理定理1設(shè)函數(shù)f:A→B，所有從A到B的函數(shù)的集合17相關(guān)定理（續(xù)）定理3

函數(shù)的復(fù)合運(yùn)算是可結(jié)合的，即如果f、g和h都是函數(shù)，則有：

（gｏf）ｏh=gｏ(fｏh)=gｏfｏh定理4

設(shè)函數(shù)f:X→Y，f的逆關(guān)系f–1是從Y→X上函數(shù)，當(dāng)且僅當(dāng)f是個(gè)雙射函數(shù)。

相關(guān)定理（續(xù)）定理3函數(shù)的復(fù)合運(yùn)算是可結(jié)合的，即如果f、g18二、本章要點(diǎn)1、掌握函數(shù)的定義（任意性、唯一性）:

設(shè)f是從集合X到Y(jié)的關(guān)系，即f:X→Y，若對任意的x

X都存在唯一的y

Y，使<x，y>

f，或y=f(x)，則稱關(guān)系f為函數(shù)（或映射）注意：函數(shù)和關(guān)系的聯(lián)系和區(qū)別。二、本章要點(diǎn)1、掌握函數(shù)的定義（任意性、唯一性）:19本章要點(diǎn)（續(xù)）2、掌握合成函數(shù)的概念：設(shè)函數(shù)f:X→Y,g:Y→Z,則:g?f={<x,z>|x∈X∧z∈Z∧(

y)(y∈Y∧y=f(x)∧z=g(y))}稱為f和g的合成函數(shù)（復(fù)合函數(shù)）。注意：合成關(guān)系和合成函數(shù)書寫格式的區(qū)別。本章要點(diǎn)（續(xù)）2、掌握合成函數(shù)的概念：20本章要點(diǎn)（續(xù)）3、掌握反函數(shù)的概念及其存在的條件： 設(shè)f:X→Y是雙射函數(shù)，則f的逆關(guān)系稱f的反函數(shù)，記作f-1注意：只有雙射函數(shù)才有反函數(shù)。本章要點(diǎn)（續(xù)）3、掌握反函數(shù)的概念及其存在的條件：21本章要點(diǎn)（續(xù)）4、掌握特種函數(shù)的定義（單射、滿射、雙射）及證明：①滿射函數(shù)：設(shè)函數(shù)f:X→Y，若f(X)=Rf=Y（值域＝陪域）。 ②單射函數(shù)：設(shè)函數(shù)f:X→Y，對任意x1，x2

∈X，如果：x1≠x2

f(x1)≠f(x2)或f(x1)=f(x2)

x1=x2；本章要點(diǎn)（續(xù)）4、掌握特種函數(shù)的定義（單射、滿射、雙射）及證22第五章 代數(shù)結(jié)構(gòu)一、主要內(nèi)容二、本章要點(diǎn)第五章 代數(shù)結(jié)構(gòu)一、主要內(nèi)容23一、主要內(nèi)容1.代數(shù)運(yùn)算2.二元運(yùn)算的性質(zhì)3．二元運(yùn)算的特異元4.可約的或可消去的5.代數(shù)系統(tǒng)的概念6.同態(tài)與同構(gòu)的概念7.代換性質(zhì)和同余關(guān)系8.商代數(shù)與積代數(shù)9.半群和群一、主要內(nèi)容1.代數(shù)運(yùn)算241.代數(shù)運(yùn)算

設(shè)X集合，f是從Xn→X上映射，則稱f為集合X中的n元運(yùn)算。特別是：(1)當(dāng)n=1時(shí)，f：X

→X稱為集合X中的一元運(yùn)算；(2)當(dāng)n=2時(shí)，f：X×X

→X稱為集合X中的二元運(yùn)算。 如果對給定的集合中的元素進(jìn)行運(yùn)算，從而產(chǎn)生了像點(diǎn)，而該像點(diǎn)又是該集合中的元素，則稱給定的運(yùn)算對該集合封閉。在上述的代數(shù)運(yùn)算的定義中蘊(yùn)含著對集合的封閉性。1.代數(shù)運(yùn)算 設(shè)X集合，f是從Xn→X上映射，則稱f為252.二元運(yùn)算的性質(zhì)

設(shè)°和*為集合X上的二元運(yùn)算，與這些運(yùn)算相關(guān)的性質(zhì)有：(1)交換律：x，y

Ｘ，有x°y=y°x；(2)結(jié)合律：x,y,z

Ｘ，有:(x°y)°z=x°(y°z)；(3)等冪律：x

Ｘ有x°x=x；

(4)分配律：x,y,z

Ｘ有:x°(y*z)=(x°y)*(x°z)2.二元運(yùn)算的性質(zhì) 設(shè)°和*為集合X上的二元運(yùn)算，與這些263．二元運(yùn)算的特異元(1)幺元(2)零元(3)逆元3．二元運(yùn)算的特異元(1)幺元27(1)幺元設(shè)*為Ｘ上的二元運(yùn)算，則:(1)如果(

el)(el

X∧(

x)(x

X→el*x=x))，則稱el為集合X關(guān)于運(yùn)算*的左幺元；(2)如果(

er)(er

X∧(

x)(x

X→x*er=x))，則稱er為集合X關(guān)于運(yùn)算*的右幺元；(3)如果運(yùn)算的左幺元和右幺元同時(shí)存在，則必有el=er=e，使得對任意的x

X，有:x*e=e*x=x并稱e為運(yùn)算*的幺元且幺元e是惟一的。(1)幺元設(shè)*為Ｘ上的二元運(yùn)算，則:28(2)零元(1)如果(

0l)(0l

X∧(

x)(x

X→0l*x=0l))，則稱0l為集合X關(guān)于運(yùn)算*的左零元；(2)如果(

0r)(0r

X∧(

x)(x

X→x*0r=0r))，則稱0r為集合X關(guān)于運(yùn)算*的右零元；

(3)如果運(yùn)算的左零元和右零元同時(shí)存在，則必有0l=0r=0，使得對任意的x

X，有:x*0=0*x=0并稱0為運(yùn)算*的零元。(2)零元(1)如果(0l)(0lX∧(x)(xX29(3)逆元

設(shè)*為Ｘ上的二元運(yùn)算，且X中對于運(yùn)算存在幺元e。令x

X。(1)如果(

xl)(xl

X∧xl*x=e)，則稱xl是x的左逆元，并稱x是左可逆的；(2)如果(

xr)(xr

X∧x*xr=e)，則稱xr是x的右逆元，并稱x是右可逆的；(3)如果元素x既是左可逆的，又是右可逆的，則稱x是可逆的。(3)逆元設(shè)*為Ｘ上的二元運(yùn)算，且X中對于運(yùn)算存在幺元e。304.可約的或可消去的

設(shè)<X,*>為代數(shù)系統(tǒng)，且a

X，如果對任意的x，y

X有：

（a*x=a*y）∨（x*a=y*a）

x=y則稱a是可約的或可消去的。4.可約的或可消去的設(shè)<X,*>為代數(shù)系統(tǒng)，且aX，如315.代數(shù)系統(tǒng)

設(shè)X是一個(gè)非空集合，

為X上的代數(shù)運(yùn)算構(gòu)成的非空集合，則稱序偶<X,

>為一個(gè)代數(shù)系統(tǒng)（或代數(shù)結(jié)構(gòu)），其中：(1)集合X為代數(shù)系統(tǒng)<X,

>的定義域。如果X是個(gè)有限集合，則稱<X,

>為有限代數(shù)系統(tǒng)，│X│=n為代數(shù)系統(tǒng)的階；否則稱<X,

>為無限代數(shù)系統(tǒng)。(2)

=

1，

2，…

n｝為X中的n元運(yùn)算（n=1，2，3，…）構(gòu)成的集合，如果

為有限集合，則可將<X,

>表示為：<X,

1，

2，…

n>。5.代數(shù)系統(tǒng) 設(shè)X是一個(gè)非空集合，為X上的代數(shù)運(yùn)算構(gòu)成326.同態(tài)與同構(gòu)的概念設(shè)U＝<X，ｏ>，V＝<Y，*>是兩個(gè)代數(shù)系統(tǒng)，ｏ和*是二元運(yùn)算，函數(shù)f：X→Y，如果對任意的x，yX有:f(xｏy)=f(x)*f(y)(運(yùn)算的像=像的運(yùn)算)則稱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)。6.同態(tài)與同構(gòu)的概念設(shè)U＝<X，ｏ>，V＝<Y，*>是兩個(gè)337.代換性質(zhì)和同余關(guān)系代換性質(zhì)：給定代數(shù)系統(tǒng)<X，*>，其中是個(gè)二元運(yùn)算。設(shè)R是X中的等價(jià)關(guān)系，如果對任意的x1，x2

X和y1，y2

X有：

(x1Rx2)∧(y1Ry2)

(x1*y1)R(x2*y2)則稱等價(jià)關(guān)系E對于運(yùn)算具有代換性質(zhì)。同余關(guān)系：給定代數(shù)系統(tǒng)U=<X，*>，且R是集合X中的等價(jià)關(guān)系。如果等價(jià)關(guān)系R對運(yùn)算具有代換性質(zhì)，則稱R是代數(shù)系統(tǒng)U中的同余關(guān)系。7.代換性質(zhì)和同余關(guān)系代換性質(zhì)：給定代數(shù)系統(tǒng)<X，*>，其348.商代數(shù)與積代數(shù)

給定代數(shù)系統(tǒng)U=<X，ｏ>，其中ｏ是個(gè)二元運(yùn)算，R是U中的同余關(guān)系。試構(gòu)成一個(gè)新的代數(shù)系統(tǒng)W=<X/R，

>，其中

(1)X/R=｛[x]R│x

X｝；

(2)對任意的x1,x2

X,有[x1]R

[x2]R=[x1ｏx2]R則稱代數(shù)系統(tǒng)W為U的商代數(shù)，簡稱商代數(shù)，并記作U/R。8.商代數(shù)與積代數(shù) 給定代數(shù)系統(tǒng)U=<X，ｏ>，其中ｏ是35商代數(shù)與積代數(shù)（續(xù)）設(shè)U＝<X，ｏ>，V＝<Y，*>是代數(shù)系統(tǒng)，試構(gòu)成一個(gè)新的代數(shù)系統(tǒng)：U×V=<X×Y，

>其中X×Y是X和Y的笛卡兒乘積，且運(yùn)算

的定義為：對任意的x1，x2

X和y1，y2

Y有<<x1,y1>,<x2,y2>>＝<x1ｏx2，y1*y2>則稱U×V是U和V的積代數(shù)，U和V是U×V的因子代數(shù)。商代數(shù)與積代數(shù)（續(xù)）設(shè)U＝<X，ｏ>，V＝<Y，*>是代數(shù)系369.半群和群半群：設(shè)<S,*>是代數(shù)系統(tǒng)，*運(yùn)算是S上的二元運(yùn)算，若*運(yùn)算是可結(jié)合的，則稱<S,*>為一個(gè)半群。群：（1）<S，*>是代數(shù)系統(tǒng)；（2）“*”運(yùn)算滿足結(jié)合律；（3）<A，*>中存在幺元e；（4）<A，*>中任意一個(gè)元素都有逆元素；則稱代數(shù)系統(tǒng)<A，*>是群。9.半群和群半群：設(shè)<S,*>是代數(shù)系統(tǒng)，*運(yùn)算是S上的二元37子群

設(shè)<A，*>是一個(gè)群，H是A的非空子集，若<H，*>也是一個(gè)群，則稱<H，*>是<A，*>的子群。子群 設(shè)<A，*>是一個(gè)群，H是A的非空子集，若<H，*>38阿貝爾群和循環(huán)群

若群<A，*>對運(yùn)算“*”滿足交換律，則稱<A，*>是阿貝爾群（交換群）。

若群<A，*>中每個(gè)元素均是它的某個(gè)元素a的整數(shù)冪，則稱<A，*>是由a生成的循環(huán)群。a稱為<A，*>的生成元素。阿貝爾群和循環(huán)群 若群<A，*>對運(yùn)算“*”滿足交換律，則39二、本章要點(diǎn)(1)理解代數(shù)運(yùn)算以及代數(shù)運(yùn)算的性質(zhì)（結(jié)合律、交換律、分配律、等冪律、消去律）。(2)掌握代數(shù)系統(tǒng)和子代數(shù)系統(tǒng)的定義，理解運(yùn)算的封閉性。(3)給定集合和運(yùn)算，會(huì)判別運(yùn)算對該集合是否封閉。二、本章