蘇XI友無密碼課件第3章-集合的基本概念和運算

Chap.3集合的基本概念和運算集合論是研究集合一般性質(zhì)的數(shù)學分支,它作為一門獨立學科誕生于19世紀,創(chuàng)始人為喬治·康托(GeorgeCantor,1845-1918).康托建立的集合論一般稱為古典(或樸素)集合論.集合論是全部現(xiàn)代數(shù)學的理論基礎(chǔ),已深入到現(xiàn)代科學的各個方面,集合的概念已成為表達各種嚴謹科學概念的必不可少的數(shù)學語言.集合論的語言適應(yīng)于描述和研究離散對象及其關(guān)系,所以它是計算機科學和技術(shù)的基礎(chǔ)理論和表達工具.集合論在程序語言、數(shù)據(jù)結(jié)構(gòu)、開關(guān)理論、形式語言、關(guān)系數(shù)據(jù)庫、編譯原理、操作系統(tǒng)、人工智能、信息檢索等領(lǐng)域都有著重要應(yīng)用.本課程主要介紹集合論的基礎(chǔ)知識,屬于古典集合論的范疇.2023/5/10北京林業(yè)大學信息學院蘇喜友1§1

集合的基本概念集合是人們直觀上或思想上能夠明確區(qū)分的一些對象所構(gòu)成的一個整體.集合是在一定范圍內(nèi)所討論的對象組成的整體.集合是把一些事物匯集到一起組成的一個整體.Cantor稱集合是“一些確定的、不同的東西的總體.這些東西,人們能夠意識到,并且能判斷一個給定的東西是否屬于這個總體.”2023/5/10北京林業(yè)大學信息學院蘇喜友2集合中的事物、對象、客體稱為集合的成員或元素.集合用大寫英文字母表示,元素用小寫英文字母表示.集合與元素之間的關(guān)系是屬于或不屬于的關(guān)系.

如,一元素a,

要么aS,

要么aS.§1

集合的基本概念2023/5/10北京林業(yè)大學信息學院蘇喜友3如果集合S中包含的元素個數(shù)是有限的,則稱S為有限(有窮)集合,否則,稱為無限(無窮)集合.稱只有一個元素的集合為單元集,稱兩個元素的集合為二元集,一般地稱有n個元素的集合為n元集.§1

集合的基本概念2023/5/10北京林業(yè)大學信息學院蘇喜友4關(guān)于集合的定義需要注意:Note1

集合的元素是彼此不同的.

如,1,1,2=1,2.Note2

集合的元素是無序的.

如,1,2,3=3,1,2.Note3

集合的元素可以是任何類型的事物,尤其可以是集合.

如,A=a,a,b,c.§1

集合的基本概念2023/5/10北京林業(yè)大學信息學院蘇喜友5集合的描述或表示通常有下述三種方法:(1)列舉法(枚舉法):列舉集合中的所有元素來表示某個集合.

例如,A=a,b,c,d,N=0,1,2,3,….(2)謂詞法(隱式法\敘述法\抽象法):用集合元素所具有的共同性質(zhì)來描述這個集合.可以用非形式化的自然語言描述,也可以用形式化的謂詞表示.§1

集合的基本概念2023/5/10北京林業(yè)大學信息學院蘇喜友6一般說來,任意的集合都可以用謂詞法表示.例如,A=a,e,i,o,u,A=x|x是英文中的元音字母.B=2,3,5,7,B=x|x是素數(shù)且x＜10.C=2,3,-5,C=x|x=2∨x=3∨x=-5.由此可見,謂詞法是表示集合的基本方法.§1

集合的基本概念2023/5/10北京林業(yè)大學信息學院蘇喜友8§1

集合的基本概念Def.1

子集(Subset)

設(shè)A和B是兩個集合,如果A的每個元素都是B的元素,則稱A是B的子集,也稱A包含于B或B包含A.記為A?B或B?A.用謂詞形式表示為:

A?B?x(xA→xB).由定義,任意一個集合都是其自身的子集,即

