第1章集合、映射與運(yùn)算2015

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

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

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

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

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

6、算及關(guān)系是貫穿于本書的一條主線.1.1.1 集合集合 集合（set）:是指具有某種特定性質(zhì)的對象匯集成的一個整體。元素（element）：集合中的每一個對象稱為集合的元素。通常用大寫字母表示集合，用小寫字母表示集合中的元素。 在數(shù)學(xué)中常用 表示整體.在討論集合時，為避免出現(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ù)集合；實(shí)數(shù)集合；nC 復(fù)數(shù)集合復(fù)數(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元音集合的表示集合的表示 遞歸法遞歸法 是指通過計(jì)算規(guī)則定義集合中的元素。首先給出該集合的初始元素；然后給出由集合中已知元素構(gòu)造其他元素的方法；最后強(qiáng)調(diào)有限次使用前面的步驟得到的元素是集合中僅有的元素。如：設(shè)a0=1,a1=1,an+1=an+an-1, A=a0,a1,a2,=akk0。 集合的表示集合的表示 巴科斯范式巴科斯范式(BNF)表示法表示法 BNF常用來定義高級程序設(shè)計(jì)語言的標(biāo)識符或表達(dá)式集合。 文氏圖法文氏圖法(John Venn) 首先畫一個大矩形表

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

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() = ) = , , .習(xí)題習(xí)題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ù)學(xué)中的基本概念。函數(shù)映射是現(xiàn)代數(shù)學(xué)中的基本概念。函數(shù)在信息科學(xué)中得到了充分的應(yīng)用。在信息科學(xué)中得到了充分的應(yīng)用。 與集合一樣，映射貫穿本書的所有內(nèi)與集合一樣，映射貫穿本書的所有內(nèi)容，深刻理解映射的有關(guān)內(nèi)容，對于其他容，深刻理解映射的有關(guān)內(nèi)容，對于其他內(nèi)容的學(xué)習(xí)是至關(guān)重要的。內(nèi)容的學(xué)習(xí)是至關(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:映射的兩個特點(diǎn)映射的兩個特點(diǎn) 假定假定 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）解析表達(dá)式）解析表達(dá)式（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 習(xí)題習(xí)題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 復(fù)合映射復(fù)合映射xy=f(x)z=g(y)=g(f(x)hfg1.2

20、.4 復(fù)合映射復(fù)合映射abc123 fg復(fù)合映射例題復(fù)合映射例題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，分別計(jì)算復(fù)合映射，分別計(jì)算復(fù)合映射和和 恒等映射恒等映射 設(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 顯然恒等映射是唯一存在的。顯然恒等映射是唯一存在的?！径ɡ矶ɡ?-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 復(fù)合映射性質(zhì)復(fù)合映射性質(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 運(yùn)算的定義及性質(zhì)運(yùn)算的定義及性質(zhì) 運(yùn)算是由已知對象得出新對象的一種運(yùn)算是由已知對象得出新對象的一種方法。運(yùn)算是討論

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

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

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

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

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

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

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

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

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

32、在 A A ，對于任意的對于任意的x x A A ，下列條件均成立：，下列條件均成立： * x = x * = 則稱為集合則稱為集合A A關(guān)于關(guān)于* *運(yùn)算的零元素。運(yùn)算的零元素。例例1 1：驗(yàn)證整數(shù)集合：驗(yàn)證整數(shù)集合Z Z關(guān)于加法運(yùn)算關(guān)于加法運(yùn)算+ +和減法運(yùn)算和減法運(yùn)算- -均沒有零元均沒有零元素。素。Z Z關(guān)于乘法運(yùn)算的零元素為關(guān)于乘法運(yùn)算的零元素為0 0。1.3.2 運(yùn)算的性質(zhì)運(yùn)算的性質(zhì)7 7、逆元素、逆元素【定義定義1-211-21】設(shè)設(shè) * * 是是A A上的上的2 2元代數(shù)運(yùn)算且有單位元元代數(shù)運(yùn)算且有單位元素素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)于乘法運(yùn)算的逆元是其逆矩陣，、一個方陣關(guān)于乘法運(yùn)算的逆元是其逆矩陣，單位元素是單位矩陣；單位元素是單位矩陣； 2 2、一個雙射的映射的復(fù)合運(yùn)算的逆元是其逆映、一個雙射的映射的復(fù)合運(yùn)算的逆元是其逆映射。單位元素是恒等映射。射。單位元素是恒等映射。1.3.2 運(yùn)算的性質(zhì)運(yùn)算的性質(zhì)例例1 1：分別考察：實(shí)數(shù)集合：分別考察：實(shí)數(shù)集合R R中各元素關(guān)于加法運(yùn)算和中各元素關(guān)于加法運(yùn)算和乘法運(yùn)算的逆元素。乘法運(yùn)算的逆元素。例例2 2：設(shè)：設(shè)A=a, b, c,A=a,

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

35、 1.3.2 運(yùn)算的性質(zhì)運(yùn)算的性質(zhì)8 8、消去性、消去性【定義定義1-221-22】設(shè)設(shè) * * 是是A A上的上的2 2元代數(shù)運(yùn)算，若元代數(shù)運(yùn)算，若A A關(guān)于關(guān)于* *運(yùn)算有零元素，如果對于任意運(yù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則稱則稱* *具有消去性，或稱具有消去性，或稱* *滿足消去律。滿足消去律。例：驗(yàn)證整數(shù)集合例：驗(yàn)證整數(shù)集合Z Z上的加法運(yùn)算上的

36、加法運(yùn)算+ +和乘法運(yùn)算均滿和乘法運(yùn)算均滿足消去律。足消去律。1.3.2 運(yùn)算的性質(zhì)運(yùn)算的性質(zhì)9 9、分配性、分配性【定義【定義1-231-23】設(shè)】設(shè) * *和和 是是A A上的上的2 2元代數(shù)運(yùn)算，若對元代數(shù)運(yùn)算，若對于任意于任意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)則稱則稱* *運(yùn)算對運(yùn)算對 運(yùn)算具有分配性，或稱滿足分配律。運(yùn)算具有分配性，或稱

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

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

39、算2、交運(yùn)算、交運(yùn)算3、補(bǔ)運(yùn)算、補(bǔ)運(yùn)算4、差運(yùn)算、差運(yùn)算5、對稱差運(yùn)算、對稱差運(yùn)算1.4.1 并運(yùn)算并運(yùn)算【定義】設(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、最小集合。的最小集合。并運(yùn)算的性質(zhì)并運(yùn)算的性質(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(空集空集是并運(yùn)算的單位元素是并運(yùn)算的單位元素) )5 5、UA=AU=U(UA=AU=U(全集全集U U是并運(yùn)算的零元素是并運(yùn)算的零元素) )1.4.2 交運(yùn)算交運(yùn)算【定義】設(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中的最大集合。中的最大集合。交運(yùn)算的性質(zhì)交運(yùn)算的性質(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= =（空集（空集是交運(yùn)算的零元素是交運(yùn)算的零元素）5 5、UA=AU=AUA=AU=A（全集（全集U U是交運(yùn)算的單位元素）是交運(yùn)算的單位元素）交和并運(yùn)算的性質(zhì)交和并運(yùn)算的性質(zhì)并、交運(yùn)算的混合性質(zhì)并、交運(yùn)算的混合性質(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 補(bǔ)運(yùn)算補(bǔ)運(yùn)算【定義定義】設(shè)設(shè)U U是全集

43、，對于集合是全集，對于集合A A，定義，定義A A的補(bǔ)集如下：的補(bǔ)集如下： =x|x=x|x U U，但，但x x A A 注意：一個集合的補(bǔ)集依賴于全集的選取。注意：一個集合的補(bǔ)集依賴于全集的選取。A陰影部分為陰影部分為A A的補(bǔ)集的補(bǔ)集U UA A例：設(shè)集合例：設(shè)集合A=a , b , c分別取全集分別取全集U=a , b , c , d和和U=a , b , c , a , b , b , c , c , 求求A的補(bǔ)集。的補(bǔ)集。補(bǔ)運(yùn)算的性質(zhì)補(bǔ)運(yùn)算的性質(zhì)補(bǔ)運(yùn)算的性質(zhì)：補(bǔ)運(yùn)算的性質(zhì)： （1）A =U （2）A = De Morgan律律AAABAB BABA1.4.4 差運(yùn)算差運(yùn)算【定義】設(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差運(yùn)算的性質(zhì)差運(yùn)算的性質(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 對稱差運(yùn)算對稱差運(yùn)算【定義】設(shè)【定義】設(shè)A A和和B B是兩個任意集合，是兩個任意集合，由所有屬于由所有屬于A A但不但不屬于屬于B B或者屬于或者屬于B B但不屬于但不屬于A A的元素構(gòu)成的集合稱為對的元素構(gòu)成的集合稱為對稱差運(yùn)算也可稱為環(huán)和運(yùn)算稱差運(yùn)算也可稱為環(huán)和運(yù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）