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

1、大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 （1）需要熟練掌握的知識點包括：命題的）需要熟練掌握的知識點包括：命題的 定義、邏輯聯(lián)結(jié)詞、命題變元、命題公式定義、邏輯聯(lián)結(jié)詞、命題變元、命題公式 （合式公式）、永真式、永假式、可滿足（合式公式）、永真式、永假式、可滿足 式、等價式、蘊(yùn)涵式、極小項、極大項、式、等價式、蘊(yùn)涵式、極小項、極大項、 主析取范式、主合取范式。主析取范式、主合取范式。 第第1章命題邏輯重點章命題邏輯重點 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 （2）掌握基本的等價式和蘊(yùn)涵式，并掌握）掌握基本的等價式和蘊(yùn)涵式，并掌握 常用的等價式和蘊(yùn)涵式的證明方法（替換常用的等價式和蘊(yùn)涵式的證明方法（替換

2、 規(guī)則和推論規(guī)則）。規(guī)則和推論規(guī)則）。 第第1章命題邏輯重點（續(xù)）章命題邏輯重點（續(xù)） 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 （3）要能準(zhǔn)確地求出命題公式的主析取范）要能準(zhǔn)確地求出命題公式的主析取范 式和主合取范式。掌握主析取范式和主合取式和主合取范式。掌握主析取范式和主合取 范式與真值表的對應(yīng)關(guān)系，主析取范式和主范式與真值表的對應(yīng)關(guān)系，主析取范式和主 合取范式的關(guān)系。合取范式的關(guān)系。 第第1章命題邏輯重點（續(xù)）章命題邏輯重點（續(xù)） 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 （4）掌握命題符號化的原則；）掌握命題符號化的原則； （5）熟練掌握四個推論規(guī)則（）熟練掌握四個推論規(guī)則（P、T、CP、 F）進(jìn)

3、行有效性論證。）進(jìn)行有效性論證。 第第1章命題邏輯重點（續(xù)）章命題邏輯重點（續(xù)） 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 第第2章章 謂詞邏輯重點謂詞邏輯重點 （1）需要熟練掌握的知識點包括：謂詞、）需要熟練掌握的知識點包括：謂詞、 全稱量詞全稱量詞( x)、存在量詞、存在量詞 ( x) 、個體、個體、 個體域、個體變元（約束變元和自由變個體域、個體變元（約束變元和自由變 元）、謂詞公式的解釋（永真、永假、可元）、謂詞公式的解釋（永真、永假、可 滿足）、謂詞公式的基本的等價式和蘊(yùn)涵滿足）、謂詞公式的基本的等價式和蘊(yùn)涵 式。式。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 第第2章章 謂詞邏輯重點（續(xù)）謂詞

4、邏輯重點（續(xù)） （2）在符號化時要特別注意量詞和邏輯聯(lián)）在符號化時要特別注意量詞和邏輯聯(lián) 結(jié)詞的搭配：全稱量詞對應(yīng)邏輯聯(lián)結(jié)詞結(jié)詞的搭配：全稱量詞對應(yīng)邏輯聯(lián)結(jié)詞 “”，存在量詞對應(yīng)邏輯聯(lián)結(jié)詞，存在量詞對應(yīng)邏輯聯(lián)結(jié)詞“”。 （3）在謂詞邏輯推理的證明中，要特別注）在謂詞邏輯推理的證明中，要特別注 意意US，ES，UG，EG規(guī)則成立的條件規(guī)則成立的條件 （用（用ES規(guī)則指定的個體不能用規(guī)則指定的個體不能用UG規(guī)則加規(guī)則加 以推廣）。以推廣）。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 第三章第三章 集合集合 (1)掌握集合的基本概念及其表示，集合之間的關(guān)掌握集合的基本概念及其表示，集合之間的關(guān) 系（子集系

