離散數(shù)學(xué) 第三章 集合

1、1西安交通大學(xué)西安交通大學(xué)電子與信息工程學(xué)院電子與信息工程學(xué)院計算機軟件所計算機軟件所劉國榮劉國榮2離散數(shù)學(xué) 目目 標(biāo)標(biāo) 掌握集合論掌握集合論、代數(shù)系統(tǒng)、布爾代數(shù)、圖論、代數(shù)系統(tǒng)、布爾代數(shù)、圖論的基本思想和方法，提高用的基本思想和方法，提高用集合論集合論、代數(shù)系、代數(shù)系統(tǒng)、布爾代數(shù)、圖論的思想和方法分析問題統(tǒng)、布爾代數(shù)、圖論的思想和方法分析問題和解決問題的能力。和解決問題的能力。3離散數(shù)學(xué) 目目 錄錄w 序言序言w 第三章集合第三章集合w 第四章關(guān)系第四章關(guān)系w 第五章函數(shù)第五章函數(shù)w 第六章代數(shù)系統(tǒng)第六章代數(shù)系統(tǒng)w 第七章格與布爾系統(tǒng)第七章格與布爾系統(tǒng)w 第八章圖論第八章圖論4離散數(shù)學(xué)Dis

2、crete Mathematics5離散數(shù)學(xué)w 敘述恰當(dāng)嚴(yán)謹(jǐn)，論證詳盡嚴(yán)密，內(nèi)容新穎豐富是本課程的特點。w 離散數(shù)學(xué)具有抽象性、非線性、非尋繹性、構(gòu)造性、結(jié)構(gòu)性、整體性等結(jié)構(gòu)性數(shù)學(xué)特點。w 證明方法除了大量的運用常用的（數(shù)學(xué)）歸納法、演繹法、反證法、歸謬法、二難法、二分法、枚舉法（窮舉法）、相容排斥法等方法之外，特別著重于存在性、結(jié)構(gòu)性、構(gòu)造性方法，以及各部分內(nèi)容自己所特有的方法（比如圖論的刪點增點方法、刪邊增邊方法、伸路蹦圈方法）。6離散數(shù)學(xué)w集合論在計算機科學(xué)中的應(yīng)用集合論在計算機科學(xué)中的應(yīng)用 集合論包括集合關(guān)系和函數(shù)3部分 1)集合集合 集合不僅可以表示數(shù)，而且可以像數(shù)一樣進(jìn)行運算，還可

3、以用于非數(shù)值信息的表示和處理，如數(shù)據(jù)的增加、刪除、排序以及數(shù)據(jù)間關(guān)系的描述，有些很難用傳統(tǒng)的數(shù)值計算來處理的問題，卻可以用集合來處理。因此，集合論在程序語言、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫與知識庫、形式語言和人工智能等領(lǐng)域得到了廣泛的應(yīng)用。 2)關(guān)系關(guān)系 關(guān)系也廣泛地應(yīng)用于計算機科學(xué)技術(shù)中，例如計算機程序的輸入和輸出關(guān)系、數(shù)據(jù)庫的數(shù)據(jù)特性關(guān)系和計算機語言的字符關(guān)系等，是數(shù)據(jù)結(jié)構(gòu)、情報檢索、數(shù)據(jù)庫、算法分析、計算機理論等計算機領(lǐng)域中的良好數(shù)據(jù)工具。另外， 關(guān)系中劃分等價類的思想也可用7離散數(shù)學(xué)于求網(wǎng)絡(luò)的最小生成樹等圖的算法中。 3)函數(shù)函數(shù) 函數(shù)可以看成是一種特殊的關(guān)系，計算機中把輸入、輸出間的關(guān)系看成是一種

