(20120831)第六章集合代數(shù).ppt

,漳州師范學(xué)院計(jì)算機(jī)科學(xué)與工程系,第六章 集合代數(shù),第六章 集合代數(shù),集合的基本概念 集合的運(yùn)算 有窮集的計(jì)數(shù) 集合恒等式 知 識(shí) 點(diǎn)：集合的概念與表示、集合的運(yùn)算、包含排斥原 理 、集合恒等式 教學(xué)要求：深刻理解和掌握有關(guān)集合的基本概念和運(yùn)算 教學(xué)重點(diǎn)：集合的基本概念和基本運(yùn)算 學(xué)時(shí): 2,6.1 集合的基本概念,集合: 把一些事物匯集到一起組成的整體稱(chēng)為集 合, 組成集合的那些事物稱(chēng)為該集合的元素 或成員. 集合一般有兩種表示法: 列舉法: 把屬于集合的元素以某種方式列舉出來(lái), 寫(xiě)在花括號(hào) 里 例: 由四個(gè)數(shù) -1, 2, 3, -4 構(gòu)成的集合表示為-1, 2, 3,-4 描述法 把屬于某個(gè)集合的元素所具有的特定性質(zhì)P 描述出來(lái), 寫(xiě)在花括號(hào) 里記為 x | P(x) 例: x | 3x+1 2 ,集合由其元素完全確定, 集合中的元素是不考慮次序的, 而且也應(yīng)是互不相同的。,6.1 集合的基本概念,集合與元素之間的隸屬關(guān)系 a是集合A的元素, 就稱(chēng) a屬于A, 記為 a A a不是集合A的元素, 就稱(chēng) a不屬于A, 記為a A 例: A= a , b,c , d , d 這里 aA, dA, d A , 但 b A 規(guī)定: A A 數(shù)集 用 N 表示自然數(shù)集, 用 Z 表示整數(shù)集, 用 Q 表示有理數(shù)集, 用 R 表示實(shí)數(shù)集, 用 C 表示復(fù)數(shù)集,6.1 集合的基本概念,集合間的包含與相等關(guān)系 定義6.1 設(shè)A, B為兩個(gè)集合, 如果B的每一個(gè)元素都屬 于A 則稱(chēng)B是A的子集, 記為B A 或 A B, 也稱(chēng) A包含B。 如果B不被A包含, 則記作 B A 包含的符號(hào)化表示為 B A (x) ( xB x A ) 對(duì)任何集合A都有 A A 例如: N Z Q R C 隸屬關(guān)系和包含關(guān)系都是兩個(gè)集合之間的關(guān)系,對(duì)某些集合可以同時(shí)成立這兩種關(guān)系 例如: A= a, a , 則 a A 并且 a A,6.1 集合的基本概念,定義 6.2 設(shè)A, B為兩個(gè)集合, 若B A且 A B, 則稱(chēng)A與B相等, 記作 A = B 相等的符號(hào)化表示為 A B (B A) ( A B ) 定義 6.3 設(shè)A,B為集合,如果 B A 且BA 則稱(chēng)B為A的真子集或A真包含B, 記為B A 真子集的符號(hào)化表示為 A B (B A) ( A B ),6.1 集合的基本概念,定義 6.4 不含任何元素的集合稱(chēng)為空集, 記為 空集的符號(hào)化表示為 = x | xx 定理 6.1 空集是一切集合的子集 A (x) ( x x A ) 推論 空集是唯一的,6.1 集合的基本概念,至少有一個(gè)元素的集合稱(chēng)為非空集. 由無(wú)限多個(gè)元素構(gòu)成的集合稱(chēng)為無(wú)限集. 由有限個(gè)元素構(gòu)成的集合稱(chēng)為有限集. 含有n個(gè)元素的集合簡(jiǎn)稱(chēng)為n元集 n元集的含有m(mn)個(gè)元素的子集叫做它的m元子集 對(duì)n元集集A,它的0元子集有Cn0個(gè), 1元子集有Cn0個(gè), m元子集有Cnm個(gè), n元子集有Cnn個(gè) 所以子集總數(shù)為 Cn0 + Cn0 + Cnn =2n,6.1 集合的基本概念,定義 6.5 設(shè)A為集合,把A的全體子集構(gòu)成的集合 叫做A的冪集,記作P(A)或2A 例如: 設(shè)A=a, b, c, 則P(A)=,a,b,c,a,b,a,c,b,c,A 定義 6.6 在一個(gè)具體的問(wèn)題中，如果所涉及的集合都是某個(gè)集合的子集,則稱(chēng)這個(gè)集合為全集,記作E。全集是相對(duì)的。,6.2 集合的運(yùn)算,定義6.7 設(shè)A,B為集合,A與B的并,交,差(相對(duì)補(bǔ)) 運(yùn)算定義如下: 并: A與B的并集記為AB , ABx|xAxB 交: A與B的交集, 記為AB ,ABx|xAxB 差: A與B的差集, 記為AB , A 與 B 的差稱(chēng)為B 關(guān)于A 的相對(duì)補(bǔ). AB x|xAx B ,6.2 集合的運(yùn)算,定義6.8 設(shè)A, B為集合, A與B 的對(duì)稱(chēng)差集 AB,定義為 A B = x | x AB x AB 定義6.9 給定全集E以后,設(shè)A是E的子集,A的絕 對(duì)補(bǔ)集A定義如下: A = EA= x|xE x A ,6.2 集合的運(yùn)算,五種運(yùn)算的文氏圖,6.2 集合的運(yùn)算,兩個(gè)集合的并和交運(yùn)算可以推廣成n個(gè)集合的并和交： A1A2Anx|xA1xA2xAn A1A2Anx|xA1xA2xAn A1A2An A1A2An 并和交運(yùn)算還可以推廣到無(wú)窮多個(gè)集合的情況： A1A2 A1A2,6.2 集合的運(yùn)算,定義6.10 設(shè)A為集合,A的元素的元素構(gòu)成的集合 稱(chēng)為A的廣義并 A的廣義并記為A A的廣義并符號(hào)化表示為 A= x | z ( zA xz ) = 例如: A= a,b,c,a,c,d,a,e,f , 則 A=a,b,c,d,e,f ,6.2 集合的運(yùn)算,定義6.11 設(shè)A為非空集合,A的所有元素的公共元 素構(gòu)成的集合稱(chēng)為A的廣義交 A的廣義交記為A A的廣義交符號(hào)化表示為 A= x | z (zA x z) 在集合論中沒(méi)有意義 , 不是集合 例如: A= a,b,c , a,c,d , a,e,f ,則 A=a,6.2 集合的運(yùn)算,集合運(yùn)算的優(yōu)先次序 廣義并,廣義交,冪集,絕對(duì)補(bǔ)運(yùn)算為一類(lèi)運(yùn)算 并,交,相對(duì)補(bǔ),對(duì)稱(chēng)差運(yùn)算為二類(lèi)運(yùn)算 一類(lèi)運(yùn)算優(yōu)先于二類(lèi)運(yùn)算 一類(lèi)運(yùn)算之間由右向左順序進(jìn)行 二類(lèi)運(yùn)算之間由括號(hào)決定先后順序,6.3 有窮集的計(jì)數(shù),使用文氏圖可以很方便地解決有窮集的計(jì)數(shù)問(wèn)題。 首先根據(jù)已知條件把對(duì)應(yīng)的文氏圖畫(huà)出來(lái)。 一般地說(shuō)，每一條性質(zhì)決定一個(gè)集合。有多少條性質(zhì)，就有多少個(gè)集合。如果沒(méi)有特殊說(shuō)明，任何兩個(gè)集合都畫(huà)成相交的，然后將已知集合的元素?cái)?shù)填入表示該集合的區(qū)域內(nèi)。 通常從n個(gè)集合的交集填起，根據(jù)計(jì)算的結(jié)果將數(shù)字逐步填入所有的空白區(qū)域。 如果交集的數(shù)字是未知的，可以設(shè)為x。 根據(jù)題目中的條件，列出一次方程或方程組， 就可以求得所需要的結(jié)果。,6.3 有窮集的計(jì)數(shù),例6.4 對(duì)24名會(huì)外語(yǔ)的科技人員進(jìn)行掌握外語(yǔ)情況的調(diào)查。其統(tǒng)計(jì)結(jié)果如下：會(huì)英、日、德和法語(yǔ)的人分別為13，5，10和9人，其中同時(shí)會(huì)英語(yǔ)和日語(yǔ)的有2人，會(huì)英、德和法語(yǔ)中任兩種語(yǔ)言的都是4人。已知會(huì)日語(yǔ)的人既不懂法語(yǔ)也不懂德語(yǔ)，分別求只會(huì)一種語(yǔ)言(英、德、法、日)的人數(shù)和會(huì)三種語(yǔ)言的人數(shù)。,6.3 有窮集的計(jì)數(shù),解: 令A(yù)，B，C，D分別表示會(huì)英、法、德、日語(yǔ)的人的集合。根據(jù)題意畫(huà)出文氏圖如圖6.3所示。設(shè)同時(shí)會(huì)三種語(yǔ)言的有x人，只會(huì)英、法或德語(yǔ)一種語(yǔ)言的分別為y1，y2和y3人。將x和y1，y2，y3填入圖中相應(yīng)的區(qū)域，然后依次填入其它區(qū)域的人數(shù)。 根據(jù)已知條件列出方程組如下： 解得x1，y14，y22，y33,6.3 有窮集的計(jì)數(shù),定理6.2 (包含排斥原理) 設(shè)S為有窮集, P1,P2,Pn是n個(gè)性質(zhì).A中的任何元素x或者具有性質(zhì)Pi或者不具有性質(zhì)Pi,兩種情況必居其一。 令A(yù)i表示A中具有性質(zhì)Pi的元素構(gòu)成的子集,則A中不具有性質(zhì)P1,P2,Pn的元素?cái)?shù)為,6.4 集合恒等式,基本集合恒等式 , A,B,C代表任意集合 冪等律 AAA (6.1) AAA (6.2) 結(jié)合律 (AB)CA(BC) (6.3) (AB)CA(BC) (6.4) 交換律 ABBA (6.5) ABBA (6.6) 分配律 A(BC)(AB)(AC) (6.7) A(BC)(AB)(AC) (6.8),6.4 集合恒等式,同一律 AA (6.9) AEA (6.10) 零律 AEE (6.11) A (6.12) 排中律 AAE (6.13) 矛盾律 AA