離散數(shù)學(xué)講義第四章集合論

1、n集合的概念與表示 n集合的運(yùn)算 nVenn氏圖及容斥原理 n集合的劃分 4.1 集合的概念與表示集合的概念與表示 將一個(gè)確定的，可以區(qū)分的事物的全體 稱為集合集合，而這些事物稱為集合的元素。元素。 若a是A的元素 稱a屬于A，記作a a A A。 若a不是A的元素 稱a不屬于A，記作a a A A。 集合用大寫字母A，B,來(lái)表示，而集 合的元素一般用小寫字母表示 元素個(gè)數(shù)有限的集合稱為有限集有限集。元素 個(gè)數(shù)無(wú)限的集合稱為無(wú)限集。無(wú)限集。有限集的元 素的個(gè)數(shù)記作A或#A，稱為A的基數(shù)?；鶖?shù)。 4.1 集合的概念與表示集合的概念與表示 關(guān)于集合，有兩點(diǎn)特別注意關(guān)于集合，有兩點(diǎn)特別注意： 1）集

2、合元素的無(wú)序性無(wú)序性 2）集合中的元素不計(jì)重度不計(jì)重度 n集合的表示方法： n列舉法 例如：A=a,b,c,d N=0,1,2 Zm=0,1,2,m-1 4.1 集合的概念與表示集合的概念與表示 n集合的表示方法： n謂詞描述法： A= x x具有某種性質(zhì) 例如： B= x 1x5,xR C= x x2-1=0, xR D=(x,y)x2+y21，x,yR 4.1 集合的概念與表示集合的概念與表示 n集合的表示方法： n遞歸法： (1)基本項(xiàng) (2)遞歸項(xiàng) (3)極小化 例如：集合Ck=0,k,2k,.的遞歸定義： 1）0Ck 2）若nCk,則n+kCk 4.1 集合的概念與表示集合的概念與表

3、示 4.1 集合的概念與表示集合的概念與表示 n集合間的關(guān)系： n包含： n相等： A A B B x(xx(x A A x x B)B) AB也可記作BA A A= =B B x(xx(x A Ax x B)(xB)(x B Bx x A A) A A BBBB A A 4.1 集合的概念與表示集合的概念與表示 n集合間的關(guān)系： n真包含： A A B Bx(xx(x A Ax x B)B)$ $x(xx(x BB x xA A) ) A A BBBBA A A B也可記作BA 4.1 集合的概念與表示集合的概念與表示 n特殊集合 n空集： 不含任何元素的集合稱為空集，記作 性質(zhì)：性質(zhì)：空集

4、是任何集合的子集 推論推論：空集是唯一的 給定一個(gè)非空集合A,則和A稱為A的 平凡子集。 4.1 集合的概念與表示集合的概念與表示 n特殊集合 n全集： 在所研究的同一個(gè)問(wèn)題中，如果涉及到的 集合均是某一個(gè)集合的子集，則稱該集合是 全集，記作。 4.1 集合的概念與表示集合的概念與表示 n特殊集合 n冪集： 設(shè)A是一個(gè)集合，由A的所有子集組成 的集合稱為A的冪集，記作(A)或2 2A 謂詞描述法表示：（A）=uuA 4.1 集合的概念與表示集合的概念與表示 例如：設(shè)例如：設(shè)A=0A=0，1 1，22寫出寫出A A的全部子集的全部子集 解：解：A A的的0 0元子集：元子集： A A的的1 1元

5、子集：元子集：00，11，22 2 2元子集：元子集：00，11，00，22，11，22 3 3元子集：元子集：00，1 1，2 2 定理：如定理：如A A是有限集，若是有限集，若 A A =n=n則則 (A)(A) =2=2n n 4.1 集合的概念與表示集合的概念與表示 例例：A=a,b,寫 （A） 解解: （A）=，a,b,a,b 例例：設(shè)A=a, 判斷下列結(jié)論是否正確 (1)A，(2)A，(3)A， (4)A,(5)aA,(6)aA, (7)aA,(8)aA 解解：1)，2），3），5），8）是正確的 4.2 集合的運(yùn)算集合的運(yùn)算 設(shè)設(shè)A和和B是兩個(gè)集合，定義是兩個(gè)集合，定義 A A

6、B=xB=x x x A A x x BB A A B=xB=x x x A A x x BB A-B=x A-B=x x x AxAx BB A=xA=x x x A A且且x x EE A A B=xB=x x x A A且且x x B B x x B B且且x x AA 定理：設(shè)定理：設(shè)A A、B B、C C是三個(gè)集合，則有是三個(gè)集合，則有 (1)A(1)A A A B B，B B A A B B (2)A(2)A B B A A，A A B B B B。 (3)A(3)A B B A A B B (4)(4)若若A A B B則則A A B=AB=A，A A B=BB=B。 4.2 集

7、合的運(yùn)算集合的運(yùn)算 4.2 集合的運(yùn)算集合的運(yùn)算 n交換律交換律 A A B=BB=B A A，A A B=BB=B A A n結(jié)合律結(jié)合律 （A A B B） C=AC=A （B B C C） （A A B B） C=A C=A（B B C C） n分配律分配律 A A （B B C C）= =（A A B B） （A A C C） A A （B B C C）= =（A A B B） （A A C C） n冪等律冪等律 A A A=AA=A，A A A=AA=A n同一律同一律 A A=A,A=A,A E=AE=A 4.2 集合的運(yùn)算集合的運(yùn)算 n零一律零一律 A A= =，A A E=EE

