第1章集合、映射與運算2015

1、(Discrete Mathematics )祁偉祁偉電話電話Q:826105276 使用教材使用教材書 名：離散數(shù)學（第三版） “十一五”國家規(guī)劃教材主 編：鄧輝文出版社：清華大學出版社講 授：第1章 _ 第6章參考書目參考書目1 1、邵學才、邵學才. . 離散數(shù)學（第二版）. . 清清華大學出版社華大學出版社. (. (應(yīng)用型規(guī)劃教材應(yīng)用型規(guī)劃教材) )2 2、周忠榮、周忠榮. . 離散數(shù)學及其應(yīng)用. . 清華清華大學出版社大學出版社. .3 3、王禮萍、王禮萍. . 離散數(shù)學簡明教程. . 清華清華大學出版社大學出版社. (. (高職教材高職教材) )4 4、耿

2、素云、耿素云, , 屈婉玲屈婉玲. . 離散數(shù)學（修訂版）. . 高等教育出版社高等教育出版社. (. (十五規(guī)劃教材，十五規(guī)劃教材，北京大學北京大學) )考核方式考核方式期末成績期末成績 = 平時成績平時成績 + 期末試卷成績期末試卷成績 平時成績平時成績20分分 平時成績平時成績 = 出勤出勤 + 小測驗小測驗 +作業(yè)作業(yè) 出勤出勤 = 10 小測驗小測驗 = 5 作業(yè)作業(yè) = 5（獨立、自主獨立、自主） 期末試卷成績期末試卷成績80分。分。研究對象研究對象 離散數(shù)學是研究離散量的結(jié)構(gòu)及其相離散數(shù)學是研究離散量的結(jié)構(gòu)及其相互之間關(guān)系的一互之間關(guān)系的一門門學科，學科，它它與當今計算機與當今計

3、算機所處理的對象相一致。所處理的對象相一致。 離散數(shù)學是研究計算機科學的離散數(shù)學是研究計算機科學的基本數(shù)學工具和最合適的理論手段；基本數(shù)學工具和最合適的理論手段；是計算機類專業(yè)的重要課程。是計算機類專業(yè)的重要課程。學習目的學習目的 離散數(shù)學是計算機及相關(guān)專業(yè)的一門核心課程，不是一門純數(shù)學課程，而是計算機學科的專業(yè)基礎(chǔ)課程。 1、為后繼課程提供必要的數(shù)學基礎(chǔ) 2、培養(yǎng)學生抽象思維能力和嚴密的邏輯推理能力?；緝?nèi)容（基本內(nèi)容（1）一、集合與關(guān)系：是離散數(shù)學研究的重點內(nèi)容 1、Chapter 1 集合、映射與運算：集合是現(xiàn)代數(shù)學的最基本概念，映射是現(xiàn)代數(shù)學的基本概念，是本書的重點。 2、Chapte

4、r 2 關(guān)系：是刻畫聯(lián)系的數(shù)學模型。二、數(shù)理邏輯：研究思維形式及思維規(guī)律尤其是推理的學科。 1、Chapter 3 命題邏輯：研究的主要對象是命題。 2、Chapter 4 謂詞邏輯：研究原子命題的內(nèi)部形式結(jié)構(gòu)及其邏輯關(guān)系?；緝?nèi)容（基本內(nèi)容（2）三、代數(shù)結(jié)構(gòu)：研究有一般元素組成的集合上的運算，以及運算滿足一些給定的數(shù)學結(jié)構(gòu)的性質(zhì)。 1、Chapter 5 (1) 代數(shù)結(jié)構(gòu)：計算機系統(tǒng)本身就是一種代數(shù)結(jié)構(gòu)。 2、Chapter 5 (2) 群、環(huán)和域：在形式語言與自動機理論學科中發(fā)揮作用。 3、Chapter 5 (3) 格與布爾代數(shù)：在自動推理和邏輯電路設(shè)計的分析和優(yōu)化等問題中得到應(yīng)用。四、

5、圖論：廣泛應(yīng)用與解決現(xiàn)實問題。 1、Chapter 6 圖論：主要研究數(shù)據(jù)結(jié)構(gòu)中圖的相關(guān)性質(zhì)。 2、Chapter 7 幾類特殊的圖：介紹生活和研究中實際的圖論的問題。第第1章章 集合、映射與運算集合、映射與運算 1.1集合的有關(guān)概念集合的有關(guān)概念 1.2映射的有關(guān)概念映射的有關(guān)概念 1.3運算的定義及性質(zhì)運算的定義及性質(zhì) 1.4集合的運算集合的運算 1.5集合的劃分與覆蓋集合的劃分與覆蓋第第1章章 集合、映射與運算集合、映射與運算 集合是現(xiàn)代數(shù)學的最基本概念. 映射又稱為函數(shù), 它是現(xiàn)代數(shù)學的基本概念, 可以借助于集合下定義. 運算本質(zhì)上是映射, 但有其特殊性.(關(guān)系也是集合)集合、映射、運

