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