離散集合的概念交并補(bǔ)差冪集演示文稿

離散集合的概念交并補(bǔ)差冪集演示文稿當(dāng)前第1頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)（優(yōu)選）離散集合的概念交并補(bǔ)差冪集當(dāng)前第2頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)PowerPointTemplate_Sub1.1集合的概念與表示1.2集合運(yùn)算1.3集合的歸納定義當(dāng)前第3頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)PowerPointTemplate_Sub

集合論是一門研究數(shù)學(xué)基礎(chǔ)的學(xué)科，產(chǎn)生于16世紀(jì)末德國(guó)數(shù)學(xué)家康托（GeorgCantor,1845~1918）通過(guò)集合的直觀定義開創(chuàng)了樸素集合論，被公認(rèn)為集合理論的創(chuàng)始人1902年英國(guó)數(shù)學(xué)家羅素（Russell,1872~1970）證明樸素集合論導(dǎo)致悖論，隨后為彌補(bǔ)這一缺陷出現(xiàn)了各種公理化集合論體系集合不僅可以表示數(shù)及其運(yùn)算，更可以用于非數(shù)值信息及離散結(jié)構(gòu)的表示和處理。集合論的原理和方法作為數(shù)學(xué)基本技術(shù)廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)的基礎(chǔ)研究和實(shí)際應(yīng)用中當(dāng)前第4頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)集合的概念、表示與基本運(yùn)算Page1to7《離散數(shù)學(xué)》第1講當(dāng)前第5頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-6-ξ第一講集合的概念、表示與基本運(yùn)算內(nèi)容提要基礎(chǔ)知識(shí)集合、元素的概念怎樣表示一個(gè)集合（列舉、描述…）空集、全集、有限集、無(wú)限集外延性公理集合相等、子集、若干定理集合的基本運(yùn)算并、交、差、補(bǔ)冪集運(yùn)算當(dāng)前第6頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-7-ξ第一講集合的概念、表示與基本運(yùn)算何為集合？何為元素？集合(sets)：指確定的、互相區(qū)別的、作整體識(shí)別的一些事物（對(duì)象）的全體。簡(jiǎn)稱集。集合中的對(duì)象稱為集合的元素(members)，或稱為元、成員。當(dāng)某一個(gè)對(duì)象a是集合A的成員時(shí)，就說(shuō)“a屬于A”，記成aA，當(dāng)a不是集合A的成員時(shí)，就說(shuō)“a不屬于A”，記成aA。對(duì)于任何對(duì)象a和任何集合A，a要么屬于A，要么不屬于A，二者必居其一。當(dāng)前第7頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-8-ξ第一講集合的概念、表示與基本運(yùn)算集合舉例師范大學(xué)全體學(xué)生師范大學(xué)所有班級(jí)全體正整數(shù)1，2，3，4，…偶質(zhì)數(shù)的全體09計(jì)算機(jī)1班和他們本學(xué)期選修的所有課程所有長(zhǎng)得像張三的人中國(guó)所有著名導(dǎo)演方程x2-2x+1=0的根方程x2+x+1=0的根當(dāng)前第8頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-9-ξ第一講集合的概念、表示與基本運(yùn)算集合與元素集合中的元素可以是任何具體或抽象的個(gè)體，也可以是集合A={1，2，{1，2}}集合與其成員是兩個(gè)截然不同的概念1≠{1}{{a}}≠{a}通常用大寫字母A,B,C表示集合，用小寫字母a,b,c表示集合的元素（并非絕對(duì)）當(dāng)前第9頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-10-ξ第一講集合的概念、表示與基本運(yùn)算集合的表示方法列舉法（枚舉法）{a,b,c},{秦始皇，漢武帝}{1,2,3,4,…},{2,4,6,8,…}{1,2,4,7,11,…}描述法A={x|P(x)}（A中的元素均滿足性質(zhì)P，而A以外的元素一個(gè)也不滿足性質(zhì)P）

xAP(x){x|x是整數(shù)且x>0}、{x|x2-2x+1=0}{x|x出生于大連}、{x|x是0到1區(qū)間的實(shí)數(shù)}當(dāng)前第10頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-11-ξ第一講集合的概念、表示與基本運(yùn)算集合的表示方法歸納法（以后介紹）文氏圖（常用于表示集合之間的關(guān)系）ABU當(dāng)前第11頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-12-ξ第一講集合的概念、表示與基本運(yùn)算常用集合及其表示{0,1}={x|x=0或x=1}自然數(shù)集合（或非負(fù)整數(shù)的集合）N={0,1,2,3,…}整數(shù)集合I={…,-2,-1,0,1,2,…}正整數(shù)集合I+

