離散數(shù)學(xué)第2章集合

離散數(shù)學(xué)(DiscreteMathematics)離散數(shù)學(xué)(DiscreteMathematics)計(jì)算機(jī)科學(xué)與工程系TianjinUniversityofTechnologyDepartmentofComputerScience&Engineering魏雪麗離散數(shù)學(xué)(DiscreteMathematics)計(jì)算機(jī)科學(xué)與工程系TianjinUniversityofTechnologyDepartmentofComputerScience&Engineering魏雪麗第二章集合Sets

本章首先采用樸素集合論的方法，介紹有關(guān)集合的一些基本知識(shí)，內(nèi)容顯得較為直觀，學(xué)起來(lái)易于接受。但集合及其相關(guān)的概念是本門課程后面各章內(nèi)容的基礎(chǔ)，同學(xué)們務(wù)必熟練的掌握。第一節(jié)集合的概念和表示法一集合的概念二集合的表示法

三元素和集合之間的關(guān)系四集合間的包含關(guān)系五特殊集合六小結(jié)一、集合的基本概念1、集合的定義具有某種共同屬性的事物的全體稱為例如：集合。計(jì)算機(jī)網(wǎng)絡(luò)是計(jì)算機(jī)之間以信息傳輸為主要目的而連接起來(lái)的計(jì)算機(jī)系統(tǒng)的集合。計(jì)算機(jī)內(nèi)存的全體單元構(gòu)成一集合。一、集合的基本概念2、集合的元素1、集合的元素表示的事物可以是具體的，注：也可以是抽象的。2、集合的元素是任意的，但必須是確定的和可以區(qū)分的。集合里含有的對(duì)象或客體稱為集合的元素。一、集合的基本概念3、集合的分類1)有限集合集合的元素個(gè)數(shù)是有限的。2)無(wú)限集合集合的元素個(gè)數(shù)是無(wú)限的。二、集合的表示法1、符號(hào)表示法通常用大寫字母A,B,C,…代表集合;用小寫字母a,b,c,…代表元素。1)如果a是集合A的一個(gè)元素,則記為a∈A,讀做“a屬于A”,或“a在集合A中”。2)如果a不是集合A的一個(gè)元素,則記為讀做“a不屬于A”,或“a不在集合A中”。a∈A,任一元素,對(duì)某一集合而言,或?qū)儆谠摷?或不屬于該集合,二者必居其一,且只居其一。注：二、集合的表示法1、符號(hào)表示法絕不容許界限不分明或含糊不清的情況存在。注：離散數(shù)學(xué)中，只討論界限清楚、無(wú)二義性的描述，不清晰的對(duì)象構(gòu)成的集合屬于模糊論的研究范疇。著名理發(fā)師問(wèn)題就屬于模糊論的研究范疇。二、集合的表示法2、描述集合中元素的方法

1)列舉法

a、全部列舉法：以任意順序?qū)懗黾系乃性?隔開(kāi)，元素間用逗號(hào)并將其放在花括號(hào)內(nèi)。例如“所有小于5的正整數(shù)”，這個(gè)集合的元素為1,2,3,4,再?zèng)]有別的元素了。如果把這個(gè)集合命名為A,A={1,2,3,4}就可記為二、集合的表示法2、描述集合中元素的方法

1)列舉法

b、部分列舉法：列舉集合的部分元素，素其他元素可從列舉的元用省略號(hào)代替。例如A表示“全體小寫英文字母”的集合，A={a,b,…,

y,z}則歸納出來(lái)

，列舉法僅適用于描述元素個(gè)數(shù)有限的集合注：或元素具有明顯排列規(guī)律的集合。二、集合的表示法2、描述集合中元素的方法

2)描述法

