1、第五章 集合的基本概念及其運算5.1 集合與元素5.2 集合間的相等和包含關系5.3 冪集5.4 集合的運算5.5 有窮集的計數原理 5.6 集合的歸納定義法5.7 有序偶和笛卡兒乘積1 5.1 集合與元素目標要求： 會用抽象法表示集合 掌握集合的抽象表示和枚舉表示的互相轉換重點難點: 集合的抽象表示 抽象原則2 集合是人們能夠明確區分的一些對象(客體)構成的一個整體。 例如：“全體中國人”，“所有英文字母”都構成集合。 但“全校高個子學生”不能構成集合，因為“高個子”是一個模糊概念。 集合通常用大寫英文字母表示，其中用: N 表示自然數集合(含0)， R 表示實數集合， Q 表示有理數集合，

2、 I (Z) 表示整數集合。 集合：集合是一個原始概念,無精確定義。1875年康托爾給其定義如下：3 如果 a是集合A 中的元素，就寫成 aA，讀作: a 屬于A。 如果 b 不是A中的元素，就寫成 bA，讀作:b不屬于A。集合的表示方法（1）枚舉法（2）抽象法枚舉法：把集合中所有元素全部列舉出來，用 括起來，元素之間用逗號分開。 元素：集合里含有的 對象 稱為該集合的元素。通常用小寫英文字母 表示元素。4例如: A = a, e, i, o, u抽象法: 用 謂詞 概括集合中元素的屬性. 其描述形式為 S = x | P(x) 例: S1 = x | x是中國的省 S2 = x | x=2k

3、+1 且 kN = x | x是正奇數 S3 = x | x = an, n N 可見 ， 一個集合的抽象描述形式不唯一。S = a0, a1, a2, , an,，其中 n為自然數。5例: A = x | x是英文元音字母 由抽象原則可知，對任意x: x A x是英文元音字母其中, 表示當且僅當。 定義5.1(抽象原則): 任給一個性質 P，就確定 了一個集合A , A 的元素恰好是具有性質 P的對象，即: A = x | P(x) 也就是說 x ( P(x) xA )6抽象原則的限制:(1) 謂詞 P(x) 要明確清楚 反例：A = x | p(x) , p(x)：x是公園里美麗的花朵 “

4、美麗” 是一模糊概念。因此A不能夠成集合。 (2) 不能取 P(x) 為 x x 這樣的謂詞來定義集合，否則就會產生悖論 。 例：設 T = x | x x , 由抽象原則，就有: x: x T x x， 把 T 代入 x 得， T T T T ， 矛盾!75.2 集合間的相等和包含關系目標要求： 掌握集合相等（=）、包含（）的定義。 掌握 、=、 之間的聯系與區別。 掌握空集的性質 重點難點： 集合間的相等與包含關系 空集的性質 證明集合相等8一 、集合的相等 定義5.2 (集合相等)（外延性公理）：設 A, B 為任意兩集合，若A和B含有相同的元素，則稱 A和B相等, 記作：A=B A =

5、 B x ( xA xB )或 A = B x (xAxB) x (xBxA)9例：2. x | x-1 = 0 = -1，1 3. 1，2，3 = 3，1，2 表明 集合與其元素排列次序無關 。a, b, a = a, a, b, b, a = a, b 表明 集合與其元素重復出現次數無關a, a, b, b, a 稱為多重集, 也稱為 bag x | x4且x是正整數 = 1,2,3,4 = x | x0，則 A= X | X =0例：證明AB=AB25 證：對任意X XA （A B） XA XA B XA （XA XB ） XA （X A X B ） （XA X A）（XA X B） X

6、A X B XAB 所以 A（A B）= AB 根據外延性公理 AB = A B 。因此，A + B又可以定義為： A + B = （A B）（ B A ）例：試證A（A B）= AB 26把兩個集合的，運算可推廣到n個集合的，運算。 設A1,A2, , An為集合，則: A1A2An= X|XA1 X A2X An A1A2An=X|XA1 X A2X An i=1ni=1ni=1i=1也可將上述n個集合的，分別記作 Ai 和 Ai 同理可把無窮多個集合的 ， 分別記為 ： Ai =A1A2An Ai =A1A2An 27設集合的聚合： A=AS1,AS2, J=S1,S2,S3，則A可以簡

