離散數(shù)學(xué)課件：3-2 集合的基本概念與運(yùn)算

1、只有一、二年級的學(xué)生才愛好體育運(yùn)動只有一、二年級的學(xué)生才愛好體育運(yùn)動A: 一年級大學(xué)生的集合一年級大學(xué)生的集合 B：二年級大學(xué)生的集合：二年級大學(xué)生的集合C：計(jì)算機(jī)學(xué)院學(xué)生的集合：計(jì)算機(jī)學(xué)院學(xué)生的集合 D：數(shù)學(xué)學(xué)院學(xué)生的集合：數(shù)學(xué)學(xué)院學(xué)生的集合E：選修離散數(shù)學(xué)的學(xué)生集合：選修離散數(shù)學(xué)的學(xué)生集合F：愛好文學(xué)學(xué)生的集合：愛好文學(xué)學(xué)生的集合 G：愛好體育運(yùn)動學(xué)生的集合：愛好體育運(yùn)動學(xué)生的集合E (D C ) B C B E(D A) E =D F G G A B 除去除去數(shù)學(xué)學(xué)院和計(jì)算機(jī)學(xué)院二數(shù)學(xué)學(xué)院和計(jì)算機(jī)學(xué)院二年級學(xué)生外年級學(xué)生外都都不選修不選修離散數(shù)學(xué)離散數(shù)學(xué)寫出下列句子對應(yīng)集合表達(dá)式 所有所

2、有計(jì)算機(jī)學(xué)院二計(jì)算機(jī)學(xué)院二年級學(xué)生都選修離散數(shù)學(xué)年級學(xué)生都選修離散數(shù)學(xué)數(shù)學(xué)學(xué)院一數(shù)學(xué)學(xué)院一年級的學(xué)生都沒有選修離散數(shù)學(xué)年級的學(xué)生都沒有選修離散數(shù)學(xué)數(shù)學(xué)學(xué)院學(xué)生數(shù)學(xué)學(xué)院學(xué)生或愛好文學(xué)或愛好體育運(yùn)動或愛好文學(xué)或愛好體育運(yùn)動第3章 集合的基本概念和運(yùn)算3.1 集合的基本概念3.2 集合的基本運(yùn)算3.3 集合中元素的計(jì)數(shù)3.2 集合的基本運(yùn)算n集合的基本運(yùn)算n并并 A B = x | x A x B n交交 A B = x | x A x B n相對補(bǔ)相對補(bǔ) A B = x | x A x B n絕對補(bǔ)絕對補(bǔ) A = E A = x | x A （A的絕對補(bǔ)集是的絕對補(bǔ)集是 A 對對 E 的相對補(bǔ)集）

3、的相對補(bǔ)集）n對稱差對稱差 A B文氏圖表示文氏圖表示集合的并和交運(yùn)算的性質(zhì)n滿足交換律nA B= B A A B = B An滿足冪等律nA A = A A A = An滿足對的分配律、 對的分配律nA (B C) = (A B) (A C)nA (B C) = (A B) (A C)nA =A A = 對于n個(gè)集合A1，A2.An的并集和交集為: 121niniAAAA |()()ixi xAn個(gè)集合的并和交12 |nx xAxAxA 121niniAAAA12 |nx xAxAxA |()()ixi xAn設(shè)A,B為集合，B對A的相對補(bǔ)集AB定義為：n重要結(jié)論： 集合相對補(bǔ)與絕對補(bǔ)的關(guān)系