把集合元素的共同屬性描述出來(lái)。集合中元素的屬性。P(x)表示任何謂詞，則A={x|P(x)}即用謂詞概括表示所有使謂詞P(x)成立的元素x所組成的集合。例：{x|x2-3x+2=0}、{x|x=2n-1∧n∈N}如果P(a)為真，則a∈A，否則a∈A,(謂詞表示法)集合的元素集合的元素必須滿足的條件二、集合的表示法1、有些集合可以用兩種方法表示，注：但是有些集合不可以用列元素法表示，如實(shí)數(shù)集合。2、集合的元素是彼此不同的，如果同一個(gè)元素在集合中多次出現(xiàn)應(yīng)該認(rèn)為是一個(gè)元素。如:{3,4,4,4,5}、{3,4,5}、{5,4,3}是同一個(gè)集合。3、集合的元素是無(wú)序的。4、集合的元素可以是一個(gè)集合，但不允許以集合自身為其元素。如:S={a,},S={a,b,S},a∈S，b∈S,∈A，三、元素和集合之間的關(guān)系元素和集合之間的關(guān)系,是隸屬關(guān)系，即屬于或不屬于，屬于記作∈，不屬于記作

。例如：A={1，{1，2}，3，{{3}}}1{1，2}3∈A，∈A，{{3}}∈A，2{3}

A，

A?？梢杂靡环N樹(shù)形圖表示集合與元素的隸屬關(guān)系。A1{1,2}3{{3}}12{3}32∈{1，2}，A?B

()四、集合間的包含關(guān)系1、子集如果集合A中每個(gè)元素都是集合B中的元素，則稱A是B的或A包含于B，子集，或者B包含A，記作A?B如果A不是B的子集，或B?A。A?B

(x)

x

∈A→x

∈B則在A中至少有一個(gè)元素不屬于B時(shí)，稱B不包含A，記作或B?A。注：1)A?A，2)A?B，B?C，則A?C。B()四、集合間的包含關(guān)系2、集合相等1)定義兩個(gè)集合相等當(dāng)且僅當(dāng)它們有相同的元素。若A和B相等，記作A=B

(x)

x

∈Ax

∈(外延性原理)

A=B。兩個(gè)集合不相等，記作A

B。四、集合間的包含關(guān)系2、集合相等2)判斷A與B互為子集。定理若A和B相等當(dāng)且僅當(dāng)A?B且B?A。即A()∈()四、集合間的包含關(guān)系3、真子集如果集合A中每個(gè)元素都屬于集合B，但B中不屬于A，則稱A是B的記作A?

B或B?A。A?B

(x)

x

∈A→x

∈B至少有一個(gè)元素真子集?！?/p>

(

x)x

∈B∧x

A?B∧A

B例A={a，b}B={a，}不是的子集。（真）四、集合間的包含關(guān)系3、真子集可以用文氏圖了表示集合間的包含關(guān)系。文氏(Venn)圖是一種利用平面上的點(diǎn)構(gòu)成的圖形來(lái)形象展示集合的一種方法。集合用矩形、園面如果A?B，或一封閉曲線來(lái)表示。則表示A的圓面一般完全落在表示B的圓面內(nèi)。ABBAA?B四、集合間的包含關(guān)系4、隸屬和包含關(guān)系的區(qū)別例A={a，{a}}，B={a}B∈A，B

A，B是A的元素，B的元素a是A的元素，B是A的子集。隸屬是元素和集合的關(guān)系，包含是集合和集合的關(guān)系，某些集合可以同時(shí)成立這兩種關(guān)系。是個(gè)體與整體的關(guān)系，是部分與整體的關(guān)系。五、特殊集合1、空集定義不含任何元素的集合空集，稱為記作。例兩條平行線交點(diǎn)的集合為。例{x|x>0∧x≤0∧x∈R}=

。注：1)

與{}的區(qū)別。是集合，沒(méi)有元素有1個(gè)元素的集合2){

}，

{

}

∈五、特殊集合1、空集

定理空集

是任一集合A的子集，即?A。下列命題是否為真。練習(xí)

1)?;2)

∈

;3)

?{};4)

∈{}?！獭獭涛?、特殊集合1、空集

推理空集

是唯一的。設(shè)

1，

2是兩個(gè)空集,則

1

2，且2

1，得

1=

2，所以空集是唯一的。證明：證明唯一性一般采用反證法(絕對(duì)唯一)證畢。五、特殊集合1、空集

2)證明一個(gè)集合是空集，或證明集合的唯一性，常采用反證方法，即假設(shè)該集合不是空集，或不唯一，導(dǎo)致與已知條件的矛盾或?qū)е挛ㄒ?。注?)任何非空集合A，至少有子集：兩個(gè)、和A。