5、（子集 、真子集、真子集 ）、元素與集合的關(guān)系）、元素與集合的關(guān)系 （屬于（屬于 ）、全集、空集、冪集、笛卡爾乘積）、全集、空集、冪集、笛卡爾乘積 等概念。等概念。 (2)能熟練地證明集合中的相等關(guān)系、包含關(guān)系。能熟練地證明集合中的相等關(guān)系、包含關(guān)系。 (3)掌握集合的五種基本運(yùn)算：掌握集合的五種基本運(yùn)算： A、A B、A B、A-B、A B 及集合運(yùn)算的基本定律。及集合運(yùn)算的基本定律。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 第四章二元關(guān)系第四章二元關(guān)系 (1)掌握關(guān)系矩陣和關(guān)系圖的表示方法。掌握關(guān)系矩陣和關(guān)系圖的表示方法。 (2)掌握合成運(yùn)算、逆運(yùn)算、閉包運(yùn)算的概掌握合成運(yùn)算、逆運(yùn)算、閉包運(yùn)算

6、的概 念。念。 (3)熟練掌握關(guān)系的性質(zhì)（自反性、反自反熟練掌握關(guān)系的性質(zhì)（自反性、反自反 性、對稱性、反對稱性、可傳遞性）及其性、對稱性、反對稱性、可傳遞性）及其 判別方法。判別方法。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 第四章二元關(guān)系（續(xù)）第四章二元關(guān)系（續(xù)） (4)掌握等價關(guān)系（自反、對稱、可傳遞）掌握等價關(guān)系（自反、對稱、可傳遞） 和偏序關(guān)系（自反、反對稱、可傳遞）的和偏序關(guān)系（自反、反對稱、可傳遞）的 概念及證明。概念及證明。 (5)掌握等價關(guān)系和劃分之間的相互關(guān)系。掌握等價關(guān)系和劃分之間的相互關(guān)系。 (6)掌握偏序關(guān)系和哈斯圖，并會求極大掌握偏序關(guān)系和哈斯圖，并會求極大 （?。┰?、

7、最大（?。┰?、上（下）界、（?。┰?、最大（?。┰?、上（下）界、 上（下）確界。上（下）確界。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 第四章第四章函數(shù)函數(shù) 一、主要內(nèi)容一、主要內(nèi)容 二、本章要點二、本章要點 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 一、主要內(nèi)容一、主要內(nèi)容 1、函數(shù)的基本概念函數(shù)的基本概念 2 2、函數(shù)的性質(zhì)、函數(shù)的性質(zhì) 3 3、特種函數(shù)、特種函數(shù) 4 4、復(fù)合函數(shù)、復(fù)合函數(shù) 5 5、逆函數(shù)、逆函數(shù) 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 1、函數(shù)的基本概念函數(shù)的基本概念 設(shè)設(shè)f是從集合是從集合X到到Y(jié)上關(guān)系上關(guān)系，若對任意的，若對任意的x X都都 存在唯一的存在唯一的y y Y Y，使，

8、使xy f，則稱關(guān)系，則稱關(guān)系f為函為函 數(shù)（或映射），記作：數(shù)（或映射），記作：f: f: XY。 (1)(1)對于函數(shù)對于函數(shù)f: f: XY，如果，如果x，y f，也寫成，也寫成 y=f(x), 并稱并稱x為自變量，為自變量，y稱為函數(shù)在稱為函數(shù)在x處的值，處的值， 或稱或稱y為在函數(shù)為在函數(shù)f的作用下的作用下x的像點，相應(yīng)地稱的像點，相應(yīng)地稱x為為 y y的原像。的原像。 (2)(2)對于函數(shù)對于函數(shù)f: f: XY，則稱，則稱X為函數(shù)為函數(shù)f的定義域，的定義域， Y稱為稱為f的陪域；的陪域；Rf是是f的值域。的值域。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 2 2、函數(shù)的性質(zhì)、函數(shù)的性質(zhì)

9、 設(shè)函數(shù)設(shè)函數(shù)f: f: XY, ,則則f滿足下面兩個性質(zhì)：滿足下面兩個性質(zhì)： (1)(1)任意性：函數(shù)的定義域必須是集合任意性：函數(shù)的定義域必須是集合X， 即：即：Df = X； (2)(2)唯一性：對任意的唯一性：對任意的x x X，必存在唯一的，必存在唯一的 y Y，使，使 f，即：，即： 對任意的對任意的x x X，y，z Y，有：，有： f f y = z。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 3 3、特種函數(shù)、特種函數(shù) 設(shè)函數(shù)設(shè)函數(shù)f: f: XY, ,則：則： (1)(1)若若f(X)=f(X)=Rf=Y, , 則稱則稱f f是滿射的；是滿射的； (2)(2)對任意對任意x1,x

