1、集合代數1、集合的描述定義、集合的描述定義 所謂所謂集合集合，是指某些可辨別的不同對象的全體，是指某些可辨別的不同對象的全體，將用大寫字母將用大寫字母A，B，X，Y，表示之。表示之。 組成集合的對象稱為集合的組成集合的對象稱為集合的元素元素或成員，將用小或成員，將用小寫字母寫字母a，b，x，y 表示之。表示之。 a是是A的元素或的元素或a屬于屬于A，記作記作a A； a不是不是A的元素或的元素或a不屬于不屬于A，記作，記作a A，或者，或者 (a A)。2、集合的表示：、集合的表示：表示一個特定集合，基本上有表示一個特定集合，基本上有兩種方法：兩種方法：枚舉法枚舉法：列出集合的所有元素，元素之

2、間用：列出集合的所有元素，元素之間用逗號分開，再用花括號括起。如：逗號分開，再用花括號括起。如：A= a, e, i, o, u 表明集合表明集合A是由字母是由字母 a, e, i ,o和和u為元素為元素構成的。構成的。謂詞法謂詞法：用：用謂詞公式謂詞公式來確定集合。即個體域中來確定集合。即個體域中能使謂詞公式為真的那些元素，確定了一個集能使謂詞公式為真的那些元素，確定了一個集合。因為這些元素都具有某種特殊性質。若合。因為這些元素都具有某種特殊性質。若P(x)含有一個自由變元的含有一個自由變元的謂詞公式謂詞公式，則，則x|P(x)定義了集合定義了集合S，并可表為：，并可表為：S=x|P(x)

3、由此可見，由此可見，P(c)為真當且僅當為真當且僅當 c S。 從而有從而有 x S P(x)=T集合的元素是彼此不同的。集合的元素是彼此不同的。如：如：1，1，2，2，31，2，3集合的元素是無序的集合的元素是無序的。 如：1，2，33，1，2 元素和集合之間的關系是隸屬關系元素和集合之間的關系是隸屬關系，屬于屬于記作 ，不屬于不屬于記作 。如：Aa，b，c，d，d 這里 aA，b，cA，dA，dA，但 bA，dA。 可以用一種樹形圖來表示這種可以用一種樹形圖來表示這種隸屬關系隸屬關系，該圖分層構，該圖分層構成，成，每個層上的結點都表示一個集合，它的兒子就是每個層上的結點都表示一個集合，它的

4、兒子就是它的元素。它的元素。上例中集合上例中集合 Aa，b，c，d，d 的樹形圖如圖所示。的樹形圖如圖所示。圖中的圖中的a，b，c，d也是集合，也是集合，由于所討論的問題與由于所討論的問題與a，b，c，d的元素無關，所以沒有列出它的元素無關，所以沒有列出它們的元素。鑒于們的元素。鑒于集合的元素是集合的元素是集合集合這一規定，這一規定，隸屬關系隸屬關系可以可以看作是處在不同層次上的集合看作是處在不同層次上的集合之間的關系。之間的關系。可形式表為可形式表為： A=B ( x)(x Ax B)或者A=B ( x)(x Ax B)( x)(x Bx A) 順便指出，在應用外延公理證明集合順便指出，在應

5、用外延公理證明集合A與與B相等時，只需考察：相等時，只需考察： 對于任意元素對于任意元素x，應有：，應有：x Ax B 成立即可。這就是說，成立即可。這就是說，證明兩集合相等時可按證明兩集合相等時可按此法行事此法行事。子集子集是描述一個集合與另一個集合之間的關是描述一個集合與另一個集合之間的關系，其定義如下系，其定義如下: 設設A和和B是任意兩個集合，如果集是任意兩個集合，如果集合合A的每個元素，都是集合的每個元素，都是集合B中的一個元素，中的一個元素，則稱則稱A是是B的的子集子集，或稱，或稱A被被包含于包含于B中，或中，或者說者說 B包含包含A，并記為，并記為A B。二、集合之間的關系二、集

6、合之間的關系集合包含的符號化表示：集合包含的符號化表示：A B ( x)(x Ax B)表明：要證明表明：要證明A B，只需對任意元素，只需對任意元素x，有下式，有下式x Ax B成立即可。成立即可。如果如果A B且且B A，則稱，則稱A與與B相等，記作相等，記作AB。若集合若集合B不包含集合不包含集合A，記為，記為A B。 設設A和和B是兩個集合，若是兩個集合，若A B且且A B，則稱，則稱A是是B的的真子集真子集，記為，記為A B，也，也稱稱B真包含真包含A。該定義也可表為。該定義也可表為A B (A BA B)如果如果A不是不是B的真子集，則記作的真子集，則記作A B。 如果一個集合包含

