第二部分第六章集合論

第六章集合代數(shù)

SetAlgebra

第七章二元關(guān)系

BinaryRelation

第八章函數(shù)

Function第二部分集合論

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

6.1集合的基本概念

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

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

S=x|A(x)

其中A(x)是謂詞。

aS

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

例如：設(shè)A=a,b,c，A是有限集，A的基數(shù)|A|=3集合之間的包含關(guān)系

定義6.1

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

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

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

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

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

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

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

設(shè)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(Φ)|=？冪集的基數(shù)定理設(shè)A為有限集合，則

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

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

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

6.2集合的運(yùn)算A為B的真子集并運(yùn)算定義6.7

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

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

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

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

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

A-B=x|xA∧xB

例如，令C=a，D=a,b，則C-D=a-a,b=ΦC-C=Φ補(bǔ)運(yùn)算——絕對補(bǔ)定義6.9設(shè)A是集合，A對于全集E的相對補(bǔ)集，稱為A的絕對補(bǔ)集，記為～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的元素構(gòu)成的集合,稱之為A與B的對稱差。記為AB.

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

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

課后閱讀N個(gè)集合的交與并無窮個(gè)集合的交與并廣義交廣義并【例】計(jì)數(shù)問題某班有50名學(xué)生第一次考試中26人成績?yōu)閮?yōu)第二次考試中21人成績?yōu)閮?yōu)已知兩次考試中都不為優(yōu)的共17人問兩次考試中都為優(yōu)的有多少人？

6.3有窮集的計(jì)數(shù)解：設(shè)A，B分別表示第一次和第二次考試中成績?yōu)閮?yōu)的學(xué)生集合。(26-x)＋x＋(21-x)＋17=50x=14|～A∩

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

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

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

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

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

120人

會(huì)英語，

80人

會(huì)法語，

60人

會(huì)日語，

50人

會(huì)英語和法語，

25人

會(huì)英語和日語，

30人

會(huì)法語和日語，10人

會(huì)英語、日語和法語。問有多少人不會(huì)這三種語言？解：令U為全集，E、F、J分別為會(huì)英語、法語和日語人的集合。|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練習(xí)

98頁習(xí)題六1516

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

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

AB=BA3.結(jié)合律

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

(AB)C=A(BC)

6.4集合恒等式

重點(diǎn)掌握集合相等與包含關(guān)系的證明方法基本的恒等式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(chǔ)Φ=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練習(xí)習(xí)題六100頁練習(xí)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