離散數(shù)學：第6章 集合代數(shù)

1、 1第6章 集合代數(shù)離散數(shù)學離散數(shù)學 2本章說明本章說明q本章的主要內(nèi)容本章的主要內(nèi)容集合的基本概念集合的基本概念集合、相等、集合、相等、( (真真) )包含、子集、空集、包含、子集、空集、全集、冪集全集、冪集 集合運算集合運算交、并、交、并、( (相對和絕對相對和絕對) )補、對稱差、廣義交、補、對稱差、廣義交、廣義并廣義并文氏圖文氏圖有窮集計數(shù)問題有窮集計數(shù)問題 集合恒等式集合恒等式q本章與后續(xù)各章的關系本章與后續(xù)各章的關系 是集合論后面各章的基礎是集合論后面各章的基礎 是典型的布爾代數(shù)系統(tǒng)是典型的布爾代數(shù)系統(tǒng) 36.1 6.1 集合的基本概念集合的基本概念 q 集合集合(Set)(Set

2、)是不能精確定義的基本概念。是不能精確定義的基本概念。所謂集合，是指我們無意中或思想中將一些確定的、彼所謂集合，是指我們無意中或思想中將一些確定的、彼此完全不同的客體的總和而考慮為一個整體。這些客體此完全不同的客體的總和而考慮為一個整體。這些客體叫做該集合的元素。叫做該集合的元素。( (康托康托) )直觀地說，把一些事物匯集到一起組成一個整體就叫直觀地說，把一些事物匯集到一起組成一個整體就叫集集合合，而這些事物就是這個集合的，而這些事物就是這個集合的元素元素或或成員成員。q 例如：例如：方程方程x x2 21 10 0的實數(shù)解集合：的實數(shù)解集合：2626個英文字母的集合；個英文字母的集合；坐標

3、平面上所有點的集合；坐標平面上所有點的集合； q 集合通常用大寫的英文字母來標記。集合通常用大寫的英文字母來標記。 4常見的數(shù)的集合常見的數(shù)的集合q N N自然數(shù)集合自然數(shù)集合q Z Z整數(shù)集合整數(shù)集合q Q Q有理數(shù)集合有理數(shù)集合q R R實數(shù)集合實數(shù)集合q C C復數(shù)集合復數(shù)集合 5集合的表示方法集合的表示方法q 表示一個集合的方法主要有兩種：表示一個集合的方法主要有兩種：列元素法列元素法和和謂詞表示法謂詞表示法。q 列元素法列元素法(roster)(roster)是列出集合的所有元素，元素之間用逗號是列出集合的所有元素，元素之間用逗號隔開，并把它們用花括號括起來。隔開，并把它們用花括號括

4、起來。A Aaa，b b，c c，zzZ Z00，1 1，2 2， C C 桌子桌子, ,燈泡燈泡, ,老虎老虎, ,自然數(shù)自然數(shù) q 謂詞表示法謂詞表示法(defining predicate)(defining predicate)是用謂詞來概括集合中元是用謂詞來概括集合中元素的屬性。素的屬性。B Bx|xRxx|xRx2 21 100q 許多集合可以用兩種方法來表示，如許多集合可以用兩種方法來表示，如B B也可以寫成也可以寫成-1-1，11。但是有些集合不可以用列元素法表示，如實數(shù)集合。但是有些集合不可以用列元素法表示，如實數(shù)集合。 6集合的元素集合的元素q 集合的元素是彼此不同的，如果

5、同一個元素在集合中多集合的元素是彼此不同的，如果同一個元素在集合中多次出現(xiàn)應該認為是一個元素。次出現(xiàn)應該認為是一個元素。例如：例如：11，1 1，2 2，2 2，3311，2 2，33q 集合的元素是無序的。集合的元素是無序的。例如：例如：11，2 2，3333，1 1，22q 在本書所采用的體系中規(guī)定：在本書所采用的體系中規(guī)定：集合的元素都是集合集合的元素都是集合。 7元素和集合之間的關系元素和集合之間的關系q 元素和集合之間的關系是隸屬關系，即元素和集合之間的關系是隸屬關系，即屬屬于于或或不屬于不屬于，屬于記作，屬于記作，不屬于記作，不屬于記作 。q 例如：例如：A Aaa，bb，cc，d