7、寫成： A=Ai | iJ其中稱A為加標集合，J為標碼集合。定義5.13（集合族或集合的聚合）:如果一個集合的所有元素都是集合，則稱該集合為集合族或集合的聚合。28定義5.14(集合的聚合上的運算) 設A是全集U的子集的聚合 A=ASi|SiJ J=S1,S2, （1）A的元素的并集表示為 A或 Asi SiJ A= ASi=x|ASi（ASiAxASi） SiJ（2）若A ,A的元素的交集表示為A或 Asi SiJ A= Asi =x|ASi （Asi AxAsi） SiJ29因為若A=,則蘊涵式ASi A x ASi的前件為假， ASi（ ASi A x ASi ）為真，這就定義了全集U，

8、因此要求A 。例：設C=0, 0,1, 0,1,2 則 C=0 0,1 0,1,2=0,1,2 C=0 0,1 0,1,2=0例：設 A=Ai| i J, J=a,b,c, Aa=0,1,2, Ab=4,5,6, Ac=2則 Ai=AaAbAc=0,1,2,4,5,6 Ai=AaAbAc=iJiJ注意: 定義（2）中要求A 。303132集合恒等式冪等律： AA=A 交換律：AB= B A AA=A AB= B A結合律：（AB）C= A （BC） （AB）C= A（BC）分配律： A（B C）= （AB） （AC） A（B C）= （AB） （AC）同一律： A= A AU= A33零律：

9、AU=U A=否定律： A A =U A A=吸收律： A（ A B）= A A（ A B）= A德摩根律： （ A B）= AB （ A B）= AB對合律： （ A）= A =U U=34對集合恒等式的說明在不含 和+ 的集合恒等式中，將 和 互換， 和 U 互換，得到的仍然是集合恒等式。 將不含 、 和 的命題邏輯等值式中的 換為 ， 換為 ， 換為 ，0 換為 ，1 換為 U， 換為 = ，就得到集合恒等式。 35 除了上述性質外，常用的性質還有 A-B=AB和下面兩個性質定理定理：設A和B是全集U的子集，B=A 當且僅當 AB=U和AB=證明：必要性 若B=A ，則AB= AA= U

10、AB = A A = 充分性 若AB=U和AB =，則B= U B = （A A） B= （A B ）（A B）=（AB）= （A A） （A B）= A （AB）=A U= A 36定理：設A和B是全集U的子集，下列四個命題等價：（1）AB（2）AB=B（3）AB=A（4）A-B=證明：（1）（2） （3） （4） （1）37（1）（2）：對于任意x，由“”定義可知x B，x AB，因此B AB對于任意x， x ABxA x B xB x BxB所以 AB=B（2） （3）： AB= A（AB）=A （吸收律）（3） （4）：A-B= （AB）-B= AB B=（4） （1）：反證法， 假設

11、AB不成立，則存在 x，xA但xB，因此xA-B，即A-B，與已知 條件（4）矛盾。故必有AB 該定理常用于證明兩個集合的包含關系。38例：設A，B，C是任意集合，試證： 若AB且CD ，則ACBD證明：因為AB且CD ，則AB=B 且 C D= D （四個等價命題） AB C D= B D 即（ A C）（B D）= B D 所以 ACBD （四個等價命題）39證明兩個集合相等常用以下兩種方法：（1）集合相等定義 （2）集合恒等式40例：試證：A(BC)(AB)(AC)。證明 ：方法一，對任意x, xA(BC) xAx (B C) xA(xB C) xA(xB x C) xA(x BxC)