6、算及關(guān)系是貫穿于本書的一條主線.1.1.1 集合集合 集合（set）:是指具有某種特定性質(zhì)的對象匯集成的一個整體。元素（element）：集合中的每一個對象稱為集合的元素。通常用大寫字母表示集合，用小寫字母表示集合中的元素。 在數(shù)學中常用 表示整體.在討論集合時，為避免出現(xiàn)某些悖論，應(yīng)指定討論范圍，這個范圍也是一個集合，稱為全集或論域，記作U。文氏圖用矩形框表示。UA隸屬關(guān)系隸屬關(guān)系集合與集合中元素的關(guān)系隸屬關(guān)系給定一個集合A， （1）若x是集合A中的元素，記作xA，讀作x屬于A； （2）若x不是集合A中的元素，則記作xA，讀作x不屬于A。說明：讀作屬于；讀作不屬于例:A=a,b,c,d，則有

7、b A，e A特殊集合表示特殊集合表示幾類特殊集合的表示：幾類特殊集合的表示：nN 自然數(shù)集合自然數(shù)集合 , 包括數(shù)包括數(shù)0；nZ 整數(shù)集合；整數(shù)集合；nQ 有理數(shù)集合；有理數(shù)集合；nR 實數(shù)集合；實數(shù)集合；nC 復數(shù)集合復數(shù)集合集合的表示集合的表示 列舉法列舉法 就是把集合中的所有元素一一列舉出來，或列出足夠多的元素以反映出集合中成員的特征，元素之間用逗號分開，并用花括號括起來。如：A=a1，a2，an B=0，2，4，6，2n，。集合的表示集合的表示 描述法描述法 是指把集合中的元素所滿足的條件或具有的性質(zhì)描述出來，即將條件或性質(zhì)用文字或符號在花括號內(nèi)豎線后面表示出來。一般形式為： A=A

8、=x x| |x x 滿足的條件或具有的性質(zhì)滿足的條件或具有的性質(zhì) 如：A=x|x 1 = 0，xR B= x|x是英文字母，x元音集合的表示集合的表示 遞歸法遞歸法 是指通過計算規(guī)則定義集合中的元素。首先給出該集合的初始元素；然后給出由集合中已知元素構(gòu)造其他元素的方法；最后強調(diào)有限次使用前面的步驟得到的元素是集合中僅有的元素。如：設(shè)a0=1,a1=1,an+1=an+an-1, A=a0,a1,a2,=akk0。 集合的表示集合的表示 巴科斯范式巴科斯范式(BNF)表示法表示法 BNF常用來定義高級程序設(shè)計語言的標識符或表達式集合。 文氏圖法文氏圖法(John Venn) 首先畫一個大矩形表

9、示全集，然后在矩形內(nèi)畫一些圓，用圓的內(nèi)部表示集合，集合之間的相互關(guān)系和有關(guān)的運算可以用文氏圖給予形象的描述。集合的特性集合的特性 確定性確定性 確定性是指一旦給定了集合確定性是指一旦給定了集合A A，對于任意元素，對于任意元素a a，我，我們就可以準確地判定們就可以準確地判定a a是否在是否在A A中。中。如：如：A=A=x x| |x x是自然數(shù)，且是自然數(shù)，且x x100100則必有則必有3030 A A，101101 A A 互異性互異性 互異性是指集合中的元素之間是彼此不同的，即集互異性是指集合中的元素之間是彼此不同的，即集合中不允許出現(xiàn)重復的元素。合中不允許出現(xiàn)重復的元素。如：集合如

10、：集合 A=a,b,c,c,b,d A=a,b,c,c,b,d 應(yīng)為應(yīng)為 A=a,b,c,dA=a,b,c,d集合的特性集合的特性 無序性無序性 無序性是指集合中的元素之間沒有次序關(guān)系。在無序性是指集合中的元素之間沒有次序關(guān)系。在不特別說明情況下，我們所討論的集合都不是多重不特別說明情況下，我們所討論的集合都不是多重集。集。 如：如： A = A = a a, , a a, , b b, , b b, , c c 與與 A=A=a a, , b b, , c c , , a a, , b b 相同相同 抽象性抽象性 抽象性是指集合中元素是抽象的，甚至可以是集合。抽象性是指集合中元素是抽象的，甚