A?A.2023/5/10北京林業(yè)大學信息學院蘇喜友9§1

集合的基本概念Def.2

相等設(shè)A,B是集合,如果A?B且B?A,則稱A和B相等.記為A＝B.若A和B不相等,記為A≠B.用謂詞形式表示:A＝B(A?B)∧(B?A)?x(xA→xB)∧?x(xB→xA)?x(xAxB).2023/5/10北京林業(yè)大學信息學院蘇喜友10§1

集合的基本概念Def.3

真子集(RealSubset)

設(shè)A,B為集合,如果A?B且A≠B,則稱A是B的真子集,也稱A真包含于B,或B真包含A.記為A?B.用謂詞形式表示:A?B(A?B)∧(A≠B)?x(xA→xB)∧?x(xB∧xA).2023/5/10北京林業(yè)大學信息學院蘇喜友11§1

集合的基本概念Def.4

全集由全體客體組成的集合稱為全集.記為E或U.全集具有相對性,不同的問題有不同的全集,既使同一個問題,也可以有不同的全集.一般說來,全集取得小一些,問題的描述和處理會簡單些.Def.5

空集不包含任何元素的集合稱為空集或零集.記為φ.用謂詞形式表示:

φ＝x|P(x)∧?P(x),其中,P(x)為任意的謂詞.2023/5/10北京林業(yè)大學信息學院蘇喜友12§1

集合的基本概念Theorem1

設(shè)A為一集合,則有

φ?A,A?A,A?E.證明.φ?A?x(xφ→xA)1.

A?A,A?E類似可證.Th.2

空集是唯一的.證明.設(shè)空集不唯一,不妨設(shè)φ和φ’都是空集.由Th.1,得

φ?φ’,φ’?φ.由集合相等的定義,得

φ＝φ’.2023/5/10北京林業(yè)大學信息學院蘇喜友13§1

集合的基本概念Def.6冪集(Powerset)

設(shè)A為集合,A的所有子集組成的集合稱為A的冪集.記為P(A)或2A,即P(A)=x|x?A.例如,A=a,b,c,則P(A)=φ,a,b,c,a,b,a,c,b,c,a,b,c.Def.7基數(shù)(CardinalNumber)

集合中不同元素的數(shù)目稱為集合的基數(shù)或勢.若基數(shù)是有限數(shù),則稱該集合為有限(有窮)集,否則稱為無限(無窮)集.有限集的基數(shù)記為|A|.如上例,|A|=3,|P(A)|=8.2023/5/10北京林業(yè)大學信息學院蘇喜友14§1

集合的基本概念Th.3(冪集的基數(shù))

設(shè)A為有限集,則P(A)的基數(shù)為|P(A)|=2|A|.證明.設(shè)|A|=n,即A中有n個不同元素.從A中n個元素任意取i個元素組成A的子集,共有個.故A的所有子集的個數(shù)為:

即2023/5/10北京林業(yè)大學信息學院蘇喜友15§1

集合的基本概念Exp.1

判斷下列命題是否為真.(1)φ?φ;(2)φφ;(3)aa;(4)a?a;(5)aa;(6)a?a;(7)a,ba,b,c,a,b;(8)a,b?a,b,c,a,b.111001112023/5/10北京林業(yè)大學信息學院蘇喜友16§1

集合的基本概念Exp.2

求下列集合的冪集.(1)φ;(2)φ;(3)a,a.解.(1)P(φ)=φ.

(2)P(φ)=φ,φ.

(3)P(a,a)=φ,a,a,a,a.2023/5/10北京林業(yè)大學信息學院蘇喜友17§2

集合的運算Def.1

集合的運算(1)并集合A與B的并記為A∪B,A∪B=x|x∈A∨x∈B.(2)交

集合A與B的交記為A∩B,A∩B=x|x∈A∧x∈B.(3)相對補(集)

集合A與B的相對補記為A-B,A-B=x|x∈A∧xB.也稱A-B為A與B的差(集),B相對于A的補(集).2023/5/10北京林業(yè)大學信息學院蘇喜友18§2

集合的運算(4)絕對補(集)