4、函數(shù)。類似地，在開關(guān)理論、自動機原理和可計算性理論等領(lǐng)域中，函數(shù)都有極其廣泛的應(yīng)用，其中雙射函數(shù)是密碼學(xué)中的重要工具。8 集合集合全集全集空集空集單元素集單元素集子集子集冪集冪集交交集集并集并集余集余集差集差集環(huán)和集環(huán)和集環(huán)積環(huán)積集集9離散數(shù)學(xué) 第三章集合第三章集合 (set)(set) .集合理論中的一些基本概念集合理論中的一些基本概念 個體與集合之間的關(guān)系個體與集合之間的關(guān)系 集合的表示法集合的表示法 集合與集合之間的關(guān)系集合與集合之間的關(guān)系 冪集冪集 2 .集合代數(shù)集合的基本運算集合代數(shù)集合的基本運算 集合的補運算集合的補運算 集合的交運算和并運算集合的交運算和并運算 集合的宏運算集合的

5、宏運算10離散數(shù)學(xué) 第三章集合第三章集合 (set) .集合理論中的一些基本概念集合理論中的一些基本概念 集合概念將作為一個不言自明的元概念（基本概念）。它不能用別的術(shù)語來精確的定義，只能用別的術(shù)語來加以說明。它本身就是用來定義其它概念的概念。我們來看看一些關(guān)于什么是集合的各種不同的說法，以便加深對集合這個元概念的理解。1. 莫斯科大學(xué)的那湯松教授說： 凡具有某種特殊性質(zhì)某種特殊性質(zhì)的對象對象的匯集匯集稱之為集。 2. 復(fù)旦大學(xué)的陳建功教授說： 凡可供吾人思維的，不論它有形或無形，都叫做物物。具有某種條件某種條件的物，稱它們的全部全部謂之一集。 3. 南開大學(xué)的楊宗磐教授說： 11離散數(shù)學(xué) 集

6、就是“烏合烏合之眾眾”。不考慮怎樣“烏合烏合”起來的，眾可以具體可以具體，可以抽象可以抽象。這種烏合性被歸納為集合的一條性質(zhì) 任意性：任意性：任意性是說組成集合的元素任意； 構(gòu)成的法則任意； 什么都可以構(gòu)成集合，不加任何限制。任意性是集合的四大性質(zhì)之一。4. 集合論之父G.Cantor（1845-1918）說： 集合是由總括總括某些個體個體成一個整體而成的。對于每個個體，只設(shè)其為可思考的對象，辨別它的異同可思考的對象，辨別它的異同。個體之間并不需要有任何關(guān)系。12離散數(shù)學(xué) 因此，對于集合，我們接受以下事實： (a)承認(rèn)集合的存在性。即，接受集合概念； (b)承認(rèn)集合是由一些個體（對象）組成的。

7、這些個體稱為該集合的成員或元素（member,element）； (c )承認(rèn)個體是可辯認(rèn)的。即，一個個體要么是一個集合的成員，要么不是；二者必居其一，也只居其一。這種存在性，可辯認(rèn)性被歸納為集合的一條性質(zhì) 確定性：確定性：確定性是說集合確定； 個體確定； 集合與個體之間的關(guān)系確定。 因此，經(jīng)典集合的邊界是分明的、清晰的。確定性是集合的四大性質(zhì)之一。13離散數(shù)學(xué) 綜上所述集合的概念有三要素： 1. 個體（元素） 2. 個體的可辨認(rèn)性 3. 集合（動詞，匯到一塊）w 通常用小寫拉丁字母表示個體：a、b、c、d、w 通常用大寫拉丁字母表示集合：A、B、C、D、w 有時還用德文花寫字母表示集合： ,

8、 , , , , , w 關(guān)于個體的辨認(rèn)有賴于各方面公認(rèn)的知識。一一.個體與集合之間的關(guān)系：個體與集合之間的關(guān)系：個體與集合之間的關(guān)系稱為屬于關(guān)系屬于關(guān)系。對于某個個體 a 和某個集合 A 而言， 只有兩種可能： (1)a 屬于（belong to） A，記為 aA（記號 是希臘字i的第一個字母，意思是“是”。由意大利數(shù)學(xué)家G.Peano首先采用），同時稱 a 是 A 的元素或A14離散數(shù)學(xué)的成員。 (2)a 不屬于 A，記為 aA或aA ，稱 a 不是 A 的元素或a 不是 A 的成員。 w 判斷個體 a 屬于 A 還是不屬于 A ，必須使用個體的可辨認(rèn)性，而且個體的可辨認(rèn)性是無二義性的，即

