離散數(shù)學(xué)第三章課件

1、集 合 論由于集合論的語言適合于描述和研究離散對象及其關(guān)系，所以也是計(jì)算機(jī)科學(xué)與工程的理論基礎(chǔ)，在程序設(shè)計(jì)、關(guān)系數(shù)據(jù)庫、形式語言和自動機(jī)理論等學(xué)科領(lǐng)域中都有重要的應(yīng)用。本篇主要介紹：集合、二元關(guān)系和函數(shù)。 第三章集合1 集合的概念和表示法2 集合的運(yùn)算3 集合中元素的計(jì)數(shù)1、集合與元素 （1）集合 把人們直觀的或想象中的某些確定的能夠區(qū)分的對象匯合在一起組成的一個整體。討論： 一些不同的確定的對象之全體。 例： 1000以內(nèi)的素數(shù)的集合； （ 集合）這個班里高個子學(xué)生的集合；（不是集合）1 集合的概念和表示法元素（成員）：組成集合的各個對象。符號：用大寫英文字母表示集合，用小寫英文字母或其它符

2、號表示元素。集合：A，B.元素：a，b. 元素與集合間的關(guān)系： 若a是集合S中的元素，則可寫成a S ；若b不是集S合中的元素，則可寫成b S 。集合也可作為某一集合的元素。 例：S= a,1,2,p,q 集合S的基數(shù)(勢)：S中的元素個數(shù)。用|S|表示。有限集合：集合的基數(shù)（元素）是有限的。 無限集合：集合的基數(shù)（元素）是無限的。 本書中常用集合符: Im(m1) 有限個正整數(shù)的集合1,2,3m Nm(m0) 有限個自然數(shù)的集合0,1,2m N 自然數(shù)集合 0,1,2 I+ 正整數(shù)集合 1,2,3 I 整數(shù)集合 -1,0,1,2 Q 有理數(shù)集合 i/j. i、j均為整數(shù)且j0 R 實(shí)數(shù)集合

3、有理數(shù)、無理數(shù) C 復(fù)數(shù)集合 a+bi，a、b可為實(shí)數(shù)(2)集合的表示方法(a) 枚舉法 (列舉法) 把集合的元素列于花括號內(nèi)。例： 命題的真假值組成的集合：S= T,F 自然數(shù)0,1,2,3,4五個元素的集合：P= 0,1,2,3,4 (b) 謂詞公式描述法所有集合均可用謂詞公式來表示：S= x | p(x) 例：大于10的整數(shù)的集合：S1= x | x I x10 偶整數(shù)集合：S2= x | y (y I x=2y) (c) 同一集合可以用多種不同的形式表示。 S3 = 1,2,3,4,5 = x | x I (1 x 5) S4 = F,T = x | x=T x=F S5 = 1, 4

4、 = x | (x-5x+4=0) (3) 三個特殊集合：全集、空集、集合族定義如果一個集合包含了所要討論的每一個集合，則稱該集合為全集合，簡稱全集，用E表示。 E=x | p(x) p(x) p(x)為任何謂詞公式定義不擁有任何元素的集合稱為空集，用表示 =x | p(x) p(x) = 注意： ， 是空集，即沒有元素的集合； 是以作為元素的集合。 定義集合中的元素均為集合，稱這樣的集合為集合族。 例 A= a，b，c、d 2、集合之間的關(guān)系定義給定二個集合A和B，當(dāng)且僅當(dāng)A和B具有同樣的元素（成員），則A和B才是相等的，記作A=B 并規(guī)定：（A=B）x (x A x B)例：a, b, c

5、= b, a, a, c, c 1, 2, 3= 3, 2, 1 設(shè) P= 1,2,4 ，Q= 1,2,4 ，則P Q定義設(shè)A、B是任意二個集合，如果集合A的每一個元素都是B的一個元素，則稱A 是B的子集，或者說A包含于B，或者說B包含A，記作AB，或者BA。 記為：A B B A x( x A x B ) 例：A1=1,2,3 A2=0 A3=1,2,3,0 B=1,2,3,0 則A1、A2、A3均為B的子集合，并記為 A1 B，A2 B，A3 B注意：區(qū)分“”和“”的關(guān)系“”關(guān)系是指集合和該集合中元素之間的關(guān)系。 例：S= a , b , c 則a S， b S，c S 而“”關(guān)系是指二個

6、集合之間的關(guān)系。 例：S1= a, b S2= a,b,1,2 則S1 S2 定義設(shè)A、B是任意二個集合，若AB且AB，則稱A是B的真子集，記作AB（A真包含于B） 記為：A B （AB AB） 例：A1=1,2,3 A2=0 B=1,2,3,0 則A1、A2 均為B的真子集，并記為 A1 B， A2 B定理設(shè)A、B是任意二個集合，當(dāng)且僅當(dāng)A B和B A才有A=B。 證明： ()充分性：（A=B）（A B B A） (A=B) x (x A x B) x (x A xBxB xA) x(xA xB)x(xB xA) (AB)(BA) ()必要性：ABBA A=B(AB)(BA)x(xA xB)