只有子集一個(gè)。五、特殊集合2、全集

定義在一定范圍內(nèi)，如果所有集合都是某一集合的子集，則稱此集合為全集,記作U。注：1)全集是相對(duì)的，不同的問(wèn)題有不同的全集，即使是同一個(gè)問(wèn)題也可以取不同的全集。2)一般地說(shuō)，全集取得小一些，問(wèn)題的描述和處理會(huì)簡(jiǎn)單些。3)全集U用一個(gè)矩形的內(nèi)部表示，U五、特殊集合3、冪集定義由集合A的所有子集為元素所組成的集合稱為A的冪集,記作注：1)冪集的元素都是集合。或P(A)或2A。2)任一集合的冪集都非空。3)在A的所有子集中，A和又叫平凡子集。

(A){}{}{、}a{}五、特殊集合3、冪集例的冪集：

{}=A={a}的冪集：

={、、、}a{}A={a，b}的冪集：

=ba、b有個(gè)元素1有個(gè)元素2有個(gè)元素4202122

(A)五、特殊集合3、冪集

一般地，集合A={a1、a2、…、an}，則有個(gè)元素。2n它的m(0≤m≤n)元子集有個(gè)，不同的子集共有+…+=(1+1)n=2n個(gè)。A={x|}，理發(fā)師問(wèn)題在一個(gè)很僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉的人刮臉。那么，誰(shuí)給這位理發(fā)師刮臉？解：設(shè)不給自己刮臉的人x是b是這位理發(fā)師。1)若b∈A，則b是不給自己刮臉的人，而由題意，b只給集合A中的人刮臉?！郻要給b刮臉，即bA?！省?)若bA，理發(fā)師問(wèn)題在一個(gè)很僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉的人刮臉。那么，誰(shuí)給這位理發(fā)師刮臉？解：則b是要給自己刮臉的人，而由題意，理發(fā)師只給自己不刮臉的人刮臉?！郻是不給自己刮臉的人，即b∈A。無(wú)論1)和2)，都有b∈A∈及bA同時(shí)成立。這種情況稱為羅索悖論，是模糊論的范疇。返回第二節(jié)集合的運(yùn)算一集合的交二集合的并

三集合的補(bǔ)四集合的對(duì)稱差五集合恒等式六小結(jié)一、集合的交1、定義2、文氏圖任意兩個(gè)集合A和B，由A和B的所有共同元素組成的集合，稱為A和B的交集，記為A∩B。A∩B={x|x∈A

x∈B}即(Intersection)A∩BAB一、集合的交如果兩個(gè)集合沒(méi)有任何共同的元素，(Intersection)例如，A={a,b,c,e,f}，B={b,e,f,r,s}，C={a,t,u,v},則A∩B={b,e,f}A∩C={a

}B∩C=

則稱它們是不相交集合。EAB一、集合的交三個(gè)或更多的集合的交集運(yùn)算：(Intersection)A∩B∩C

={x|x∈A

x∈B

x∈C}一、集合的交3、性質(zhì)A∩A1)冪等律(Intersection)=AA∩

2)零律=

A∩E3)同一律=AA∩B4)交換律=B∩AA∩(B∩C)5)結(jié)合律=(A∩B)∩C()B一、集合的交3、性質(zhì)(Intersection)若A?B，6)則A∩C

B∩C。

?反之

不然。

證：A?B

(x)

x

∈A→x

∈分析：若x∈A∩C，

即x∈Ax∈C,

∵A?B∴x∈A→x∈B則x∈Bx∈C,

∴x∈B∩C。反之，

取C=

，

A={a}，B=，則A∩C

=

B∩C=

?但A?B證畢一、集合的交3、性質(zhì)(Intersection)A∩B7)A,A∩B??B（集合越交越小）注：集合運(yùn)算的規(guī)律和命題演算的某些規(guī)律是一致的，所以命題演算的方法是證明集合恒等式的基本方法。二、集合的并1、定義2、文氏圖任意兩個(gè)集合A和B，由屬于A或?qū)儆贐組成的集合，稱為A和B的并集，記為A∪B。A∪B={x|x∈A∨x∈B}即(Union)的元素AB二、集合的并三個(gè)或更多的集合的并集運(yùn)算：(Union)EABA∪B∪C

