離散數(shù)學(xué)課件2

1第一章集合2集合是數(shù)學(xué)中最基本的概念。既然是最基本的概念，就不是很好定義，一般只是說明。要說明什么是集合，有多種描述方法：“所要討論的一類對象的整體”；“具有同一性質(zhì)單元的集體”等。當(dāng)我們討論某一類對象的時候，就把這一類對象的整體稱為集合。而集合中的對象就成為該集合中的元素。Cantor是這樣描述集合的：所謂集合，是指我們無意中或思想中將一些確定的，彼此完全不同的客體的總和考慮為一個整體。這些客體叫做該集合的元素。31.2集合的概念和集合之間的關(guān)系

1.3集合的運算

1.4基本的集合恒等式*1.5集合列的極限41.2集合的概念和集合之間的關(guān)系集合的概念集合的表示集合間的關(guān)系冪集集族56集合的表示：集合用大寫字母，集合元素用小寫字母。如xA，yA。（1）列舉法----列出集合中的全體元素，元素之間用逗號分開，用花括號{…}括起來。例：設(shè)A是由a,b,c,d為元素的集合，B是正偶數(shù)集合，則A={a,b,c,d},B={2,4,6,8,…}（2）描述法----通過說明集合中元素所具有的共同的性質(zhì)來定義一個集合。用謂詞P(x)表示x具有性質(zhì)P，{x|P(x)}表示具有性質(zhì)P的集合。例：P(x):x是英文字母，Q(y):y是十進制數(shù)字。則C={x|P(x)}和D={y|Q(y)}分別表示26個英文字母和10個十進制數(shù)字集合。7注意：1）集合中的元素各不相同2）集合中的元素不規(guī)定順序3）集合的兩種表示方法有時是可以相互轉(zhuǎn)化的例：B={x|xN且x為非0偶數(shù)}，或{x|x=2(k+1)且kN}8幾個常用的集合及其記號：N(自然數(shù)集合):+*封閉,逆運算不封閉Z(整數(shù)集合):+及其逆運算,*封閉,但*的逆運算不封閉Q(有理數(shù)集合):

+,*,逆運算封閉，全序域，具有稠密性空隙（不連通）R(實數(shù)集合)C(復(fù)數(shù)集合)9集合之間的關(guān)系子集、相等、真子集空集、全集冪集、n元集、有限集集族10定義1.1

給定集合Ａ和Ｂ，如果B中每個元素都是A中的元素，則稱B為A的子集，記作ＢＡ或ＡＢ，讀作“Ｂ包含于Ａ”或“Ａ包含Ｂ”。

AB(x)(x∈A→x∈B)設(shè)A={a,b,c},B={a,b,c,d},C={a,b}，則AB,CA,CB

按子集的定義，對于任何集合A、B、C，

AA(自反性)(AB)∧(BC)(AC)(傳遞性)11“A是B的子集(subset)”，記作AB是指：（1）A中的所有元素都是B的元素?；蛘撸?）在A中找不到一個不屬于B的元素?；蛘撸?）對xA，均有xB?！癆不是B的子集”是指：

A中至少有一個元素不屬于B。（xA，但xB）記作A

B。

12證明：AB(x)(x∈AxB)證明：AB(AB) ((x)(x∈A→x∈B)) (x)((x∈A)(x∈B))

(x)(x∈AxB)13定義1.2兩個Ａ和Ｂ，若A包含B且B包含A，則稱A與B相等，記作Ａ＝Ｂ。集合Ａ與Ｂ不相等，記作Ａ≠Ｂ。

A=B(x)(x∈Ax∈B)

(AB)(BA)例：設(shè)A={2},B={1，4},C={x|x2-5x+4=0},D={x|x為偶素數(shù)}則A=D,B=C14定義1.3

給定集合Ａ和Ｂ，如果ＡＢ且Ａ≠Ｂ，則稱Ａ為Ｂ的真子集，記作ＡＢ。

AB(x)(x∈A→x∈B)∧(x)(x∈B∧xA)設(shè)三個集合Ａ，Ｂ，C，從定義可以得到下面3個命題為真：AA;(2)若AB，則BA;(3)若AB且BC，則AC15空集

定義1.4

不含任何元素的集合叫空集，記作Φ。例如，

Φ＝{x|P(x)∧P(x)}，P(x)是任意謂詞。

A={x|x∈R∧x2＋1＝0}是空集，式中Ｒ表示實數(shù)集合。全集定義1.5在研究某一問題時，如果限定所討論的集合都是某一集合的子集，則稱該集合為全集，記作Ｅ。即

