第六章集合代數

SetAlgebra

第七章二元關系

BinaryRelation

第八章函數

Function第二部分集合論

SetTheory重點第六章集合代數6.1集合的基本概念6.2集合的運算6.3有窮集合的計數6.4集合恒等式一些確定的、能區分的對象的全體是集合。集合通常用大寫的英文字母表示。組成集合的對象叫做集合的元素。元素常用小寫的英文字母表示。

6.1集合的基本概念

什么是集合？集合的例子①26個英文字母組成一個集合，任一英文字母是該集合的元素。②直線上的所有點組成實數集合R，每一個實數是集合R的元素。③全體命題組成一個集合，每個命題都是集合的元素。元素與集合的“隸屬”關系

設S是集合，a是S的一個元素，記為aS，讀做“a屬于S”，也可讀做“a在S中”。如果a不是S的元素，記為aS，讀做“a不屬于S”，也可讀做“a不在S中”。對集合的進一步理解①對于一個集合而言，一個對象，要么屬于這個集合，要么不屬于這個集合，是唯一確定的（二元論）。②集合的元素又是能區分的，能區分的是指集合中的元素是互不相同的。如果一個集合中有幾個元素相同，算做一個。③集合的元素又是無序的。④集合也可以作為其它集合的元素。集合的表示①列舉法在花括號“”中列舉出該集合的元素，元素之間用逗號隔開。例如：A=1,2,3,4,5B=1,2,3,…Z=0,1,-1,2,-2,…D=T,F集合的表示②謂詞表示法例如：Q=x|x是有理數R=x|x是實數D=x|x是重言式一般地說，集合可用描述法表示為：

S=x|A(x)

其中A(x)是謂詞。

aS

的充分必要條件是A(a)為真。有限集與基數具有有限個元素的集合叫有限集（n元集合），否則叫無限集。有限集元素的個數稱為該集合的基數，也叫集合的勢。有限集A的基數記為|A|

例如：設A=a,b,c，A是有限集，A的基數|A|=3集合之間的包含關系

定義6.1

設A，B是任意的集合，如果B的每一元素都是A的元素時，則稱B是A的子集，也稱B包含在A內或A包含B.記為BA當B不是A的子集時，記為B?ABA符號化表示為：

BAx(xB→xA)B?A表示為：

B?Ax(xB∧xA)集合之間的相等關系定義6.2設A，B是集合，如果AB且BA，則稱A與B相等。記為A=B如果A與B不相等，記為A≠B集合相等的符號化表示：

A=BAB∧BA真子集定義6.3設A，B是集合，如果BA且A≠B，則稱B是A的真子集。記為BA如果B不是A的真子集，記為BA真子集的符號化表示為：

BABA∧B≠Ax(xB→xA)∧x(xA∧xB)空集—小而無內定義6.4不包含任何元素的集合叫空集。記為Φ|Φ|=0定理6.1

空集是任意集合的子集。證明：ΦA(x)(xΦ→xA)推論空集是惟一的。冪集—子集的集合定義6.5設A是集合，A的所有子集構成的集合稱為A的冪集，記為P(A)，即

P(A)=x|xA【例6.1】

設A=a,b,c，Φ是空集，試求P(A)，P(P(Φ)).

解：P(A)=Φ,a,b,c,a,b,a,c,b,c,a,b,cP(Φ)=ΦP(P(Φ))=Φ,Φ

|P(A)|=？|P(Φ)|=？冪集的基數定理設A為有限集合，則

|P(A)|=2|A|定義6.6在一個具體問題中，如果所涉及的集合都是某個集合的子集，則稱這個集合為全集（大而無外），記為E.全集是相對的，不同的問題有不同的全集。即使是同一問題也可以取不同的全集。練習96-97頁習題六38練習請用集合的語言描述：指令程序軟件軟件是程序與文檔的集合程序是指令的集合機器語言是機器指令的集合

集合的另一種表示法是文氏圖（VennDiagram）。集合的文氏圖畫法如下：

用矩形表示全集E，在矩形中畫一些圓表示其它集合，不同的圓代表不同的集合。如果沒有特別說明，任何兩個圓彼此相交。

6.2集合的運算A為B的真子集并運算定義6.7

設A，B是任意的集合，由A中的元素或B中的元素組成的集合，稱為A和B的并集，記為A∪B.