12、(xAxB) (xAxC) xABxA C x(AB) (A C)所以，A(B C)(AB) (A C) 。 41例： 試證：A(BC)(AB)(AC)。證明 ：方法二 A(BC) A(BC)A(BC)德摩根律(AA)(BC)冪等律(AB)(AC)結合律，交換律(AB)(AC) 42例 設A,B,C是任意集合, 試證： (A-B) +B=(A-B)B證明：（A-B）+ B=(A-B)-B)(B-(A-B) (“+” 定義)=（ABB)(B(AB) =(AB)(B(BA)=（A-B）B （吸收律） 435.5 有窮集的計數原理 引理5.1：若A和B是有窮集合，且AB，則 （AB)= AB 定理5

13、.12：若A和B是有窮集合，則 （AB)= AB （AB)證明： 顯然AB和AB是有窮集。 AB= BA =（BA）（B B) = B (A B) （分配律）44由于B (A B) ，根據引理5.1得（AB)B（AB) (1)又 AA(B B) (AB) (A B) （分配律） 同樣(AB) (A B) ，根據引理5.1得 A（AB) （AB) （AB)A- （AB)代入(1)式得 （AB) A+ B -（AB)45推論：若A，B和C是有窮集合，則 （AB C)ABC (AB) (AC)(BC) （AB C)有窮集合計數問題的求解，可利用上述定理或推論，還可利用文氏圖和代數相結合的方法。舉例如

14、下：46例：外語系120名學生中，其中有100名學生至少學習英語、德語、法語這三門外語中的一種，有65人學英語，45人學德語，42人學法語，20人既學英語又學德語，25人既學英語又學法語，15人既學德語又學法語。求同時學這三種外語的人數和僅學其中一門外語的人數。解：方法一 。 （EG F)EGF (EG)(EF)(GF)（EG F) , 其中（EG F) =100,E=65,G=45,F=42， (EG)=20,(EF)=25,(GF)=15，因此得 (EG F)=8,即同時學三種外語有8人僅學英語和德語的人數為208=12，僅學英語和法語的人數為258=17，僅學德語和法語的人數為158=7

15、,因此僅學其中一門外語的人數為100-12-17-7-8=5647方法二設同時學這三種外語的人數為x，僅學英語、德語、法語的學生人數分別為y1,y2,y3 。因此，僅學英語和德語的人數為20 x僅學英語和法語的人數為25x僅學德語和法語的人數為15x由學英語的有65人得 y120 xx25x65,由學德語的有45人得 y220 xx15x45,由學法語的有42人得 y325xx15x42,y120 xx25xy215xy310048 解方程組得： x8 ，y128, y218, y310 因此，同時學這三門外語的有8人， 僅學這三門外語中一門的有28181056人。 495.6 集合的歸納定義

16、法前面介紹了集合的表示方法有 1. 枚舉法：常用于有窮集合的表示。2. 抽象法：用于有窮集或無窮集的表示。但抽象法表示集合時，有時不可能清楚地表示某些 集合。例如算術表達式集合，某高級語言程序集合等等，這時可用集合歸納定義法來描述。502.歸納語句：規定由已知元素構成集合中新元素的規則（集合生成算法） 一般表述為“若x,y,z,是集合中的元素，則根據某些規則進行有限次的組合，其結果也是集合中的元素”。3.極限語句：限定集合的范圍。（是滿足1和2的最小集合，注：這步有時省略）一般表述為“只有有限次應用基礎語句和歸納語句得到的元素才是該集合中的元素”。集合的歸納定義有三部分組成 1.基礎語句：規定

17、集合生成元（集合的原子元素），表明集合非空。51例：非負偶數集合 E=xx0y(yI x=2y)或E=x y(yN x=2y) E的歸納定義如下： . 0 E . 若n E，則(n+2 )E . 只有有限次應用、得到的數才是E中的元素。例：求下列歸納定義的集合P .3 P .若x,yP,則(x+y)P .只有有限次應用. 得到的元素才在P中。 顯然，P是由3的倍數的正整數組成。52字符串在計算機科學中有重要作用，下面引入有關術語字母表是字母(或稱符號)的非空有限集合，通常記作。字母表上的字符串是由中的字母所組成的有窮序列。字符串長度 ：字符串x所含字母的個數，稱為字符串。x的長度,記作|x|，

