集合的基本概念和運算

1、華中師范大學(xué)計算機科學(xué)系華中師范大學(xué)計算機科學(xué)系離散數(shù)學(xué)離散數(shù)學(xué)第三章第三章 集合的基本概念和運算集合的基本概念和運算第三章第三章 集合的基本概念和運算集合的基本概念和運算3.1 集合的基本概念3.2 集合的基本運算3.3 集合中元素的計數(shù)3.4 笛卡爾乘積3.1 集合的基本概念集合的基本概念 集合是不能精確定義的基本的數(shù)學(xué)概念，直觀地講，集合是由某些可以相互區(qū)別的事物匯集在一起所組成的整體。對于給定的集合和事物，應(yīng)該可以斷定這個特定的事物是否屬于這個集合。如果屬于，就稱它為這個集合的元素。 集合通常用大寫的英文字母來表示。 集合有兩種表示方法：枚舉法和謂詞表示法。前一種方法是將集合中的所有元

2、素羅列出來，元素之間用逗號隔開，并把它們用花括號括起來。例如 ， ， ，都是合法的表示。 謂詞表示法是用謂詞來概括集合中元素的屬性，例如 ， ， 集合的元素是彼此不同的，如果同一個元素在集合中多次出現(xiàn)應(yīng)該認(rèn)為是一個元素。集合的元素也是無序的，元素的排列順序?qū)蠜]有影響。 ,cbaA., 3, 2, 1B冬秋，夏，春，C|是學(xué)生xxD |是整數(shù)xxE 01|2xRxxF3.1 集合的基本概念集合的基本概念 定義定義3.1.1 設(shè)A，B為集合，如果B中的每個元素都是A中的元素，則稱B為A的子集合，簡稱子集。這時也稱B被A包含，或A包含B。記作BA。包含的符號化表示為 定義定義3.1.2設(shè)A，B為

