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

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

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

xAP(x){x|x是整數(shù)且x>0}、{x|x2-2x+1=0}{x|x出生于大連}、{x|x是0到1區(qū)間的實數(shù)}當(dāng)前第10頁\共有35頁\編于星期一\8點-11-ξ第一講集合的概念、表示與基本運算集合的表示方法歸納法（以后介紹）文氏圖（常用于表示集合之間的關(guān)系）ABU當(dāng)前第11頁\共有35頁\編于星期一\8點-12-ξ第一講集合的概念、表示與基本運算常用集合及其表示{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頁\共有35頁\編于星期一\8點-13-ξ第一講集合的概念、表示與基本運算常用集合及其表示偶數(shù)集合E={…,-4,-2,0,2,4,…}={x|x是偶數(shù)}={x|xI且2|x}前n個自然數(shù)的集合Nn={0，1，2，…,n-1}={x|xN且x<n}當(dāng)前第13頁\共有35頁\編于星期一\8點-14-ξ第一講集合的概念、表示與基本運算常用集合及其表示P：全體素數(shù)的集合Q：全體有理數(shù)的集合Q＋：全體正有理數(shù)的集合R：全體實數(shù)的集合R＋：全體正實數(shù)的集合C：全體復(fù)數(shù)的集合當(dāng)前第14頁\共有35頁\編于星期一\8點-15-ξ第一講集合的概念、表示與基本運算空集、有限集和無限集定義1.1：沒有任何元素的集合稱為空集，記為，={}。由全體對象組成的集合稱為全集，記為U。定義1.2：只含有限多個元素的集合稱為有限集；不是有限集的集合稱為無限集?？占怯邢藜邢藜螦中元素的個數(shù)稱為A的基數(shù)(cardinality)，記為|A|空集的基數(shù)是0，即||=0當(dāng)前第15頁\共有35頁\編于星期一\8點-16-ξ第一講集合的概念、表示與基本運算空集、有限集和無限集舉例{x|x=0或x=1}自然數(shù)集合N正整數(shù)集合A={1，2，{1，2}}{}師范大學(xué)全體學(xué)生方程x2+x+1=0的根當(dāng)前第16頁\共有35頁\編于星期一\8點-17-ξ第一講集合的概念、表示與基本運算外延性公理（extensionalityaxiom）

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

因為AB，所以xB；又因為BC，所以xC

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

2

且2

1

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

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

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

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

因此，集合A共有子集C(n,0)+C(n,1)+…C(n,n)=2n個。當(dāng)前第22頁\共有35頁\編于星期一\8點-23-ξ第一講集合的概念、表示與基本運算集合的運算集合運算——以集合作為運算對象，運算結(jié)果仍為集合的運算算術(shù)運算：3+5=84×6=24集合運算：{1,2}{2,3}={2}{1,2}{2,3}={1,2,3}有哪些集合運算交、并、差、補求冪運算廣義并、交求笛卡爾積運算當(dāng)前第23頁\共有35頁\編于星期一\8點-24-ξ第一講集合的概念、表示與基本運算集合的并運算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頁\共有35頁\編于星期一\8點-25-ξ第一講集合的概念、表示與基本運算集合的交運算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頁\共有35頁\編于星期一\8點-26-ξ第一講集合的概念、表示與基本運算集合的差運算difference（–）定義1.5：(3)設(shè)A、B為任意集合，則由在A中而不在B中的元素所組成的集合稱為A對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頁\共有35頁\編于星期一\8點-27-ξ第一講集合的概念、表示與基本運算集合的補運算complement（–）定義1.5：(4)設(shè)U為全集，A為任意集合，則所有在全集U中但不屬于A的元素所組成的集合稱為A的補集，記成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頁\共有35頁\編于星期一\8點-28-ξ第一講集合的概念、表示與基本運算文氏圖表示的集合并、交、差、補運算UAAUAAˉA∩BUABA∪BUABA－BUAB(A∪B)ˉ∩CUABC當(dāng)前第28頁\共有35頁\編于星期一\8點-29-ξ第一講集合的概念、表示與基本運算關(guā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頁\共有35頁\編于星期一\8點-30-ξ第一講集合的概念、表示與基本運算關(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頁\共有35頁\編于星期一\8點-31-ξ第一講集合的概念、表示與基本運算關(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頁\共有35頁\編于星期一\8點-32-ξ第一講集合的概念、表示與基本運算關(guān)于并、交、差、補運算的幾個定理

定理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)對任意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頁\共有35頁\編于星期一\8點-33-ξ第一講集合的概念、表示與基本運算關(guān)于并、交、差、補運算的幾個定理

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

A∪B=U