離散數(shù)學(xué)課件資料.ppt

1、2020/9/10,離散數(shù)學(xué),1,第三章 集合的基本概念和運(yùn)算 3.1 集合的基本概念 3.2 集合的基本運(yùn)算 3.3 集合中元素的計(jì)數(shù),2020/9/10,離散數(shù)學(xué),2,一、集合,集 合：一些可確定的可分辨的事物構(gòu)成的整體。 用大寫(xiě)字母A, B, C, 標(biāo)記。,3.1 集合的基本概念,集合的元素：一個(gè)集合的每一個(gè)特定的事物。用小 寫(xiě)字母a, b, c, 標(biāo)記。,如:(1) 26個(gè)英文字母的集合； (2) 坐標(biāo)平面上所有點(diǎn)的集合。,規(guī)定：集合的元素之間彼此相異，無(wú)次序關(guān)系。,2020/9/10,離散數(shù)學(xué),3,二、常用的集合,常用的集合記號(hào)： N: 自然數(shù)集合(包括0 ) Z: 整數(shù)集合 Q:

2、有理數(shù)集合 R: 實(shí)數(shù)集合 C: 復(fù)數(shù)集合 : 空集(不含任何元素) E: 全集,2020/9/10,離散數(shù)學(xué),4,三、集合的表示方法,列出集合的所有元素，元素之間用逗號(hào) 隔開(kāi)。如A = a, b, c ,用謂詞概括該集合中元素的屬性。 即：A = x | P (x) 如：A = x | xZ 3 x 6 ,1、列舉法： 2、描述法：,元素與集合之間的關(guān)系(屬于): 若A=a,a,b,a,b,則aA ,a A,2020/9/10,離散數(shù)學(xué),5,3、真子集：如果B A且A B，則B是A的真子集。 記作B A。,四、集合之間的關(guān)系,1、子 集：集合B中的每個(gè)元素都是集合A中的元素， 則B是A的子集

3、，記作B A。符號(hào)化為 B A x(xB xA),2、相等集：如果A B且B A，則A與B相等。記作 A = B。符號(hào)化為A = B A B B A,顯然：A A， A,2020/9/10,離散數(shù)學(xué),6,解：0元子集：，,四、集合之間的關(guān)系（續(xù)）,4、冪 集：集合A的全體子集構(gòu)成的集合，記作P (A)。 符號(hào)化為P (A) = x | x A,例1：A = a, b, c，求A的冪集P (A)。,n 元集A的冪集P (A)含有2n個(gè)元素。,1元子集：a, b, c，,2元子集：a, b, a, c, b, c，,P(A) = , a, b, c, a, b, a, c, b, c,a, b,

4、c,3元子集：a, b, c,2020/9/10,離散數(shù)學(xué),7,四、集合之間的關(guān)系（續(xù)）,例2：計(jì)算以下冪集。 (1) P()； (2) P(,)； (3) P(1, 2, 3)。,解：(1) P () = ,(2) P (, ) = , , , , ,(3) P (1, 2, 3) = , 1, 2, 3, 1, 2, 3,2020/9/10,離散數(shù)學(xué),8,1、并：AB = x | xA xB ,一、幾種常見(jiàn)的運(yùn)算,3.2 集合的基本運(yùn)算,2、交：AB = x | xA xB ， 若AB = ，則稱(chēng)A與B不交。,3、相對(duì)補(bǔ)：A B = x | xA xB （B對(duì)A的）,4、絕對(duì)補(bǔ)：A對(duì)全集E

5、的相對(duì)補(bǔ)集，記作： A A = E A = x | xE xA ,5、對(duì)稱(chēng)差：A B = (AB)(BA) = (AB) (AB),2020/9/10,離散數(shù)學(xué),9,二、文氏圖,2020/9/10,離散數(shù)學(xué),10,三、集合算律,(1) 冪等律：,AA = A,AA = A,(2) 結(jié)合律：,(3) 交換律：,(4) 分配律：,(AB)C = A(BC),(AB)C = A(BC),AB = BA,AB = BA,A(BC) = (AB)(AC),A(BC) = (AB)(AC),2020/9/10,離散數(shù)學(xué),11,三、集合算律（續(xù)）,(5) 同一律：,A = A,AE = A,(6) 零 律：