={1,2,3,…}={x|xI且x>0}當(dāng)前第12頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-13-ξ第一講集合的概念、表示與基本運(yùn)算常用集合及其表示偶數(shù)集合E={…,-4,-2,0,2,4,…}={x|x是偶數(shù)}={x|xI且2|x}前n個(gè)自然數(shù)的集合Nn={0，1，2，…,n-1}={x|xN且x<n}當(dāng)前第13頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-14-ξ第一講集合的概念、表示與基本運(yùn)算常用集合及其表示P：全體素?cái)?shù)的集合Q：全體有理數(shù)的集合Q＋：全體正有理數(shù)的集合R：全體實(shí)數(shù)的集合R＋：全體正實(shí)數(shù)的集合C：全體復(fù)數(shù)的集合當(dāng)前第14頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-15-ξ第一講集合的概念、表示與基本運(yùn)算空集、有限集和無(wú)限集定義1.1：沒(méi)有任何元素的集合稱為空集，記為，={}。由全體對(duì)象組成的集合稱為全集，記為U。定義1.2：只含有限多個(gè)元素的集合稱為有限集；不是有限集的集合稱為無(wú)限集。空集是有限集有限集合A中元素的個(gè)數(shù)稱為A的基數(shù)(cardinality)，記為|A|空集的基數(shù)是0，即||=0當(dāng)前第15頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-16-ξ第一講集合的概念、表示與基本運(yùn)算空集、有限集和無(wú)限集舉例{x|x=0或x=1}自然數(shù)集合N正整數(shù)集合A={1，2，{1，2}}{}師范大學(xué)全體學(xué)生方程x2+x+1=0的根當(dāng)前第16頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-17-ξ第一講集合的概念、表示與基本運(yùn)算外延性公理（extensionalityaxiom）

外延性公理：兩個(gè)集合相等當(dāng)且僅當(dāng)這兩個(gè)集合具有完全相同的成員。即對(duì)任意的集合A和B：A=B當(dāng)且僅當(dāng)對(duì)任意元素x，x屬于A則一定有x屬于B；反之，x屬于B也一定有x屬于A。也就是說(shuō)，集合A中的所有元素均是集合B中的元素，反之，B中的所有元素均是A中的元素例1.4{0,1}={1,0}={0,1,0}={x|x(x2-2x+1)=0}外延性公理事實(shí)上刻畫了集合元素的無(wú)序性、相異性及集合表示形式的不唯一性當(dāng)前第17頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-18-ξ第一講集合的概念、表示與基本運(yùn)算子集合(subsets)定義1.3：設(shè)A，B為集合，若A中每一個(gè)元素都同時(shí)是B的元素，則稱A是B的子集。即對(duì)于任意元素x，當(dāng)x屬于A時(shí)一定有x屬于B。表示為AB，讀成A包含于B，或B包含A。任意集合A均是自己的子集，即：AA若要說(shuō)明A不是B的子集，只須在A中找到某一個(gè)元素x，使得xB即可定義1.4：設(shè)A、B為集合，當(dāng)AB且AB時(shí)，稱A為B的真子集，記成AB。讀做A真包含于B，或B真包含A當(dāng)前第18頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-19-ξ第一講集合的概念、表示與基本運(yùn)算包含關(guān)系vs.隸屬關(guān)系包含——集合與集合之間的關(guān)系{1,2}{1,2,3,4}{1,2}{1,2,3,4}{a}{a}隸屬——元素與集合之間的關(guān)系1{1,2,3,4}5{1,2,3,4}{a}{{a}}當(dāng)前第19頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-20-ξ第一講集合的概念、表示與基本運(yùn)算關(guān)于子集的若干定理定理1.1：對(duì)任何集合A，B，A=B當(dāng)且僅當(dāng)AB且BA。對(duì)任何集合A，AA定理1.3：對(duì)于任何集合A，B，C，若AB，BC，則AC。證明：設(shè)x為A中任一元素，

因?yàn)锳B，所以xB；又因?yàn)锽C，所以xC

這就是說(shuō)，A中所有元素均屬于C，所以有AC。當(dāng)前第20頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-21-ξ第一講集合的概念、表示與基本運(yùn)算關(guān)于子集的若干定理定理1.2，1.4：對(duì)任意集合A，AU，A定理1.5：空集是唯一的證明：假設(shè)1,2都是空集，根據(jù)定理3，應(yīng)該有1

2

且2

1

，從而由定理1知1=2。當(dāng)前第21頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-22-ξ第一講集合的概念、表示與基本運(yùn)算關(guān)于子集的若干定理定理1.6：設(shè)A為一個(gè)有限集，且|A|=n，則A的子集個(gè)數(shù)為2n證明：集合A的子集最多有n個(gè)元素，最少有0個(gè)元素。

0個(gè)元素的子集共有C(n,0)個(gè)；

1個(gè)元素的子集共有C(n,1)個(gè)；

……n個(gè)元素的子集共有C(n,n)個(gè).

因此，集合A共有子集C(n,0)+C(n,1)+…C(n,n)=2n個(gè)。當(dāng)前第22頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-23-ξ第一講集合的概念、表示與基本運(yùn)算集合的運(yùn)算集合運(yùn)算——以集合作為運(yùn)算對(duì)象，運(yùn)算結(jié)果仍為集合的運(yùn)算算術(shù)運(yùn)算：3+5=84×6=24集合運(yùn)算：{1,2}{2,3}={2}{1,2}{2,3}={1,2,3}有哪些集合運(yùn)算交、并、差、補(bǔ)求冪運(yùn)算廣義并、交求笛卡爾積運(yùn)算當(dāng)前第23頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-24-ξ第一講集合的概念、表示與基本運(yùn)算集合的并運(yùn)算union