6、 d，dda aA A，bb，ccA A，d dA A，ddA A，b b A A，dd A A。b b和和dd是是A A的元素的元素。的元素的元素。q 可以用一種樹形圖表示集合與元素的隸屬可以用一種樹形圖表示集合與元素的隸屬關系。關系。說說明明q 隸屬關系可以看作是處在不同層次上的集合之間的關系。隸屬關系可以看作是處在不同層次上的集合之間的關系。q 規(guī)定：對任何集合規(guī)定：對任何集合A A都有都有A A A A。A Aa ab,cb,cd dddb bc cddd d 8子集（子集（subsetsubset）定義定義6.16.1 設設A A，B B為集合，如果為集合，如果B B中的每個元素都是

7、中的每個元素都是A A中的元素，中的元素，則稱則稱B B是是A A的子集合，簡稱的子集合，簡稱子集子集。這時也稱。這時也稱B B被被A A包含包含，或，或A A包包含含B B，記作，記作 B B A A。q 包含的符號化表示為包含的符號化表示為B B A A x(xBxA)x(xBxA)q如果如果B B不被不被A A包含，則記作包含，則記作 B AB A。 q例如：例如：N N Z Z Q Q R R C C，但，但Z NZ N。 q顯然對任何集合顯然對任何集合A A都有都有 A A A A。 9隸屬和包含的說明隸屬和包含的說明q 隸屬關系和包含關系都是兩個集合之間的關系，對于某隸屬關系和包含

8、關系都是兩個集合之間的關系，對于某些集合可以同時成立這兩種關系。些集合可以同時成立這兩種關系。q 例如例如 A Aaa，aa和和aa既有既有aAaA，又有，又有aa A A。前者把它們看成是不同層次上的兩個集合，前者把它們看成是不同層次上的兩個集合，后者把它們看成是同一層次上的兩個集合。后者把它們看成是同一層次上的兩個集合。 10集合相等集合相等(equal)(equal)定義定義6.26.2 設設A A，B B為集合，如果為集合，如果 A A B B 且且 B B A A，則稱，則稱A A與與B B相等相等，記作，記作A AB B。q 相等的符號化表示為：相等的符號化表示為：A AB B A

9、 A B BB B A A q 如果如果A A與與B B不相等，則記作不相等，則記作ABAB。 11真子集真子集定義定義6.36.3 設設A A，B B為集合，如果為集合，如果 B B A A 且且 BABA，則稱，則稱B B是是A A的的真子集真子集，記作，記作B B A A。q 真子集的符號化表示為真子集的符號化表示為B B A A B B A BAA BAq 如果如果B B不是不是A A的真子集，則記作的真子集，則記作B B A A。例如：例如：N N N N 12空集空集(empty set)(empty set)定義定義6.46.4 不含任何元素的集合叫做不含任何元素的集合叫做空集空

10、集，記作，記作?？占姆柣硎緸椋嚎占姆柣硎緸椋?x|xxx|xx。例如例如: x|xRx: x|xRx2 2+1=0+1=0是方程是方程x x2 2+1=0+1=0的實數(shù)解集，因為該方程無實數(shù)解，所以是的實數(shù)解集，因為該方程無實數(shù)解，所以是空集?？占?。 13空集的性質(zhì)空集的性質(zhì)推論推論 空集是唯一的?？占俏ㄒ坏摹ＷC明證明：假設存在空集：假設存在空集1 1和和2 2，由定理，由定理6.16.1有有1 1 2 2 ， 2 2 1 1。根據(jù)集合相等的定義，有根據(jù)集合相等的定義，有 1 1 2 2。 定理定理6.16.1 空集是一切集合的子集?？占且磺屑系淖蛹ＷC明證明：任給集合：任給

