離散數(shù)學(xué)集合的運算

離散數(shù)學(xué)集合的運算1第1頁，共24頁，2023年，2月20日，星期一集合的運算以給定的集合為對象,按照確定的規(guī)則得到另一些集合。集合的另一種表示法是文氏圖（VennDiagram）。人們常用文氏圖描述集合運算和它們之間的關(guān)系。集合的文氏圖畫法如下：用矩形表示全集E，在矩形中畫一些圓表示其它集合，不同的圓代表不同的集合。如果沒有特別說明，任何兩個圓彼此相交。例如，AB的文氏圖如圖2第2頁，共24頁，2023年，2月20日，星期一一、交P87定義3-2.1

設(shè)A，B是集合，由A與B的公共元素組成的集合，稱為A和B的交集，記為A∩B。

A∩B=x|xA∧xB

交集的定義如圖右圖所示。

從交集的定義可以得到：

A∩BA，A∩BB例1例2例3及性質(zhì)P87*如果A與B無公共元素，即A∩B=?，則稱A和B是互不相交的。例如，令A(yù)=a,b,c，B=d,e，則A∩B=?，A和B是互不相交的。3第3頁，共24頁，2023年，2月20日，星期一一、并P88定義3-2.2

設(shè)A，B是任意的集合，由A中的元素或B中的元素組成的集合，稱為A和B的并集，記為A∪B。

A∪B=x|xA∨xB

并集的定義如右圖所示。

并集的定義可以得到：

AA∪B，BA∪BP88例題集合并運算性質(zhì)定理3-2.13-2.24第4頁，共24頁，2023年，2月20日，星期一三、補（差）P90定義3-2.3

設(shè)A，B是集合，屬于A的而不屬于B的元素組成的集合，稱為B對于A的補集，也叫B對于A的相對補集。記為A-B。

A-B=x|xA∧xBA-B也稱集合A和B的差

相對補集定義如右圖所示。

例如，令A(yù)=?,?，B=?，則

A-B=?,?-?=?,?

又如，令C=a，D=a,b，則

C-D=a-a,b=?C-C=?P90例題3、4

5第5頁，共24頁，2023年，2月20日，星期一四、絕對補定義3-2.4

設(shè)A是集合，A對于全集E的相對補集，稱為A的絕對補，記為~A。

~A=E-A=x|xE∧xA=x|xA~A的定義如圖所示。

例如，令全集E=1,2,3,4，A=

1,2,3，則

~A=1,2,3,4-1,2,3=4P90絕對補運算性質(zhì)6第6頁，共24頁，2023年，2月20日，星期一四、絕對補例設(shè)A,B是任意的集合，求證:A-B=A∩(~B)

證明：

xA-BxA∧xBxA∧x~B

xA∩~B即A-BA∩~B。

xA∩~BxA∧x~BxA∧xBxA-B

故A∩~BA-B

所以，A-B=A∩(~B)。

A-B=A∩(~B)是一個重要的公式，在集合的運算中經(jīng)常用到，它的意義在于將相對補運算轉(zhuǎn)換絕對補和交運算。P91定理3-2.5設(shè)A、B為任意兩個集合，則下列關(guān)系式成立：a)A-B=A∩~Bb)A-B=A-(A∩B)P91定理3-2.6交運算對差運算的分配P91定理3-2.7

7第7頁，共24頁，2023年，2月20日，星期一五、對稱差

P92定義3-2.5設(shè)A，B是集合，由A中元素或B中元素，但不是A與B的公共元素組成的集合，稱為A和B的對稱差，記為A

B。

AB=x|xAxB=(A-B)∪(B-A)=(A∪B)-(A∩B)AB的定義如圖所示。

例如，令A(yù)=1,2,3,4，

B=

1,2,5,6，則

AB=A∪B-A∩B=1,2,3,4,5,6-1,2=3,4,5,68第8頁，共24頁，2023年，2月20日，星期一五、對稱差

例設(shè)A,B是任意的集合，求證:

AB=(A-B)∪(B-A)=(A∩~B)∪(B∩~A)。

證明：先證AB=(A-B)∪(B-A)。

xAB(xA)(xB)

((xA)∧(xB))∨((xA)∧(xB))(xA∧xB)∨(xA∧xB)xA-B∨xB-Ax(A-B)∪(B-A)

所以，AB=(A-B)∪(B-A)。再證(A-B)∪(B-A)=(A∩~B)∪(B∩~A)。很容易得到此結(jié)論，這里從略。9第9頁，共24頁，2023年，2月20日，星期一五、對稱差利用例3.7中的公式可以證明對稱差A(yù)B下列的性質(zhì)。設(shè)A,B是任意的集合。①AA=?

證明：AA=(A-A)∪(A-A)=??=?②A

?=A

證明：A

?=(A-?)∪(?-A)=A∪?=A③AE=~A

證明：AE=(A-E)∪(E-A)=?∪~A=~A此外：滿足交換律結(jié)合律P94圖3-2.7及結(jié)論10第10頁，共24頁，2023年，2月20日，星期一六、五種集合運算的性質(zhì)對以上運算，可知其具性質(zhì)：1）冪等：AA=A，AA=A2）交換：AB=BA，AB=BA3）結(jié)合：（AB）C=A（BC）（AB）C=A（BC）4）分配：A（BC）=（AB）（AC）

A（

BC）=（AB）（AC）5）吸收：A（AB）=AA（AB）=A11第11頁，共24頁，2023年，2月20日，星期一六、五種集合運算的性質(zhì)6）互補：AA=，AA=E7）德摩根：（AB）=AB（AB）=AB8）同一：A=A，EA=A9）零律：AE=E，A=10）雙重否定：（A）=A11）E=12）