8、=E n補(bǔ)余律補(bǔ)余律 A AA=A=，A AA=EA=E n吸收律吸收律 A A （A A B B）=A =A A A （A A B B）=A=A n德摩根律德摩根律 （A A B B）= = A AB B （A A B B）= = A AB B n雙重否定律雙重否定律 （ A A）=A=A 4.2 集合的運(yùn)算集合的運(yùn)算 謂詞的等價(jià)與集合的相等包含之間的相似謂詞的等價(jià)與集合的相等包含之間的相似 性討論：性討論： 用謂詞定義集合的方法稱為指定原理。被用謂詞定義集合的方法稱為指定原理。被 某一謂詞指定的子集稱為該謂詞在全集中的一某一謂詞指定的子集稱為該謂詞在全集中的一 個(gè)廣延。個(gè)廣延。 如果兩個(gè)謂

9、詞是等價(jià)的，則它們具有相同如果兩個(gè)謂詞是等價(jià)的，則它們具有相同 的外延。即等價(jià)謂詞指定的集合是相等的。的外延。即等價(jià)謂詞指定的集合是相等的。 4.3 Venn圖及容斥原理圖及容斥原理 nVennVenn圖圖 A A B B A A B BA A-B B 4.3 Venn圖及容斥原理圖及容斥原理 n容斥原理容斥原理 |A|A B|=|A|+|B|-| AB|=|A|+|B|-| A B |B | 解解 設(shè)職員和學(xué)生的集合分別是設(shè)職員和學(xué)生的集合分別是A A和和B B。 由已知條件由已知條件 A A =10,=10, B B =12, =12, A A B B =5=5 A A B B = = A

10、 A + + B B - - A A B B =10+12-5=17=10+12-5=17 則則(A(A B)B) = = E E - - A A B B =20-17=3=20-17=3 有有3 3名既不是職員又不是學(xué)生名既不是職員又不是學(xué)生 例例 在在2020名青年有名青年有1010名是公司職員名是公司職員,12,12名名 是學(xué)生是學(xué)生, ,其中其中5 5名既是職員又是學(xué)生名既是職員又是學(xué)生, ,問(wèn)有問(wèn)有 幾名既不是職員幾名既不是職員, ,又不是學(xué)生？又不是學(xué)生？ 4.3 Venn圖及容斥原理圖及容斥原理 4.3 Venn圖及容斥原理圖及容斥原理 n 三個(gè)集合的容斥定理三個(gè)集合的容斥定理

11、A A B B C C = = A A + + B B + + C C - - A A B B - - A A C C - - B B C C + + A A B B C C n n n個(gè)集合的容斥定理個(gè)集合的容斥定理 A A1 1 A A2 2 . . A An n = = |A|Ai i|-|- |A|Ai i A Aj j|+|+ |A|Ai i A Aj j A Ak k| | + +.+(-1)+(-1)n-1 n-1|A |A1 1 A A2 2 . A An n| | 4.3 集合的劃分集合的劃分 定義定義4.4.1 設(shè)設(shè)A是一非空集合，是一非空集合，是是A的非的非 空子集組成的

12、集合，若空子集組成的集合，若 1 1） S S1 1,S,S2 2，要么，要么S S1 1 S S2 2=，要么要么S S1 1= =S S2 2 2 2） 則稱則稱是集合是集合A的劃分的劃分.|稱為劃分稱為劃分的秩。的秩。 S SA n集合的劃分集合的劃分 4.3 集合的劃分集合的劃分 n關(guān)于集合的劃分的理解：關(guān)于集合的劃分的理解： n劃分中的每一塊是非空的劃分中的每一塊是非空的 n劃分中的任意兩塊沒有公共元素劃分中的任意兩塊沒有公共元素 nA的一個(gè)劃分耗盡了的一個(gè)劃分耗盡了A中的所有元素中的所有元素 例例 設(shè)設(shè)A=a,b,c,考察下列由考察下列由A的非空子集組成的非空子集組成 的集合是否是

13、的集合是否是A的劃分？的劃分？ 1 1=a,b,b,c =a,b,b,c 2 2=a,a,b,a,b,c=a,a,b,a,b,c 3 3=a,b,c =a,b,c 4 4=a,b,c =a,b,c 5 5=a,b,c =a,b,c 6 6=a,a,b =a,a,b 解答：解答： 3 3 、 、4 4 、 、 5 5是是A A的劃分。的劃分。 4 4稱為最?。ù郑﹦澐?，稱為最?。ù郑﹦澐郑?5 5稱為最大稱為最大 （細(xì)）劃分。（細(xì)）劃分。 4.3 集合的劃分集合的劃分 4.3 集合的劃分集合的劃分 設(shè)設(shè)A是一非空集合，是一非空集合，是是A的非空子集組成的的非空子集組成的 集合，若集合，若 ，則稱

14、，則稱是集合是集合A的覆的覆 蓋蓋. n集合的覆蓋集合的覆蓋 S SA 4.3 集合的劃分集合的劃分 設(shè)設(shè)1 1=A1 1,A2 2, .,Ar r和和2 2=B1 1,B2 2, .,Bt t是集是集 合合A的兩個(gè)不同劃分，則稱所有使的兩個(gè)不同劃分，則稱所有使 Ai i Bj j （i=1,2,.,r;j=1,2,.,t)i=1,2,.,r;j=1,2,.,t)者組成的集合者組成的集合稱稱 為為1 1和和2 2的交叉劃分的交叉劃分。 n交叉劃分與細(xì)分交叉劃分與細(xì)分 1 12 2 定理定理 集合集合A的劃分的劃分1 1 和 和2 2的交叉的交叉 劃分是劃分是A的劃分的劃分。 4.3 集合的劃分集合的劃分 4.3 集合的劃分集合的劃分 設(shè)設(shè)1 1=A1 1,A2 2, .,Ar