11、集合A A，由子集定義有，由子集定義有 A A x(xx(x xA) xA)右邊的蘊涵式因前件假而為真命題，右邊的蘊涵式因前件假而為真命題，所以所以 A A也為真。也為真。 14n n元集元集q 含有含有n n個元素的集合簡稱個元素的集合簡稱n n元集元集，它的含有，它的含有m(mn)m(mn)個元個元素的子集叫做它的素的子集叫做它的m m元子集元子集。例例6.16.1 A A1,2,31,2,3，將，將A A的子集分類：的子集分類：0 0元子集（空集）元子集（空集）1 1元子集（單元集）元子集（單元集）11，22，332 2元子集元子集1,21,2，1,31,3，2,32,33 3元子集元子

12、集1,2,31,2,3 15冪集冪集 ( power set )q 一般地說，對于一般地說，對于n n元集元集A A，它的，它的0 0元子集有元子集有 個，個，1 1元子集有元子集有 個，個，m m元子集有元子集有 個，個，n n元子集有元子集有 個。子集總數(shù)為個。子集總數(shù)為n nn nn n2 2n n1 1n n0 0n n2 2C CC CC CC C0 0n nC C1 1n nC Cm mn nC Cn nn nC C定義定義6.56.5 設設A A為集合，把為集合，把A A的全部子集構成的集合叫做的全部子集構成的集合叫做A A的的冪集冪集，記作記作P(A)(P(A)(或或PAPA，

13、2 2A A) )。q 冪集的符號化表示為冪集的符號化表示為P(A)P(A)x | xx | x A A q 若若A A是是n n元集，則元集，則P(A)P(A)有有 2 2n n 個元素。個元素。 16全集全集定義定義6.66.6 在一個具體問題中，如果所涉及的集合都是某個集在一個具體問題中，如果所涉及的集合都是某個集合的子集，則稱這個集合為合的子集，則稱這個集合為全集全集，記作，記作E E。說說明明q 全集是有相對性的，不同的問題有不同的全集，即使全集是有相對性的，不同的問題有不同的全集，即使是同一個問題也可以取不同的全集。是同一個問題也可以取不同的全集。q 例如，在研究平面上直線的相互關

14、系時，可以把整個例如，在研究平面上直線的相互關系時，可以把整個平面平面( (平面上所有點的集合平面上所有點的集合) )取作全集，也可以把整個取作全集，也可以把整個空間空間( (空間上所有點的集合空間上所有點的集合) )取作全集。取作全集。q 一般地說，全集取得小一些，問題的描述和處理會簡一般地說，全集取得小一些，問題的描述和處理會簡單些。單些。 176.2 6.2 集合的運算集合的運算定義定義6.76.7 設設A A，B B為集合，為集合，A A與與B B的的并集并集ABAB，交集交集AB AB ，B B對對A A的的相對補集相對補集A AB B分別定義如下：分別定義如下：ABABx|xAxB

15、 x|xAxB (union set)(union set)ABABx|xAxB x|xAxB (intersection set)(intersection set)A AB Bx|xAxx|xAx B B (difference set)(difference set)舉例舉例設設 A Aaa，b b，cc，B Baa，C Cbb，d d 則有則有 ABABaa，b b，cc，ABABaa， A AB Bbb，cc， B BA A ，BCBC說說明明q 如果兩個集合的交集為如果兩個集合的交集為 ，則稱這兩個集合是不相交，則稱這兩個集合是不相交的。例如的。例如B B和和C C是不相交的。是不

16、相交的。 18n n個集合的并和交個集合的并和交q 兩個集合的并和交運算可以推廣成兩個集合的并和交運算可以推廣成n n個集合的并和交：個集合的并和交：A A1 1AA2 2AAn nx|xAx|xA1 1xAxA2 2xAxAn n A A1 1AA2 2AAn nx|xAx|xA1 1xAxA2 2xAxAn n 上述的并和交可以簡記為：上述的并和交可以簡記為：n n1 1i ii iA AA A1 1AA2 2AAn nn n1 1i ii iA AA A1 1AA2 2AAn nq 兩個集合的并和交運算可以推廣到無窮多個集合的情況：兩個集合的并和交運算可以推廣到無窮多個集合的情況：1 1