3、集合，如果BA且AB，則稱A與B相等，記作A=B。相等的符號化表示為 由以上定義可知，兩個集合相等的充分必要條件是它們具有相同的元素。如 ， 則A=B。)( )(AxBxxABABBAAB3|的素數(shù)是小于等于xxA 32|xxxB3.1 集合的基本概念集合的基本概念 定義定義3.1.3設(shè)A，B為集合，如果BA且BA，則稱B是A的真子集，記作BA。真子集的符號化表示為BABABA 如果B不是A的真子集，則記作 。例如0, 1是0, 1, 2的真子集，但0, 3和0, 1, 2都不是0, 1, 2的真子集。 定義定義3.1.4 不含任何元素的集合叫做空集，記作，空集可以符號化表示為=x | xx

4、定理定理3.1.1 空集是一切集合的子集。 證明：任何集合，由子集定義有 右邊的蘊涵式中因前件 為假，所以整個蘊涵式對一切x為真，因此 為真。AB AxxxAxA 3.1 集合的基本概念集合的基本概念 推論推論 空集是唯一的。 一般地，稱集合A的子集和A為A的平凡子集。 含有n個元素的集合簡稱n元集，它的含有m個(mn)元素的子集稱作它的m元子集。任給一個n元集，如何求出它的全部子集呢？ 例3.1.4 A= a, b, c，求A的全部子集。 解： 將A的子集從小到大分類： 0元子集，即空集, ； 1元子集，即單元集，a，b，c； 2元子集，a, b，b, c，a, c； 3元子集，a, b,

5、c。 一般地，對n元集A，它的m(0mn)元子集有 個，不同的子集總數(shù)有mnCnnnnnnCCCC2.2103.1 集合的基本概念集合的基本概念 定義定義3.1.5 設(shè)A為集合，把A的全體子集構(gòu)成的集合叫做A的冪集，記作(A)。冪集的符號化表示為(A) = x | xA 對于例3.1.4中的集合A有(A) = , a, b, c, a, b, a, c, b, c, a, b, c。 定義定義3.1.6 在一個具體的問題中，如果所涉及的集合都是某個集合的子集，則稱這個集合為全集，記作U。 全集是有相對性的，不同的問題有不同的全集，即使是同一個問題也可以取不同的全集。例如在研究平面上直線的相互關(guān)

6、系時，可以把整個平面（平面上所有點的集合）取作全集，也可以把整個空間（空間上所有點的集合）取作全集。一般地，全集取得小一些，問題的描述和處理會簡單些。第三章第三章 集合的基本概念和運算集合的基本概念和運算3.1 集合的基本概念3.2 集合的基本運算3.3 集合中元素的計數(shù)3.4 笛卡爾乘積3.2 集合的基本運算集合的基本運算 3.2.1 集合的運算 3.2.2 集合運算算律 3.2.1 集合的運算集合的運算 給定集合A和B，可以通過集合的并，交，相對補-，絕對補和對稱差 等運算產(chǎn)生新的集合。 定義定義3.2.1設(shè)A，B為集合，A與B的并集AB，交集AB，B對A的相對補集A-B分別定義如下： 顯

7、然AB由A或B中的元素構(gòu)成， AB由A和B中的公共元素構(gòu)成， A-B由屬于A但不屬于B的元素構(gòu)成。 把以上定義加以推廣，可以得到n個集合的并集和交集，即|BxAxxBAU|BxAxxBAI|BxAxxBA.|.2121nnAxAxAxxAAAUUU.|.2121nnAxAxAxxAAAIII3.2.1 集合的運算集合的運算 定義定義3.2.2 設(shè)U為全集， AU，則稱A對U的相對補集為A的絕對補集，記作A。 定義定義3.2.3 設(shè)A，B為集合，則A與B的對稱差為 A與B的對稱差還有一個等價的定義，即 。 例3.2.1 A=0, 1, 2，B=2, 3，計算 或 集合之間的相互關(guān)系和有關(guān)運算可用

8、文氏圖給出形象的描述。|AxUxxAUA)()(ABBABAU)()(ABBABAIUBA3, 1, 031, 0UBA3, 1, 023, 2, 1, 0BA3.2 集合的基本運算集合的基本運算 3.2.1 集合的運算 3.2.2 集合運算算律 3.2.2 集合運算算律集合運算算律 任何代數(shù)運算都遵從一定的算律，集合運算也不例外。下面給出集合運算的主要算律，其中A，B，C表示任意的集合。 冪等律 結(jié)合律 交換律 分配律 同一律 零 律 排中律 矛盾律 吸收律 雙重否定律 德摩根律 AAAUAAAICBACBAUUUUCBACBAIIIIABBAUUABBAII CABACBAUIUIU CA

9、BACBAIUIUIAAUAUAIUUAUAIUAAUAAI, ABAAIUABAAUIAA CABACBAIU CABACBAUICBCBIUCBCBUIU U 3.2.2 集合運算算律續(xù)集合運算算律續(xù) 除了以上算律，還有一些關(guān)于集合運算性質(zhì)的重要結(jié)論，在此一并給出。 建立了相對補運算和交運算之間的聯(lián)系，可以利用它將相對補轉(zhuǎn)變成交。 給出了 的三種等價的定義，為證明兩個集合之間包含關(guān)系提供了新方法，同時也可以用于集合公式的化簡。BBAABAIIBABBAAUUABABABAIBAABABABBAIUABBACBACBAAOAOAACBCABABABAIBAABABABBAIUBA 第三章第三

10、章 集合的基本概念和運算集合的基本概念和運算3.1 集合的基本概念3.2 集合的基本運算3.3 集合中元素的計數(shù)3.4 笛卡爾乘積3.3 集合中元素的計數(shù)集合中元素的計數(shù) 3.3.1 容斥原理 3.3.2 容斥原理實例 3.3.1 容斥原理容斥原理 集合A含有n個元素，可以說集合A的基數(shù)是n，記作card A=n。所謂基數(shù)就是表示集合中所含元素多少的量。如果集合A的基數(shù)是n，也可以記為|A|=n。顯然空集的基數(shù)是0，即|=0 。 定義定義3.3.1 設(shè)為集合，若存在自然數(shù)n（0也是自然數(shù)），使得|A|=card A=n ，則稱A為有窮集，否則就稱A為無窮集。 例3.3.1 有100名程序員，其

11、中47名熟悉C語言，35名熟悉C+語言，23名熟悉這兩種語言。問有多少人對這兩種語言都不熟悉？ 解：設(shè)A，B分別表示熟悉C和C+語言的程序員的集合，則該問題可以用圖3.3.1的文氏圖表示。將熟悉兩種語言的對應(yīng)人數(shù)23填入AB的區(qū)域內(nèi)，不難得到A-B和B-A的人數(shù)分別為| A-B| = |A|-| AB|=47-23=24| B-A| = |B|-| AB|=35-23=12 從而得到| AB|=24+23+12=59, 故，| (AB)|=100-59=41， 即兩種語言都不熟悉的有41人。 3.3.1 容斥原理容斥原理 設(shè)S是有窮集，P1和P2分別表示兩種性質(zhì)，對于S中的任何一個元素x，只能

12、處于以下四種情況之一： （1）只具有性質(zhì)P1 ； （2）只具有性質(zhì)P2 ； （3）具有P1和P2兩種性質(zhì)； （4）兩種性質(zhì)都沒有。 令A(yù)1和A2分別表示S中具有性質(zhì)P1和P2的元素的集合。為了使表達(dá)式簡潔，對任何集合B，用 代替B。由文氏圖不難得到以下公式 這就是容斥原理的一種簡單形式。 如果涉及到三條性質(zhì)，容斥原理的公式則變成B212121AAAASAAII 321323121321321AAAAAAAAAAAASAAAIIIIIII3.3.1 容斥原理容斥原理 定理定理 3.3.1 S中不具有性質(zhì)P1, P2, , Pm的元素數(shù)是 定理3.3.1證明略。 推論推論 在S中至少具有一條性質(zhì)的

13、元素數(shù)是mmmkjikjimjijimiimAAAAAAAAASAAAIIIIIIIII.1.2111121mmmkjikjimjijimiimAAAAAAAAAAAAIIIIIIUUU.1.211111213.3 集合中元素的計數(shù)集合中元素的計數(shù) 3.3.1 容斥原理 3.3.2 容斥原理實例 3.3.2 容斥原理實例容斥原理實例 例3.3.4 某班學(xué)生150人。數(shù)學(xué)考試成績90分以上的有80人，語文考試成績90分以上的有75人，兩門課程均在90分以上的有50人，問 （1）只有一門課程成績90分以上的學(xué)生有多少人？ （2）兩門課程成績均不在90分以上的學(xué)生有多少人？ 解：全集為該班學(xué)生組成的

14、集合。設(shè) 由題意可知 ， ， ， （1）即需求 。因為 所以， ，即分以上的數(shù)學(xué)成績在90| xxA 分以上的語文成績在90| xxB 80A75B50BA I150UBABAIUIBABBBABBABAABABABABAUUIUUIIUUIIUIUIBABABABABABABAUIIIUIIIUI5550507580BABABABABABABAIIIUIUI3.3.2 容斥原理實例續(xù)容斥原理實例續(xù) （2）即需求BA I45507580150BABAUBAUBABAIUUI第三章第三章 集合的基本概念和運算集合的基本概念和運算3.1 集合的基本概念3.2 集合的基本運算3.3 集合中元素的計數(shù)

15、3.4 笛卡爾乘積3.4 笛卡爾乘積笛卡爾乘積 3.4.1 有序?qū)?3.4.2 笛卡爾積 3.4.3 n階笛卡爾積 3.4.1 有序?qū)τ行驅(qū)?定義定義3.4.1 由兩元素x和y（允許x=y）按一定的順序排列成的二元組叫做一個有序?qū)Γㄒ卜Q序偶），記作,其中x是它的第一元素，y是它的第二元素。 一般地，有序?qū)哂幸韵绿攸c： （1）當(dāng) xy 時x, yy, x。 （2）兩個有序?qū)ο嗟?，即x,y=u,v的充分必要條件是x = u且y = v。 這兩個特點是集合x, y所不具備的，原因在于有序?qū)χ袕娬{(diào)x和y的順序性，而集合x, y中的x和y是無序的。3.4.1 有序?qū)τ行驅(qū)?例3.4.1 證明x,y=u