11、至可以是集合。如：如：A = a, a, b, b, c；相關(guān)概念相關(guān)概念有限集有限集 由有限個元素由有限個元素a1,an組成的集合稱為有限集。組成的集合稱為有限集?；鶖?shù)（或勢）基數(shù)（或勢） 若集合若集合A是有限集，則集合是有限集，則集合A中的元素個數(shù)稱為集中的元素個數(shù)稱為集合合A的基數(shù)（或勢），通常記作的基數(shù)（或勢），通常記作|A|。無限集無限集 無限集是指由無限個元素組成的集合。無限集是指由無限個元素組成的集合。空集空集 不含有任何元素的集合是空集。記不含有任何元素的集合是空集。記或或 。1.1.2 子集子集子集子集集合間的包含關(guān)系集合間的包含關(guān)系 給定兩個集合A和B，若A中的任意元素都屬

12、于B，則稱A是B的子集，或稱A包含在B，或稱B包含A，通常記作A B，或BA。（若任意aA，必有aB，則A B） 若若A A不是不是B B的子集，則集合的子集，則集合A A中至少有一中至少有一個元素不屬于個元素不屬于B B。子集定理子集定理1-1 對于任意的集合對于任意的集合A，有，有 A。1-2 設(shè)設(shè)A、B、C是任意的集合，則有是任意的集合，則有自反性：自反性：A A.（任意集合是其子集）（任意集合是其子集）反對稱性：反對稱性：A B,B A A = B.傳遞性：傳遞性：A B,B C A C.1-3 A = B 的充要條件是的充要條件是A B 且且 B A真子集真子集 若若A A B B，

13、且，且A A B B，則稱，則稱A A是是B B的真子集，通常記作的真子集，通常記作A A B B。（若。（若A A是是B B的真子集，則的真子集，則B B中至少有一個元素不屬中至少有一個元素不屬于于A A）注意區(qū)別：注意區(qū)別： 1.1.3 冪集冪集定理定理 設(shè)設(shè)A是一個有限集且是一個有限集且|A|=n，則，則|P(A)|=2n|)(XAAXP冪集示例冪集示例X X = = a a, , b b P P( (X X) = ) = , , a a, , b b, , a a, , b b.P P() = ) = , , .習題習題1.1 (7)1.1 (7)1.1.4 n元組元組),(yxO),