={x|x∈AC∨

x∈B∨

x∈C}A∪B∪C

二、集合的并3、性質(zhì)A∪A1)冪等律(Union)=AA∪U2)零律=UA∪

3)同一律=AA∪B4)交換律=B∪AA∪(B∪C)5)結(jié)合律=(A∪B)∪C二、集合的并3、性質(zhì)，(Union)若A?B，6)則A∪C

B∪D。

反之

不然。

若x∈A∪C，

即x∈Ax∈C,

∨C?D，?1)若x∈A，則x∈B，∴x∈B∪D，

2)若x∈C，則x∈D，∴x∈B∪D，

∴始終有x∈B∪D。

反之，

取C=D=E，

A={a}，B=，則A∪CE=

B∪D=E?但A?B證：證畢。二、集合的并3、性質(zhì)(Union)A∪B，7)A?（集合越并越大）A∪BB?x∈B()}x∈Bx∈A()∨()}二、集合的并4、∩和∪的關(guān)系(Union)定理對(duì)任意集合A、B和C有:1)A∪(B∩C)=(A∪B)∩(A∪C);2)A∩(B∪C)=(A∩B)∪(A∩C)。即∩對(duì)∪可以分配,∩對(duì)∪可以分配。1)A∪(B∩C)={x|x∈A

x∈C={x|∨

x∈A∨x∈C=(A∪B)(A∪C)∩

={x|x∈A∨x∈B}∩x∈A∨x∈C}{x|分配律分配律證：x∈B∨()}x∈A二、集合的并4、∩和∪的關(guān)系(Union)定理對(duì)任意集合A、B有:1)A∪(A∩B)=A2)A∩(A∪B)=A證一：1)A∪(A∩B)={x|x∈A

={x|x∈A}=A吸收律吸收律命題邏輯中的吸收律二、集合的并4、∩和∪的關(guān)系吸收律(Union)定理對(duì)任意集合A、B有:A?BA∪B=B或A∩B=A。當(dāng)且僅當(dāng)∵A?B，B?B，∴A∪B?B∪B=B由性質(zhì)7)BA∪B?∴A∪B=B反之，

由性質(zhì)7)AA∪B,?A∪B=B∴A?B證：證畢。三、集合的補(bǔ)1、定義2、文氏圖任意兩個(gè)集合A和B，由屬于A但不屬于B組成的集合，稱為B對(duì)于A的補(bǔ)集記為A－B。A－B={x|x∈A∧x∈B}即(Relative

Complement)所有元素或相對(duì)的補(bǔ)或A和B的差。={x|x∈A∧﹁(

x∈B)}BA三、集合的補(bǔ)3、絕對(duì)補(bǔ)集全集U和集合A的差集稱為A的絕對(duì)補(bǔ)記為U－

A～A

=即(Relative

Complement)或A的余集或A的補(bǔ)集。={x|x∈U∧

x∈A}～A或﹁A或A。U－

Ax∈～A?x∈A(AbsoluteComplement).三、集合的補(bǔ)4、性質(zhì)(Relative

Complement)~(~A)1)雙重否定律=A~U2)=

~3)=UA∪~A4)排中律=UA∩～A5)矛盾律=

三、集合的補(bǔ)4、性質(zhì)(Relative

Complement)(1)~(A∪B)6)德摩根律=~A∩~B(2)~(A∩B)=~A∪~B~(A∪B)={x|x∈U∧﹁(x∈A∪B)}={x|x∈U﹁(x∈A∧∨={x|x∈U﹁(x∈A)∧∧﹁(

x∈B)}={x|(x∈U﹁(x∈A))∧∧﹁(

x∈B))}(x∈U∧=~A~B∩x∈B)}證:(1)~A∩

()~B

()三、集合的補(bǔ)5、定理：(Relative

Complement)2)利用(3)的結(jié)論。A-(A∩B)=A∩