A∪B=x|xA∨xB從并集的定義可以得到：AA∪B，BA∪B交運算定義6.7設A，B是集合，由A與B的公共元素組成的集合，稱為A和B的交集，記為A∩B.

A∩B=x|xA∧xB從交集的定義可以得到：A∩BA，A∩BB

如果A與B無公共元素，即A∩B=Φ，則稱A和B是互不相交的。補運算——相對補定義6.7

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

A-B=x|xA∧xB

例如，令C=a，D=a,b，則C-D=a-a,b=ΦC-C=Φ補運算——絕對補定義6.9設A是集合，A對于全集E的相對補集，稱為A的絕對補集，記為～A.

～A=E-A=x|xE∧xA

=x|xA例如，令全集E=1,2,3,4，A=1,2,3，則

～A=1,2,3,4-1,2,3=4對稱差定義6.8

A、B是集合,由屬于A而不屬于B，或者屬于B而不屬于A的元素構成的集合,稱之為A與B的對稱差。記為AB.

AB=(A-B)∪(B-A)={x|(x∈A∧xB)∨(x∈B∧xA)}

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

課后閱讀N個集合的交與并無窮個集合的交與并廣義交廣義并【例】計數問題某班有50名學生第一次考試中26人成績為優第二次考試中21人成績為優已知兩次考試中都不為優的共17人問兩次考試中都為優的有多少人？

6.3有窮集的計數解：設A，B分別表示第一次和第二次考試中成績為優的學生集合。(26-x)＋x＋(21-x)＋17=50x=14|～A∩

～B|=17包含排斥原理例如有A、B兩個商店，A店經營1000種商品，B店經營1200種商品，其中有100種商品兩個商店都經營，問兩個商店共經營多少種商品？顯然

|A∪B|=|A|+|B|-|A∩B|

ABA∩BA∪B對A、B、C三個有限集合，則

|A∪B∪C|=|A|+|B|+|C|－|A∩B|－|A∩C|－|B∩C|+|A∩B∩C|

包含排斥原理定理6.2一般地，有n個有限集合A1,A2,...An,則例題某個研究所有170名職工，其中

120人

會英語，

80人

會法語，

60人

會日語，

50人

會英語和法語，

25人

會英語和日語，

30人

會法語和日語，10人

會英語、日語和法語。問有多少人不會這三種語言？解：令U為全集，E、F、J分別為會英語、法語和日語人的集合。|U|=170|E|=120|F|=80|J|=60|E∩F|=50|E∩J|=25|F∩J|=30|E∩F∩J|=10|E∪F∪J|=|E|+|F|+|J|-|E∩F|-|E∩J|-|F∩J|+|E∩F∩J|＝165|U-(E∪F∪J)|=170-165=5練習

98頁習題六1516

恒等式中A，B，C是任意的集合。1.雙重否定律

～(～A)=A2.交換律 A∪B=B∪AA∩B=B∩A

AB=BA3.結合律

A∪(B∪C)=(A∪B)∪CA∩(B∩C)=(A∩B)∩C

(AB)C=A(BC)

6.4集合恒等式

重點掌握集合相等與包含關系的證明方法基本的恒等式4.分配律 A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)A∩(BC)=(A∩B)(A∩C)5.德摩根律

～(A∩B)=～A∪～B ～(A∪B)=～A∩～B6.冪等律

A∪A=AA∩A=A

基本的恒等式7.吸收律 A∪(A∩B)=AA∩(A∪B)=A8.零律

A∪E=EA∩Φ=Φ9.同一律

A∪Φ=AA∩E=A10.排中律 A∪～A=E11.矛盾律 A∩～A=Φ基本的恒等式12.其它

A-(B∪C)=(A-B)∩(A-C) A-(B∩C)=(A-B)∪(A-C)

AA=ΦAΦ=AAE=～A

A-B=A∩～BA-B=A-(A∩B)常用的恒等式例題【例6.8】證明 A-(B∪C)=(A-B)∩(A-C) A-(B∩C)=(A-B)∪(A-C)【例6.11】證明

A-B=A∩～B【例6.12】證明(A-B)∪B=A∪B【例6.10】證明A∪(A∩B)=AA∩(A∪B)=A練習習題六100頁練習32證明 (1)(A-B)-C=A-(B∪C)(A-B)-C=(A-C)-(B-C)(A-B)-C=(A-C)-B例題【例6.13】證明 A∪B=B