18、例如：| ab |=2 , | an | = n 。若|x|=0，則稱x為空串，記做。53字符串相等：設 x 和y 是任意兩個字符串，則 x =y 當且僅當 | x | = | y |，并且組成x的諸字符與組成y的諸字符依次相同。例如：若x = ab,y= ab, 則x=y；若x= ab, y= ba, 則x y。 字符串的連接：設是一個字母表，x、y是 上的字符串， x=a1a2 an ， y=b1 b2 bn ，x和y的連接記作xy，xy = a1 a2 an b1 b2 bn 。特別地： x = x=x， n個x的連接記作xn ， x0= ，x n+1 = xn x。顯然：| xy |

19、= | x | + | y | ，字符串的連接運算滿足結合律。 54設 x ，y，z是任意字符串，則稱 x是字符串xy的前綴， y是后綴。稱 x ，y，z分別是字符串 xyz的子串。是每個字符串的前綴、后綴、子串。若x 是 y 的子串（前綴，后綴）并且xy ，則稱x是y 的真子串（真前綴，真后綴）上的所有字符串構成的集合記做 * ，其歸納法定義如下：（1） * （2）若x *和a ，則xa *（3） *中的每一個元素都可通過有限次應用上述（1）、（2）規則得到。55上的語言： *的子集例如：a，ab，cba，bba 是 =a，b，c上的語言。語言的運算如下：語言的乘積（連接）：設A和B是上的語

20、言， A和B的乘積記作 AB ， AB=zx y ( z=xy x Ay B) 例：A=，a，ab，B=a，bb，則AB=a，bb，aa，abb，aba，abbb語言的冪運算An :（ 1）A0=,（2）An+1=AnA, nN語言的閉包運算A* :A* =A A2A的正閉包A+ ：A+ =A A2例：令 B=a，bb，則B2 =aa，abb，bba，bbbbB* =，a，bb， aa，abb，bba，bbbb， 56定理：設A、B、C、D是上的任意語言，則下列關系成立：A =A =A= A =A(AB)C=A(BC)若AB和CD, 則AC BDA(BC)=ABAC(BC) A =BACAA(

21、BC) ABAC(BC) A BACA57試證：若AB和CD, 則AC BD證明：對于任意zzAC x y ( z=xy x Ay C)x y ( z=xy x B (y D) (AB和CD ) z BD所以， AC BD58證明A(BC)=ABAC證明：對于任意zzA（B C) x y（ z=xy x Ay (BC) x y （ z=xy x A(y B y C) x y (（ z=xy x Ay B) (z=xy x A y C) x y (（ z=xy x Ay B) x y (z=xy x A y C) zAB zAC zAB AC 59定理：設A、B是上的任意語言，m、n是任意自然數

22、，則下列關系成立：（1）Am An =Am+n（2）（ Am ） n =Amn（3）若AB則An Bn 定理：設A、B是上的任意語言，nN，則下列關系成立：（1）A* =A+ （2）AnA* ，n0（3）An A + ， n160（4）AAB*（5） AB*A（6）若 AB，則 A*B*（7）若AB， 則A+ B+（8）AA* = A*A =A+ （9） 若 A，則 A* = A+ （10）（ A* ）* =A* A*=A* （11）（ A* ）* =（A+ ） *=A* （12）（ A +）+ =A+ 證明略。61 5.7 有序偶和笛卡兒乘積 掌握有序偶和笛卡兒乘積的定義和性質 熟練掌握求兩

23、個集合的笛卡兒乘積62定義5.22：（有序偶）任給兩個對象x和y，將它們按規定的順序構成的序列，稱之為有序偶，記為 x，y 。其中x稱為有序偶的第一元，y稱為第二元。 顯然有序偶與二元集在概念和性質上都有根本的不同。如： a，b b，a a，a a 而 a，b = b，a a，a = a 63 1921年波蘭數學家庫拉托夫斯基（Kuratovski）給出了一種有序偶的集合表示 x，y = x ， x，y 。 定理5.16 有序偶的唯一性定理： u，v = x，y ，當且僅當u=x和v=y。證：充分性 當u=x，v=y時，有 u = x 和 u，v = x，y ， 因此有 u ， u，v = x ， x，y 。 即 u，v = x，y 64 必要性 分兩種情況來證u=