(A∩

B)~=A∩~A∪(3)的結(jié)論德摩根律=A∪A∩~B

()

=A-B1)A-B=A∩~B2)A-B=A-(A∩B)分配律三、集合的補(bǔ)5、定理(Relative

Complement)4)A∩(B-C)=(A∩B)-(A∩C)三、集合的補(bǔ)5、定理(Relative

Complement)4)a)A?B

~B?~Ab)A?B

(B-A)∪A=B證：a)

若x∈A則必有x∈B，因此x∈B，必有x∈A，即x∈~B

x∈~A∴

~B?~A∵A?B

由上述證明可知：~(~A)∵

~B?~A~(~B)?A==B∴A?B

~B?~A四、集合的對(duì)稱差1、定義(SymmetricDifference)設(shè)A、B是兩個(gè)集合，其元素但集合A和B的對(duì)稱差(環(huán)和）是集合，記作A

B,或?qū)儆贏，或?qū)儆贐,不能既屬于A

又屬于B，即：A

B=(A-B)∪(B-A)例如A={a,b,c},B={b,d},則A

B={a,c,d}={x|(x∈A

x∈B)

(x∈B

x∈A)}

四、集合的對(duì)稱差2、文氏圖(SymmetricDifference)AB四、集合的對(duì)稱差3、性質(zhì)(SymmetricDifference)1)交換律2)同一律3)零律A

B=4)A

B=B

AA

=AAA=

∪∩

B)(A(A∩B)四、集合的對(duì)稱差3、性質(zhì)(SymmetricDifference)(A

B)C=A(BC)5)結(jié)合律定義2.2-6

A、B兩集合的環(huán)積記為A

B，是集合。

定理2.2-12(1)

=A

B，(2)A

B=B

A，

(3)A

A=U。

定理2.2-13定理2.2-14

例1

已知A

B＝A

C，是否必須B＝C？解：是?！逜

B=A

C，∴A(A

B)=A(A

C)(A

A)

B∴

=(A

A)

C∴

B=

C∴B=C。例2

已知A∪B=A∪C，是否必須B=C？解：否。例：設(shè)A={1、2}，B={1}，C={2}例3

已知A∩B=A∩C，是否必須B=C？解：例：設(shè)A={1}，B={1、2}，C={1、3}否。2-5集合的笛卡爾積

1、序偶(有序2元組)：兩個(gè)具有固定次序的客體組成一個(gè)序偶(有序2元組)，記作<x，y>，其中x是它的第一元素，y是它的第二元素。一、有序n元組例：平面直角坐標(biāo)系中的一個(gè)點(diǎn)的坐標(biāo)就構(gòu)成為一個(gè)有序序偶，我們可用<x，y>表示。注：序偶是講究次序的。例<1，3>和<3，1>表示平面上兩個(gè)不同的點(diǎn)，這與集合不同，{1，3}和{3，1}是兩個(gè)相等的集合。2、定義：兩個(gè)序偶相等，<x，y>=<u，v>，當(dāng)且僅當(dāng)x=u且y=v。一、有序n元組3、有序３元組：是一個(gè)序偶，其第一元素本身也是一個(gè)序偶，表示為<<x，y>，z>或<x，y，z>。4、有序n元組：有序n元組也是一個(gè)序偶，其第一元素是一個(gè)n-1元組。<<x1，x2，…，xn-1>，xn>，通常簡(jiǎn)記為：<x1，x2，…，xn-1，xn>，其中xi稱作它的第i坐標(biāo)，i=1，2，…，n。<x1，x2，…，xn-1，xn>=<y1，y2，…，yn-1，yn>的充要條件是xi=yi，i=1，2，…，n。序偶<x,y>其元素可以分別屬于不同的集合，因此任給兩個(gè)集合A和B，我們可以定義一種序偶的集合。1、定義：設(shè)A和B是任意兩個(gè)集合，由A中元素作第一元素，B中元素作第二元素構(gòu)成序偶，所有這樣序偶的集合稱集合A和B的笛卡爾積或直積。記作AB。即

AB={<x，y>|xA∧yB}二、笛卡爾積2、n個(gè)集合的笛卡爾積：集合A1，A2，…，An，則