第03章集合代數(shù)

1第03章集合代數(shù)

第三章集合代數(shù)3.1集合的概念和表示法3.2集合的運(yùn)算3.3包含排斥原理3.4集合的笛卡爾積與無序積3.1集合的概念與表示法一、集合與元素1、集合的描述定義所謂集合，是指某些可區(qū)分的不同對象的全體，將用大寫字母A，B，X，Y，···表示之。組成集合的對象稱為集合的元素或成員，將用小寫字母a，b，x，y···表示之。

a是A的元素或a屬于A，記作aA；

a不是A的元素或a不屬于A，記作aA，或者(aA)。2、集合的表示：表示一個特定集合，根本上有兩種方法：枚舉法：列出集合的所有元素，元素之間用逗號分開，再用花括號括起。如：A={a,e,i,o,u}

說明集合A是由字母a,e,i,o和u為元素構(gòu)成的。謂詞法：用謂詞公式來確定集合。即個體域中能使謂詞公式為真的那些元素，確定了一個集合。因為這些元素都具有某種特殊性質(zhì)。假設(shè)P(x)含有一個自由變元的謂詞公式，那么{x|P(x)}定義了集合S，并可表為：

S={x|P(x)}

由此可見，P(c)為真當(dāng)且僅當(dāng)cS。從而有xSP(x)=T集合的元素是彼此不同的。 如：{1，1，2，2，3}＝{1，2，3}集合的元素是無序的。 如：{1，2，3}＝{3，1，2}元素和集合之間的關(guān)系是隸屬關(guān)系，屬于記作，不屬于記作。 如：A＝{a，{b，c}，d，{ufgipzr}}

這里a∈A，{b，c}∈A，d∈A，{bssyh28}∈A， 但bA，5t0hbqeA?？梢杂靡环N樹形圖來表示這種隸屬關(guān)系，該圖分層構(gòu)成，每個層上的結(jié)點都表示一個集合，它的兒子就是它的元素。上例中集合A＝{a，{b，c}，d，{fmg7nae}}的樹形圖如下圖。圖中的a，b，c，d也是集合，由于所討論的問題與a，b，c，d的元素?zé)o關(guān)，所以沒有列出它們的元素。鑒于集合的元素是集合這一規(guī)定，隸屬關(guān)系可以看作是處在不同層次上的集合之間的關(guān)系。集合的元素一旦給定，這一集合便完全確立。這一事實被形式地表達(dá)為外延公理。外延公理：兩集合A和B相等，當(dāng)且僅當(dāng)它們有相同的元素。假設(shè)A與B相等，記為：A=B；否那么，記為：AB。外延公理可形式表為：

A=B(x)(xAxB)或者A=B(x)(xAxB)∧(x)(xBxA)

順便指出，在應(yīng)用外延公理證明集合A與B相等時，只需考察：對于任意元素x，應(yīng)有：xAxB

成立即可。這就是說，證明兩集合相等時可按此法行事。子集是描述一個集合與另一個集合之間的關(guān)系，其定義如下:

設(shè)A和B是任意兩個集合，如果集合A的每個元素，都是集合B中的一個元素，那么稱A是B的子集，或稱A被包含于B中，或者說B包含A，并記為AB。二、集合之間的關(guān)系集合包含的符號化表示：AB(x)(xAxB)說明：要證明AB，只需對任意元素x，有下式

xAxB 成立即可。如果AB且BA，那么稱A與B相等，記作A＝B。假設(shè)集合B不包含集合A，記為A?B。

設(shè)A和B是兩個集合，假設(shè)AB且AB，那么稱A是B的真子集，記為AB，也稱B真包含A。該定義也可表為

AB(AB∧AB)如果A不是B的真子集，那么記作AB。

如果一個集合包含了所要討論的每一個集合，那么稱該集合為全集，記為E。它可形式地表為E={x|P(x)∨?P(x)}其中：P(x)為任何謂詞公式。