=E*以上共21個性質(zhì)，都須證明12第12頁，共24頁，2023年，2月20日，星期一六、五種集合運算的性質(zhì)例如：證明分配律A（BC）=（AB）（AC）

證：任取aA(BC)

即aA且aBC

即aA且aB或aC

即aA且aB或aA且aC

即是aAB或aAC

就是a(AB)(AC)

A(BC)(AB)(AC)反之，任取

a(AB)(AC)

即aAB或aAC

就是aA且aB或aA且aC

即aA且aB或aC

aA(BC)A(BC)(AB)(AC)

A(BC)=(AB)(AC)13第13頁，共24頁，2023年，2月20日，星期一練習(xí)例1：設(shè)F表示一年級大學(xué)生的集合，S表示二年級大學(xué)生的集合，R表示計算機科學(xué)系學(xué)生的集合，M表示數(shù)學(xué)系學(xué)生的集合，T表示選修離散數(shù)學(xué)學(xué)生的集合，L表示愛好文學(xué)學(xué)生的集合，P表示愛好體育運動學(xué)生的集合。則下列各句子所對應(yīng)的集合表達式分別是：（1）所有計算機科學(xué)系二年級的學(xué)生都選修離散數(shù)學(xué)。（A）（2）數(shù)學(xué)系的學(xué)生或者愛好文學(xué)或者愛好體育運動。（B）（3）數(shù)學(xué)系一年級的學(xué)生都沒有選修離散數(shù)學(xué)。（C）（4）只有一、二年級的學(xué)生才愛好體育運動。（D）（5）除去數(shù)學(xué)系和計算機科學(xué)系二年級的學(xué)生外都不選修離散數(shù)學(xué)。（E）14第14頁，共24頁，2023年，2月20日，星期一練習(xí)答案：A：RST；B：MLP；C：(MF)T=；D：PFS；E：T(MR)S。（1）計算機系二年級學(xué)生的集合為RS，選修離散數(shù)學(xué)的學(xué)生集合為T，前者為后者子集。（2）數(shù)學(xué)系學(xué)生集合為M，愛好文學(xué)或愛好體育學(xué)生集合為LP，前者為后者子集。（3）數(shù)學(xué)系一年級學(xué)生集合為MF,選修離散數(shù)學(xué)學(xué)生集合為T，這兩個集不相交。（4）只有P才Q，這種句型的邏輯含義是如果Q則P。所以這句話可理解為：愛好體育的學(xué)生一定是一、二年級的學(xué)生。愛好體育的學(xué)生構(gòu)成集P，一、二年的學(xué)生構(gòu)成集FS，前者為后者子集。（5）除去P都不Q，這種句型的邏輯含義可理解為如果Q則P。原來句子就變?yōu)椋哼x修離散數(shù)學(xué)的學(xué)生都是數(shù)學(xué)系和計算機系二年級的學(xué)生。所以T(MR)S。15第15頁，共24頁，2023年，2月20日，星期一練習(xí)例2：設(shè)S1＝{1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},S5={3,5}確定在以下條件下x可能與S1,…,S5中哪個集合相等。（1）若xS5=

，則（A）。（2）若xS4但xS2=，則（B）。（3）若xS1且xS3，則（C）（4）若x-S3=，則（D）（5）若xS3且xS1，則（E）16第16頁，共24頁，2023年，2月20日，星期一練習(xí)答案：A：x=S2；B：x=S5C：x=S1,S2或S4；D：x=S3或S5：x與其中任何集合都不相等。分析：（1）與S5不相交的集合不含3和5，只能是S2。（2）只有S4和S5是S4的子集，但S4S2，所以S5滿足要求。（3）xS3意味著x中必含有偶數(shù)，S1,S2和S4中含有偶數(shù)并且都是S1的子集。（4）由x-S3=知xS3。因此x可能是S3或S5。（5）由于S3S1，所以有xS3S1與xS1矛盾。x與這5個集合中的任一個都不相等。17第17頁，共24頁，2023年，2月20日，星期一練習(xí)例某班有50名學(xué)生，第一次考試中26人成績?yōu)閮?yōu)，第二次考試中21人成績?yōu)閮?yōu)，已知兩次考試中都不為優(yōu)的共17人。問兩次考試中都為優(yōu)的有多少人？（用文氏圖解）

18第18頁，共24頁，2023年，2月20日，星期一練習(xí)例某班有50名學(xué)生，第一次考試中26人成績?yōu)閮?yōu)，第二次考試中21人成績?yōu)閮?yōu)，已知兩次考試中都不為優(yōu)的共17人。問兩次考試中都為優(yōu)的有多少人？解：設(shè)A，B分別表示第一次和第二次考試中成績?yōu)閮?yōu)的學(xué)生集合。畫出文氏圖，如圖3.7所示。首先填A(yù)∩B中的人數(shù)，這正是要求的，設(shè)為x。A-B中的人數(shù)是26-x，

B-A中的人數(shù)是21-x，分別填入對應(yīng)的區(qū)域。并列出如下方程：

(26-x)＋x＋(21-x)＋17=50

解得：x=14

19第19頁，共24頁，2023年，2月20日，星期一約定和說明為了使集合的表達式更加簡潔，我們對集合運算的優(yōu)先順序規(guī)定如下：絕對補的運算級別比其它的4個運算高，先進行絕對補運算，再進行其它的4個運算；其它的4個運算的運算順序由括號決定。由于并運算滿足結(jié)合律，故約定以下的符號：由于交運算滿足結(jié)合律，故約定以下的符號：20第20頁，共24頁，