集合論與圖論

集合論與圖論第一頁，共二十二頁，2022年，8月28日2第三章目錄第3-1講集合的概念和集合的運算第3-2講笛卡兒積與關系第3-3講復合關系、逆關系與閉包運算第3-4講等價關系第3-5講序關系第二頁，共二十二頁，2022年，8月28日3第3-1講集合的概念和運算1.集合的概念2.集合的表示3.集合間的關系4.冪集5.集合的運算6.集合運算的性質7.課堂練習8.第3-1講作業(yè)第三頁，共二十二頁，2022年，8月28日41、集合的概念將一些確定的、彼此不同的事物的全體稱之為集合。對于給定的集合和事物，應能判斷這個特定的事物是否屬于給定的集合。集合中的事物稱為該集合的元素。

通常，用大寫的英文字母表示集合，用小寫英文字母表示集合的元素。例如，習慣上用Ｎ表示非負整數(shù)的集合，用Ｑ表示有理數(shù)集合，Ｒ表示實數(shù)集合等等。如果ａ是集合Ｓ的元素,記作ａ∈Ｓ,讀作“ａ屬于Ｓ”。如ｂ不是Ｓ的元素，記作bＳ，讀作“ｂ不屬于Ｓ”，它等價于（b∈s）。若一個集合的元素個數(shù)是有限的，則稱為有限集，否則稱為無限集。第四頁，共二十二頁，2022年，8月28日52、集合的表示列舉法：列出集合的所有元素，并用花括號括起來，元素之間用逗號隔開。例如：

S={e1,e2,…,en}(具有n個元素的有限集)

Ａ＝{a,{b,c},{fmvuvmd}}（a,{b,c},{woagwit}是該集合的元素）Ｎ＝{0,1,2,3,...}(N是非負整數(shù)集)

在一個集合中，元素是彼此不同的，相同的元素被認為是一個元素，而且元素之間沒有次序關系，例如集合{1,2,3}，{3,1,2}和{3,3,1,2}被視為同一個集合。敘述法（或描述法）

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

定義1

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

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

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

Ｅ＝{x|P(x)∨P(x)}。（P(x)是任意謂詞）顯然，全集的概念相當于論域，它是一個相對概念。第六頁，共二十二頁，2022年，8月28日73、集合間的關系兩個集合相等，當且僅當它們有相同的成員。集合Ａ與Ｂ相等，記作Ａ＝Ｂ。集合Ａ與Ｂ不相等，記作Ａ≠Ｂ。定義１

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

AB(x)(x∈A→x∈B)AB(x)(x∈A→x∈B)∧(x)(x∈B∧xA)

按子集的定義，對于任何集合A、B、C都有AA(自反性)，(AB)∧(BC)(AC)(傳遞性)第七頁，共二十二頁，2022年，8月28日83、集合間的關系（續(xù)1）定理１

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

(A＝B)(x)(x∈A→x∈B)∧(x)(x∈B→x∈A)

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

定理２

空集是任意集合的子集。證明：任給集合Ａ，Φ是空集。則（x)(x∈Φ→x∈A)永真。這是因為條件式的前件(x∈Φ)永假，所以該條件式對一切ｘ皆為真。按子集的定義，ΦA為真。第八頁，共二十二頁，2022年，8月28日93、集合間的關系（續(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

確定下列命題的真值⑴ΦΦ；⑵Φ∈Φ；⑶Φ{Φ}；⑷Φ∈{Φ}。解：⑴、⑶、⑷為真；（因為空集是任何集合的子集，所以⑴、⑶為真。）⑵為假。（因為空集不含任何元素。）第九頁，共二十二頁，2022年，8月28日103、集合間的關系（續(xù)3）例3

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

。例4設集合Ｅ＝{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}。第十頁，共二十二頁，2022年，8月28日114、冪集定義４集合Ａ的所有子集構成的集合叫Ａ的冪集，記作ρ(A)。

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

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

設B＝{Φ,{Φ}}求ρ(B)。解：ρ(B)＝{Φ，{Φ}，{{Φ}}，{Φ,{Φ}}}第十一頁，共二十二頁，2022年，8月28日124、冪集（續(xù)）定理３設A有ｎ個元素，則ρ(A)有2n個元素。

證明：A的所有由ｋ個元素組成的子集個數(shù)為從ｎ個元素中?。雮€元素的組合數(shù)：在(x+y)2的展開式中令x=y=1得：另外，因ΦA，故ρ(A)中元素的個數(shù)Ｎ可表示為：第十二頁，共二十二頁，2022年，8月28日135、集合的運算定義1

設Ａ、Ｂ為兩個集合，則Ａ與Ｂ的交集Ａ∩Ｂ、并集Ａ∪Ｂ、差集Ａ－Ｂ（也稱Ｂ對Ａ的相對補集）和對稱差AB分別定義如下：

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}用文氏圖可將集合表示如下：第十三頁，共二十二頁，2022年，8月28日145、集合的運算（續(xù)）定義2