顯然，全集E即是第二章中的全總個體域。于是，每個元素x都屬于全集E，即命題(x)(xE)為真。由定義易知，對任意集合A，都有AE。在實際應(yīng)用中，常常把某個適當(dāng)大的集合看成全集E。全集是有相對性的。

不含任何元素的集合，稱為空集，記作，它可形式地表為：={x|P(x)∧?P(x)}

其中：P(x)為任何謂詞公式。由定義可知，對任何集合A，有A。這是因為任意元素x，公式xxA總是為真。注意： 與{}是不同的。{}是以為元素的集合，而沒有任何元素，能用構(gòu)成集合的無限序列：(1)，{}，{{}}，···

該序列除第一項外，每項均以前一項為元素的集合。(2)，{}，{，{}}，···該序列除第一項外，每項均以前面各項為元素的集合。它即是馮·諾依曼在1924年使用空集給出自然數(shù)的集合表示：0:=，1:={}，2:={,{}}，···

空集是一切集合的子集。推論空集是唯一的。

(ⅰ)對任一集合A，有AA。

(ⅱ)假設(shè)AB且BC，那么AC。三、集合的基數(shù)

表示集合中元素多少或度量集合大小的數(shù)，稱作集合的基數(shù)或勢。一個集合A的基數(shù)，記為|A|。如果一個集合恰有m個不同的元素，且m是某個非負(fù)整數(shù)，稱該集合是有限的或有窮的，否那么稱這個集合為無限的或無窮的。例如：Nm={0,1,2,···,m-1}為含m個元素的有窮集。常見的無窮集合有：N={0,1,2,3,···}，即自然數(shù)集合。Z={···,-2,-1,0,1,2,3,···}，即整數(shù)集合。Z+={1,2,3,···}，即正整數(shù)集合。Q=有理數(shù)集合。R=實數(shù)集合。C=復(fù)數(shù)集合。四、集合的冪集

一個集合的冪集是指以該集合所有子集為元素的集合，即是由這些子集所組成的集合族。設(shè)A為一集合，A的冪集是一集合族，記為(A)，(A)={B|BA}由定義可知，(A)，A(A)。任給一個n元集，怎樣求出它的全部子集？如果有限集合A有n個元素，那么其冪集(A)有2n個元素。五、文氏圖

文氏(Venn)圖是一種利用平面上的點構(gòu)成的圖形來形象展示集合的一種方法。全集E用一個矩形的內(nèi)部表示，其他集合用矩形內(nèi)的園面或一封閉曲線圈成的面積來表示。如果AB，那么表示A的圓面一般將完全落在表示B的圓面內(nèi)，如圖中(a)。如果A與B沒有公共元素，那么表示A的圓面將同表示B的圓面分開，如圖中(b)。當(dāng)A和B是兩個任意的集合時，可能會是：有些元素在A中但不在B中，有些元素在B中卻不在A中，有些元素同時在A和B中，有些元素那么既不在A中也不在B中，因此用圖中(c)表示任意兩個集合A和B。3.2集合的運(yùn)算集合運(yùn)算是指用的集合去生成新的集合。假設(shè)所有集合都是全集E的子集，即這些集合是利用子集公理得到的。下面依次介紹常見的集合運(yùn)算。

設(shè)A和B是任意兩個集合，①A和B的并是集合，記為：A∪B，A∪B={x|xA∨xB}②A和B的交是集合，記為：A∩B，A∩B={x|xA∧xB}③A和B的差，或B關(guān)于A的相對補(bǔ)是集合，記為：AB，AB={x|xA∧xB}一、并、交和差運(yùn)算

假設(shè)A和B是集合，且A∩B=，那么稱A和B是不相交的。如果C是個集合族，且C中任意兩個不同元素都不相交，那么稱C中的集合是互不相交的，或稱C是兩兩不相交的集合族。