16、,v的充分必要條件是x = u且y = v。 證明：充分性 顯然成立。 必要性 若x,y=u,v,則xx, x, y=x,y =u,v=u, u, v （1）若x=u，則因為uu=x，所以u = x。 （2）若x=u, v，則因為uu, v=x，所以有x = u, u=x。 故總有x=u及x = u成立。 由x, x, y=u, u, v，x=u得x, y=u, v 再由x, y=u, v和x = u可得y = v。 定義定義3.4.2 一個有序n元組（n3）是一個有序?qū)?，其中第一個元素是第一個有序n-1元組，一個有序n元組記作x1,x2,xn，即 nnnxxxxxxx,.,.,121213.

17、4 笛卡爾乘積笛卡爾乘積 3.4.1 有序?qū)?3.4.2 笛卡爾積 3.4.3 n階笛卡爾積 3.4.2 笛卡爾積笛卡爾積 定義定義3.4.3 設(shè)A，B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)Γ羞@樣的有序?qū)M成的集合叫做A和B的笛卡爾積，記作AB。符號化表示為 從笛卡爾積的定義和邏輯演算的知識可以看出，若 則有 和 。若 ，則有 或 。 由排列組合知識不難證明，如果A中有m個元素，B中有n個元素，則AB和BA都有mn個元素。例如 ， ，則有|,ByAxyxBABAyx ,AxByBAyx ,AxBy,baA2, 1, 0B2,1,0,2,1,0,bbbaaaBA, 2, 2, 1, 1, 0, 0bababaAB3.4.2 笛卡爾積笛卡爾積 笛卡爾積運算具有以下性質(zhì)： （1）若A，B中有一個空集，則它們的笛卡爾積是空集，即 （2）若AB且A，B都不是空集時，有 即笛卡爾積運算不滿足交換律。 （3）當(dāng)A , B, C都不是空集時有 即笛卡爾積運算不滿足結(jié)合律。 （4）笛卡爾積運算對或運算滿足分配律，即ABABBACBACBA CABACBAUU ACABACBUU CABACBAII ACABACBII3.4 笛卡爾乘積笛卡爾乘積 3.4.1