設Ｅ為全集，Ａ為任一集合，稱Ｅ－Ａ為Ａ的絕對補，記作A。A＝E－A＝{x│x∈E∧xA}例6

設Ｅ＝{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設A＝{1,2,3}，B＝{1,4}，C＝{3}。求A∪B,B∪A，A∩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＝Φ第十四頁，共二十二頁，2022年，8月28日156、集合運算的性質(1)交運算的性質A∩A=AA∩Ф=ФA∩E=AA∩B=B∩A(A∩B)∩C=A∩(B∩C)例8

證明(A∩B)∩C=A∩(B∩C)證：(A∩B)∩C={x|x∈(A∩B)x∈C}={x|x∈Ax∈Bx∈C}={x|x∈A(x∈Bx∈C)}={x|x∈Ax∈B∩C)}=A∩(B∩C)第十五頁，共二十二頁，2022年，8月28日166、集合運算的性質(續(xù)1)(2)并運算的性質A∪A=AA∪E=EA∪B=B∪A(A∪B)∪C=A∪(B∪C)AA∪B，BA∪B例9設AB，CD，則A∪CB∪D。證:對任意x∈A∪C，則x∈A或x∈C。若x∈A，因AB，x∈B，故x∈B∪D；若x∈C，因CD，所以x∈D亦有x∈B∪D。按子集的定義可知原式成立。第十六頁，共二十二頁，2022年，8月28日176、集合運算的性質(續(xù)2)(3)絕對補運算的性質（A）=AE=ΦΦ=EA=EA∩A=Φ（A∪B）=A∩B例10

證明(A∩B)=A∪B證:（A∩B）={x|x∈(A∩B)}={x|xA∩B}={x|x∈A∩B}={x|(x∈A∧x∈B)}={x|x∈A∨x∈B}={x|xA∨xB}={x|x∈A∨x∈B}=A∪B第十七頁，共二十二頁，2022年，8月28日186、集合運算的性質(續(xù)3)(4)差運算的性質A-B=A∩BA-B=A-(A∩B)A∩(B-C)=(A∩B)-(A∩C)例11

證明A-B=A-(A∩B)證:因為x∈A-Bx∈AxB

x∈Ax(A∩B)x∈A-(A∩B)

所以，A-BA-(A∩B)。反之，x∈A-(A∩B)x∈Ax(A∩B)x∈Ax∈(A∩B)x∈Ax∈ABx∈A(x∈Ax∈B))(x∈Ax∈A)(x∈Ax∈B)）F(x∈Ax∈B))x∈Ax∈Bx∈AxBx∈A-B所以，A-(A∩B)A-B?？v上所述，原式成立。第十八頁，共二十二頁，2022年，8月28日196、集合運算的性質(續(xù)4)(5)對稱差運算的性質AB=BAAΦ=AAA=ΦAB=（A∩B）∪（A∩B）(AB)C=A(BC)對結合律，用文氏圖說明如下：第十九頁，共二十二頁，2022年，8月28日207、課堂練習練習1

證明A∩(B-C)=(A∩B)-(A∩C)證法1：(A∩B)-(A∩C)=(A∩B)∩(A∩C)=(A∩B)∩(A∪C)=(A∩B∩A)∪(A∩B∩C)=Φ∪(A∩B∩C)（從左往右的關鍵步驟）

=A∩B∩C=A∩(B-C)證法2:按集合相等的定義證明。任取x∈A∩(B-C),有x∈A∩(B-C)x∈Ax∈(B-C)(x∈Ax∈BxC)(x∈Ax∈BxA)(x∈Ax∈BxC)(x∈Ax∈B)(xAxC)x∈(A∩B)(x∈Ax∈C)x∈(A∩B)(x∈Ax∈C)x∈(A∩B)(x∈A∩C)x∈(A∩B)xA∩Cx∈(A∩B)-(A∩C)所以，A∩(B-C)=