7、了所要討論的如果一個集合包含了所要討論的每一個集合，則稱該集合為每一個集合，則稱該集合為全集全集，記為，記為 E。它可形式地表為它可形式地表為E = x|P(x)P(x)其中：其中：P(x)為任何謂詞公式。為任何謂詞公式。 顯然，顯然，全集全集E即是第二章中的即是第二章中的全總個體域全總個體域。于是，每個元素于是，每個元素 x 都屬于全集都屬于全集 E，即命題，即命題( x)(x E)為真。為真。由定義易知，對任意集合由定義易知，對任意集合A，都有，都有A E。在實際應用中，常常把某個適當大的集合看在實際應用中，常常把某個適當大的集合看成全集成全集 E。全集是有相對性的。全集是有相對性的。 不

8、含任何元素的集合，稱為不含任何元素的集合，稱為，記作記作，它可形式地表為：，它可形式地表為：= x|P(x)P(x) 其中：其中：P(x)為任何謂詞公式。為任何謂詞公式。由定義可知，對任何集合由定義可知，對任何集合A，有，有A。這是。這是因為任意元素因為任意元素x，公式，公式xx A總是為真。總是為真。(2) ， ， ， ，該序列除第一項外，每項均以前面各項為元素的該序列除第一項外，每項均以前面各項為元素的集合。它即是集合。它即是在在1924年使用空集年使用空集給出給出自自然數然數的集合表示：的集合表示：0:=，1:= ，2:= , ， 空集是一切集合的子集。空集是一切集合的子集。 空集是唯一

9、的。空集是唯一的。 () 對任一集合對任一集合A，有，有A A。() 若若A B且且B C，則，則A C。三、集合的基數三、集合的基數 表示集合中元素多少或度量集合大小的數，稱作表示集合中元素多少或度量集合大小的數，稱作集合的集合的或勢。一個集合或勢。一個集合A的基數，記為的基數，記為|A|。 如果一個集合恰有如果一個集合恰有m個不同的元素，且個不同的元素，且m是某個是某個非負整數，稱該集合是非負整數，稱該集合是有限的有限的或或有窮的有窮的，否則稱這，否則稱這個集合為個集合為無限的無限的或或無窮的無窮的。 例如：例如： Nm=0,1,2,m-1為含為含m個元素的有窮集。個元素的有窮集。N =

10、0, 1, 2, 3, ，即自然數集合。，即自然數集合。Z = , -2, -1, 0, 1, 2, 3, ，即整數集合。，即整數集合。Z+ = 1, 2, 3, ，即正整數集合。，即正整數集合。Q = 有理數集合。有理數集合。R = 實數集合。實數集合。C = 復數集合。復數集合。四、集合的冪集四、集合的冪集 一個集合的冪集是指以該集合所有子集為元素的一個集合的冪集是指以該集合所有子集為元素的集合，即是由這些子集所組成的集合族。集合，即是由這些子集所組成的集合族。 設設A為一集合，為一集合，A的的是一集合族，記是一集合族，記為為 (A)， (A) = B|B A 由定義可知，由定義可知， (

11、A)，A (A)。任給一個任給一個n元集，怎樣求出它的全部子集？元集，怎樣求出它的全部子集？ (A)有有2n個元素。個元素。五、文氏圖五、文氏圖 文氏文氏(Venn)圖是一種利用平面上的點構圖是一種利用平面上的點構成的圖形來形象展示集合的一種方法。成的圖形來形象展示集合的一種方法。 全集全集E用一個矩形的內部表示，其他集用一個矩形的內部表示，其他集合用矩形內的園面或一封閉曲線圈成的面積合用矩形內的園面或一封閉曲線圈成的面積來表示。來表示。如果如果A B，則表示，則表示A的圓面一般將完全落在表示的圓面一般將完全落在表示B的圓面的圓面內，如圖中內，如圖中(a)。如果如果A與與B沒有公共元素沒有公共

12、元素，那么表示，那么表示A的圓面將同表示的圓面將同表示B的的圓面分開，如圖中圓面分開，如圖中(b)。當當A和和B是兩個是兩個任意的集合任意的集合時，可能會是：有些元素在時，可能會是：有些元素在A中但不在中但不在B中，有些元素在中，有些元素在B中卻不在中卻不在A中，有些元素同中，有些元素同時在時在A和和B中，有些元素則既不在中，有些元素則既不在A中也不在中也不在B中，因此用中，因此用圖中圖中(c)表示任意兩個集合表示任意兩個集合A和和B。集合運算是指用已知的集合去生成集合運算是指用已知的集合去生成新新的集合。的集合。假設所有集合都是假設所有集合都是全集全集E的子集，即這些集的子集，即這些集合是利