7、x(xB xA) x (x A xBxB xA) x (x A x B) (A=B) 定理對于任一集合A，則有A A。定理設(shè)有空集和任一集合A，則A 證明：設(shè)xA，要證明A 只要證：x(x xA)為“T” 中沒有元素 x為假，x（x xA）為“T” 則 A 定理設(shè)E是全集，A是一個集合，則一定有A E。定理設(shè)A、B、C是任意集合，如果AB和BC，則AC 。推論若AB和BC，則AC 。定理 是唯一的。 證明：設(shè)有二個空集合1和2 是任何集合的子集 （1 22 1） (1=2) 是唯一的。 3、冪集和索引集合 （1）冪集定義 設(shè)A是集合，A的所有子集（作為元素）構(gòu)成的集合稱為A的冪集。 記作(A)

8、， 且有：(A) = x | x A 例：若A1=，其子集為： ，則 (A1)= 若A2=a，其子集為： ，a ，則 (A2)=，a 若A3=1，2，其子集為：，1，2，1，2 則 (A3)=，1，2，1，2 注： |(S)|=2 |s| 為冪集(S)的基數(shù) （2）索引集合 為了在計(jì)算機(jī)上表示集合，必須給每一個集合的元素加上標(biāo)記，以用來表示元素在集合中的位置。 例：S1=a，b 假設(shè)集合S1中，a,b的位置已經(jīng)固定。 則用二進(jìn)制下標(biāo)法來表示S的所有子集： = =B00，a=B10，b=B01，a，b=B11 則(S1)=B00，B01，B10，B11=Bi | iJ 其中J=00，01，10，

9、11 （索引集合或指標(biāo)集合）2 集合的運(yùn)算 1.交集（交運(yùn)算）定義任何二個集合A和B的交集AB是由A和B所共有的全部元素構(gòu)成的集合。 記作：AB=x | x A x B 例：A=a，b B=a，c A B = a ABAB2 集合的運(yùn)算 定理 集合的相交運(yùn)算是可交換的和可結(jié)合的，即對于任何集合A，B，C有 A B = B A (可交換) （AB） C = A （BC） (可結(jié)合) 證明：設(shè)x是AB中任一元素 則x AB x x | x A x B x x | x B x A x BA AB=BA 定理設(shè)A是E的任一子集，則有（1）A A = A（2）A = （3）A E = A2.并集（并運(yùn)算

10、） 定義 A、B是任意二個集合，A和B的并集AB是由A和B的所有元素構(gòu)成的集合。記作：AB = x xAxB 例：A=a, b, c ,B=1,2,3 ，則 AB = a,b,c,1,2,3 ABAB定理集合的并運(yùn)算是可交換和可結(jié)合的. AB = BA (可交換) （AB） C = A （BC） (可結(jié)合)定理設(shè)A、B、C是全集E的任意子集，則有： (1) AA = A (2) A = A (3) AE = E定理集合的并和交運(yùn)算滿足分配律，即并對交分配，交對并分配。 (1)A （BC）=（AB）（AC）(并對交分配) (2)A （BC）=（AB）（AC） (交對并分配) 定理設(shè)A，B，C，D

11、是E的子集，則有： (1 )若A B和C D，則A C B D (2 )若A B和C D，則AC BD (3 ) 若A A B，則 B A B (4 ) 若A B A，則A B B (5 ) 若A B，則AB = B (6) 若A B，則A B = A3.相對補(bǔ)集定義設(shè)A和B是二個任意集合，B對A的相對補(bǔ)集（A B）是由屬于A且不屬于B的所有元素組成的集合。 記作：A B = xxAxB 例：設(shè)A = 0，1，2 ，B = 2，3，4 則 A B = 0,1 ，B A = 3，4 A B B A，相對補(bǔ)集不滿足交換律。定理設(shè)A，B，C，D是E的子集，則有： (1 ) A B A (2 ) A

12、= A (3 ) A A = (4 ) A (B A) = (5) A( B A) = AB4、絕對補(bǔ)集（補(bǔ)運(yùn)算 ）定義設(shè)E是全集，任一集合A對E的相對補(bǔ)集稱為A的絕對補(bǔ)集（或稱補(bǔ)集），記作A（或A）。 即：A = E A = x| x E x A 例：設(shè) E = a，b，c，d， A = a，b 則 A = c，d AA定理：補(bǔ)集的性質(zhì)如下： (1) AA = E (2) A A = (3) （A）= A (4) （AB）= A B (5) （A B）= AB (6) = E (7) A B = A B 例：設(shè) A = 2，5，6，B = 2，3，4 ，E = 1 ， 2，3，4，5，6則 A B = 5，6 A B = 2，5，6 1，5，6 = 5，6 A B = A B 5、環(huán)和(對稱差)定義設(shè)A、B是任意二集合，A和B的環(huán)和記作AB。即：AB = (A B)(B A)=(AB) (A B) 或者 x (AB) x x |xA xB 例：設(shè)A = 2，5，6，B = 2，3，4 則 A B = 3，4，5，6 ABAB定理：對稱差的性質(zhì)：(1) A B = B A (可交換)(2) (A B) C = A (B C) (可結(jié)合)(3) A A = (4) A = A(5) A (B C) = (A B) ( A C) (對是可以分配的)6、文氏圖(1) 文氏圖