Ｅ＝{x|P(x)∨P(x)}。（P(x)是任意謂詞）顯然，全集的概念相當(dāng)于論域，它是一個相對概念。例如，如果討論(a,b)上的實數(shù)，就取(a,b)為全集。也可以取[a,b),(a,b],實數(shù)集R等為全集。16

定理1.1

空集是任意集合的子集。證明：

推論

空集是唯一的。證明：反證法17

定理1.1

空集是任意集合的子集。證明：任給集合Ａ，Φ是空集。則（x)(x∈Φ→x∈A)永真，這是因為條件式的前件(x∈Φ)永假，所以該條件式對一切ｘ皆為真。按子集的定義，ΦA(chǔ)為真。#

推論

空集是唯一的。證明：證：假定Φ1和Φ2為二空集。由定理2，Φ1Φ2，Φ2Φ1。再根據(jù)定理1，Φ1＝Φ2

。#18定義1.6

集合Ａ的所有子集構(gòu)成的集合叫Ａ的冪集，記作P(A)。用描述法表示為：P(A)={x|xA}。性質(zhì)（1）xP(A)當(dāng)且僅當(dāng)x

A。（2）設(shè)A,B是兩個集合,AB當(dāng)且僅當(dāng)P(A)P(B)。19例,設(shè)Ａ＝{a,b,c},則0元子集：Φ；1元子集：{a},,{c}；2元子集：{a,b},{a,c},{b,c}3元子集：{a,b,c}

P(A)＝{Φ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}含有n個元素的集合為n元集(n1)20定理1.2設(shè)A有ｎ個元素，則P(A)有2n個元素。

在(x+y)n的展開式中令x=y=1得：另外，因ΦA(chǔ)，故P(A)中元素的個數(shù)Ｎ可表示為：證明：A的所有由ｋ個元素組成的子集個數(shù)為從ｎ個元素中?。雮€元素的組合數(shù)：#21定義1.7

設(shè)A為一個集族，S為一個集合，若對于任意的S,存在唯一的ＡA與之對應(yīng)，而且A中的任何集合都對應(yīng)S中的某一個元素，則稱A是以S為指標(biāo)集的集族，S稱為Ａ的指標(biāo)集。

為空集族集族：由集合構(gòu)成的集合定義：設(shè)A是一個集合。若A的元素都是集合，則稱A為集合族。若集合族A可表示為A={Sd|dD},則稱D為集合族A的指標(biāo)集。22例如[1]設(shè)A1={x|xNx為奇數(shù)}，A2={x|xNx為偶數(shù)}，則{A1,A2}是以{1,2}為指標(biāo)集的集族[2]P(A)是一個集合族，設(shè)A1,A2,A3,...是集合的序列，且兩兩之間互不相同，則集合{A1,A2,A3,...}是一個集合族，可表示為{Ai|iZ}，其中Z為自然數(shù)集合，是指標(biāo)集。[3]設(shè)p是一個素數(shù)，Ak={x|x=k(modp)},k=0,1,…,p-1,則{A1,A2,…,Ap-1}是以{0,1,2,…,p-1}為指標(biāo)集的集族23多重集合設(shè)全集為E，E中元素可以不止一次在A中出現(xiàn)的集合A，稱為多重集合.若E中元素在A中出現(xiàn)k(k0)次，則稱在A中的重復(fù)度為k.例：設(shè)全集E={a,b,c,d,e}，A={a,a,b,b,c}為多重集合，其中a,b的重復(fù)度為2，c的重復(fù)度為1，而d,e的重復(fù)度均為0。集合可看作是各元素重復(fù)度均小于等于1的多重集合。241.3集合的運算定義1.8

設(shè)Ａ、Ｂ為兩個集合，稱由Ａ與Ｂ的所有元素組成的集合為Ａ與Ｂ的并集，記作Ａ∪Ｂ，稱∪為并運算符，A∪B的描述法表示為A∪B＝{x│x∈A∨x∈B}設(shè)：A={x|x∈N5x10}，B={x|x∈Nx10x為素數(shù)},則A∪B={2,3,5,6,7,8,9,10}25集合的并運算可以推廣到有限個或可數(shù)個集合26定義1.9

設(shè)Ａ、Ｂ為兩個集合，稱由Ａ與Ｂ的公共元素組成的集合為Ａ與Ｂ的交集，記作Ａ∩Ｂ，稱∩為交運算符，A∩B的描述法表示為A∩B＝{x│x∈A∧x∈B}設(shè)：A={x|x∈N5x10}，B={x|x∈Nx10x為素數(shù)},則A∩B={5,7}集合的交運算可以推廣到有限個或可數(shù)個集合27定義1.10