13、用子集公理得到的。下面依次介紹常合是利用子集公理得到的。下面依次介紹常見的集合運算。見的集合運算。 設設A和和B是任意兩個集合，是任意兩個集合， A和和B的的并并是集合，記為：是集合，記為：AB，AB = x | x A x B A和和B的的交交是集合，記為：是集合，記為：AB，AB = x | x A x B A和和B的的差差，或，或B關于關于A的的是集合，記為：是集合，記為：A B，A B = x | x A x B 一、并、交和差運算一、并、交和差運算 若若A和和B是集合，且是集合，且AB=，則，則稱稱A和和B是是不相交不相交的。的。 如果如果C是個是個集合族集合族，且，且C中任意兩個不

14、同元素中任意兩個不同元素都都不相交不相交，則稱，則稱C中的集合是互不相交的，或中的集合是互不相交的，或稱稱C是是兩兩不相交的集合族兩兩不相交的集合族。 任給集合任給集合A，B和和C，則：，則： AB=BA AB= BA (AB)C=A(BC) (AB)C=A(BC)該定理表明，集合該定理表明，集合并并和和交交運算滿足運算滿足交換律交換律和和結結合律。合律。 任給集合任給集合A、B和和C，則，則 A(BC)=(AB)(AC) A(BC)=(AB)(AC)該定理表明，集合運算該定理表明，集合運算并對交并對交、交對并交對并都是都是可分配可分配的。的。 任給集合任給集合A，B，C和和D，則，則 若若A

15、 B，則，則AB=B，AB=A 若若A B和和C D， 則則AC BD，AC BD AE=E，AE=A 任給集合任給集合A，B和和C，則，則 A (BC)=(A B)(A C) A (BC)=(A B)(A C) 集合集合A的補是集合，記為的補是集合，記為 A， A=E A=x|x Ex A=x|x A 任給集合任給集合A，則，則 A A=E， A A=。 任給集合任給集合A和和B，則，則B= A iff AB=E 且且 AB=該定理表明了若該定理表明了若A的補是的補是B，則，則B的補是的補是A，即即A和和B互補。補的唯一性。互補。補的唯一性。 E=， =E 任給集合任給集合A，則，則A=A。

16、該定理表明了，該定理表明了，A的補的補是的補的補是A。 任給集合任給集合A和和B，則，則 (AB)= A B， (AB)= A B。 任給集合任給集合A和和B，A和和B的的對稱差對稱差是是集合，記為集合，記為A B， A B =(A B)(B A)=x|(x Ax B)(x Bx A) 任給集合任給集合A和和B，則，則A B=(AB)( A B)=(AB) (AB) A B=A B A B=B A A A= A=A集合之間的關系和運算可以用文氏圖集合之間的關系和運算可以用文氏圖給予形象的描述給予形象的描述 二、集合代數與對偶原理二、集合代數與對偶原理 這里將形式地討論由集合、集合變元、集合運算

17、這里將形式地討論由集合、集合變元、集合運算和圓括號所構成的和圓括號所構成的以及集合代數中的以及集合代數中的。 與命題邏輯相似，對于給定集合實行集合運算，與命題邏輯相似，對于給定集合實行集合運算，可以生成可以生成的集合。同用大寫英文字母表示確定集合的集合。同用大寫英文字母表示確定集合一樣，也用大寫字母表示不確定的集合，前者稱為一樣，也用大寫字母表示不確定的集合，前者稱為集集合常元合常元，后者稱為，后者稱為集合變元集合變元。集合變元用以集合常元。集合變元用以集合常元代替后，才表示確定的集合。下面將給出集合的合式代替后，才表示確定的集合。下面將給出集合的合式公式定義。公式定義。 可按下列規則生成可按

18、下列規則生成： 單個集合變元是集合合式公式。單個集合變元是集合合式公式。 若若A是集合合式公式，則是集合合式公式，則A也是集合合式公式。也是集合合式公式。 若若A和和B是集合合式公式，則是集合合式公式，則(AB)，(AB)，(A B)和和(A B)也都是集合合式公式。也都是集合合式公式。 只有有限次使用、和構成的符號串才是集只有有限次使用、和構成的符號串才是集合合式公式。合合式公式。 簡稱集合合式公式為簡稱集合合式公式為。 用任意集合常元取代兩個集合公式用任意集合常元取代兩個集合公式中的各個集合變元，若所得集合是相等的，則中的各個集合變元，若所得集合是相等的，則稱該兩個集合公式是稱該兩個集合公