14、(xyn=2n=3.,., ,.,),.,(212121nnnxxxxxxxxx),(zyxO序偶序偶.,),.,(),.,(2121iyxyyyxxxiinn1.1.5 笛卡兒積笛卡兒積設(shè)設(shè)A1，A2，An是集合，稱集合是集合，稱集合為為A1，A2，An的笛卡兒積（直積，叉積）的笛卡兒積（直積，叉積）.,.,2 , 1,| ),.,(.2121niAxxxxAAAiinn.By,Ax| )y, x(BA笛卡兒積定理笛卡兒積定理.| ,|mnBAnBmA1.2 映射的有關(guān)概念映射的有關(guān)概念 映射就是函數(shù)，研究的是任意兩個集映射就是函數(shù)，研究的是任意兩個集合之間的一種對應(yīng)關(guān)系。合之間的一種對應(yīng)關(guān)

15、系。 映射是現(xiàn)代數(shù)學中的基本概念。函數(shù)映射是現(xiàn)代數(shù)學中的基本概念。函數(shù)在信息科學中得到了充分的應(yīng)用。在信息科學中得到了充分的應(yīng)用。 與集合一樣，映射貫穿本書的所有內(nèi)與集合一樣，映射貫穿本書的所有內(nèi)容，深刻理解映射的有關(guān)內(nèi)容，對于其他容，深刻理解映射的有關(guān)內(nèi)容，對于其他內(nèi)容的學習是至關(guān)重要的。內(nèi)容的學習是至關(guān)重要的。1.2.1 映射的定義映射的定義 任意給定兩個集合任意給定兩個集合A和和B，若存在對應(yīng)法則，若存在對應(yīng)法則 f ，使得對于，使得對于任意任意x A，均存在，均存在唯一唯一的的y B與它與它對應(yīng)，則稱對應(yīng)，則稱 f 是集合是集合A到到B的一個映射，或稱的一個映射，或稱A到到B的一個函數(shù)

16、，記為的一個函數(shù)，記為 f :AB。ABfBAf:映射的兩個特點映射的兩個特點 假定假定 f :AB, y= f(x) ,通常把通常把x稱為自變量，其取值范圍稱稱為自變量，其取值范圍稱為為定義域記為定義域記為dom f ；將；將y稱為因變量，其取值范圍稱為值域，稱為因變量，其取值范圍稱為值域，記為記為ran f。 映射映射f的定義域是集合的定義域是集合A,記為記為dom f =A； 對于任意對于任意xA,對應(yīng)于對應(yīng)于B中唯一的元素中唯一的元素f(x),x為為f的自的自變量變量(也稱為原像也稱為原像),f(x)稱為稱為x在映射在映射f下的像下的像,通常記為通常記為y= f(x).映射的表示映射的

17、表示（1）解析表達式）解析表達式（2）圖示）圖示（3）表格法）表格法B BA A （讀作（讀作B B上上A A）定義）定義.:|BAffBA定理：定理： 對于集合對于集合A和和B，若，若|A|=m，|B|=n，則，則|BA|=nm。教材教材P7例題例題1-51.2.2 映射的性質(zhì)映射的性質(zhì)1、單射、單射 假設(shè)假設(shè)f :AB,如果對任意如果對任意x1,x2 A,由由f(x1) = f(x2) 可推出可推出x1=x2,則稱則稱f是是A到到B的單射的單射,或稱或稱f是是A到到B的一對一映射。的一對一映射。fBA.)()(,212121xxxfxfAxx).()(,212121xfxfxxAxx例：設(shè)

18、例：設(shè)f f:NN:NN，f f(x)=2x,(x)=2x,則則f f是是N N到到N N的單射，試證明之。的單射，試證明之。1.2.2 映射的性質(zhì)映射的性質(zhì)2、滿射、滿射假設(shè)假設(shè)f :AB，如果對任意，如果對任意y B,均存在均存在x A，使，使得得y = f(x)，則稱，則稱f是是A到到B的滿射，或稱的滿射，或稱f是是A到到B的映上的映上(onto)的映射。的映射。fBA例：例：設(shè)設(shè)f:ZN, f(x)=|x|, f:ZN, f(x)=|x|, 則則f f是是Z Z到到N N的滿射。的滿射。1.2.2 映射的性質(zhì)映射的性質(zhì)3、雙射、雙射假設(shè)假設(shè)f :AB，f 既是單射又是滿射，則稱既是單射

19、又是滿射，則稱f是是A到到B的的雙射雙射,或稱或稱f 是是A到到B的一的一 一對應(yīng)。一對應(yīng)。fBA例：試建立一個例：試建立一個Z到到N的一的一一對應(yīng)。一對應(yīng)。 2x x0f(x) = 2|x| - 1 x0 習題習題1.2 (2)1.2 (2)置換的定義置換的定義例如：寫出例如：寫出A=1，2，3上的所有置換。上的所有置換。(個數(shù)：個數(shù)：n!),3213211p,3123212p,1233213p,2313214p,1323215p.2133216p123(1)(2)(3)pppp1.2.3 逆映射逆映射 ，則，則1.2.4 復合映射復合映射xy=f(x)z=g(y)=g(f(x)hfg1.2

20、.4 復合映射復合映射abc123 fg復合映射例題復合映射例題f f( (A A) ) dom(dom(g g) )例例2 2：設(shè)設(shè)R R到到R R有兩個映射有兩個映射f f和和g g，定義如下：，定義如下：f(x) = f(x) = x x2 2,g(x) = x + 2,g(x) = x + 2，分別計算復合映射，分別計算復合映射和和 恒等映射恒等映射 設(shè)設(shè)A A是集合，令是集合，令f f: A: AA, A, f f( (x x) = ) = x x，稱稱f f為集合為集合A A上的恒等映射上的恒等映射(identity (identity function on A)function

21、 on A)，記為，記為IA 顯然恒等映射是唯一存在的。顯然恒等映射是唯一存在的。【定理定理1-9】若若f: : A A B B是雙射，則有是雙射，則有f f-1 = IA，f-1 f = I B. .特別地，若特別地，若f: : A A A A是雙射，則是雙射，則f f-1= f-1 f = IA 復合映射性質(zhì)復合映射性質(zhì)【定理定理1-10】設(shè)設(shè)f: : A A B B , , g: : B B C C ，(1)若若 f 和和 g 是單射是單射, 則則 f g是單射是單射.(2)若若 f 和和 g 是滿射是滿射, 則則 f g 是滿射是滿射.(3)若若 f 和和 g 是雙射是雙射, 則則 f

22、 g 是雙射是雙射.【定理定理1-11】設(shè)設(shè)f: : A A B B , , g: : B B C C ，(1) 若若f g是單射是單射, 則則f是單射是單射, g不一定不一定.(2) 若若f g是滿射是滿射, 則則g是滿射是滿射, f 不一定不一定.(3) 若若f g是雙射是雙射, 則則f是單射且是單射且g是滿射是滿射.【定理定理1-12】設(shè)設(shè)f: : A A B B , , g: : B B C C ，h: : C C D D，則則( (f g) h = f (g h)1.3 運算的定義及性質(zhì)運算的定義及性質(zhì) 運算是由已知對象得出新對象的一種運算是由已知對象得出新對象的一種方法。運算是討論

23、對象之間有何聯(lián)系的一方法。運算是討論對象之間有何聯(lián)系的一種方法。種方法。 運算本質(zhì)上是映射，但運算更側(cè)重于運算本質(zhì)上是映射，但運算更側(cè)重于研究運算滿足的一些運算性質(zhì)。研究運算滿足的一些運算性質(zhì)。 1.3.1 運算的定義運算的定義 設(shè)設(shè)A1 , A2 , , An和和B是集合，若是集合，若 f: A1 A2 AnB 則稱則稱f為為A1 , A2 , , An到到B的的n元運算。在不需元運算。在不需要強調(diào)集合要強調(diào)集合A1 , A2 , , An和和B時，可以簡稱時，可以簡稱f為為運算運算， f: AAAB稱稱f為為A到到B的的n元運算，或稱元運算，或稱f f為為A上的上的n元運算。元運算。 如如

24、y = f(xy = f(x1 1,x,x2 2,x,xn n) )中，中， x x1 1,x,x2 2,x,xn n是參加運是參加運算的算的n n個有順序的對象，個有順序的對象，f f稱為稱為n n元運算，元運算，y y是運算結(jié)果，是運算結(jié)果，由定義知道：由定義知道：運算結(jié)果一定是唯一的運算結(jié)果一定是唯一的。運算的特征運算的特征1 1、封閉運算封閉運算：若對于：若對于x x1 1 , x , x2 2 , , x , , xn n A A，有有f f(x(x1 1 , x , x2 2 , , x , , xn n) = y) = y A A，則稱，則稱f f為為A A上的上的n n元封閉運

25、算元封閉運算(closed operation)(closed operation)，或稱，或稱為為A A上的上的n n元代數(shù)運算。元代數(shù)運算。習題習題1.3(1)(2)1.3(1)(2)2 2、運算符號的選取運算符號的選取：常用符號和定義符號：常用符號和定義符號3 3、運算符號的位置運算符號的位置：前面、中間和后面：前面、中間和后面4 4、運算表運算表：方便直觀：方便直觀運算的例題運算的例題例例1 （絕對值運算絕對值運算） f: Z N, f(x) = |x|. （一元運算）（一元運算） 例例2 (模運算模運算) f: Z N, f(x) = x(mod k), 例例3（模（模m加法運算和模

26、加法運算和模m乘法運算）乘法運算）例例4（最大公（最大公因因數(shù)數(shù)gcd和最小公倍數(shù)和最小公倍數(shù)lcm）1.3.2 運算的性質(zhì)運算的性質(zhì)1、對合性、對合性【定義定義】設(shè)設(shè)*是是A上的上的1元代數(shù)運算，若對于元代數(shù)運算，若對于x x A A ，均有均有 *(*x) = x 則稱則稱*具有對合性，或稱具有對合性，或稱*滿足對合律滿足對合律例例1-20實數(shù)集上的取反數(shù)運算實數(shù)集上的取反數(shù)運算“”具有對合性，具有對合性，而其上的絕對值運算而其上的絕對值運算|不具有對合性。矩陣的逆運算不具有對合性。矩陣的逆運算及轉(zhuǎn)置運算具有對合性，因為及轉(zhuǎn)置運算具有對合性，因為(A-1)-1 = A并且并且(AT)T =

27、 A1.3.2 運算的性質(zhì)運算的性質(zhì)2 2、冪等性、冪等性【定義定義】設(shè)設(shè) * * 是是A A上的上的2 2元代數(shù)運算，若對于元代數(shù)運算，若對于x x A A ，有有 x x * * x = x x = x 則稱則稱x x為關(guān)于為關(guān)于* *運算的冪等元；若對于任意的運算的冪等元；若對于任意的x x A A，x x均為冪等元，則稱均為冪等元，則稱* *具有冪等性，或稱具有冪等性，或稱* *滿足冪等率。滿足冪等率。例例1 1：設(shè)：設(shè)A = 1,2,3A = 1,2,3，A A上的上的* *運算見表，指運算見表，指出出A A中的冪等元，并判斷是否滿足冪等率？中的冪等元，并判斷是否滿足冪等率？例例2

28、2：正整數(shù)集合：正整數(shù)集合N N+ +上上gcdgcd和和lcmlcm是否冪等率？是否冪等率？例例3 3：實數(shù)集合：實數(shù)集合R R上乘法是否滿足冪等率？上乘法是否滿足冪等率？1.3.2 運算的性質(zhì)運算的性質(zhì)3、交換性、交換性【定義定義】設(shè)設(shè)*是是A上的上的2元代數(shù)運算，若對于任意元代數(shù)運算，若對于任意x,yx,y A A，均有均有 x * y = y * x則稱則稱*具有交換性，或稱具有交換性，或稱*滿足交換律。滿足交換律。例例1 1：驗證整數(shù)集合：驗證整數(shù)集合Z Z上的加法運算和減法運算是否滿足交換上的加法運算和減法運算是否滿足交換律律例例2 2：設(shè)：設(shè)* *是有理數(shù)集合是有理數(shù)集合Q Q上

29、的上的2 2元運算，定義如下：任意元運算，定義如下：任意x x1 1,x,x2 2 Q Q， x x1 1* *x x2 2 = x = x1 1x2x2。證明。證明* *不具有交換性。不具有交換性。例例3 3：說明復合映射是否具有交換性。：說明復合映射是否具有交換性。1.3.2 運算的性質(zhì)運算的性質(zhì)4、結(jié)合性、結(jié)合性【定義定義】設(shè)設(shè) * 是是A上的上的2元代數(shù)運算，若對于元代數(shù)運算，若對于任意的任意的 x,y,zx,y,z A A ，均有，均有 (x * y) * z = x * (y * z)則稱則稱*具有結(jié)合性，或稱具有結(jié)合性，或稱*滿足結(jié)合律。滿足結(jié)合律。 例例1 1：驗證整數(shù)集合：驗

30、證整數(shù)集合Z Z上的加法運上的加法運算和減法運算是否滿足結(jié)合率。算和減法運算是否滿足結(jié)合率。53145534314421213343142254321154321*例例2 2：判定集合：判定集合A=1,2,3,4,5A=1,2,3,4,5見見表，是否滿足交換率和結(jié)合率？表，是否滿足交換率和結(jié)合率？例例3 3：判定映射的復合運算是否：判定映射的復合運算是否滿足結(jié)合率？滿足結(jié)合率？1.3.2 運算的性質(zhì)運算的性質(zhì)5、單位元素、單位元素【定義定義】設(shè)設(shè) * 是是A上的上的2元代數(shù)運算，若存在元代數(shù)運算，若存在e e A A ，對于任意的對于任意的x x A A ，下列條件均成立：，下列條件均成立：

31、e * x = x x * e = x則稱則稱e為集合為集合A關(guān)于關(guān)于*運算的單位元素或幺元素。運算的單位元素或幺元素。 例例1 1：驗證整數(shù)集合：驗證整數(shù)集合Z Z關(guān)于加法運算關(guān)于加法運算+ +的單位元素為的單位元素為0 0，而，而Z Z關(guān)于關(guān)于乘法運算的單位元素為乘法運算的單位元素為1 1，Z Z關(guān)于減法運算沒有單位元素。關(guān)于減法運算沒有單位元素。定理：若定理：若A A關(guān)于關(guān)于* *運算有單位元素，則單位元素是唯一的。運算有單位元素，則單位元素是唯一的。1.3.2 運算的性質(zhì)運算的性質(zhì)6 6、零元素、零元素【定義定義】設(shè)設(shè) * * 是是A A上的上的2 2元代數(shù)運算，若存在元代數(shù)運算，若存

32、在 A A ，對于任意的對于任意的x x A A ，下列條件均成立：，下列條件均成立： * x = x * = 則稱為集合則稱為集合A A關(guān)于關(guān)于* *運算的零元素。運算的零元素。例例1 1：驗證整數(shù)集合：驗證整數(shù)集合Z Z關(guān)于加法運算關(guān)于加法運算+ +和減法運算和減法運算- -均沒有零元均沒有零元素。素。Z Z關(guān)于乘法運算的零元素為關(guān)于乘法運算的零元素為0 0。1.3.2 運算的性質(zhì)運算的性質(zhì)7 7、逆元素、逆元素【定義定義1-211-21】設(shè)設(shè) * * 是是A A上的上的2 2元代數(shù)運算且有單位元元代數(shù)運算且有單位元素素e e，若對于，若對于x x A A，存在，存在y y A A，下列條

33、件均成立：下列條件均成立： y * x = e x * y = e則稱則稱y y為為x x的逆元素。的逆元素。注意：注意： 1 1、一個方陣關(guān)于乘法運算的逆元是其逆矩陣，、一個方陣關(guān)于乘法運算的逆元是其逆矩陣，單位元素是單位矩陣；單位元素是單位矩陣； 2 2、一個雙射的映射的復合運算的逆元是其逆映、一個雙射的映射的復合運算的逆元是其逆映射。單位元素是恒等映射。射。單位元素是恒等映射。1.3.2 運算的性質(zhì)運算的性質(zhì)例例1 1：分別考察：實數(shù)集合：分別考察：實數(shù)集合R R中各元素關(guān)于加法運算和中各元素關(guān)于加法運算和乘法運算的逆元素。乘法運算的逆元素。例例2 2：設(shè)：設(shè)A=a, b, c,A=a,

34、 b, c,關(guān)于關(guān)于* *運算的運算表。分析逆元。運算的運算表。分析逆元。 結(jié)論：一個元素的逆元不一定存在，存在也不一結(jié)論：一個元素的逆元不一定存在，存在也不一定唯一。定唯一。習題習題1.3(8)1.3(8)caccaabbcbaacba*【定理】設(shè)【定理】設(shè)A A關(guān)于關(guān)于* *運算的單位元素為運算的單位元素為e e且且* *運算滿足結(jié)合律，若運算滿足結(jié)合律，若x x在在A A中有左逆中有左逆元元y y及右逆元及右逆元z z，則，則y = zy = z。進而，對于。進而，對于一個滿足結(jié)合律的運算來說，若一個元一個滿足結(jié)合律的運算來說，若一個元素有逆元則其逆元是唯一的。素有逆元則其逆元是唯一的。

35、 1.3.2 運算的性質(zhì)運算的性質(zhì)8 8、消去性、消去性【定義定義1-221-22】設(shè)設(shè) * * 是是A A上的上的2 2元代數(shù)運算，若元代數(shù)運算，若A A關(guān)于關(guān)于* *運算有零元素，如果對于任意運算有零元素，如果對于任意x,y,zx,y,z A A ，只要，只要xx ，則下列條件均成立：，則下列條件均成立： x x * * y = x y = x * * z y = z z y = z y y * * x = z x = z * * x y = z x y = z則稱則稱* *具有消去性，或稱具有消去性，或稱* *滿足消去律。滿足消去律。例：驗證整數(shù)集合例：驗證整數(shù)集合Z Z上的加法運算上的

36、加法運算+ +和乘法運算均滿和乘法運算均滿足消去律。足消去律。1.3.2 運算的性質(zhì)運算的性質(zhì)9 9、分配性、分配性【定義【定義1-231-23】設(shè)】設(shè) * *和和 是是A A上的上的2 2元代數(shù)運算，若對元代數(shù)運算，若對于任意于任意x,y,zx,y,z A A ，下列條件均成立：，下列條件均成立： x x * * (y (y z) = (x ) = (x * * y) y) (x (x * * z) z) (y (y z) ) * * x = (y x = (y * * x) x) (z (z * * x) x)則稱則稱* *運算對運算對 運算具有分配性，或稱滿足分配律。運算具有分配性，或稱

37、滿足分配律。注意：當注意：當* *運算滿足交換性時，條件之一成立即可。運算滿足交換性時，條件之一成立即可。例：實數(shù)集合例：實數(shù)集合R上的乘法運算對加法運算可分配。上的乘法運算對加法運算可分配。1.3.2 運算的性質(zhì)運算的性質(zhì)1010、吸收性、吸收性【定義【定義1-241-24】設(shè)】設(shè) * * 和和 是是A A上的兩個上的兩個2 2元代數(shù)運算，元代數(shù)運算，若對于若對于x,yx,y A A ，下列條件均成立：，下列條件均成立： x x * * (x (x y) = x) = x (y (y x) ) * * x = x x = x則稱則稱* *運算對運算運算對運算 可吸收?？晌?。注意：當注意：當

38、* *和和 運算滿足交換性，以上公式之一運算滿足交換性，以上公式之一成立即可。成立即可。1.3.2 運算的性質(zhì)運算的性質(zhì)1111、德、德摩根（摩根（De MorganDe Morgan）律）律 【定義定義】設(shè)設(shè)是集合是集合A A上的上的1 1元代數(shù)運算，元代數(shù)運算， * * 和和 是是A A上的兩個上的兩個2 2元代數(shù)運算，若對于元代數(shù)運算，若對于x,yx,y A A ，下列條件，下列條件均成立：均成立： (x * y) = (x) (y) (x y) = (x) *(y)則稱這三種運算滿足則稱這三種運算滿足De MorganDe Morgan律律 1.4 集合的運算集合的運算1、并運算、并運

39、算2、交運算、交運算3、補運算、補運算4、差運算、差運算5、對稱差運算、對稱差運算1.4.1 并運算并運算【定義】設(shè)【定義】設(shè)A A和和B B是兩個任意集合，由所有屬于是兩個任意集合，由所有屬于A A或?qū)倩驅(qū)儆谟贐 B的元素組成的集合稱為集合的元素組成的集合稱為集合A A和和B B的并集，通常記的并集，通常記作作ABAB。即：。即：AB=AB=x x| |x x A A或或x x BB陰影部分為陰影部分為ABABU U B BA A如：設(shè)如：設(shè) A=a，b，c，d，B=b，d，e，f，求求ABAB定理：設(shè)定理：設(shè)A A和和B B是集合，則是集合，則ABAB是包含集合是包含集合A A和和B B的

40、最小集合。的最小集合。并運算的性質(zhì)并運算的性質(zhì)設(shè)設(shè)A A，B B，C C是集合，則是集合，則1 1、冪等律：、冪等律：AA = AAA = A2 2、交換律：、交換律：AB = BAAB = BA3 3、結(jié)合律：、結(jié)合律：(AB)C=A(BC)(AB)C=A(BC)4 4、A=AA=A= =A(A(空集空集是并運算的單位元素是并運算的單位元素) )5 5、UA=AU=U(UA=AU=U(全集全集U U是并運算的零元素是并運算的零元素) )1.4.2 交運算交運算【定義】設(shè)【定義】設(shè)A A和和B B是兩個任意集合，由所有屬于是兩個任意集合，由所有屬于A A又屬又屬于于B B的元素組成的集合，稱為

41、的元素組成的集合，稱為A A和和B B的交集，通常記作的交集，通常記作ABAB。即。即AB=AB=x x| |x x A A且且x x BB陰影部分為陰影部分為ABABU U B BA A如：設(shè)如：設(shè) A=a，b，c，d，B=b，d，e，f，求求A AB B定理：設(shè)定理：設(shè)A A和和B B是集合，則是集合，則A AB B是包含在集合是包含在集合A A和和B B中的最大集合。中的最大集合。交運算的性質(zhì)交運算的性質(zhì)設(shè)設(shè)A A，B B，C C是集合，則是集合，則1 1、冪等律：冪等律：AA=AAA=A2 2、交換律：、交換律：AB= BAAB= BA3 3、結(jié)合律：、結(jié)合律：(AB)C=A (BC)

42、(AB)C=A (BC)4 4、A=AA=A= =（空集（空集是交運算的零元素是交運算的零元素）5 5、UA=AU=AUA=AU=A（全集（全集U U是交運算的單位元素）是交運算的單位元素）交和并運算的性質(zhì)交和并運算的性質(zhì)并、交運算的混合性質(zhì)并、交運算的混合性質(zhì)( (吸收律吸收律) )： 設(shè)設(shè)A A，B B，C C是集合，則是集合，則（1）對對可吸收：可吸收：AA(AB)= A （2）對對可吸收：可吸收：AA(AB)= A （3）對對可分配：可分配：AA(BC)= (AB)(AC) （4）對對可分配：可分配：AA(BC)= (AB)(AC) 1.4.3 補運算補運算【定義定義】設(shè)設(shè)U U是全集

43、，對于集合是全集，對于集合A A，定義，定義A A的補集如下：的補集如下： =x|x=x|x U U，但，但x x A A 注意：一個集合的補集依賴于全集的選取。注意：一個集合的補集依賴于全集的選取。A陰影部分為陰影部分為A A的補集的補集U UA A例：設(shè)集合例：設(shè)集合A=a , b , c分別取全集分別取全集U=a , b , c , d和和U=a , b , c , a , b , b , c , c , 求求A的補集。的補集。補運算的性質(zhì)補運算的性質(zhì)補運算的性質(zhì)：補運算的性質(zhì)： （1）A =U （2）A = De Morgan律律AAABAB BABA1.4.4 差運算差運算【定義】設(shè)

44、【定義】設(shè)A A和和B B是兩個任意集合，是兩個任意集合，由所有屬于由所有屬于A A但不但不屬于屬于B B的元素組成的集合稱為的元素組成的集合稱為A A和和B B的差集的差集，通常記作，通常記作A-BA-B。即。即A-B=x|xA-B=x|x A A且且x x BBU UA AB B陰 影 部 分陰 影 部 分為為A-BA-B如：設(shè)如：設(shè) A=a，b，c，d，B=b，d，e，f，求求A-BA-B和和B-AB-A差運算的性質(zhì)差運算的性質(zhì)（1 1）A-A = A-A = （2 2）A-A- = A = A（3 3）A-U = A-U = 定理：對于集合定理：對于集合A , BA , B，有，有A

45、A B = AB B = AB1.4.5 對稱差運算對稱差運算【定義】設(shè)【定義】設(shè)A A和和B B是兩個任意集合，是兩個任意集合，由所有屬于由所有屬于A A但不但不屬于屬于B B或者屬于或者屬于B B但不屬于但不屬于A A的元素構(gòu)成的集合稱為對的元素構(gòu)成的集合稱為對稱差運算也可稱為環(huán)和運算稱差運算也可稱為環(huán)和運算 ，通常記作，通常記作A A B B。即。即A A B =B =（A-BA-B） （B-AB-A）A A B =B =（A AB B）- -（BABA）U UA AB B陰影部分為陰影部分為A A B B如：設(shè)如：設(shè) A=a，b，c，d，B=b，d，e，f，求求A A B B對稱差的性質(zhì)對稱差的性質(zhì)（1 1）A A B = B B = B A A（2 2）A A = A = A（3 3）A A A = A = （4 4）（）（A A B B） C = A C = A （B B C C）