離散數(shù)學(xué)-3-1 集合的概念和表示法.ppt

1、1,第三章 集合與關(guān)系,3-1 集合的概念和表示法 授課人：李朔 Email:,2,一、集合的概念,集合是不能精確定義的數(shù)學(xué)基本概念, 當(dāng)我們討論某一類對(duì)象時(shí)，就把這一類對(duì)象的全體稱為集合。這些對(duì)象稱為集合中元素。元素也是抽象的，無(wú)法精確定義，可以認(rèn)為是存在于世界上的一切客觀物體。 例如：地球上的人。 公園里的花。 坐標(biāo)平面上的點(diǎn)。,3,一、集合的概念,通常用大寫字母表示一個(gè)集合，例A，B，。 用小寫字母表示一個(gè)集合的元素，例a, b, x, y, 。 若元素a屬于集合A，記作aA, 否則記aA。 若一個(gè)集的元素個(gè)數(shù)是有限，稱有限集，否則稱為無(wú)限集。 有限集合的元素個(gè)數(shù)稱為該集合的基數(shù)，集合A

2、的基數(shù)記為|A|。,4,一、集合的概念,本書通常用N表示自然數(shù)集（包含0），Z代表整數(shù)數(shù)集，Q代表有理數(shù)集，R代表實(shí)數(shù)集，C代表復(fù)數(shù)集。 集合的表示通常有二種方法： 1）列舉法：把集合的元素在花括號(hào)內(nèi)列出 例 A=a, b, c, d N=0, 1, 2, W=風(fēng)馬牛 Z=3，5，6，9 （沒有規(guī)律，所以不能用列舉法）,5,一、集合的概念,2）描述法：用謂詞概括該集合元素的屬性。 B = x P(x) 表示B由使P(x)為真的x組成。 例： B=x x R 3 x 6 , C=x x2=1（=1，-1） D=y| y是教室中所有聽課的同學(xué) 集合的元素必須是確定的。所謂確定的，是指任何一個(gè)對(duì)象是

3、不是集合的元素是明確的、確定的，不能模棱兩可。即對(duì)于集合A，任一元素a，要么a屬于A，要么a不屬于A，兩者必居其一。 集合的元素又是能區(qū)分的，能區(qū)分的是指集合中的元素是互不相同的。如果一個(gè)集合中有幾個(gè)元素相同，算做一個(gè)。例如集合1,2,3,3和1,2,3是同一集合, a, b, a, a, b與a,a,b,b,b 是相同的集合。 集合的元素又是無(wú)序的，即1,2,3和3,1,2是同一集合。 集合的元素還可以允許是一個(gè)集合，如S= 1,2, 3, a,a,6,二集合之間的關(guān)系,集合之間有二種基本關(guān)系： 1）相等：兩個(gè)集A，B稱作相等，當(dāng)且僅當(dāng)A，B的元素完全相同，記A=B，否則AB。(P82外延性

4、原理） 例 1, 2, 4 1, 2, 4 1, 3, 5 =x x是正奇數(shù) 2）子集（83 定義3-1.1）：A，B為兩個(gè)集合，若A的每個(gè)元素都是B的元素，稱A為B的子集，或A包含在B內(nèi)，或包含，記AB或BA。 即 A B x(xAxB) 根據(jù)子集的定義，可立即有：對(duì)任意集合A，B，C： 1）AA； （自反性） 2）AB，BC則AC；(傳遞性）,7,二集合之間的關(guān)系,定理3-1.1 A=B AB且BA 證:設(shè)A=B，則x (xAxB)與x (xBxA)都為真，故AB且BA。 反之，若AB且BA而AB，設(shè)某一xA但xB（或xB但xA）這與AB（或BA）矛盾。 *本定理結(jié)論是我們以后證明兩個(gè)集合

5、相等的主要判定方法。(互為子集法） 定義3-1.2:真子集。A，B為兩個(gè)集合，若A的每個(gè)元素都是B的元素，但B中至少有一個(gè)元素不屬于A，則稱A為B的真子集，或A包含在B內(nèi)，記AB。 即A B x (xAxB)(x)(xBxA) ABABAB 例如：Z Q 又例如：設(shè) A=a，B=a,b，C=a,b,c 則 AB，BC，AC，但 AA,8,三、空集,84 定義3-1.3 不含任何元素的集合稱為空集，記為，即= 。 =x | P(x)P(x) 其中，P(x)為任意謂詞 空集是不包含任何元素的集合，所以，|=0。 注： ， 。 定理3-1.2 對(duì)任一個(gè)集合A， A。 證：設(shè)不是A的子集，則必有x 而

6、xA，這與的定義矛盾。 根據(jù)本定理，空集是任意集合的子集，即 A；對(duì)任意集合A，AA。一般地說(shuō)，任意集合A至少有兩個(gè)子集，一個(gè)是空集 ，另一個(gè)是它本身A。 (稱與為的平凡子集） 推論 空集是惟一的。,9,例：確定下列命題的真假： (a) (b) (c) (d) (e)a,b a,b,ca,b,c (f)a,b a,b,ca,b,c (g)a,b a,b,c,a,b (h)a,b a,b,c,a,b,10,例：求出下列集合的全部子集： (a) , , (b)a,b,a,a,b,b,a,b , a,b,11,四、全集,定義3-1.4全集 若在特定條件下考慮的對(duì)象均屬于E，則稱E為全集。 全集概念相

7、當(dāng)于論域。如討論宇宙萬(wàn)物的集合時(shí)一切客體都屬于全集。而討論一個(gè)班級(jí)，則該班級(jí)的全部學(xué)生組成了全集。 以一個(gè)集合的所有子集為元素，可以組成另外一種集合。,12,五、冪集,定義3-1.5 給定集合A，由A的所有子集為元素組成的集合稱為A的冪集，記P(A)。 即 P (A) =S | SA 例如 設(shè)A=a,b,c， 是空集，試求 P (A)，P (P ()。 解： P (A)= ,a,b,c,a,b,a,c,b,c,a,b,c P ()= ， P (P () = , *一個(gè)有限集A，可以有多少個(gè)不同的子集？即它的冪集的基數(shù),13,五、冪集,P85 定理3-1.3：如果有限集合A有n個(gè)元素,則其冪集P(n)有2n個(gè)元素。 證明：A的所有由k個(gè)元素組成的子集為從n個(gè)元素中取k個(gè)元素的組合數(shù)。 另外，因 ，故P(A)的總數(shù)N可表示為： 又因 令x=y=1， 故P(A)的元素個(gè)數(shù)是2n,14,六、子集編碼,引進(jìn)一種編碼，用來(lái)唯一地表示有限集冪集的元素。 以S=a,b,c為例： P(S)=Si|iJ J=i|i是二進(jìn)制且000J111 *先元素排列，后各元素與對(duì)應(yīng)位映射。 例如：S3=S011=b,c,S6=S110=a,b等。 *一般地P（S）=S0，S1，S2n-1 即P(S)=i|I是二進(jìn)制數(shù)且 ,15,本課小結(jié),集合，有限集，無(wú)