設(shè)E為全集,A?E,A的絕對補記為~A(或A),~A=E-A=x|x∈E∧xA.(5)對稱差(集)

集合A與B的對稱差記為AB,AB=(A-B)∪(B-A)=x|(x∈A∧xB)∨(x∈B∧xA).也稱AB為A與B的環(huán)和.2023/5/10北京林業(yè)大學信息學院蘇喜友19§2

集合的運算上述定義可以用文氏(JohnVenn)圖描述如下:ABA∪BA∩B~AA-BABAABABAB由文氏圖立得,A-B=A∩~B,AB=(A∪B)-(A∩B).EEEEE2023/5/10北京林業(yè)大學信息學院蘇喜友20§2

集合的運算集合運算中~優(yōu)先于∪,∩,-和,后幾種運算平級,有括號先進行括號里的運算,無括號按從左到右次序運算.Th.1

設(shè)E是全集,A,B,C是E的任意子集,則下述等式成立.(1)交換律A∪B=B∪A,A∩B=B∩A,AB=BA.(2)結(jié)合律(A∪B)∪C=A∪(B∪C),(A∩B)∩C=A∩(B∩C),(AB)C=A(BC).2023/5/10北京林業(yè)大學信息學院蘇喜友21§2

集合的運算(3)分配律

A∪(B∩C)=(A∪B)∩(A∪C),A∩(B∪C)=(A∩B)∪(A∩C).

(4)同一律

A∪φ=A,A∩E=A,A-φ=A,Aφ=A.(5)零律

A∩φ=φ,A∪E=E,A-A=φ,A-E=φ,AA=φ.(6)補余律

A∪~A=E,

排中律

A∩~A=φ.

矛盾律(7)雙否律

~(~A)=A.2023/5/10北京林業(yè)大學信息學院蘇喜友22§2

集合的運算(8)冪等律

A∪A=A,A∩A=A.(9)吸收律

A∪(A∩B)=A,A∩(A∪B)=A.(10)德·摩根律A-(B∪C)=(A-B)∩(A-C),A-(B∩C)=(A-B)∪(A-C),~(B∪C)=~B∩~C,~(B∩C)=~B∪~C,

~φ=E,~E=φ.2023/5/10北京林業(yè)大學信息學院蘇喜友23§2

集合的運算以上恒等式的證明主要用到命題演算的等值式.基本思想是:欲證P=Q,即證

P?Q∧Q?P,也就是要證對任意的x有

x∈Px∈Q∧x∈Qx∈P即

x∈Px∈Q.一般,要證明兩個集合相等,可以按照上述思路根據(jù)定義來證,也可以根據(jù)已知的集合恒等式證明.2023/5/10北京林業(yè)大學信息學院蘇喜友24§2

集合的運算1.利用集合相等定義證明.Exp.1A∪B=B∪A.證明.對任意的x,x∈A∪Bx∈A∨x∈Bx∈B∨x∈Ax∈B∪A.所以,?x(x∈A∪Bx∈B∪A),即

A∪B=B∪A.2023/5/10北京林業(yè)大學信息學院蘇喜友25§2

集合的運算Exp.2

證明:A-B=A∩~B.證.對任意x,

x∈A-Bx∈A∧xB

x∈A∧x∈~Bx∈A∩~B.故

A-B=A∩~B.2023/5/10北京林業(yè)大學信息學院蘇喜友26§2

集合的運算Exp.3

證明

A-(B∪C)=(A-B)∩(A-C).證.對任意的x,x∈A-(B∪C)x∈A∧xB∪Cx∈A∧?(x∈B∪C)x∈A∧?(x∈B∨x∈C)x∈A∧?(x∈B)∧?(x∈C)x∈A∧xB∧xCx∈A∧x∈A∧xB∧xC(x∈A∧xB)∧(x∈A∧xC)x∈A-B∧x∈A-Cx∈(A-B)∩(A-C).故

A-(B∪C)=(A-B)∩(A-C).2023/5/10北京林業(yè)大學信息學院蘇喜友27§2