17、i ii iA AA A1 1AA2 21 1i ii iA AA A1 1AA2 2 19對稱差集對稱差集定義定義6.86.8 設設A A，B B為集合，為集合，A A與與B B的的對稱差集對稱差集 A A B B定義為：定義為：A A B B(A(AB)(BB)(BA) A) q 對稱差運算的另一種定義是對稱差運算的另一種定義是A A B B(AB)(AB)(AB) (AB) q 例如例如: A: Aaa，b b，cc，B Bbb，dd，則則 A A B Baa，c c，d d 20絕對補集絕對補集定義定義6.96.9 A AE EA Ax|xExx|xEx A A q 因為因為E E是全

18、集，是全集，xExE是真命題，所以是真命題，所以A A可以定義為：可以定義為：A Ax|x x|x A A q 例如例如: E: Eaa，b b，c c，dd，A Aaa，b b，cc A Ad d 21廣義并和廣義交廣義并和廣義交定義定義6.106.10 設設A A為集合，為集合，A A的的元素的元素元素的元素構成的集合稱為構成的集合稱為A A的的廣義并廣義并，記為，記為A A。符號化表示為符號化表示為A Ax | x | z(zAxz)z(zAxz)定義定義6.116.11 設設A A為為非空非空集合，集合，A A的所有的所有元素的公共元素元素的公共元素構構成的集合稱為成的集合稱為A A的

19、的廣義交廣義交，記為，記為A A。符號化表示為符號化表示為 A Ax | x | z(zAxz)z(zAxz) 22例例6 6 設設 A Aa,b,c,a,c,d,a,e,fa,b,c,a,c,d,a,e,f B Baa C Ca,c,da,c,d則則 A Aa,b,c,d,e,fa,b,c,d,e,f B Baa C Cac,dac,d A Aaa B Baa C Cac,dac,d 23廣義并與廣義交的說明廣義并與廣義交的說明q 若若A AAA1 1,A,A2 2, ,A,An n ，則，則A AA A1 1AA2 2AAn nq 若若A AAA1 1,A,A2 2, ,A,An n ，則

20、，則A AA A1 1AA2 2AAn nq 在后面的敘述中，若只說并或交，則這都是指集合的初級在后面的敘述中，若只說并或交，則這都是指集合的初級并或初級交；如果在并或交前邊冠以并或初級交；如果在并或交前邊冠以“廣義廣義”兩個字，則兩個字，則指集合的廣義并或廣義交。指集合的廣義并或廣義交。q 為了使得集合表達式更為簡潔，我們對集合運算的優(yōu)先順為了使得集合表達式更為簡潔，我們對集合運算的優(yōu)先順序做如下規(guī)定：序做如下規(guī)定：稱廣義并、廣義交、冪集、絕對補運算為一類運算稱廣義并、廣義交、冪集、絕對補運算為一類運算并、交、相對補、對稱差運算為二類運算。并、交、相對補、對稱差運算為二類運算。一類運算優(yōu)先于

21、二類運算一類運算優(yōu)先于二類運算一類運算之間由右向左順序進行一類運算之間由右向左順序進行二類運算之間由括號決定先后順序。二類運算之間由括號決定先后順序。 24例例例例 設設 A Aa,a,ba,a,b計算計算A A，A A，A(AA(AA)A)解答解答 A Aa,ba,bAAaaAAababAAa aAA(AAA A) )(ab)(ab)(ababa a) )(ab)(b-a)(ab)(b-a)b b 25文氏圖文氏圖(Venn Diagram)(Venn Diagram) q 集合之間的關系和運算可以用集合之間的關系和運算可以用文氏圖文氏圖給予形象的描述。給予形象的描述。q 文氏圖的構造方法如

22、下：文氏圖的構造方法如下：畫一個大矩形表示全集畫一個大矩形表示全集E(E(有時為簡單起見可將全集省有時為簡單起見可將全集省略略) )。在矩形內(nèi)畫一些圓在矩形內(nèi)畫一些圓( (或任何其它的適當?shù)拈]曲線或任何其它的適當?shù)拈]曲線) )，用，用圓的內(nèi)部表示集合。圓的內(nèi)部表示集合。不同的圓代表不同的集合。如果沒有關于集合不交的不同的圓代表不同的集合。如果沒有關于集合不交的說明，任何兩個圓彼此相交。說明，任何兩個圓彼此相交。圖中陰影的區(qū)域表示新組成的集合。圖中陰影的區(qū)域表示新組成的集合?？梢杂脤嵭狞c代表集合中的元素?？梢杂脤嵭狞c代表集合中的元素。 26文氏圖的實例文氏圖的實例 27有窮集的計數(shù)問題有窮集的計

