離散數(shù)學(xué)集合的概念和表示法

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

2、|A|。3一、集合的概念 本書通常用N表示自然數(shù)集（包含0），Z代表整數(shù)數(shù)集，Q代表有理數(shù)集，R代表實(shí)數(shù)集，C代表復(fù)數(shù)集。集合的表示通常有二種方法：1）列舉法：把集合的元素在花括號內(nèi)列出例 A=a, b, c, dN=0, 1, 2, W=風(fēng)馬牛Z=3，5，6，9 （沒有規(guī)律，所以不能用列舉法）4一、集合的概念 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è)對象是不是集合的元素是明確的、確定的，

3、不能模棱兩可。即對于集合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 是相同的集合。集合的元素又是無序的，即1,2,3和3,1,2是同一集合。集合的元素還可以允許是一個(gè)集合，如S= 1,2, 3, a,a 5二集合之間的關(guān)系集合之間有二種基本關(guān)系：1）相等：兩個(gè)集A，B稱作相等，當(dāng)且僅當(dāng)A，B的元素完全相同，記A=B，否則AB。(P82外延性原理）例 1, 2, 4 1, 2, 4 1

4、, 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ù)子集的定義，可立即有：對任意集合A，B，C：1）AA； （自反性）2）AB，BC則AC；(傳遞性）6二集合之間的關(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è)集合相等的主要判定方法。(互為子集法）定義3-1.2:真子集。A，B

5、為兩個(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，但 AA7三、空集84 定義3-1.3 不含任何元素的集合稱為空集，記為，即= 。 =x | P(x)P(x) 其中，P(x)為任意謂詞空集是不包含任何元素的集合，所以，|=0。注： ， 。定理3-1.2 對任一個(gè)集合A， A。證：設(shè)不是A的子集，則必有x 而xA，這與的定義矛盾。根據(jù)本定理，空集是任意集合的子集，即 A；對任意集合A，AA。一

6、般地說，任意集合A至少有兩個(gè)子集，一個(gè)是空集 ，另一個(gè)是它本身A。 (稱與為的平凡子集）推論 空集是惟一的。8例：確定下列命題的真假：(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,b9例：求出下列集合的全部子集：(a) ,(b)a,b,a,a,b,b,a,b, a,b10四、全集定義3-1.4全集若在特定條件下考慮的對象均屬于E，則稱E為全集。全集概念相當(dāng)于論域。如討論宇宙萬物的集合時(shí)一切客體都屬于全集。而討論一個(gè)班級，則該班級的全部學(xué)生組成了全集。以一個(gè)集合的所有子集為元素，可

7、以組成另外一種集合。11五、冪集 定義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ù) 12五、冪集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ù)是2n13六、子集編碼引進(jìn)一種編碼，用來唯一地表示有限集冪集的元素。以S=a,b,c為例：P(S)=Si|iJ J=i|i是二進(jìn)制且000J111*先元素排列，后各元素與對應(yīng)位映射。例如：S3=S011=b,c,S6=S110=a,b等。*一般地P（S）=S0，S1，S2n-1即P(S)=i|I是二進(jìn)制數(shù)且 14本課小結(jié)集合，有