集合的運算2.利用集合恒等式證明.Exp.4

證明

(A∩B)∪(A∩~B)=A.證.(A∩B)∪(A∩~B)=A∩(B∪~B)=A∩E=A.2023/5/10北京林業(yè)大學信息學院蘇喜友28§2

集合的運算Exp.5

已知AB=AC,證明B=C.證.因為AB=AC,

所以A(AB)=A(AC),

(AA)B=(AA)C,

φB=φC,

故B=C.2023/5/10北京林業(yè)大學信息學院蘇喜友29§2

集合的運算Exp.6

證明(A∪B)-A=B-A.證.(A∪B)-A=(A∪B)∩~A=(A∩~A)∪(B∩~A)=φ∪(B∩~A)=B∩~A=B-A.此外,還有利用文氏圖、用集合成員表和利用規(guī)定原理證明兩集合相等等方法,但都不很常用.2023/5/10北京林業(yè)大學信息學院蘇喜友30§2

集合的運算Exp.7

證明A∩C?B∩C∧A-C?B-CA?B.證.因為

A∩C?B∩CA-C?B-C

所以

(A∩C)∪(A-C)?(B∩C)∪(B-C)(A∩C)∪(A∩~C)?(B∩C)∪(B∩~C)A∩(C∪~C)?B∩(C∪~C)A∩E?B∩E

故

A?B.證明中利用了P1?Q1∧P2?Q2P1∪P2?Q1∪Q2,同時也有

P1?Q1∧P2?Q2P1∩P2?Q1∩Q2.2023/5/10北京林業(yè)大學信息學院蘇喜友31§2

集合的運算Th.2

設(shè)A和B是任意集合,則以下四個命題等價：(1)A?B;(2)A∪B=B;(3)A∩B=A;(4)A-B=φ.證.(1)(2)(3)(4)(1).2023/5/10北京林業(yè)大學信息學院蘇喜友32§2

集合的運算(1)A?B(2)A∪B=B.

對任意x,x∈B,則x∈A∨x∈B,從而x∈A∪B,故

B?A∪B;

對任意x,x∈A∪B,則x∈A∨x∈B,由于A?B,所以總有x∈B,故

A∪B?B.所以

A∪B=B.2023/5/10北京林業(yè)大學信息學院蘇喜友33§2

集合的運算(2)A∪B=B(3)A∩B=A.

因為

A∪B=B,所以

A∩B=A∩(A∪B)=A.(3)A∩B=A(4)A-B=φ.

A-B=A∩~B=(A∩B)∩~B=A∩(B∩~B)

=A∩φ=φ.(4)A-B=φ(1)A?B.

任取x∈A,若xB,則x∈A-B,與A-B=φ矛盾.所以x∈B,故

A?B.2023/5/10北京林業(yè)大學信息學院蘇喜友34§2

集合的運算Exp.8

在什么條件下等式(A-B)∩(A-C)=φ成立?解.(A-B)∩(A-C)=A-(B∪C),由Th.2知,A-(B∪C)=φ當且僅當A?B∪C.故(A-B)∩(A-C)=φ成立的充要條件是A?B∪C.2023/5/10北京林業(yè)大學信息學院蘇喜友35§2

集合的運算Exp.7

證明:A∩C?B∩C∧A-C?B-CA?B.證二.因為A∩C?B∩C,A-C?B-C,所以(A∩C)∩(B∩C)=A∩C,(A-C)∩(B-C)=A-C,A∩B∩C=A∩C,A∩B∩~C=A∩~C.上述等式兩邊分別取并,得

(A∩B∩C)∪(A∩B∩~C)=(A∩C)∪(A∩~C),(A∩B)∩(C∪~C)=A∩(C∪~C),(A∩B)∩E=A∩E,即A∩B=A,故A?B.2023/5/10北京林業(yè)大學信息學院蘇喜友36§3

有窮集合的計數(shù)Exp.1

對24名會外語的科技人員進行掌握外語情況的調(diào)查,其統(tǒng)計結(jié)果如下:會英、日、德和法語的人分別為13