10、2 X，如果，如果: x1x2f(x)f(y),f(x)f(y), 或或:f(:f(x1)=f()=f(x2) )x1 = =x2； 則稱則稱f f是單射的；是單射的； (3)(3)若若f f是既是滿射的，又是單射的，則稱是既是滿射的，又是單射的，則稱f f 是雙射的。是雙射的。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 4 4、復(fù)合函數(shù)、復(fù)合函數(shù) 給定函數(shù)給定函數(shù)f: f: XY，g: : XZ，則：，則： gf=x Xz Z( y) (fg) 則稱則稱gf為為f和和g的合成函數(shù)（或復(fù)合函數(shù)）。的合成函數(shù)（或復(fù)合函數(shù)）。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 5 5、逆函數(shù)、逆函數(shù) 如果如果f f是

11、個雙射函數(shù)，則是個雙射函數(shù)，則f f的逆關(guān)系稱為的逆關(guān)系稱為 f f的逆函數(shù)（或反函數(shù)），并記作：的逆函數(shù)（或反函數(shù)），并記作：f1。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 相關(guān)定理相關(guān)定理 定理定理1 1 設(shè)函數(shù)設(shè)函數(shù)f: ABf: AB，所有從，所有從A A到到B B的函數(shù)的函數(shù) 的集合的集合 f | f: AB f | f: AB，記作，記作BA，如果，如果 |A|A|m, |B|=n,m, |B|=n,則則| |BA| |n nm m 。 。 定理定理2 2 設(shè)函數(shù)設(shè)函數(shù)f: f: XY，g: Y: YZ，則復(fù)合，則復(fù)合 函數(shù)函數(shù)gf是從是從XZ上的函數(shù)，并對任意的上的函數(shù)，并對任意的

12、xX，都有：（，都有：（gf）（）（x）= g (f (x) )。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 相關(guān)定理（續(xù)）相關(guān)定理（續(xù)） 定理定理3 函數(shù)的復(fù)合運(yùn)算是可結(jié)合的，即如果函數(shù)的復(fù)合運(yùn)算是可結(jié)合的，即如果 f、g和和h都是函數(shù)，則有：都是函數(shù)，則有： （gf）h = g(fh) = gfh 定理定理4 4 設(shè)函數(shù)設(shè)函數(shù)f: f: XY，f的逆關(guān)系的逆關(guān)系f 1是從是從 YX上函數(shù)，當(dāng)且僅當(dāng)上函數(shù)，當(dāng)且僅當(dāng)f是個雙射函數(shù)。是個雙射函數(shù)。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 二、本章要點二、本章要點 1、掌握函數(shù)的定義（任意性、唯一性）、掌握函數(shù)的定義（任意性、唯一性）: 設(shè)設(shè)f是從集合是從