任給集合A，B和C，那么： ①A∩B=B∩A ②A∪B=B∪A ③(A∪B)∪C=A∪(B∪C) ④(A∩B)∩C=A∩(B∩C)該定理說明，集合并和交運(yùn)算滿足交換律和結(jié)合律。

任給集合A、B和C，那么 ①A∪(B∩C)=(A∪B)∩(A∪C) ②A∩(B∪C)=(A∩B)∪(A∩C)該定理說明，集合運(yùn)算并對交、交對并都是可分配的。

任給集合A，B，C和D，那么 ①假設(shè)AB，那么A∪B=B，A∩B=A ②假設(shè)AB和CD，那么A∪CB∪D，A∩CB∩D①A∪E=E，②A∩E=A

任給集合A，B和C，那么 ①A(B∪C)=(AB)∩(AC) ②A(B∩C)=(AB)∪(AC)集合A的補(bǔ)是集合，記為A，A=EA={x|xE∧xA}={x|xA}任給集合A，那么 ①A∪A=E， ②A∩A=。任給集合A和B，那么 B=AiffA∪B=E且A∩B=該定理說明了①假設(shè)A的補(bǔ)是B，那么B的補(bǔ)是A，即A和B互補(bǔ)。②補(bǔ)的唯一性。①E=，②=E任給集合A，那么A=A。該定理說明了，A的補(bǔ)的補(bǔ)是A。任給集合A和B，那么 ①(A∪B)=A∩B， ②(A∩B)=A∪B。任給集合A和B，A和B的對稱差是集合，記為AB，AB=(AB)∪(BA) ={x|(xA∧xB)∨(xB∧xA)}任給集合A和B，那么AB=(A∪B)∩(A∪B)=(A∪B)(A∩B)

①AB=AB ②AB=BA ③AA=④A=A集合之間的關(guān)系和運(yùn)算可以用文氏圖給予形象的描述二、集合代數(shù)與對偶原理這里將形式地討論由集合、集合變元、集合運(yùn)算和圓括號所構(gòu)成的集合代數(shù)以及集合代數(shù)中的對偶原理。與命題邏輯相似，對于給定集合實行集合運(yùn)算，可以生成新的集合。同用大寫英文字母表示確定集合一樣，也用大寫字母表示不確定的集合，前者稱為集合常元，后者稱為集合變元。集合變元用以集合常元代替后，才表示確定的集合。下面將給出集合的合式公式定義?？砂匆韵乱?guī)那么生成集合合式公式：①單個集合變元是集合合式公式。②假設(shè)A是集合合式公式，那么～A也是集合合式公式。③假設(shè)A和B是集合合式公式，那么(A∪B)，(A∩B)，(AB)和(AB)也都是集合合式公式。④只有有限次使用①、②和③構(gòu)成的符號串才是集合合式公式。簡稱集合合式公式為公式。用任意集合常元取代兩個集合公式中的各個集合變元，假設(shè)所得集合是相等的，那么稱該兩個集合公式是相等的，簡稱等式。因為集合公式相等，不依賴于取代集合變元的集合，故常稱這些等式為集合恒等式，或集合定律。它們刻劃了集合運(yùn)算的某些性質(zhì)，這些性質(zhì)描述一個代數(shù)，稱為集合代數(shù)。下面列出常用集合定律：〔1〕等冪律A∪A=A A∩A=A〔2〕結(jié)合律(A∪B)∪C=A∪(B∪C) (A∩B)∩C=A∩(B∩C)〔3〕交換律A∪B=B∪A A∩B=B∩A〔4〕分配律A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C)〔5〕同一律A∪=A A∩E=A〔6〕零律 A∪E=E A∩=〔7〕補(bǔ)余律A∪～A=E A∩～A=〔8〕吸收律 A∪(A∩B)=A A∩(A∪B)=A〔9〕德·摩根律～(A∪B)=～A∩～B ～(A∩B)=～A∪～B〔10〕雙重否認(rèn)律 ～～A=A3.3包含排斥原理一、有限集基數(shù)的有關(guān)結(jié)果 設(shè)A、B為任意有限集合，那么有

