離散數(shù)學第三章第一節(jié)

第三章集合與關(guān)系集合的概念是現(xiàn)代數(shù)學中最基本的概念之一，集合論是現(xiàn)代數(shù)學的重要理論基礎(chǔ)，并且深入到各個科學與技術(shù)領(lǐng)域之中。對計算機科學而言，它在開關(guān)理論，數(shù)據(jù)結(jié)構(gòu)與形式語言等領(lǐng)域中有著廣泛的應(yīng)用。本章介紹集合論的基礎(chǔ)知識，包括集合的運算、性質(zhì)、序偶、關(guān)系、函數(shù)、基數(shù)等。在方法上盡量采用前兩章的符號和推理規(guī)則，作出形式的證明。1第三章目錄第3-1講集合的概念和集合的運算第3-2講笛卡兒積與關(guān)系第3-3講復合關(guān)系、逆關(guān)系與閉包運算第3-4講等價關(guān)系第3-5講序關(guān)系2第3-1講集合的概念和運算1.集合的概念2.集合的表示3.集合間的關(guān)系4.冪集5.集合的運算6.集合運算的性質(zhì)7.課堂練習8.第3-1講作業(yè)31、集合的概念集合是數(shù)學中最基本的概念之一，如同幾何中的點、線等概念一樣，不能再用其它有明確定義的詞來定義它。

將一些確定的、彼此不同的事物的全體稱之為集合。對于給定的集合和事物，應(yīng)能判斷這個特定的事物是否屬于給定的集合。集合中的事物稱為該集合的元素。通常，用大寫的英文字母表示集合，用小寫英文字母表示集合的元素。例如，習慣上用Ｎ表示非負整數(shù)的集合，用Ｑ表示有理數(shù)集合，Ｒ表示實數(shù)集合等等。如果ａ是集合Ｓ的元素,記作ａ∈Ｓ,讀作“ａ屬于Ｓ”。如ｂ不是Ｓ的元素，記作bＳ，讀作“ｂ不屬于Ｓ”，它等價于（b∈s）。若一個集合的元素個數(shù)是有限的，則稱為有限集，否則稱為無限集。42、集合的表示列舉法：列出集合的所有元素，并用花括號括起來，元素之間用逗號隔開。例如：

S={e1,e2,…,en}(具有n個元素的有限集)Ａ＝{a,{b,c},{ie00ewm}}（a,{b,c},{c26mkgc}是該集合的元素）Ｎ＝{0,1,2,3,...}(N是非負整數(shù)集)在一個集合中，元素是彼此不同的，相同的元素被認為是一個元素，而且元素之間沒有次序關(guān)系，例如集合{1,2,3}，{3,1,2}和{3,3,1,2}被視為同一個集合。敘述法（或描述法）

用謂詞概括出集合中元素的特性，以確定集合的元素。S＝{x|Ｐ(x)}，如果Ｐ(e)為真，那麼e∈S，否則eS。例如，設(shè)A＝{x|x∈Ｎ∧3＜x≤8}，則A＝{4,5,6,7,8}。52、集合的表示（續(xù)）空集

定義1不含任何元素的集合叫空集，記作Φ。

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

例如，A={x∈R∧x2＋1＝0}是空集，式中Ｒ表示實數(shù)集合。全集定義2在研究某一問題時，如果所有涉及的集合都是某一集合的部分元素組成的（子集），則稱該集合為全集，記作Ｅ。即

Ｅ＝{x|P(x)∨P(x)}。（P(x)是任意謂詞）顯然，全集的概念相當于論域，它是一個相對概念。63、集合間的關(guān)系兩個集合相等，當且僅當它們有相同的成員。集合Ａ與Ｂ相等，記作Ａ＝Ｂ。集合Ａ與Ｂ不相等，記作Ａ≠Ｂ。定義１

給定集合Ａ和Ｂ，如果Ａ中每個元素都是Ｂ中的元素，則稱Ａ為Ｂ的子集，記作ＡＢ或ＢＡ，讀作“Ａ包含于Ｂ”或“Ｂ包含Ａ”。如果ＡＢ且Ａ≠Ｂ，則稱Ａ為Ｂ的真子集，記作ＡＢ。AB(x)(x∈A→x∈B)AB(x)(x∈A→x∈B)∧(x)(x∈B∧xA)按子集的定義，對于任何集合A、B、C都有AA(自反性)，(AB)∧(BC)(AC)(傳遞性)73、集合間的關(guān)系（續(xù)1）定理１