23、數(shù)問題q 使用文氏圖可以很方便地解決使用文氏圖可以很方便地解決有窮集的計數(shù)問題有窮集的計數(shù)問題。q 首先根據(jù)已知條件把對應的文氏圖畫出來。首先根據(jù)已知條件把對應的文氏圖畫出來。一般地說，每一條性質(zhì)決定一個集合。一般地說，每一條性質(zhì)決定一個集合。有多少條性質(zhì)，就有多少個集合。有多少條性質(zhì)，就有多少個集合。如果沒有特殊說明，任何兩個集合都畫成相交的如果沒有特殊說明，任何兩個集合都畫成相交的q 然后將已知集合的元素數(shù)填入表示該集合的區(qū)域內(nèi)。然后將已知集合的元素數(shù)填入表示該集合的區(qū)域內(nèi)。通常從通常從n n個集合的交集填起，個集合的交集填起，根據(jù)計算的結果將數(shù)字逐步填入所有的空白區(qū)域。根據(jù)計算的結果將數(shù)

24、字逐步填入所有的空白區(qū)域。如果交集的數(shù)字是未知的，可以設為如果交集的數(shù)字是未知的，可以設為x x。q 根據(jù)題目中的條件，列出一次方程或方程組，就可以求得所根據(jù)題目中的條件，列出一次方程或方程組，就可以求得所需要的結果。需要的結果。 28例例6.26.2例例6.46.4 對對2424名會外語的科技人員進行掌握外語情況的調(diào)查。名會外語的科技人員進行掌握外語情況的調(diào)查。其統(tǒng)計結果如下：會英、日、德和法語的人分別為其統(tǒng)計結果如下：會英、日、德和法語的人分別為1313，5 5，1010和和9 9人，其中同時會英語和日語的有人，其中同時會英語和日語的有2 2人，會英、德和人，會英、德和法語中任兩種語言的都

25、是法語中任兩種語言的都是4 4人。已知會日語的人既不懂法人。已知會日語的人既不懂法語也不懂德語，分別求只會一種語言語也不懂德語，分別求只會一種語言( (英、德、法、日英、德、法、日) )的的人數(shù)和會三種語言的人數(shù)。人數(shù)和會三種語言的人數(shù)。 解解：令：令A A，B B，C C，D D分別表示會英、法、德、日語的人的集合分別表示會英、法、德、日語的人的集合。根據(jù)題意畫出文氏圖。設同時會三種語言的有。根據(jù)題意畫出文氏圖。設同時會三種語言的有x x人，只人，只會英、法或德語一種語言的分別為會英、法或德語一種語言的分別為y y1 1，y y2 2和和y y3 3人。將人。將x x和和y y1 1，y y

26、2 2，y y3 3填入圖中相應的區(qū)域，然后依次填入其它區(qū)域的填入圖中相應的區(qū)域，然后依次填入其它區(qū)域的人數(shù)。人數(shù)。 29例例6.26.24-x4-x4-x4-x4-x4-xx xy y2 2y y1 1y y3 32 25-25-2英英 1313法法 9 9德德 1010日日 5 5y y1 1+2(4-x)+x+2+2(4-x)+x+21313y y2 2+2(4-x)+x+2(4-x)+x9 9y y3 3+2(4-x)+x+2(4-x)+x1010y y1 1+y+y2 2+y+y3 3+3(4-x)+x+3(4-x)+x24-524-5 30包含排斥原理包含排斥原理定理定理6.26.