19、式是相等相等的，簡稱等式。的，簡稱等式。因為集合公式相等，不依賴于取代集合變元的因為集合公式相等，不依賴于取代集合變元的集合，故常稱這些等式為集合，故常稱這些等式為，或，或。它們刻劃了集合運算的某些性質，。它們刻劃了集合運算的某些性質，這些性質描述一個代數，稱為這些性質描述一個代數，稱為。下。下面列出常用面列出常用：（1）等冪律等冪律 AA=A AA=A（2）結合律結合律 (AB)C=A(BC) (AB)C=A(BC)（3）交換律交換律 AB=BA AB=BA（4）分配律分配律 A(BC)=(AB)(AC) A(BC)=(AB)(AC)（5）同一律同一律 A=A AE=A（6）零律零律AE=E

20、 A=（7）補余律補余律 AA=E AA=（8）吸收律吸收律 A(AB)=A A(AB)=A（9）德德摩根律摩根律 (AB)= AB (AB)= AB（10）雙重否定律雙重否定律 A=A一、有限集基數的有關結果一、有限集基數的有關結果設設A A、B B為任意有限集合，則有為任意有限集合，則有|AB| |A|+|B|-|AB| |AB| |A|+|B|-|AB| |AB|min(|A|,|B|)|AB|min(|A|,|B|)|A|A B|=|A|+|B|-2|AB|B|=|A|+|B|-2|AB|A-B|A|-|B| |A-B|A|-|B| (|A-B|+|B|=|AB|A|) (|A-B|+

21、|B|=|AB|A|) 任給集合任給集合A和和B，則，則 | |AB| = |A| |B| |AB|當當AB= ，則有，則有 |AB|=|A|+|B|。當當AB，則，則 |A| = |A(B B)| = |A B|+|AB| |B| = |B A|+|BA| |A|+|B| = |A B|+| AB|+|AB|+|AB| = |AB|+|AB| |AB| = |A|+|B|-|AB| 例：例：設某班有設某班有60名同學，其中班足球隊員有名同學，其中班足球隊員有28名，籃球隊員有名，籃球隊員有15名。若有名。若有25名同學沒有名同學沒有參加這二個隊，問同時參加這二個隊的隊員參加這二個隊，問同時參

22、加這二個隊的隊員有多少名？有多少名？解：解：設設A A為足球隊員集合，為足球隊員集合，B B為籃球隊員集合，為籃球隊員集合，則則 |AB|=60-25=35|AB|=60-25=35， |AB|=|A|+|B|-|AB|=28+15-35=8 |AB|=|A|+|B|-|AB|=28+15-35=8二、包含二、包含n n個集合的包含排斥原理個集合的包含排斥原理|A|A1 1AA2 2AAn n|=|= i=1n A Ai i - - 1ijn1ijn A Ai iAAj j + + 1ijkn1ijkn A Ai iAAj jAAk k + + (-1) (-1)n-1n-1 A A1 1AA

23、2 2AAn n 特別地，特別地，n=3n=3， |A|A1 1AA2 2AA3 3|=|A|=|A1 1|+|A|+|A2 2|+|A|+|A3 3|-|A|-|A1 1AA2 2|-|-|A|A1 1AA3 3|-|A|-|A2 2AA3 3|+|A|+|A1 1AA2 2AA3 3| |證明：證明：當當n=2時，結論成立。時，結論成立。設設n-1n-1時，結論成立，則時，結論成立，則|A|A1 1AA2 2AAn n| |=|=|i=1i=1n-1n-1A Ai i|+|A|+|An n|-|(|-|(i=1i=1n-1n-1A Ai i)A)An n| |= = i=1i=1n n A

24、 Ai i - - 1ijn-11ijn-1A Ai iAAj j+(-1)+(-1)n-2n-2|i=1i=1n-1n-1A Ai i|-|- I=1I=1n-1n-1A Ai iAAn n- - 1ijn-11ijn-1A Ai iAAj jAAn n+ + (-1) (-1)n-2n-2|i=1i=1n-1n-1A Ai iAAn n|= = i=1i=1n n A Ai i - - 1ijn1ijnA Ai iAAj j+(-1)+(-1)n-1n-1|i=1i=1n nA Ai i| |例：例：試決定在試決定在1到到100之間能被之間能被2，3，5中某一數整除的中某一數整除的數的個數