|A∪B|≤|A|+|B|-|A∩B| |A∩B|≤min(|A|,|B|) |AB|=|A|+|B|-2|A∩B| |A-B|≥|A|-|B|(∵|A-B|+|B|=|A∪B|≥|A|)任給集合A和B，那么 |A∪B|=|A||B||A∩B|證明：①當(dāng)A∩B=，那么有|A∪B|=|A|+|B|。②當(dāng)A∩B，那么 |A|=|A∩(B∪B)|=|A∩B|+|A∩B| |B|=|B∩A|+|B∩A| |A|+|B|=|A∩B|+|A∩B|+|A∩B|+|A∩B|=|A∪B|+|A∩B| ∴|A∪B|=|A|+|B|-|A∩B|{包含排斥原理}例：設(shè)某班有60名同學(xué)，其中班足球隊員有28名，籃球隊員有15名。假設(shè)有25名同學(xué)沒有參加這二個隊，問同時參加這二個隊的隊員有多少名？解：設(shè)A為足球隊員集合，B為籃球隊員集合，那么

|A∪B|=60-25=35，∴|A∩B|=|A|+|B|-|A∪B|=28+15-35=8二、包含n個集合的包含排斥原理|A1∪A2∪……∪An|=i=1nAi-1≤i<j≤nAi∩Aj+1≤i<j<k≤nAi∩Aj∩Ak+……(-1)n-1A1∩A2∩……∩An特別地，n=3，|A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1∩A2|- |A1∩A3|-|A2∩A3|+|A1∩A2∩A3|證明：當(dāng)n=2時，結(jié)論成立。 設(shè)n-1時，結(jié)論成立，那么|A1∪A2∪……∪An|=|∪i=1n-1Ai|+|An|-|(∪i=1n-1Ai)∩An|=i=1nAi-1≤i<j≤n-1Ai∩Aj+……(-1)n-2|∩i=1n-1Ai|-[I=1n-1Ai∩An-1≤i<j<n-1Ai∩Aj∩An+……(-1)n-2|∩i=1n-1Ai∩An|]=i=1nAi-1≤i<j≤nAi∩Aj+……(-1)n-1|∩i=1nAi|例：試決定在1到100之間能被2，3，5中某一數(shù)整除的數(shù)的個數(shù)。解：A1表示1到100之間能被2整除的整數(shù)集，

A2表示1到100之間能被3整除的整數(shù)集，

A3表示1到100之間能被5整除的整數(shù)集，那么|A1|=int(100/2)=50，|A2|=int(100/3)=33，

|A3|=int(100/5)=20，|A1∩A2|=int(100/(2*3))=16，|A1∩A3|=int(100/(2*5))=10，

|A2∩A3|=int(100/(3*5))=6|A1∩A2∩A3|=int(100/(2*3*5))=3所以|A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1∩A2|-|A1∩A3|-|A2∩A3|+|A1∩A2∩A3|=50+33+20-16-10-6+3=743.4集合的笛卡爾積與無序積

笛卡爾積與無序積在后面討論關(guān)系和圖論時，都有重要應(yīng)用。首先引入有序?qū)蜔o序?qū)Φ母拍?。一、序偶由兩個具有固定次序的元素a,b組成的有序?qū)行蚺?，并記?lt;a,b>，其中：稱a為第一元素，b為第二元素。假設(shè)它們無次序區(qū)分，稱為二元無序組或無序?qū)Γ洖?a,b)。注：假設(shè)ab時，<a,b><b,a>。但(a,b)=(b,a)。序偶的性質(zhì)：①由兩個元素組成的序偶是有序的。即當(dāng)xy時，有<x,y><y,x>。假設(shè)<x,y><y,x>iffxy。②兩個序偶相等<x,y><u,v> iff<xu>∧<yv>例：<x+2,4>＝<5,2x+y>，求：x和y。解：由有序?qū)ο嗟鹊某湟獥l件有