13、集合X到到Y(jié)的關(guān)系，即的關(guān)系，即f:XY， 若對任意的若對任意的x X都存在唯一的都存在唯一的y Y，使，使 f，或，或y=f(x)，則稱關(guān)系，則稱關(guān)系f為函數(shù)（或為函數(shù)（或 映射）映射） 注意：函數(shù)和關(guān)系的聯(lián)系和區(qū)別。注意：函數(shù)和關(guān)系的聯(lián)系和區(qū)別。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 本章要點（續(xù)）本章要點（續(xù)） 2、掌握合成函數(shù)的概念：、掌握合成函數(shù)的概念： 設(shè)函數(shù)設(shè)函數(shù)f: XY ,g: YZ,則則: g f=|xXXzZZ( y)(yYy =f(x)z=g(y) 稱為稱為f和和g的合成函數(shù)（復(fù)合函數(shù)）。的合成函數(shù)（復(fù)合函數(shù)）。 注意：合成關(guān)系和合成函數(shù)書寫格式的區(qū)別。注意：合成關(guān)系和合

14、成函數(shù)書寫格式的區(qū)別。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 本章要點（續(xù)）本章要點（續(xù)） 3、掌握反函數(shù)的概念及其存在的條件：、掌握反函數(shù)的概念及其存在的條件： 設(shè)設(shè) f: XY是雙射函數(shù)，則是雙射函數(shù)，則f的逆關(guān)系稱的逆關(guān)系稱 f的反函數(shù)，記作的反函數(shù)，記作f-1 注意：只有雙射函數(shù)才有反函數(shù)。注意：只有雙射函數(shù)才有反函數(shù)。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 本章要點（續(xù)）本章要點（續(xù)） 4、掌握特種函數(shù)的定義（單射、滿射、雙、掌握特種函數(shù)的定義（單射、滿射、雙 射）及證明：射）及證明： 滿射函數(shù)：設(shè)函數(shù)滿射函數(shù)：設(shè)函數(shù)f: f: XY，若若 f(X)=Rf=Y（值域陪域）。（值域陪域）。

15、 單射函數(shù)：設(shè)函數(shù)單射函數(shù)：設(shè)函數(shù)f: f: XY，對任意對任意x1， x2 X，如果：，如果： x1x2 f(f(x1)f()f(x2) ) 或或 f(f(x1)=f()=f(x2) ) x1= =x2； 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 第五章第五章代數(shù)結(jié)構(gòu)代數(shù)結(jié)構(gòu) 一、主要內(nèi)容一、主要內(nèi)容 二、本章要點二、本章要點 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 一、主要內(nèi)容一、主要內(nèi)容 1. 1. 代數(shù)運(yùn)算代數(shù)運(yùn)算 2. 2. 二元運(yùn)算的性質(zhì)二元運(yùn)算的性質(zhì) 3 3二元運(yùn)算的特異元二元運(yùn)算的特異元 4. 4. 可約的或可消去的可約的或可消去的 5. 5. 代數(shù)系統(tǒng)的概念代數(shù)系統(tǒng)的概念 6. 6.

16、同態(tài)與同構(gòu)的概念同態(tài)與同構(gòu)的概念 7. 7. 代換性質(zhì)和同余關(guān)系代換性質(zhì)和同余關(guān)系 8. 8. 商代數(shù)與積代數(shù)商代數(shù)與積代數(shù) 9.9.半群和群半群和群 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 1. 1. 代數(shù)運(yùn)算代數(shù)運(yùn)算 設(shè)設(shè)X X集合，集合，f f是從是從X Xn n X X上映射，則稱上映射，則稱f f為集合為集合 X X中的中的n n元運(yùn)算。特別是：元運(yùn)算。特別是： (1)(1)當(dāng)當(dāng)n=1n=1時，時，f f：X X XX稱為集合稱為集合X X中的一元運(yùn)算；中的一元運(yùn)算； (2)(2)當(dāng)當(dāng)n=2n=2時，時，f f：X XX X XX稱為集合稱為集合X X中的二元運(yùn)中的二元運(yùn) 算。算。 如果

17、對給定的集合中的元素進(jìn)行運(yùn)算，從而如果對給定的集合中的元素進(jìn)行運(yùn)算，從而 產(chǎn)生了像點，而該像點又是該集合中的元素，產(chǎn)生了像點，而該像點又是該集合中的元素， 則稱給定的運(yùn)算對該集合封閉。在上述的代數(shù)則稱給定的運(yùn)算對該集合封閉。在上述的代數(shù) 運(yùn)算的定義中蘊(yùn)含著對集合的封閉性。運(yùn)算的定義中蘊(yùn)含著對集合的封閉性。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 2. 2. 二元運(yùn)算的性質(zhì)二元運(yùn)算的性質(zhì) 設(shè)設(shè) 和和* *為集合為集合X X上的二元運(yùn)算，與這些上的二元運(yùn)算，與這些 運(yùn)算相關(guān)的性質(zhì)有：運(yùn)算相關(guān)的性質(zhì)有： (1)(1)交換律：交換律：x x，y y ，有，有 x x y=yy=y x x； (2)(2)結(jié)

18、合律：結(jié)合律：x,y,zx,y,z ，有，有: : (x(x y)y) z=xz=x (y(y z)z)； (3)(3)等冪律：等冪律：x x 有有x x x=xx=x； (4)(4)分配律：分配律：x,y,z 有有: : x (y*z)=(x y)* (x z) 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 3 3二元運(yùn)算的特異元二元運(yùn)算的特異元 (1)幺元幺元 (2)零元零元 (3)逆元逆元 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 (1)幺元幺元 設(shè)設(shè)* *為上的二元運(yùn)算，則為上的二元運(yùn)算，則: : (1)(1)如果如果( ( e el l)()(e el l X(X( x)(xx)(x XXe el

19、l* *x=x)x=x)，則稱，則稱 e el l為集合為集合X X關(guān)于運(yùn)算關(guān)于運(yùn)算* *的左幺元；的左幺元； (2)(2)如果如果( ( e er r)()(e er r X(X( x)(xx)(x XxXx* *e er r=x)=x)，則稱，則稱 e er r為集合為集合X X關(guān)于運(yùn)算關(guān)于運(yùn)算* *的右幺元；的右幺元； (3)(3)如果運(yùn)算的左幺元和右幺元同時存在，則必有如果運(yùn)算的左幺元和右幺元同時存在，則必有 e el l=e=er r=e=e，使得對任意的，使得對任意的x x X X，有，有:x:x* *e=ee=e* *x=xx=x 并稱并稱e e為運(yùn)算為運(yùn)算* *的幺元且幺元的幺

20、元且幺元e e是惟一的。是惟一的。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 (2)零元零元 (1)(1)如果如果( ( 0 0l l)(0)(0l l X( X( x)(xx)(x X0X0l l* *x=0 x=0l l)，則，則 稱稱0 0l l為集合為集合X X關(guān)于運(yùn)算關(guān)于運(yùn)算* *的左零元；的左零元； (2)(2)如果如果( ( 0 0r r)(0)(0r r X( X( x)(xx)(x XxXx* *0 0r r=0=0r r)，則，則 稱稱0 0r r為集合為集合X X關(guān)于運(yùn)算關(guān)于運(yùn)算* *的右零元；的右零元； (3)(3)如果運(yùn)算的左零元和右零元同時存在，則必有如果運(yùn)算的左零元和右

21、零元同時存在，則必有 0 0l l= =0 0r r= =0 0，使得對任意的，使得對任意的x x X X，有，有:x:x* *0 0= =0 0* *x=0 x=0 并稱并稱0 0為運(yùn)算為運(yùn)算* *的零元。的零元。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 (3)逆元逆元 設(shè)設(shè)* *為上的二元運(yùn)算，且為上的二元運(yùn)算，且X X中對于運(yùn)算存在幺元中對于運(yùn)算存在幺元 e e。令。令x x X X。 (1)(1)如果如果( ( x xl l)(x)(xl l XxXxl l* *x=x=e e) )，則稱，則稱x xl l是是x x的左逆的左逆 元，并稱元，并稱x x是左可逆的；是左可逆的； (2)(2)

22、如果如果( ( x xr r)(x)(xr r XxXx* *x xr r= =e e) )，則稱，則稱x xr r是是x x的右逆的右逆 元，并稱元，并稱x x是右可逆的；是右可逆的； (3)(3)如果元素如果元素x x既是左可逆的，又是右可逆的，則既是左可逆的，又是右可逆的，則 稱稱x x是可逆的。是可逆的。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 4. 4. 可約的或可消去的可約的或可消去的 設(shè)設(shè) 為代數(shù)系統(tǒng)，且為代數(shù)系統(tǒng)，且a a X，如果對任，如果對任 意的意的x，y X有：有： （a*x=a*y）（x*a=y*a）x = y 則稱則稱a是可約的或可消去的。是可約的或可消去的。 大連海事

23、大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 5. 5. 代數(shù)系統(tǒng)代數(shù)系統(tǒng) 設(shè)設(shè)X X是一個非空集合，是一個非空集合， 為為X X上的代數(shù)運(yùn)算構(gòu)上的代數(shù)運(yùn)算構(gòu) 成的非空集合，則稱序偶成的非空集合，則稱序偶X, 為一個代數(shù)系為一個代數(shù)系 統(tǒng)（或代數(shù)結(jié)構(gòu)），其中：統(tǒng)（或代數(shù)結(jié)構(gòu)），其中： (1)(1)集合集合X X為代數(shù)系統(tǒng)為代數(shù)系統(tǒng)X, 的定義域。如果的定義域。如果X X是個是個 有限集合，則稱有限集合，則稱X, 為有限代數(shù)系統(tǒng)，為有限代數(shù)系統(tǒng)， X=nX=n為代數(shù)系統(tǒng)的階；否則稱為代數(shù)系統(tǒng)的階；否則稱X, 為無限為無限 代數(shù)系統(tǒng)。代數(shù)系統(tǒng)。 (2)(2) = = 1 1， 2 2， n n為為X X中的中的n

24、n元運(yùn)算（元運(yùn)算（n=1n=1，2 2， 3 3，）構(gòu)成的集合，如果）構(gòu)成的集合，如果 為有限集合，則可為有限集合，則可 將將X, 表示為：表示為：X, 。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 6. 6. 同態(tài)與同構(gòu)的概念同態(tài)與同構(gòu)的概念 設(shè)設(shè)U UX ，V VY 是兩個代數(shù)系統(tǒng)，和是兩個代數(shù)系統(tǒng)，和* *是二元是二元 運(yùn)算，函數(shù)運(yùn)算，函數(shù)f f：XYXY，如果對任意的，如果對任意的x x，yXyX有有: : f f(x(xy)=y)=f f(x)(x)* *f f(y) (y) (運(yùn)算的像運(yùn)算的像= =像的運(yùn)算像的運(yùn)算) ) 則稱則稱f f是代數(shù)系統(tǒng)是代數(shù)系統(tǒng)U U到到V V同態(tài)映射同態(tài)映射

25、( (簡稱同態(tài)簡稱同態(tài)) )，并稱代數(shù)系，并稱代數(shù)系 統(tǒng)統(tǒng)U U與與V V同態(tài)。同態(tài)。 (1) (1) 如果如果f f是滿射的，則稱是滿射的，則稱f f 是從是從U U到到V V的滿同態(tài)；的滿同態(tài)； (2) (2) 如果如果f f是單射的，則稱是單射的，則稱f f 是從是從U U到到V V的單一同態(tài)；的單一同態(tài)； (3) (3) 如果如果f f是雙射的，則稱是雙射的，則稱f f 是從是從U U到到V V的同構(gòu)。的同構(gòu)。 (4) (4) 如果如果U=VU=V，則稱，則稱f f是從是從U U到到U U的自同構(gòu)。的自同構(gòu)。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 7. 7. 代換性質(zhì)和同余關(guān)系代換性質(zhì)和

26、同余關(guān)系 代換性質(zhì)：給定代數(shù)系統(tǒng)代換性質(zhì)：給定代數(shù)系統(tǒng)X ，其中是個二元運(yùn)，其中是個二元運(yùn) 算。設(shè)算。設(shè)R R是是X X中的等價關(guān)系，如果對任意的中的等價關(guān)系，如果對任意的x x1 1， x x2 2 X X和和y y1 1，y y2 2 X X有：有： (x(x1 1RxRx2 2)(y)(y1 1RyRy2 2) )(x(x1 1* *y y1 1)R(x)R(x2 2* *y y2 2) ) 則稱等價關(guān)系則稱等價關(guān)系E E對于運(yùn)算具有代換性質(zhì)。對于運(yùn)算具有代換性質(zhì)。 同余關(guān)系：給定代數(shù)系統(tǒng)同余關(guān)系：給定代數(shù)系統(tǒng)U=XU= ，且，且R R是集合是集合X X 中的等價關(guān)系。如果等價關(guān)系中的等

27、價關(guān)系。如果等價關(guān)系R R對運(yùn)算具有代換性對運(yùn)算具有代換性 質(zhì)，則稱質(zhì)，則稱R R是代數(shù)系統(tǒng)是代數(shù)系統(tǒng)U U中的同余關(guān)系。中的同余關(guān)系。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 8. 8. 商代數(shù)與積代數(shù)商代數(shù)與積代數(shù) 給定代數(shù)系統(tǒng)給定代數(shù)系統(tǒng)U=XU= ，其中是個二元，其中是個二元 運(yùn)算，運(yùn)算，R R是是U U中的同余關(guān)系。試構(gòu)成一個新的代中的同余關(guān)系。試構(gòu)成一個新的代 數(shù)系統(tǒng)數(shù)系統(tǒng)W=X/RW= ，其中，其中 (1)X/R=(1)X/R=xxR R x x X X； (2)(2)對任意的對任意的x x1 1,x,x2 2 X,X,有有xx1 1 R R xx2 2 R R=x=x1 1x x2

28、 2 R R 則稱代數(shù)系統(tǒng)則稱代數(shù)系統(tǒng)W W為為U U的商代數(shù)，簡稱商代數(shù)，并記的商代數(shù)，簡稱商代數(shù)，并記 作作U/RU/R。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 商代數(shù)與積代數(shù)（續(xù)）商代數(shù)與積代數(shù)（續(xù)） 設(shè)設(shè)U UX ，V VY 是代數(shù)系統(tǒng)，試構(gòu)成一是代數(shù)系統(tǒng)，試構(gòu)成一 個新的代數(shù)系統(tǒng)：個新的代數(shù)系統(tǒng)：U UV = XV = 其中其中X XY Y是是X X和和Y Y的笛卡兒乘積，且運(yùn)算的笛卡兒乘積，且運(yùn)算 的定義的定義 為：對任意的為：對任意的x x1 1，x x2 2 X X和和y y1 1，y y2 2 Y Y有有 x,x 則稱則稱U UV V是是U U和和V V的積代數(shù)，的積代數(shù)，U

29、U和和V V是是U UV V的因子代的因子代 數(shù)。數(shù)。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 9.9.半群和群半群和群 半群：設(shè)半群：設(shè)是代數(shù)系統(tǒng)，是代數(shù)系統(tǒng)，*運(yùn)算是運(yùn)算是S上的二元上的二元 運(yùn)算，若運(yùn)算，若*運(yùn)算是可結(jié)合的，則稱運(yùn)算是可結(jié)合的，則稱為一個為一個 半群。半群。 群：（群：（1）是代數(shù)系統(tǒng)；是代數(shù)系統(tǒng)； （2） “*”運(yùn)算滿足結(jié)合律；運(yùn)算滿足結(jié)合律； （3）中存在幺元中存在幺元e； （4）中任意一個元素都有逆元素；中任意一個元素都有逆元素； 則稱代數(shù)系統(tǒng)則稱代數(shù)系統(tǒng)是群。是群。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 子群子群 設(shè)設(shè)是一個群，是一個群，H是是A的非空子的非空子 集，若

30、集，若也是一個群，則稱也是一個群，則稱是是的子群。的子群。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 阿貝爾群和循環(huán)群阿貝爾群和循環(huán)群 若群若群對運(yùn)算對運(yùn)算“*”滿足交換律，滿足交換律， 則則 稱稱是阿貝爾群（交換群）。是阿貝爾群（交換群）。 若群若群中每個元素均是它的某個中每個元素均是它的某個 元素元素a的整數(shù)冪，則稱的整數(shù)冪，則稱是由是由a生成的生成的 循環(huán)群。循環(huán)群。a稱為稱為的生成元素。的生成元素。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 二、本章要點二、本章要點 (1)理解代數(shù)運(yùn)算以及代數(shù)運(yùn)算的性質(zhì)（結(jié)理解代數(shù)運(yùn)算以及代數(shù)運(yùn)算的性質(zhì)（結(jié) 合律、交換律、分配律、等冪律、消去合律、交換律、分配律、等冪律、消去 律）。律）。 (2)掌握代數(shù)系統(tǒng)和子代數(shù)系統(tǒng)的定義，理掌握代數(shù)系統(tǒng)和子代數(shù)系統(tǒng)的定義，理 解運(yùn)算的封閉性。解運(yùn)算的封閉性。 (3)給定集合和運(yùn)算，會判別運(yùn)算對該集合給定集合和運(yùn)算，會判別運(yùn)算對該集合 是否封閉。是否封閉。 大連海事大學(xué)離散數(shù)學(xué)期末復(fù)習(xí)綱 要 本章要點（續(xù)）本章要點（續(xù)） (4)給定二元運(yùn)算，說明運(yùn)算是否滿足交換給定二元運(yùn)算，說明運(yùn)算是否滿足交換 律、結(jié)合律、等冪律、分配律和消去律。律、結(jié)合律、等冪律、分配律和消去律。 (5)掌握和理解幺元