設(shè)Ａ、Ｂ為兩個集合，Ａ＝Ｂ當且僅當ＡＢ且ＢＡ。即(A＝B)AB∧BA。證明：兩個集合相等，則它們有相同的元素。(A＝B)(x)(x∈A→x∈B)∧(x)(x∈B→x∈A)

(AB)∧(BA)。反之，若(AB)∧(BA)，如果A≠B，則A與B的元素不完全相同。設(shè)x∈A但xB，這與AB矛盾；或x∈B但xA，這與BA矛盾，故A與B的元素必相同，即A＝B。

定理２

空集是任意集合的子集。證明：任給集合Ａ，Φ是空集。則（x)(x∈Φ→x∈A)永真，這是因為條件式的前件(x∈Φ)永假，所以該條件式對一切ｘ皆為真。按子集的定義，ΦA(chǔ)為真。83、集合間的關(guān)系（續(xù)2）例1證明對于任何集合A、B、C都有(AB)∧(BC)(AC)證：(AB)∧(BC)(x)(x∈A→x∈B)∧(x)(x∈B→x∈C)

(x)（(x∈A→x∈B)∧(x∈B→x∈C)）

(x)(x∈A→x∈C)AC例2

確定下列命題的真值⑴ΦΦ；⑵Φ∈Φ；⑶Φ{Φ}；⑷Φ∈{Φ}。解：⑴、⑶、⑷為真；（因為空集是任何集合的子集，所以⑴、⑶為真。）⑵為假。（因為空集不含任何元素。）93、集合間的關(guān)系（續(xù)3）例3

證明空集是唯一的證：假定Φ1和Φ2為二空集。由定理2，Φ1Φ2，Φ2Φ1。再根據(jù)定理1，Φ1＝Φ2。例4設(shè)集合Ｅ＝{a,b,c}，寫出它的所有可能的子集。解：集合Ｅ＝{a,b,c}的所有可能的子集是：

S0=Φ，S1={a}，S2=，S3={c}，S4={a,b}，S5={a,c}，S6={b,c}，S7={a,b,c}。104、冪集定義４集合Ａ的所有子集構(gòu)成的集合叫Ａ的冪集，記作ρ(A)。

根據(jù)定義，ρ(A)={X|XA}。例如,設(shè)Ａ＝{a,b,c},則

ρ(A)＝{Φ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}例5

設(shè)B＝{Φ,{Φ}}求ρ(B)。解：ρ(B)＝{Φ，{Φ}，{{Φ}}，{Φ,{Φ}}}114、冪集（續(xù)）定理３設(shè)A有ｎ個元素，則ρ(A)有2n個元素。

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

設(shè)Ａ、Ｂ為兩個集合，則Ａ與Ｂ的交集Ａ∩Ｂ、并集Ａ∪Ｂ、差集Ａ－Ｂ（也稱Ｂ對Ａ的相對補集）和對稱差A(yù)B分別定義如下：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）＝{x│x∈Ax∈B}用文氏圖可將集合表示如下：135、集合的運算（續(xù)）定義2設(shè)Ｅ為全集，Ａ為任一集合，稱Ｅ－Ａ為Ａ的絕對補，記作A。A＝E－A＝{x│x∈E∧xA}例6設(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。例7設(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＝Φ,B∩C＝Φ146、集合運算的性質(zhì)(1)交運算的性質(zhì)A∩A=AA∩Ф=ФA∩E=AA∩B=B∩A(A∩B)∩C=A∩(B∩C)156、集合運算的性質(zhì)(續(xù)1)(2)并運算的性質(zhì)A∪A=AA∪E=EA∪B=B∪A(A∪B)∪C=A∪(B∪C)AA∪B，BA∪B166、集合運算的性質(zhì)(續(xù)2)(3)絕對補運算的性質(zhì)（A）=AE=ΦΦ=EA=EA∩A=Φ（A∪B）=A∩B176、集合運算的性質(zhì)(續(xù)3)(4)差運算的性質(zhì)A-B=A∩BA-B=A-(A∩B)A∩(B-C)=(A∩B)-(