9、或者 a 屬于 A 或者 a 不屬于 A，二者居其一且只居其一。AaAaAaAa15離散數(shù)學(xué)w 集合論是一種語言。它可以作為別的學(xué)科的描述工具語言。二二.集合的表示法：集合的表示法： 我們規(guī)定用花括號 表示集合。w (1)文字表示法： 用文字表示集合的元素，兩端加上花括號。 在座的同學(xué) ； 奇數(shù) ； 去年的下雨天 ； 高等數(shù)學(xué)中的積分公式 ； 閉區(qū)間0,1上的連續(xù)函數(shù) ； 比較粗放。比較適合在對集合中的元素了解甚少、不詳，難以用精確的數(shù)學(xué)語言來刻劃時使用。w (2)元素列舉法（羅列法）： 16離散數(shù)學(xué)將集合中的元素逐一列出，兩端加上花括號。 1，2，3，4，5； 風(fēng)，馬，牛 ； 2，4，6，8

10、，10， ； 3，7，11，15，19， ； 比較適合集合中的元素有限（較少或有規(guī)律），無限（離散而有規(guī)律）的情況。w (3)謂詞表示法： x:P(x) 或者 xP(x) 其中：P表示 x 所滿足的性質(zhì)（一元謂詞）。 x : x I （且） x8 =，-3，-2， -1，0，1，2，3，4，5，6 ,7 ；17離散數(shù)學(xué) x: x2 = 1 ； y : y 是開區(qū)間 (a,b) 上的連續(xù)函數(shù) ；（混合表示法） 使 x2 = 1 的實數(shù) = 1，-1 = x : x2 = 1 比較適合在對集合中的元素性質(zhì)了解甚詳，且易于用精確的數(shù)學(xué)語言來刻劃時使用。w 外延外延(extension) ：集合 x:

11、P(x) 稱為性質(zhì)謂詞P(x) 的外延；w 內(nèi)涵內(nèi)涵(intension,connotation)：性質(zhì)謂詞P(x) 稱為集合 x:P(x) 的內(nèi)涵； 由此看到，采用謂詞法定義集合，關(guān)鍵是要得出內(nèi)涵P(x) ，并且顯然有如下的18離散數(shù)學(xué)w 概括原理：概括原理：集合 x:P(x) 恰由那些滿足性質(zhì)謂詞P(x) 的元素組成。即 x x:P(x) (當(dāng)且僅當(dāng)) P(x)真。w 悖論悖論(paradox)： 所謂悖論是指這樣一個所謂的命題P，由P真立即推出P假；由P假立即推出P真；即 P真P假 。w 理發(fā)師悖論：理發(fā)師悖論：某偏遠(yuǎn)小山村僅有一位理發(fā)師。這位理發(fā)師規(guī)定：他只給那些不給自己刮臉的人刮臉。