27、2 設設S S為有窮集，為有窮集，P P1 1,P,P2 2, ,P,Pm m是是m m個性質(zhì)。個性質(zhì)。S S中的任何中的任何元素元素x x或者具有性質(zhì)或者具有性質(zhì)P Pi i，或者不具有性質(zhì)，或者不具有性質(zhì)P Pi i(i=1,2,(i=1,2,m),m),兩種情況必居其一。令兩種情況必居其一。令A Ai i表示表示S S中具有性質(zhì)中具有性質(zhì)P Pk k的元素構成的元素構成的子集，則的子集，則S S中不具有性質(zhì)中不具有性質(zhì)P P1 1,P,P2 2, ,P,Pm m的元素為的元素為| |A AA AA A| |1)1)( (| |A AA AA A| | |A AA A| | |A A| |

28、 |S S| | |A AA AA A| |m m2 21 1m mk kj jm mk kj ji i1 1i ij jm mj ji i1 1i im m1 1i ii im m2 21 1 31推論推論qS S中至少具有一條性質(zhì)的元素數(shù)為中至少具有一條性質(zhì)的元素數(shù)為m mk kj ji i1 1m m2 21 11 1m mk kj ji im mj ji i1 1j ji im m1 1i ii im m2 21 1| |A AA AA A| |1 1) )( (| |A AA AA A| | |A AA A| | |A A| | |A AA AA A| | 32例例6.36.3例例6

29、.5 6.5 求求1 1到到10001000之間之間( (包含包含1 1和和10001000在內(nèi)在內(nèi)) )既不能被既不能被5 5和和6 6，也，也不能被不能被8 8整除的數(shù)有多少個。整除的數(shù)有多少個。解答解答 設設S Sx|xZ1x1000 x|xZ1x1000 A A x|xSx x|xSx可被可被5 5整除整除 B B x|xSx x|xSx可被可被6 6整除整除 C C x|xSx x|xSx可被可被8 8整除整除 |T|T|表示有窮集表示有窮集T T中的元素數(shù)中的元素數(shù) x x 表示小于等于表示小于等于x x的最大整數(shù)的最大整數(shù)lcm(xlcm(x1 1,x,x2 2, ,x,xn n

30、) )表示表示x x1 1,x,x2 2, ,x,xn n的最小公倍數(shù)的最小公倍數(shù) 33例例6.36.3|A|A| 1000/51000/5 200200|B|B| 1000/61000/6 166166|C|C| 1000/81000/8 125125|AB|AB| 1000/1000/lcm(5,6)lcm(5,6) 3333|AC|AC| 1000/1000/lcm(5,8)lcm(5,8) 2525|BC|BC| 1000/1000/lcm(6,8)lcm(6,8) 4141|ABC|ABC| 1000/1000/lcm(5,6,8)lcm(5,6,8) 8 8 將這些數(shù)字依次填入文氏

31、圖，得到將這些數(shù)字依次填入文氏圖，得到 34例例6.36.3q 根據(jù)包含排斥原理，所求不能被根據(jù)包含排斥原理，所求不能被5 5，6 6和和8 8整除的數(shù)應為整除的數(shù)應為q由文氏圖也可得知，不能被由文氏圖也可得知，不能被5 5，6 6和和8 8整除的數(shù)有整除的數(shù)有10001000(200+100(200+100333367)67)600600個。個。 6006008 8- -41)41)2525(33(33125)125)166166(200(200- -10001000| |C CB BA A| |)|)C CB B| | |C CA A| | |B BA A(|(|)|)C C| | |B