25、。數的個數。解：解：A1表示表示1到到100之間能被之間能被2整除的整數集，整除的整數集， A2表示表示1到到100之間能被之間能被3整除的整數集，整除的整數集， A3表示表示1到到100之間能被之間能被5整除的整數集，整除的整數集， 則則 |A1|=int(100/2)=50，|A2|=int(100/3)=33， |A3|=int(100/5)=20， |A1A2|=int(100/(2*3)=16， |A1A3|=int(100/(2*5)=10， |A2A3|=int(100/(3*5)=6 |A1A2A3|=int(100/(2*3*5)=3所以所以|A1A2A3|=|A1|+|A2

26、|+|A3|-|A1A2|-|A1A3|- |A2A3|+|A1A2A3|=50+33+20-16-10-6+3=74 笛卡爾積與無序積在后面討論關系和圖論時，都笛卡爾積與無序積在后面討論關系和圖論時，都有重要應用。有重要應用。 首先引入首先引入有序對有序對和和無序對無序對的概念。的概念。 由兩個具有固定次序的元素由兩個具有固定次序的元素a, b組成的組成的叫叫序偶序偶，并記作，并記作，其中：稱，其中：稱a為第一元為第一元素，素，b為第二元素。若它們無次序區分，稱為二元無為第二元素。若它們無次序區分，稱為二元無序組或序組或無序對無序對，記為，記為(a, b)。注：注：若若a b時，時， 。但。

27、但(a, b) = (b, a)。 兩個序偶相等兩個序偶相等 iff 例：例： 已知已知，求：求：x和和y。解：解：由有序對相等的充要條件有由有序對相等的充要條件有 x+252x+y4 解得解得 x3, y-2。 序偶的概念可進一步推廣：三元組、四元組、序偶的概念可進一步推廣：三元組、四元組、n元組：元組：1、三元組三元組是一個序偶，其第一元素是是一個序偶，其第一元素是序偶序偶，記作：，記作：注：注： 據定義：據定義： = , z , z x, 2、n元組元組：一個有序：一個有序n元組元組(n3)是一個有序對，其中第一元是一個有序對，其中第一元素是一個有序素是一個有序n-1元組元組，記作，記作

28、 即即 =,xn注：注： ,xn x1, = iff (x1=y1)(x2=y2)(xn-1=yn-1)(xn=yn) 設設A、B是任意兩個集合，則由第是任意兩個集合，則由第一元素屬于一元素屬于A，第二元素屬于，第二元素屬于B的所有序偶構的所有序偶構成的集合，叫做集合成的集合，叫做集合A和和B的笛卡爾積，記為的笛卡爾積，記為AB，即，即AB=|x Ay B1、假設、假設A表示某大學所有學生的集合，表示某大學所有學生的集合，B表示大學開設表示大學開設的所有課程的集合，的所有課程的集合，則則AB可用來表示該校學生選課的所有可能情況。可用來表示該校學生選課的所有可能情況。2、令、令A是直角坐標系中是

29、直角坐標系中x軸上的點集，軸上的點集，B是直角坐標系是直角坐標系中中y軸上的點集，軸上的點集，則則AB就與平面點集一一對應。就與平面點集一一對應。 3、設設A=a,b, B=0,1,2，則，則AB=,BA=, 若若|A|=n，|B|=m，則，則 |AB|=n m。笛卡爾積運算的性質：笛卡爾積運算的性質： B = A = 當當A B且且A、B均不空時，有均不空時，有AB BA (AB)C A(BC) 笛卡爾積對笛卡爾積對、滿足分配律滿足分配律 A CB D AB CD 任給集合任給集合A，B和和C，則，則 A(BC)=(AB)(AC) A(BC)=(AB)(AC) (AB)C=(AC)(BC)

30、(AB)C=(AC)(BC) A(BC)=(AB)(AC)的證明的證明任取任取 A(BC) xA yBC xA (yByC) (xAyB) (xAyC) AB AC (AB)(AC) A(BC)=(AB)(AC) 若若C ，則，則A B (AC BC) (CA CB)設設A、B、C、D為四個為四個非空非空集合，集合，則則AB CD 的充要條件為的充要條件為A C，B D。 該性質的該性質的不成立，可分以下情況討論。不成立，可分以下情況討論。（1）當）當A=B=時，顯然有時，顯然有A C 和和 B D 成立。成立。（2）當）當A且且B時，也有時，也有A C和和B D成立。成立。任取任取xA，由于，由于B，必存在，必存在yB，因此有，因此有 xAyB AB CD xCyD xC從而證明了從而證明了 A C。同理可證同理可證 B D。該性質的該性質的不成立，可分