12、那么要問：這位理發(fā)師的臉由誰來刮？ 如果他給自己刮臉，那么，按他的規(guī)定，他不應(yīng)該給自己刮臉； 如果他不給自己刮臉，那么，按他的規(guī)定，他應(yīng)該給自己刮臉； 19離散數(shù)學(xué)w 羅素悖論羅素悖論(Russell paradox(1902)： 羅素1902年在集合論中也發(fā)現(xiàn)了如下的悖論。他構(gòu)造了這樣一個集合 S= x:xx 然后他提出問題： SS？ 如果SS ，那么，按羅素給S的定義，則應(yīng)有 S S ； 如果S S ，那么，按羅素給S的定義，則應(yīng)有SS ；羅素悖論的發(fā)現(xiàn)，幾乎毀滅集合論，動搖數(shù)學(xué)的基礎(chǔ)，傾危數(shù)學(xué)的大廈。直接引發(fā)了數(shù)學(xué)的第三次危機。20離散數(shù)學(xué) 為了解決集合論中的悖論問題，人們產(chǎn)生了類型論和

13、形式化公理化集合論(ZF和ZFC公理系統(tǒng))，以求排除集合論中的悖論。 近年來，基于ZFC公理系統(tǒng)和一階邏輯(謂詞邏輯) ，人們提出了抽象的計算機程序設(shè)計語言_Z語言語言。 在公理化集合論中，人們引進(jìn)了類(class)的概念。)()()()(不能進(jìn)行運算非集合固有類包含悖論的類可進(jìn)行運算集合類不包含悖論的類類OK21離散數(shù)學(xué) 本章我們所講解的集合論是樸素(naive)集合論；所討論的集合一般也不會產(chǎn)生悖論。三三.集合的名字：集合的名字：(1)大寫的拉丁字母：例如A=x: x =1,B=-1,1；(2)小寫的希臘字母：例如=a,b,c,=n:nN3n；(3)花寫的徳文字母：例如=y:yR0y 1,

14、 =u:u I u+30 ；不夠用時可以加下標(biāo)。同一個集合可以有幾個名字。四四.集合的相等集合的相等（equality） ： 外延性原理：外延性原理：兩個集合相等，當(dāng)且僅當(dāng)，它們的成員完全相同。即 A=B x(xA xB)；22離散數(shù)學(xué)23離散數(shù)學(xué)24離散數(shù)學(xué)X25離散數(shù)學(xué)八八.子集子集（subset）： 對于兩個集合A，B，若A中的每個元素x都是B 的一個元素，則稱A包含在B中（或者說B包含A ），記為AB。同時稱A是B的子集（稱B是A 的超集(superset)）。即 AB x(xA xB) 。w 真子集真子集（proper subset）： 稱A是B的真子集或者說A真包含在B中（或者說B

15、真包含A ），記為AB。即ABX例例.X=a,b,c,d,e,f,A=a,c,d ,B=a, b, c,d 。則 。AB 。26離散數(shù)學(xué) AB ABAB 。 w 子集的兩種特殊情況（平凡子集）： (1)空集（見下面定理2）； (2)每個集合自己（見下面定理1的(1)）；九九.集合與集合之間的關(guān)系集合與集合之間的關(guān)系: 集合與集合之間的關(guān)系有四種。列舉如下 (1)B包含A， AB x(xA xB) ； (2)A包含B， BA x(xB xA)； (3)A等于B， A=B x(xB xA) ABBA ； (4)A與B互不包含， (AB)(BA) x(xAxB)y(yByA) ； 例例.X=a,b,

16、c,d,e,f,A=a,c,d ,B=a, c, d,e 。則 AB 。27離散數(shù)學(xué)定理定理1.設(shè)A,B,C為任意三個集合。那么 (1) 自反性：A A (每個集合是它自己的子集) ； (2) 反對稱性：AB BA A=B ； (3) 傳遞性：AB BC AC ； 這說明包含關(guān)系是集合間的半序關(guān)系(參見第二章6 )。證明.（采用邏輯法）(1) x(xA xA) (同一律： pp ) AA xyX例例.X=a,b,c,d,e,f,A=a,c,d ,B=c, d,e 。則 (AB)(BA)。 即A與B互不包含28離散數(shù)學(xué) 所以包含關(guān)系是自反的； (2)ABBA x(xA xB)x(xB xA) x

17、(xA xB)(xB xA) (量詞對 的分配律： xA(x)xB(x)x(A(x)B(x) ) x(xAxB) A=B 所以包含關(guān)系是反對稱的； (3)ABBC x(xA xB)x(xB xC) x(xA xB) (xB xC) (量詞對 的分配律： xA(x)xB(x)x(A(x)B(x) )29離散數(shù)學(xué) x(xA xC) ( (假言) 三段論原則：(pq)(q r) p r ) AC 所以包含關(guān)系是傳遞的。定理定理2.空集是任一集合的子集。即 A 。證明.(采用邏輯法) x(x） (空集的定義) x (x) x(xxA) (由析取構(gòu)成式及聯(lián)結(jié)詞歸約有： p( p q)(pq) A 。 3

18、0離散數(shù)學(xué)十十.冪集冪集(power set)：定義定義1.冪集 一個集合A的所有子集構(gòu)成的集合稱為A的冪集。記為 2A(或P(A)或 P(A)，即 2A = B ：B A 。顯然， A的兩個平凡子集 和A 都屬于A的冪集。即 2A ，A 2A 。例例1. 若A=1,2,3，則 2A =,1,2,3, 1,2, 1,3, 2,3, 1,2,3。注注：(1) 包含關(guān)系兩邊必須是集合，并且這兩個集合的級別（廣義上）相同； (2)屬于關(guān)系左邊是元素（廣義上） ，右邊是集合，兩邊級別差一級。31離散數(shù)學(xué)定義定義2.基數(shù) 一個有窮集合（有限集合元素個數(shù)有限的集合）A中元素的個數(shù)稱為A的基數(shù)。記為 |A|

19、 (或A，)。 顯然基數(shù)有以下兩個性質(zhì)： (1)齊性： |=0； (2)非負(fù)性： |A|0（對任何集合A ）；另外，由于2= ，所以|2|=1 。 一般地，關(guān)于冪集有以下結(jié)果定理定理3. 若A是有限集合， 則有 | 2A |= 2 |A| 。 這個定理也說明，我們?yōu)槭裁窗岩磺凶蛹瘶?gòu)成的集合稱為冪集。證明.由于集合A有限，故可設(shè)A=a1，a2，an，于是A32離散數(shù)學(xué)| A |=n。A的子集按其基數(shù)大小可分為0，1，2，n共n+1類。 A的所有k個元素的子集（基數(shù)為k的類）為從n個元素中取k個元素的組合數(shù) 。另外，因A，故（按加法原理） | 2A | =1+ + + + = 但由于二項式定理 (

20、x+y)n= xkyn-k 令x=y=1，則有2n = ， 從而，有 | 2A |= 2n = 2 | A | 。knC1nC2nCnnCknC0nknkC0nknkC0nknkC33離散數(shù)學(xué)定理定理4. 若A，B是兩個集合，那么，A=B 2A = 2B。證明. .）：由冪集的定義，顯然； )：一方面， AA (自反性) A2A (因為2AB: :B A ) A2B (充分性條件： 2A 2B) AB (因為2B A: :AB ) 另一方面， B B (自反性) B2B (因為2B A: :AB ) B2A (充分性條件： 2A 2B) BA (因為2A B: :BA) 因此，由包含關(guān)系的反對

21、稱性，得到 AB。34離散數(shù)學(xué) 2 .集合代數(shù)集合的基本運算集合代數(shù)集合的基本運算定義定義1.余(補或非)運算(absolute)complment) 設(shè)X是全集。 一元運算 :2X 2X 對任何集合A X ，使得A= x : xX x A (當(dāng)全集明確時， A =x : x A )稱為集合的余運算。稱A是A關(guān)于X的余集。余運算有時也記為，或 ，或A或A。 AXAA 集合A以外的元素!35離散數(shù)學(xué)例例1.X=a,b,c,d,e,f,A=a,c,d。則 A = b,e,f 。定理定理1.余運算基本定理 設(shè)X是全集，A，B是X的子集。則 (1)反身律(對合律)：(A) =A； (2)換質(zhì)位律（逆否

22、律）；AB B A； (3)A = B A= B ； (4)零壹律：X= ，=X。證明.(采用邏輯法) (1)對任何元素xX， x(A) xA xA 所以 (A) =A ；36離散數(shù)學(xué)(2)對任何元素xX， xB xB xA(條件：AB) xA 所以 B A ； (4)對任何元素x， xX xX x 所以 X= ； 對任何元素x，x x xX (已證 ：X=) xX 所以 =X。37離散數(shù)學(xué)定義定義2.交運算，并運算(intersection,union) 設(shè)X是全集。 (1)二元運算 :2X2X 2X 對任何集合A,BX ，使得 AB = x : xAxB 稱為集合的交運算。稱AB為A與B的

23、交集。 英語讀作cap（帽子）。若AB= ，則稱A與B互不相交(pairwise)disjoint)。 (2)二元運算 :2X2X 2X 對任何集合A,B X ，使得 AB = x : xAxB 稱為集合的并運算。稱AB為A與B的并集。英語讀作cup（酒杯）。 同時屬于集合A和集合B的元素! 至少屬于集合A和集合B之一的元素!38離散數(shù)學(xué)例例2.設(shè)X=a,b,c,d,e,f,A=a,c,d,f,B=b,d,f。則 AB = d,f, AB = a,b,c,d,f。定理定理2.交、并、余運算的基本定理 設(shè)X是全集，A，B，C是X的三個子集。則 (1)冪等律：AA=A， AA=A； (2)互補律：

24、AA = ， AA =X；XXABABABBA39離散數(shù)學(xué) (2)零壹律：AX=A，AX=X ； (全集是交的幺元,并的零元) (2”)零壹律：A = ，A =A； (空集是交的零元,并的幺元) (3)上界：A AB， B AB ； 下界：AB A ， AB B ； (3)上確界： A C B C AB C； (并集AB是同時包含A和B的集合中最小的一個) (3”)下確界：C A C B C AB； (交集AB是同時被A和B所包含的集合中最大的一個) (4)吸收律： A(AB) = A ， A(AB) = A； (5)交換律：AB= BA， AB= BA； 40離散數(shù)學(xué) (6)結(jié)合律：(AB)

25、 C = A (BC)， (AB) C = A (BC) ； (7)分配律：A(B C) = (AB) (AC) ， A(B C) = (AB) (AC) ；證明. (3)(采用邏輯法) 對任何元素xX ， xAB xAxB xCxC (已知條件：AC，BC) xC (冪等律：ppp) 所以，ABC。 (7)先證：A(BC)(AB)(AC) (采用元素法) 對任何元素xX ，若xA(BC)，則xA，且xBC。于是x A，且x B或者xC。 41離散數(shù)學(xué) 若xB，則xA且xB，于是xAB； 若xC，則xA且xC，于是xAC； 綜合xAB或者xAC，因此 x(AB)(AC) ； 所以，A(BC)(

26、AB)(AC) 。次證：(AB)(AC)A(BC)(采用包含法) 由(3)有ABA，ABBBC（逐步放大法）。于是根據(jù)(3”)可得ABA(BC) 同理可得 ACA(BC)于是根據(jù)(3)可得 (AB)(AC)A(BC) 。 最后，根據(jù)包含關(guān)系的反對稱性，就得到 A(BC)=(AB)(AC)。42離散數(shù)學(xué)定理定理3. de Morgan律（也叫對偶律） 設(shè)A，B為兩個集合。則 (1)( AB) = AB， (2)( AB) = AB。證明.只證(1) 先證：(AB)AB (采用包含法) 由定理2(3)有 AAB，BAB于是由定理1(2)可得 (AB)A，(AB) B再用定理2(3”)，就有 (AB

27、)AB； 次證：AB(AB) (采用邏輯法) 對任何元素x X ， xAB43離散數(shù)學(xué) xAxB xAxB xAB (否則 xAB xAxB，這與xAxB矛盾) x(AB) 所以AB(AB) 最后，根據(jù)包含關(guān)系的反對稱性，就得到 (AB)= AB。定理定理4 設(shè)A，B為兩個集合。則下面三式等價。 (1)A B ； (2)AB = B ； (3)AB=A 。44離散數(shù)學(xué)證明.(采用循環(huán)論證法) (1)(2)：(采用包含法) 首先，根據(jù)定理2(3)，我們得到 BAB； 其次，由已知條件AB，及自反性BB，根據(jù)定理2(3)，我們得到 ABB ； 最后，根據(jù)包含關(guān)系的反對稱性，我們就得到 AB=B 。

28、 (2)(3)：(采用變換法(公式法) AB=A(AB) (根據(jù)(2) AB=B) =A (根據(jù)定理2(4)吸收律) 即 AB=A。 (3)(1)：(采用：包含法) A= AB (根據(jù)(3)AB=A) B (根據(jù)定理2 (3)ABB) 45離散數(shù)學(xué) 即AB。定義定義3 . 差運算(difference) 設(shè)X是全集。 二元運算 :2X2X 2X 對任何集合A,BX ，使得 AB = x : xA xB 稱為集合的差運算。稱 AB 為 A 和 B 的差集。 差集有時也稱為相對補(relative complement)。 而余運算可看成絕對補。即 A = XA 。ABBAX 屬于集合A但不屬于集

29、合B的元素!46離散數(shù)學(xué)例例3. X=a,b,c,d,e,f,A=a,c,d,f,B=b,d,f。 則 AB = a,c, BA = b 。 由差運算、交運算、余運算的定義知 AB = AB。由于差運算可以由交、并、余運算線性表出，因此稱差運算為宏運算。請問：交、并、余三個運算是線性無關(guān)的嗎？注注：答案是否定的。實際上，根據(jù)反身律、 de Morgan律，我們有 AB = (AB)； AB = (AB)。47離散數(shù)學(xué)定理定理5.差運算基本定理設(shè)X是全集，A，B，C是X的三個子集。則 (1)ABA ； (2)ABAB = ； (3)AA = ； (4)XA = A ；AX = ； (5)A =

30、A ； A = ； (6)A(BC)= (AB) ( AC) (交對差的分配律) ； (7)A(BC)=(AB)(AC) ； (8)A(BC) = (AB) (AC) (相對補的de Morgan律)； (9) A(BC) = (AB)(AC) (相對補的de Morgan律) 。48離散數(shù)學(xué)證明.(采用包含法和變換法(公式法)法) (1)AB=AB A (根據(jù)定理2 (3)ABA)； (2)AB=AB =(AB)B (由已知條件AB根據(jù)定理4(3)有AB=A) =A(BB) (結(jié)合律) =A (互補律BB=) = (零壹律) ； (3)，(4)，(5)：顯然； (6)A(BC) = A(BC

31、) =(ABC) (零壹律,結(jié)合律) =(B)(ABC) (零壹律) 49離散數(shù)學(xué) =(BAA)(ABC) (互補律,結(jié)合律) =(ABA)(ABC) (交換律) =(AB)(AC) (分配律) =(AB)(AC) (de Morgan律) =(AB)(AC) ； (7)A(BC)=A(BC) =A(BC) =A(BC) (de Morgan律,反身律) =(AB)(AC) (分配律) =(AB)(AC) ； (8)A(BC)=A(BC) =A(BC) (de Morgan律) =(AA)(BC) (冪等律) 50離散數(shù)學(xué) =(AB)(C) (結(jié)合律，交換律) =(AB)(AC) ； (9)A

32、(BC)= A(BC) =A(BC) (de Morgan律) =(AB)(C) (分配律) =(AB)(AC) 。定義定義4. 對稱差（環(huán)和）運算(symmetric difference) 設(shè)X是全集。 二元運算 :2X2X 2X ， 對任何集合A,BX ，使得 AB=x : (xA xB) (xB xA) 稱為集合的對稱差運算。稱 AB 為 A 和 B 的對稱差集。 屬于集合A和集合B，但不同時屬于集合A和集合B的元素!51離散數(shù)學(xué)w由環(huán)和運算和并、差運算的定義可知 AB= (AB)(BA)w由環(huán)和運算和交、并、余運算的定義可知 AB= (AB)(BA)因此環(huán)和運算也是宏運算。例例4.

33、設(shè)X=a,b,c,d,e,f,A=a,c,d,f,B=b,d,f 。 則 AB = a,c, BA = b, 于是 AB= a,b,c 。ABXAB52離散數(shù)學(xué)定理定理6 .環(huán)和運算基本定理 設(shè)X是全集，A，B，C是X的三個子集。則 (1)AB = (AB)(AB) = (AB)(AB) ； (2)A = A （空集是環(huán)和的幺元）； AX = A ； (3)AA = （自己是自己（環(huán)和）的逆元）； AA= X ； (4)AB = AB ； (5)(AB) = AB = AB ； (6)交換律：AB = BA ； (7)結(jié)合律：A(BC) = (AB)C ； (8)分配律：A(BC) = (AB

34、)(AC) (交對環(huán)和的)； (9)消去律：AB = AC B=C 。53離散數(shù)學(xué)證明.(采用變換法(公式法)只證(5)，(7)，(9) (5)(AB) =(AB)(AB) =(AB)(AB) (de Morgan律) =(AB)(AB) (de Morgan律，反身律) =(AB)A)(AB)B) (分配律) =(AA)(BA)(AB)(BB) (分配律，結(jié)合律) =(AA)(AB)(AB)(BB) (交換律) =(AB)(AB) (互補律) =(AB)(AB) (零壹律) AB=(AB)(AB) =(AB)(AB) (反身律) =(AB)(AB) (交換律) 54離散數(shù)學(xué) AB=(AB)(

35、AB) =(AB)(AB) (反身律) 所以 (AB)=AB=AB=(AB)(AB) ； (7)A(BC) =(A(BC)(A(BC) =(A(BC)(BC)(A(BC)(BC) (根據(jù)本定理的(5)的證明) =(ABC)(ABC)(ABC)(ABC) (分配律，結(jié)合律) (AB)C =(AB)C)(AB)C) =(AB)(AB)C)(AB)(AB)C) (根據(jù)本定理的(5)的證明) (BC)=BC=BC=(BC)(BC)(1,1.1)=7,(1,0,0)=4,(0,1,0)=2, (0,0,1)=1(AB)=AB=AB=(AB)(AB)55離散數(shù)學(xué) =(ABC)(ABC)(ABC)(ABC)

36、 (分配律，結(jié)合律) =(ABC)(ABC)(ABC)(ABC) (交換律，結(jié)合律) 所以 A(BC)=(AB)C； (9)B=B (根據(jù)本定理的(2) =(AA)B (根據(jù)本定理的(3) =A(AB) (根據(jù)本定理的(7)結(jié)合律) =A(AC) (已知條件AB=AC) =(AA) B (根據(jù)本定理的(7)結(jié)合律) =C (根據(jù)本定理的(3) =C (根據(jù)本定理的(2)。(1,1.1)=7,(1,0,0)=4,(0,1,0)=2, (0,0,1)=156離散數(shù)學(xué)定義定義5 .環(huán)積運算 設(shè)X是全集。 二元運算 :2X2X 2X 對任何集合A,BX ，使得 AB=x : (xAxB)(xBxA) 稱為集合的環(huán)積運算。稱 AB 為 A 和 B 的環(huán)積集。w由環(huán)積運算和交、并、余運算 的定義可知 AB= (AB)(BA) 因此環(huán)積運算也是宏運算。ABXAB57離散數(shù)學(xué)例例5. 設(shè)X=a,b,c,d,e,f,A=a,c,d,f,B=b,d,f。 則 AB = a,c,d,e,f, BA = b,d,e,f, 于是 AB= d,e,f 。定理定理7.