32、B| | |A A(|(| |S S| | |C CB BA A| | 356.3 6.3 集合恒等式集合恒等式 q 下面的恒等式給出了集合運算的主要算律，其中下面的恒等式給出了集合運算的主要算律，其中A A，B B，C C代表任意集合。代表任意集合。冪等律冪等律 AAAAA A (6.1)(6.1) AAAAA A (6.2)(6.2)結合律結合律 (AB)C(AB)CA(BC)A(BC) (6.3)(6.3) (AB)C (AB)CA(BC)A(BC) (6.4)(6.4)交換律交換律 ABABBABA (6.5)(6.5) AB ABBABA (6.6)(6.6)分配律分配律 A(BC)

33、A(BC)(AB)(AC) (AB)(AC) (6.7)(6.7) A(BC) A(BC)(AB)(AC) (AB)(AC) (6.8)(6.8)同一律同一律 AAA A (6.9)(6.9) AE AEA A (6.10)(6.10) 366.3 6.3 集合恒等式集合恒等式零律零律 AEAEE E (6.11)(6.11) AA (6.12)(6.12)排中律排中律 AAA AE E (6.13)(6.13)矛盾律矛盾律 AAA A (6.14)(6.14)吸收律吸收律 A(AB)A(AB)A A (6.15)(6.15) A(AB) A(AB)A A (6.16)(6.16)德摩根律德摩

34、根律 A A(BC)(BC)(A(AB)(AB)(AC)C)(6.17)(6.17) A A(BC)(BC)(A(AB)(AB)(AC)C)(6.18)(6.18)(BC)(BC)BBC C (6.19)(6.19)(BC)(BC)BBC C (6.20)(6.20)E E (6.21)(6.21)E E (6.22)(6.22)雙重否定律雙重否定律 ( (A)A)A A (6.23)(6.23) 37集合運算性質(zhì)的一些重要結果集合運算性質(zhì)的一些重要結果ABAB A A，ABAB B B(6.24)(6.24)A A ABAB，B B ABAB(6.25)(6.25)A AB B A A(6.

35、26)(6.26)A AB BAAB B (6.27)(6.27)ABABB B A A B B ABABA A A AB B(6.28) (6.28) A A B BB B A A (6.29)(6.29)(A(A B)B) C CA A (B(B C)C) (6.30)(6.30)A AA A (6.31)(6.31)A A A A (6.32)(6.32)A A B BA A C C B BC C (6.33)(6.33) 38對偶對偶(dual)(dual)原理原理q對偶對偶(dual)(dual)式式：一個集合表達式，如果只含有：一個集合表達式，如果只含有、E E、 、 ，那么同時把

36、，那么同時把與與互換，把互換，把與與E E互換，把互換，把 與與 互換互換，得，得到式子稱為原式的對偶式。到式子稱為原式的對偶式。q對歐原理對歐原理：對偶式同真假。或者說，集合恒等：對偶式同真假?；蛘哒f，集合恒等式的對偶式還是恒等式。式的對偶式還是恒等式。 39集合恒等式的證明方法集合恒等式的證明方法q邏輯演算法邏輯演算法利用利用邏輯等值式邏輯等值式和和推理規(guī)則推理規(guī)則q集合演算法集合演算法利用利用集合恒等式集合恒等式和和已知結論已知結論 40邏輯演算法的格式邏輯演算法的格式題目：題目：A AB B證明：證明： x x， x xAA x xBB所以所以 A AB B或證或證 P P Q QQ

37、Q P P 題目：題目：A A B B證明：證明： x x， x xAA x xBB所以所以 A A B B 41集合演算法的格式集合演算法的格式題目：題目：A AB B證明：證明： A A B B所以所以 A AB B題目：題目：A A B B證明：證明：A A B B所以所以 A A B B 42例例6.86.8例例6.86.8 證明式證明式6.176.17，即，即 A A(BC)(BC)(A(AB)( AB)( AC)C)證明證明 對任意的對任意的x x，有，有xAxA(BC)(BC)xA xxA x BCBCxA (xBxC)xA (xBxC) xA (xBxC)xA (xBxC) x

38、A (xxA (x B xB x C)C) (xAx(xAx B) (xAxB) (xAx C)C) xA xAB xAB xAC C x(A x(AB)(AB)(AC)C)所以所以 A A(BC)(BC)(A(AB)( AB)( AC)C) 43例例6.96.9例例6.96.9 證明式證明式6.106.10，即，即 AEAEA A證明證明 對任意的對任意的x x，有，有xAExAExA xExA xExA (xA (因為因為xExE是恒真命題是恒真命題) )所以所以 AEAEA A 44例例6.106.10例例6.106.10 假設已知等式假設已知等式6.16.16.146.14，試證等式，

39、試證等式6.156.15，即即 A(AB)A(AB)A A。證明證明 A(AB)A(AB) (AE)(AB) (AE)(AB) (由等式由等式6.10)6.10)A(EB) A(EB) ( (由等式由等式6.8)6.8)A(BE) A(BE) ( (由等式由等式6.5)6.5)AE AE ( (由等式由等式6.11)6.11)A A ( (由等式由等式6.10)6.10) 45例例6.116.11例例6.116.11 證明等式證明等式6.276.27，即即 A AB BAAB B證明證明 對于任意的對于任意的x x，有，有xAxAB B xA x xA x B B xA x xA xB B x

40、A xAB B 所以所以 A AB BAAB B。說說明明q 等式等式6.276.27把相對補運算轉(zhuǎn)換成交運算，這在證明有關把相對補運算轉(zhuǎn)換成交運算，這在證明有關相對補的恒等式中是很有用的。相對補的恒等式中是很有用的。 46例例6.126.12例例6.126.12 證明證明 (A(AB)BB)BABAB證明證明(A(AB)BB)B(A(AB)BB)B(AB)(AB)(BB)BB)(AB)E(AB)E ABAB 47例例6.136.13例例6.136.13 證明命題證明命題6.286.28是真命題。是真命題。 ABABB B A A B B AB ABA A A AB B說明說明 式式6.286