x+2＝5

2x+y＝4

解得x＝3,y＝-2。二、n元序偶 序偶的概念可進(jìn)一步推廣：三元組、四元組、……n元組：1、三元組是一個序偶，其第一元素是序偶，記作：<x,y,z>注：①據(jù)定義：<x,y,z>=<<x,y>,z>②<<x,y>,z><x,<y,z>>2、n元組：一個有序n元組(n≥3)是一個有序?qū)Γ渲械谝辉厥且粋€有序n-1元組，記作<x1,x2,···,xn-1,xn>即

<x1,x2,···,xn-1,xn>=<<x1,x2,···,xn-1>,xn>注：①<<x1,x2,···,xn-1>,xn><x1,<x2,···,xn-1,xn>> ②<x1,x2,···,xn-1,xn>=<y1,y2,···,yn-1,yn> iff

(x1=y1)∧(x2=y2)∧···∧(xn-1=yn-1)∧(xn=yn)三、笛卡爾積設(shè)A、B是任意兩個集合，那么由第一元素屬于A，第二元素屬于B的所有序偶構(gòu)成的集合，叫做集合A和B的笛卡爾積，記為AB，即AB={<x,y>|xA∧yB}笛卡爾積舉例1、假設(shè)A表示某大學(xué)所有學(xué)生的集合，B表示大學(xué)開設(shè)的所有課程的集合，那么

A×B可用來表示該校學(xué)生選課的所有可能情況。2、令A(yù)是直角坐標(biāo)系中x軸上的點集，B是直角坐標(biāo)系中y軸上的點集，那么

A×B就與平面點集一一對應(yīng)。3、設(shè)A={a,b},B={0,1,2}，那么

A×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>} B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}定理3.4.1假設(shè)|A|=n，|B|=m，那么

|AB|=n?m。笛卡爾積運(yùn)算的性質(zhì)： ①B=A= ②當(dāng)AB且A、B均不空時，有ABBA ③(AB)CA(BC) ④笛卡爾積對∪、∩滿足分配律 ⑤AC∧BDABCD任給集合A，B和C，那么①A(B∪C)=(AB)∪(AC)②A(B∩C)=(AB)∩(AC)③(A∪B)C=(AC)∪(BC)④(A∩B)C=(AC)∩(BC)①

A×(B∪C)=(A×B)∪(A×C)的證明證：任取<x,y> <x,y>∈A×(B∪C) x∈A∧y∈B∪C x∈A∧(y∈B∨y∈C) (x∈A∧y∈B)∨(x∈A∧y∈C) <x,y>∈A×B∨<x,y>∈A×C <x,y>∈(A×B)∪(A×C)

A×(B∪C)=(A×B)∪(A×C)假設(shè)C≠，那么 AB(ACBC)(CACB)定理3.4.4設(shè)A、B、C、D為四個非空集合，那么ABCD的充要條件為AC，BD。關(guān)于AC∧BDA×BC×D的討論該性質(zhì)的逆命題不成立，可分以下情況討論?！?〕當(dāng)A=B=時，顯然有AC和BD成立?！?〕當(dāng)A≠且B≠時，也有AC和BD成立。證：任取x∈A，由于B≠，必存在y∈B，因此有

x∈A∧y∈B <x,y>∈A×B <x,y>∈C×D x∈C∧y∈D x∈C

從而證明了AC。 同理可證BD。關(guān)于AC∧BDA×BC×D的討論該性質(zhì)的逆命題不成立，可分以下情況討論?！?〕當(dāng)A=B=時，顯然有AC和BD成立。〔2〕當(dāng)A≠且B≠時，也有AC和BD成立。證：任取x∈A，由于B≠，必存在y∈B，因此有

x∈A∧y∈B <x,y>∈A×B <x,y>∈C×D x∈C∧y∈D x∈C

從而證明了AC。 同理可證BD。關(guān)于AC∧BDA×BC×D的討論〔