4、將相對補(bǔ)集與絕對補(bǔ)集聯(lián)系在一起 n設(shè)A，B為集合，則A與B的對稱差是集合的對稱差運(yùn)算 A B = (A-B) ( B-A)= (A B) (B A) 其文氏圖如下：其文氏圖如下： A B =(A B) (A B)集合對稱差運(yùn)算的性質(zhì)n滿足交換律滿足交換律nA B = B An滿足結(jié)合律滿足結(jié)合律n(A B) C = A (B C )nA = A A A = nA B = A C B = C 交換交換A B=B AA B=B AA B=B A結(jié)合結(jié)合(A B) C=A (B C)(A B) C=A (B C)(A B) C=A (B C)冪等冪等A A=AA A=A 與與 與與 分配分配 A (

5、B C)=(A B) (A C)A (B C)=(A B) (A C)A (B C)=(A B) (A C)吸收吸收A (A B)=AA (A B)=A集合運(yùn)算的算律吸收律的前提：吸收律的前提： 、 可交換可交換集合運(yùn)算的算律（續(xù)） D.M 律律A (B C)=(A B) (A C)A (B C)=(A B) (A C) (B C)= BC (B C)= BC雙重否定雙重否定A=AE補(bǔ)元律補(bǔ)元律AA=AA=E零律零律A=A E=E同一律同一律A=AA E=A否定否定=E E=例題n例例3.5 證明證明 : (A-B) B=A B證證: (A-B) B = (A B) B = (A B) (B

6、B) = A BAB=A B例3.4 證明式3.17n證明：證明：A(B C)(A B) ( AC)n證證: 對對 x， x (A(B C) = x A x (B C) = x A (x B x C) = x A ( x B x C) = x A (x B x C) = (x A x B) (x A x C) = x (AB) x (AC) = x (AB) (AC) 所以所以 A(B C)(AB) (AC)A-B=x|x A x B集合包含的證明方法n證明證明 X Yn命題演算法命題演算法n包含傳遞法包含傳遞法n等價(jià)條件法等價(jià)條件法n反證法反證法n并交運(yùn)算法并交運(yùn)算法以上的以上的 X, Y

7、代表集合公式代表集合公式任取任取 x ， x X x Y命題演算法證 X Yn證證: (1) A B P(A) P(B) 任取任取x, x P(A) x A x B x P(B) (2) P(A) P(B) A B 任取任取x x A x A x P(A) x P(B) x B x B 例例1 證明證明 A B P(A) P(B)X Yx (x Xx Y)包含傳遞法證 X Y找到集合找到集合T 滿足滿足 X T 且且 T Y，從而有，從而有X Y例例2 A B A B證證 因?yàn)橐驗(yàn)?A B A 而而 A A B 所以所以 A B A B 利用包含的等價(jià)條件證 X Y A-BABABBABA (

8、1) 證證 (A B) C=C A C A C =C B C B C =C (A B) C = A (B C) = A C =C(A B) C=C A B C (2) 證證 (A B) C= A B A C A C = A B C B C = B (A B) C = (A C) (B C) = A B(A B) C=A BA B C例例3 A C B C A B C 反證法證 X Y欲證欲證X Y, 假設(shè)命題不成立，必存在假設(shè)命題不成立，必存在 x 使得使得 x X 且且 x Y. 然后推出矛盾然后推出矛盾. 例例4 證明證明 A C B C A B C證證: 假設(shè)假設(shè) A B C 不成立，則

9、不成立，則 A B C x (x A B x C) x (x A x B) x C) x (x A x C) (x B x C) x ( x A x C) x (x B x C) A C B C （與前提矛盾）（與前提矛盾）Q P P Q A B x(x A x B)利用已知包含式并交運(yùn)算證 X Y例例5 證明證明 A C B C A C B C A B證證: 上述兩條件分別兩邊上述兩條件分別兩邊求并，得求并，得 (A C) (A C) (B C) (B C) (A C) (A C) (B C) (B C) A (C C) B (C C) A E B E A B由已知包含式通過運(yùn)算產(chǎn)生新的包含

10、式由已知包含式通過運(yùn)算產(chǎn)生新的包含式 (X Y)(SW ) (X S) (Y W ) (X Y)(SW ) (X S) (Y W )集合相等的證明方法n證明證明 X=Yn命題演算法命題演算法n等式替換法等式替換法n反證法反證法n運(yùn)算法運(yùn)算法以上的以上的 X, Y 代表集合公式代表集合公式 例例6 證明證明 A (A B)=A （吸收律）（吸收律） 證證 任取任取x, x A (A B) x A x (A B) x A (x A x B) x A 命題演算法證明X=Y任取任取 x ， x X x Y x Y x X 或者或者 x X x Y X (X Y)XX Y Y XA=B x(x Ax B

11、)等式替換證明X=Y例例7 證明證明A (A B)=A （吸收律）（吸收律）證證 ( (假設(shè)假設(shè)分配律、同一律、零律分配律、同一律、零律成立成立) ) A (A B) =(A E) (A B) 同一律同一律 =A (E B) 分配律分配律 =A E 零律零律 =A 同一律同一律不斷進(jìn)行代入化簡，最終得到兩邊相等不斷進(jìn)行代入化簡，最終得到兩邊相等反證法證明X=Y例例8 證明證明 A B A B =證證: 假設(shè)假設(shè) A B ，即，即 x (x A x B) x ( x A x B) x (x A x B) A B 與條件與條件 A B 矛盾矛盾. 所以所以， 結(jié)論正確。結(jié)論正確。假設(shè)假設(shè) X=Y

12、不成立，則存在不成立，則存在 x 使得使得 x X且且x Y，或者或者存在存在 x 使得使得 x Y且且x X，然后推出矛盾，然后推出矛盾. A Bx(x A x B)集合運(yùn)算法證明X=Y例例9 證明證明 A C=B C A C=B C A=B證證: 由第二個(gè)條件減第一個(gè)條件由第二個(gè)條件減第一個(gè)條件得得 (A C)-(A C)=(B C)-(B C) 從而有從而有 A C=B C (A C) C =(B C) C A (C C) =B (C C) A = B A=B由已知等式通過運(yùn)算產(chǎn)生新的等式由已知等式通過運(yùn)算產(chǎn)生新的等式 (X=Y)(Z=W) X Z=Y W, X Z=Y W, X-Z=Y-W例題n例例3.6 化簡化簡 : (A B C) (A B) (A (BC ) A)證證: 因?yàn)椋阂驗(yàn)椋?(A B C) (A B) = (A B) (A (BC ) A = A 所以，原式所以，原式= (A B) A = (A B) A = B A = B A 例：對于任意集合A、B和C，給出 (A-B) (A-C)=