（∪）定義1.5：(1)設(shè)A、B為任意集合，則由A、B的所有元素合在一起所組成的集合稱為A與B的并集，記成A∪B。即：A∪B={x|xA或xB}

xA∪BxA或xB例1.6U={0,1,2,…,9}A={2,4},B={4,5,6,7},C={0,8,9},D={1,2,3}A∪B，A∪C，C∪D，B∪D當(dāng)前第24頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-25-ξ第一講集合的概念、表示與基本運(yùn)算集合的交運(yùn)算intersection（∩）定義1.5：(2)設(shè)A、B為任意集合，則由A、B的公共元素所組成的集合稱為A與B的交集，記成A∩B。即：A∩B={x|xA并且xB}xA∩BxA并且xB例1.6U={0,1,2,…,9}A={2,4},B={4,5,6,7},C={0,8,9},D={1,2,3}A∩B，A∩C，C∩D，B∩D當(dāng)前第25頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-26-ξ第一講集合的概念、表示與基本運(yùn)算集合的差運(yùn)算difference（–）定義1.5：(3)設(shè)A、B為任意集合，則由在A中而不在B中的元素所組成的集合稱為A對(duì)B的差，記成A–B。即：A–B={x|xA且xB}xA–BxA并且x

B

例1.6U={0,1,2,…,9}A={2,4},B={4,5,6,7},C={0,8,9},D={1,2,3}A－B，A－C，C－D，B－D當(dāng)前第26頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-27-ξ第一講集合的概念、表示與基本運(yùn)算集合的補(bǔ)運(yùn)算complement（–）定義1.5：(4)設(shè)U為全集，A為任意集合，則所有在全集U中但不屬于A的元素所組成的集合稱為A的補(bǔ)集，記成Aˉ。即：Aˉ={x|xU且xA}xAˉx

A例1.6U={0,1,2,…,9}A={2,4},B={4,5,6,7},C={0,8,9},D={1,2,3}Aˉ

，Bˉ，Cˉ，Dˉ當(dāng)前第27頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-28-ξ第一講集合的概念、表示與基本運(yùn)算文氏圖表示的集合并、交、差、補(bǔ)運(yùn)算UAAUAAˉA∩BUABA∪BUABA－BUAB(A∪B)ˉ∩CUABC當(dāng)前第28頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-29-ξ第一講集合的概念、表示與基本運(yùn)算關(guān)于并、交、差、補(bǔ)運(yùn)算的一些直觀結(jié)論A∪A=A，A∪=A，A∪U=UA∩A=A，A∩=，A∩U=AA–A=，A–=A，A–U=，

–A=

Aˉ=U–A，ˉ=U，Uˉ=，Aˉˉ=AA∩Aˉ=，A∪Aˉ=UAA∪B，BA∪B，A∩BA，A∩BBA–BA若AB，則A∪B=B，A∩B=A，A–B=若A∩B=，則A–B=A當(dāng)前第29頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-30-ξ第一講集合的概念、表示與基本運(yùn)算關(guān)于交換律和結(jié)合律交換律2+3=3+2，a×b=b×aA∪B=B∪A，A∩B=B∩A一般而言，A–B≠B–A結(jié)合律2+(3+5)=(2+3)+5，a×(b×c)=(a×b)×cA∪(B∪C)=(A∪B)∪CA∩(B∩C)=(A∩B)∩C一般而言，

A–(B–C)≠(A–B)–C當(dāng)前第30頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-31-ξ第一講集合的概念、表示與基本運(yùn)算關(guān)于分配律和吸收率分配律a×(b+c)=a×b+a×cA∪(B∩C)=(A∪B)∩(A∪C)A∩(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當(dāng)前第31頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-32-ξ第一講集合的概念、表示與基本運(yùn)算關(guān)于并、交、差、補(bǔ)運(yùn)算的幾個(gè)定理

定理1.6：A–(B∪C)=(A–B)∩(A–C)A–(B∩C)=(A–B)∪(A–C)定理1.8：(A∪B)ˉ=Aˉ∩Bˉ(A∩B)ˉ=Aˉ∪BˉA–B=A∩Bˉ證明A–(B∩C)=(A–B)∪(A–C)對(duì)任意x，xA–(B∩C)xA且xB∩C

xA且(xB或者xC)

(xA且xB)或者(xA且xC)xA–B或者xA–C

x(A–B)∪(A–C)當(dāng)前第32頁(yè)\共有35頁(yè)\編于星期一\8點(diǎn)-33-ξ第一講集合的概念、表示與基本運(yùn)算關(guān)于并、交、差、補(bǔ)運(yùn)算的幾個(gè)定理

定理1.10：AB，A–B=，A∪B=B，A∩B=A四命題等價(jià)定理1.11：對(duì)任意集合A、B，若它們滿足1)

A∪B=U