41、.28給出了給出了A A B B的另外三種等價的定義，這不僅為證的另外三種等價的定義，這不僅為證明兩個集合之間的包含關系提供了新方法，同時也可以用明兩個集合之間的包含關系提供了新方法，同時也可以用于集合公式的化簡。于集合公式的化簡。證明思路證明思路 ABABB B A A B B AB ABA A A AB B ABABB B 48例例6.136.13證明證明 ABABB B A A B B對于任意的對于任意的x x，有，有 xAxA xAxB xAxB xAB xAB xB xB( (因為因為ABABB)B)所以所以 A A B B。 49例例6.136.13證明證明 A A B B AB

42、ABA A顯然有顯然有 AB AB A A， 下面證下面證 A A AB AB。對于任意的對于任意的x x，有，有 xA xA xAxA xAxA xAxB xAxB( (因為因為A A B)B) xAB xAB 所以所以 A A AB AB 由集合相等的定義有由集合相等的定義有 ABABA A。 50例例6.136.13證明證明 ABABA A A AB B A AB B AAB B (AB)(AB)B B( (因為因為ABABA)A) A(BA(BB)B) AA 51例例6.136.13證明證明 A AB B ABABB B。由例由例6.10 (A6.10 (AB)BB)BAB AB 及及

43、 A AB B 有有 ABAB B(AB(AB)B) BB B B 52例例6.146.14例例6.146.14 化簡化簡(ABC)(AB)(ABC)(AB)(A(B(A(BC)A)C)A)解答解答 因為因為 AB AB ABC ABC，A A A(BA(BC)C)，由式由式6.286.28有：有： (ABABC)C)(AB)(AB) )(AA(B(BC)C)AA) )(AB)(AB)A AB BA A 53例例6.156.15例例6.156.15 已知已知 A A B BA A C C，證明，證明B BC C。證明證明 已知已知 A A B BA A C C，所以有，所以有A A (A(A

44、B)B)A A (A(A C)C) (A(A A)A) B B(A(A A)A) C C ( (由式由式6.30)6.30) B BC C ( (由式由式6.32)6.32) B BC C ( (由式由式6.29)6.29) B BC C ( (由式由式6.31)6.31) 54學習要求學習要求 q 熟練掌握集合的子集、相等、空集、全集、冪集等概念熟練掌握集合的子集、相等、空集、全集、冪集等概念及其符號化表示及其符號化表示 q 熟練掌握集合的交、并、（相對和絕對）補、對稱差、熟練掌握集合的交、并、（相對和絕對）補、對稱差、廣義交、廣義并的定義及其性質(zhì)廣義交、廣義并的定義及其性質(zhì) q 掌握集合的文氏圖的畫法及利用文氏圖解決有限集的計掌握集合的文氏圖的畫法及利用文氏圖解決有限集的計數(shù)問題的方法數(shù)問題的方法 q 牢記基本的集合恒等式（等冪律、交換律、結合律、分牢記基本的集合恒等式（等冪律、交換律、結合律、分配律、德配律、德摩