設(shè)Ａ、Ｂ為兩個集合，若Ａ∩Ｂ=?，則稱A,B是不交的，設(shè)A1,

A2，…是可數(shù)個集合，若對于任意的ij，均有Ａi∩Aj=?,則稱A1,

A2，…是不相交的28定義1.11

設(shè)Ａ、Ｂ為兩個集合，稱屬于Ａ而不屬于Ｂ的全體元素組成的集合為B對Ａ的相對補集，記作Ａ－Ｂ，稱－為相對補運算符，A－B的描述法表示為

A－B＝{x│x∈A∧xB}定義1.13

設(shè)E為全集，AE，稱A對E的相對補集為A的絕對補集，并將E－A簡記為A，稱為絕對補運算符，A的描述表示為A={x│x∈E∧xA}29定義1.12

設(shè)Ａ、Ｂ為兩個集合，稱屬于Ａ而不屬于Ｂ,或?qū)儆贐而不屬于A的全體元素組成的集合為Ａ與B的對稱差，記作ＡＢ，稱為對稱差運算符，AB的描述法表示為AB＝{x│(x∈A∧xB)∨(xA∧x∈B)}AB=（A－B）∪（B－A）＝（A∪B）－（A∩B）設(shè)：A={x|x∈R0

x<2}，B={x|x∈R1

x<3},則A–B={x|x∈R0

x<1}=[0,1)B-A={x|x∈R2

x<3}=[2,3)AB=[0,1)∪[2,3)將R作為全集，則~A=(-,0)∪[2,+)30用文氏圖可將集合表示如下：A∩B＝{x│x∈A∧x∈B}A∪B＝{x│x∈A∨x∈B}A－B＝{x│x∈A∧xB}AB＝（A－B）∪（B－A）A={x│x∈E∧xA}文氏圖：用矩形代表全集，用圓或其他閉合曲線的內(nèi)部代表E的子集，并將運算結(jié)果得到的集合用陰影部分表示。注意：文氏圖只是對某些集合之間的關(guān)系及運算結(jié)果給出一種直觀而形象的示意性的表示，而不能用來證明集合等式及包含關(guān)系。31例2

設(shè)Ｅ＝{a,b,c,d},A＝{a,c},B＝{a,b,c,d},c＝Φ,

求A,B,C。解：例1設(shè)A＝{1,2,3}，B＝{1,4}，C＝{3}。求A∪B,B∪AA∩B,B∩A,A－B,AB,C∩A,B∩C。解:32例2

設(shè)Ｅ＝{a,b,c,d},A＝{a,c},B＝{a,b,c,d},c＝Φ,

求A,B,C。解：A＝{b,d}，B＝Φ，C＝{a,b,c,d}＝E。例1設(shè)A＝{1,2,3}，B＝{1,4}，C＝{3}。求A∪B,B∪AA∩B,B∩A,A－B,AB,C∩A,B∩C。解:A∪B＝{1,2,3,4}＝B∪AA∩B＝{1}＝B∩AA－B＝{2,3}AB＝{2,3,4}C∩A＝{3},B∩C＝Φ33定義1.14

設(shè)A為一個集族，稱由A中全體元素的元素組成的集合為A的廣義并集，記作∪A，稱∪為廣義并運算符，讀作“大并”，∪A的描述法表示為∪A

＝{x│z(z∈A∧x∈z)}例：設(shè)A={{a,b},{c,d},{d,e,f}},則∪A={a,b,c,d,e,f}定義1.15

設(shè)A為非空的集族，稱由A中全體元素的公共元素組成的集合為A的廣義交集，記作∩A，稱∩為廣義交運算符，讀作“大交”，∩A的描述法表示為

∩A

＝{x│z(z∈A

x∈z)}例：設(shè)A={{1,2,3},{1,a,b},{1,6,7}},則∩A={1}34廣義并、廣義交舉例35第一類運算：絕對補，求冪集，廣義并，廣義交按由右到左的順序進行第二類運算：并，交，相對補，對稱差往往由括號決定，按左向右的順序進行運算的優(yōu)先級36有窮集合的計算—包含排斥原理設(shè)A1，A2，

…，An為n個集合，則此定理稱為包含排斥原理，簡稱容斥定理3738容斥定理的應(yīng)用[