離散數(shù)論-第五章

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

2、 I (Z) 表示整數(shù)集合。 集合：集合是一個原始概念,無精確定義。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是正奇數(shù) S3 = x | x = an, n N 可見 ， 一個集合的抽象描述形式不唯一。S = a0, a1, a2, , an,，其中 n為自然數(shù)。5例: A = x | x是英文元音字母 由抽象原則可知，對任意x: x A x是英文元音字母其中, 表示當(dāng)且僅當(dāng)。 定義5.1(抽象原則): 任給一個性質(zhì) P，就確定 了一個集合A , A 的元素恰好是具有性質(zhì) 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 這樣的謂詞來定義集合，否則就會產(chǎn)生悖論 。 例：設(shè) T = x | x x , 由抽象原則，就有: x: x T x x， 把 T 代入 x 得， T T T T ， 矛盾!75.2 集合間的相等和包含關(guān)系目標(biāo)要求： 掌握集合相等（=）、包含（）的定義。 掌握 、=、 之間的聯(lián)系與區(qū)別。 掌握空集的性質(zhì) 重點(diǎn)難點(diǎn)： 集合間的相等與包含關(guān)系 空集的性質(zhì) 證明集合相等8一 、集合的相等 定義5.2 (集合相等)（外延性公理）：設(shè) 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 表明 集合與其元素排列次序無關(guān) 。a, b, a = a, a, b, b, a = a, b 表明 集合與其元素重復(fù)出現(xiàn)次數(shù)無關(guān)a, a, b, b, a 稱為多重集, 也稱為 bag x | x4且x是正整數(shù) = 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 根據(jù)外延性公理 AB = A B 。因此，A + B又可以定義為： A + B = （A B）（ B A ）例：試證A（A B）= AB 26把兩個集合的，運(yùn)算可推廣到n個集合的，運(yùn)算。 設(shè)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設(shè)集合的聚合： A=AS1,AS2, J=S1,S2,S3，則A可以簡

7、寫成： A=Ai | iJ其中稱A為加標(biāo)集合，J為標(biāo)碼集合。定義5.13（集合族或集合的聚合）:如果一個集合的所有元素都是集合，則稱該集合為集合族或集合的聚合。28定義5.14(集合的聚合上的運(yùn)算) 設(shè)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因?yàn)槿鬉=,則蘊(yùn)涵式ASi A x ASi的前件為假， ASi（ ASi A x ASi ）為真，這就定義了全集U，

8、因此要求A 。例：設(shè)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例：設(shè) 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結(jié)合律：（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 除了上述性質(zhì)外，常用的性質(zhì)還有 A-B=AB和下面兩個性質(zhì)定理定理：設(shè)A和B是全集U的子集，B=A 當(dāng)且僅當(dāng) 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定理：設(shè)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）：反證法， 假設(shè)

11、AB不成立，則存在 x，xA但xB，因此xA-B，即A-B，與已知 條件（4）矛盾。故必有AB 該定理常用于證明兩個集合的包含關(guān)系。38例：設(shè)A，B，C是任意集合，試證： 若AB且CD ，則ACBD證明：因?yàn)锳B且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)結(jié)合律，交換律(AB)(AC) 42例 設(shè)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 有窮集的計(jì)數(shù)原理 引理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) ，根據(jù)引理5.1得（AB)B（AB) (1)又 AA(B B) (AB) (A B) （分配律） 同樣(AB) (A B) ，根據(jù)引理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)有窮集合計(jì)數(shù)問題的求解，可利用上述定理或推論，還可利用文氏圖和代數(shù)相結(jié)合的方法。舉例如

14、下：46例：外語系120名學(xué)生中，其中有100名學(xué)生至少學(xué)習(xí)英語、德語、法語這三門外語中的一種，有65人學(xué)英語，45人學(xué)德語，42人學(xué)法語，20人既學(xué)英語又學(xué)德語，25人既學(xué)英語又學(xué)法語，15人既學(xué)德語又學(xué)法語。求同時學(xué)這三種外語的人數(shù)和僅學(xué)其中一門外語的人數(shù)。解：方法一 。 （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,即同時學(xué)三種外語有8人僅學(xué)英語和德語的人數(shù)為208=12，僅學(xué)英語和法語的人數(shù)為258=17，僅學(xué)德語和法語的人數(shù)為158=7

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

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

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

18、例如：| ab |=2 , | an | = n 。若|x|=0，則稱x為空串，記做。53字符串相等：設(shè) x 和y 是任意兩個字符串，則 x =y 當(dāng)且僅當(dāng) | x | = | y |，并且組成x的諸字符與組成y的諸字符依次相同。例如：若x = ab,y= ab, 則x=y；若x= ab, y= ba, 則x y。 字符串的連接：設(shè)是一個字母表，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 | ，字符串的連接運(yùn)算滿足結(jié)合律。 54設(shè) x ，y，z是任意字符串，則稱 x是字符串xy的前綴， y是后綴。稱 x ，y，z分別是字符串 xyz的子串。是每個字符串的前綴、后綴、子串。若x 是 y 的子串（前綴，后綴）并且xy ，則稱x是y 的真子串（真前綴，真后綴）上的所有字符串構(gòu)成的集合記做 * ，其歸納法定義如下：（1） * （2）若x *和a ，則xa *（3） *中的每一個元素都可通過有限次應(yīng)用上述（1）、（2）規(guī)則得到。55上的語言： *的子集例如：a，ab，cba，bba 是 =a，b，c上的語言。語言的運(yùn)算如下：語言的乘積（連接）：設(shè)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語言的冪運(yùn)算An :（ 1）A0=,（2）An+1=AnA, nN語言的閉包運(yùn)算A* :A* =A A2A的正閉包A+ ：A+ =A A2例：令 B=a，bb，則B2 =aa，abb，bba，bbbbB* =，a，bb， aa，abb，bba，bbbb， 56定理：設(shè)A、B、C、D是上的任意語言，則下列關(guān)系成立：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定理：設(shè)A、B是上的任意語言，m、n是任意自然數(shù)

22、，則下列關(guān)系成立：（1）Am An =Am+n（2）（ Am ） n =Amn（3）若AB則An Bn 定理：設(shè)A、B是上的任意語言，nN，則下列關(guān)系成立：（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 有序偶和笛卡兒乘積 掌握有序偶和笛卡兒乘積的定義和性質(zhì) 熟練掌握求兩

23、個集合的笛卡兒乘積62定義5.22：（有序偶）任給兩個對象x和y，將它們按規(guī)定的順序構(gòu)成的序列，稱之為有序偶，記為 x，y 。其中x稱為有序偶的第一元，y稱為第二元。 顯然有序偶與二元集在概念和性質(zhì)上都有根本的不同。如： a，b b，a a，a a 而 a，b = b，a a，a = a 63 1921年波蘭數(shù)學(xué)家?guī)炖蟹蛩够↘uratovski）給出了一種有序偶的集合表示 x，y = x ， x，y 。 定理5.16 有序偶的唯一性定理： u，v = x，y ，當(dāng)且僅當(dāng)u=x和v=y。證：充分性 當(dāng)u=x，v=y時，有 u = x 和 u，v = x，y ， 因此有 u ， u，v = x ， x，y 。 即 u，v = x，y 64 必要性 分兩種情況來證u=