6、,(7) 排中律：,(8) 矛盾律：,AE = E,A = ,A A = E,A A = ,A(AB) = A,A(AB) = A,(9) 吸收律：,2020/9/10,離散數(shù)學(xué),12,三、集合算律（續(xù)）,(10) 德 摩根律：,A (BC) = (A B)(A C),A (BC) = (A B)(A C), (BC) = B C, (BC) = B C, = E, E = , ( A) = A,(11) 雙重否定律：,2020/9/10,離散數(shù)學(xué),13,四、集合算律（續(xù)）,以上恒等式的證明主要通過(guò)命題演算等值式。,P Q Q P,即證xP xQ和 xQ xP 成立，,即證xP xQ,證明的基

7、本思想是：欲證P=Q，即證：,2020/9/10,離散數(shù)學(xué),14,四、集合算律（續(xù)）,例3：證明A (BC) = (A B)(A C), x A x BC, x A (x BC),證明：,x A (BC), x A (x B x C), x A (x B ) (x C), x A (x B x C), (xA x B) (xA xC), (xA B)(xA C),故：A (BC) = (A B)(A C), x ( A B)(A C),2020/9/10,離散數(shù)學(xué),15,四、常用運(yùn)算性質(zhì),(1) AB A AB B,(2) A AB B AB,(3) A B A,(4) A B = A B,(

8、5) AB = B A B AB = A A B = ,(6) A B = B A,(7) (A B) C = A (B C),2020/9/10,離散數(shù)學(xué),16,四、常用運(yùn)算性質(zhì)（續(xù)）,(8) A = A,(9) A A = ,(10) A B = A C B = C,證明兩個(gè)集合相等，除了采用命題演算等值式外，還可以采用集合運(yùn)算性質(zhì)。集合運(yùn)算性質(zhì)也可用于證明兩個(gè)集合之間的包含關(guān)系。,2020/9/10,離散數(shù)學(xué),17,四、常用運(yùn)算性質(zhì)（續(xù)）,證明： (A B)B = (A B)B,= (AB) ( BB),例4：證明(A B)B = AB,= (AB)E,= AB,2020/9/10,離散

9、數(shù)學(xué),18,四、常用運(yùn)算性質(zhì)（續(xù)）,例3：化簡(jiǎn)(ABC)(AB) (A(B C)A),解： AB ABC 和 A A(B C), (ABC)(AB) = AB,原式 = (AB) A = (AB) A = B A, (A(B C)A = A,2020/9/10,離散數(shù)學(xué),19,3.3 集合中元素的計(jì)數(shù),基數(shù)：集合中元素的個(gè)數(shù)，用|A|表示。,容斥原理：對(duì)任意兩個(gè)有限集A和B，有 |AB| = |A| + |B| |AB|,一、理論,推廣1：| ABC | = |A| + |B| + |C| |AB| |AC| |BC| + |ABC|,| | = |E| |ABC|,推廣2：,2020/9/1

10、0,離散數(shù)學(xué),20,例4：某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì) 打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球， 2人會(huì)打這三種球，而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外 一種球(指籃球或排球)，求不會(huì)打這三種球的人數(shù)？,二、應(yīng)用,解：分別用A,B,C表示會(huì)打籃球、排球、網(wǎng)球的學(xué) 生集合。,依題意有：|A| = 14，|B| = 12，|C| = 6， |AB| = 6，|AC| = 5，|ABC| = 2， 且有C AB，求| |,2020/9/10,離散數(shù)學(xué),21,二、應(yīng)用（續(xù)）,于是 C = C(AB) = (CA)(CB),| | = |E| |ABC| =25 20 = 5,從而|ABC| = |A| + |B| + |C| |AB| |AC| |BC| + |ABC| = 14 + 12 + 6 6 5 3 + 2 = 20,得 |BC| = 3,6 = 5+ |BC| 2,|C| = |AC| + |BC| |ABC|,2020/9/10,離散數(shù)學(xué),22,例5：一個(gè)班有50個(gè)學(xué)生，第一次考試有26人得5分，第二次考試有21人得5分。如果兩次考試都沒(méi)得5分