第1章 集合的概念與運算

離散數(shù)學(xué)引論

集合論與圖論

周二：4~5(10:45~12:25)/C203

周五：4~5(10:45~12:25)/C203

中山大學(xué)計算機(jī)科學(xué)系蔡國揚

email:isscgy@

課件下載：dm_cs2010_sysu@163.com緒論離散數(shù)學(xué)的研究目標(biāo)離散量的結(jié)構(gòu)及相互關(guān)系離散數(shù)學(xué)是“計算機(jī)數(shù)學(xué)”計算機(jī)只能處理離散結(jié)構(gòu)的數(shù)據(jù)。信息的編碼結(jié)構(gòu)是離散的。連續(xù)的、復(fù)雜的應(yīng)用結(jié)構(gòu)只能通過適當(dāng)?shù)碾x散化，分解抽象出離散的計算模型，才能由計算機(jī)進(jìn)行處理。離散數(shù)學(xué)是計算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)，而且隨著計算機(jī)科學(xué)與技術(shù)的發(fā)展不斷形成新的應(yīng)用體系。緒論離散數(shù)學(xué)是在符號處理的通用層面上談?wù)摑M足構(gòu)造性思維的通用結(jié)構(gòu)，其研究對象是符號化、結(jié)構(gòu)化與可構(gòu)造的數(shù)學(xué)對象，相應(yīng)地需要采用符號化、結(jié)構(gòu)化與可構(gòu)造的思維方法。歸納原理與公理化方法：歸納原理提供了一種使用有限步驟證明具有無限元素的離散結(jié)構(gòu)的性質(zhì)的基本方法。公理化方法則在結(jié)構(gòu)元素一些基本性質(zhì)的基礎(chǔ)上進(jìn)行演繹，考察系統(tǒng)的內(nèi)在規(guī)律。緒論離散數(shù)學(xué)是計算機(jī)專業(yè)的核心課程通過離散數(shù)學(xué)的學(xué)習(xí)提高抽象思維和邏輯推理能力，形成基本的離散思維方法。離散數(shù)學(xué)也是后續(xù)課程（數(shù)據(jù)結(jié)構(gòu)、編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫原理、人工智能等）的數(shù)學(xué)基礎(chǔ)。緒論離散數(shù)學(xué)（II）課程的主要內(nèi)容集合論(數(shù)學(xué)語言)、圖論及其應(yīng)用離散數(shù)學(xué)的應(yīng)用體系舉例命題邏輯布爾代數(shù)：數(shù)字邏輯理論，邏輯設(shè)計謂詞邏輯：程序正確性證明圖論：大量實際應(yīng)用模型代數(shù)結(jié)構(gòu)：編碼理論耿素云,屈婉玲,集合論與圖論（離散數(shù)學(xué)二分冊）石純一,數(shù)理邏輯與集合論,清華大學(xué)出版社,2000.戴一奇,圖論與代數(shù)結(jié)構(gòu),清華大學(xué)出版社,1995.盧開澄,圖論及其應(yīng)用,清華大學(xué)出版社,2001王樹禾,圖論,科學(xué)出版社,2004.李盤林等,離散數(shù)學(xué),高等教育出版社,1999.KennethH.Rosen,DiscreteMathematicsanditsApplications(SixthEdition),機(jī)械工業(yè)出版社（影印版）,2008.D.S.Malik,DiscreteMathematicalStructures–TheoryandApplications,高等教育出版社（影印版）,2005.D.B.West,IntroductiontoGraphTheory(SecondEdition),

機(jī)械工業(yè)出版社（影印版）,2004.參考書目第一篇集合與關(guān)系

第一章集合的概念與運算1.1集合和元素[集合]集合是由一些可相互區(qū)分的客觀對象匯集在一起構(gòu)成的一個整體。這些對象稱為構(gòu)成集合的元素。集合是一個描述性的原始概念。對象是廣義的，無性質(zhì)、數(shù)量上的限制；對象之間無必然聯(lián)系，只需滿足可區(qū)分性；對象之間是無序的；外延性原則：一個集合僅由組成它的元素所確定1.1集合和元素[成員關(guān)系]

構(gòu)成集合的元素與集合之間的關(guān)系。若a是構(gòu)成集合A的元素之一，可記為aA，否則記為aA。集合A確定之后，對任意事物

a，aA

或aA

兩者必居其一。[集合的表示法]列舉法（外延原則）和部分列舉法命題/謂詞刻劃法（抽象原則）：使用謂詞符號：，，，，，，歸納法（基本項+歸納項+極小化）1.1集合和元素[歸納表示法的例]

設(shè)N是所有自然數(shù)的集合，Ak表示一個能被自然數(shù)k

整除的自然數(shù)集合。(1)0Ak；(2)若nAk

則(n+k)Ak，這里nN。1.1集合和元素[有限集合與無限集合]基數(shù)(階)：集合A中元素的個數(shù)，記為|A|或n(A)有限集合：基數(shù)為一個自然數(shù)的集合。無限集合：無限可數(shù)集：集合元素可與自然數(shù)集N中元素建立一一對應(yīng)關(guān)系。無限不可數(shù)集合[空集]

：||=0，集合中沒有元素存在。[完全集合]

E：與論域有關(guān)1.2集合的相等與蘊(yùn)含[集合相等的外延性公理]

集合A和B相等，當(dāng)且僅當(dāng)它們由相同的元素所構(gòu)成，記作A=B。[包含]

A、B是任意集合，若A中的每一元素都屬于B，則說A包含于B或說A是B的一個子集，記為AB。謂詞描述：ABiff(x)(xAxB)1.2集合的相等與蘊(yùn)含討論：與：概念上的區(qū)別與=：A=BiffABandBA。與：是任何集合的子集。

是唯一的。AA[定理]

對集合A和B，A=BiffAB且BA。[定理]對集合A，B和C，若AB且BC則AC。1.2集合的相等與蘊(yùn)含[真包含]對集合A和B，若AB且AB，則說A真包含于B或說A是B的一個真子集，記作AB。[定理]對集合A，B和C，若AB且BC則AC。1.3冪集[冪集]設(shè)任一集合A，A的全部子集構(gòu)成的集合稱為A的冪集，記作(A)。描述：(A)={X|XA}[定理]①

(A)②A(A)③若AB，則(A)(B)④若AB，則(A)(B)⑤若|A|=n<+，則|(A)|=Cn0+Cn1+…+Cnn

=2n1.4集合的運算(1)交集與交運算[交集]

稱AB={x|xAxB}為集合A和B的交集，求交集的過程稱為交運算。[定理]①AA=A 冪等律②AB=BA 交換律③(AB)C=A(BC) 結(jié)合律④A= 零律⑤AE=A 同一律[定理]|AB|min(|A|,|B|)1.4集合的運算(2)并集與并運算[并集]

稱AB={x|xAxB}為集合A和B的并集，求并集的過程稱為并運算。[定理]①AA=A 冪等律②AB=BA 交換律③(AB)C=A(BC) 結(jié)合律④A=A 同一律⑤AE=E 零律[定理]

|AB||A|+|B|1.4集合的運算[定理]

A(BC)=(AB)(AC)A(BC)=(AB)(AC) 分配律[定理]

A(AB)=A，A(AB)=A吸收律(3)相對補(bǔ)集[相對補(bǔ)]

稱A–B={x|xAxB}為集合A和B的相對補(bǔ)集。[定理]

|A–B||A|–|B|1.4集合的運算(4)補(bǔ)集（絕對補(bǔ)集）[補(bǔ)集]

稱

~A=E–A={x|xExA}={x|xA}為集合A的補(bǔ)集。這里E是論域的全集。[定理]①~(~A)=A ②~E=,~=E③A~A=, A~A=E④A-B=A(~B)=A-(AB)⑤~(AB)=~A~B，~(AB)=~A~B1.4集合的運算(5)對稱差[對稱差]

稱AB=(AB)–(AB)為集合A和B的對稱差。[定理]①AB=BA

②(AB)C=A(BC)③AA=④A=A[定理]

|AB|=|A|+|B|–2|AB|1.4集合的運算(6)容斥原理[定理]

對有限集合A和B，有|AB|=|A|+|B|–|AB|[證明]（作業(yè)：證明定理）[推廣]

對有限集合A，B和C，有|ABC|=|A|+|B|+|C|–|AB|–|BC|–|AC|+|ABC|1.4集合的運算[例]10名同學(xué)中有5人選修物理，7人選修生物，其中有3人既選修物理又選修生物，問有幾名同學(xué)既沒有選修物理又沒有選修生物？[解]

設(shè)選修物理的集合為A，選修生物的集合為B，則|A|=5，|B|=7，且|AB|=3。將10名同學(xué)分解為兩部分：有選修的和沒有選修的，即|~A~B|+|AB|=10故|~A~B|=10–|AB|=10–(|A|+|B|–|AB|)=10–(5+7–3)=11.5文氏圖

[VennDiagram]

文氏圖提供了一種關(guān)于集合的形象化的表示。在Venn

圖中，用一個矩形表示全集，用圓表示全集的一個子集A，圓的內(nèi)部表示該子集的成員。A1.5文氏圖

VennDiagram

可用于表示集合的運算。（如圖，藍(lán)色部分為運算結(jié)果）ABAB1.5文氏圖

A-B~AAB1.5文氏圖

[例]

165個學(xué)生選修課程A、B、C，已知有79人選A，83人選B，63人選C；33人選A和C，20人選A和B，24人選B和C；8人選了A、B和C。問：有多少人沒有選修任何課程？通過文氏圖的圖解分析或容斥原理計算，得到答案是9人。1.5文氏圖

[一般相處]設(shè)集合A、B，若存在元素p、q、r，使得pApB，qBqA，rArB，則稱A和B一般相處。1.5文氏圖

[定理]任何兩個集合A、B，只能有五種可能的相處，即①A=B②AB③BA④AB=⑤

一般相處

1.6序偶[序偶]由兩個固定次序的對象構(gòu)成的序列稱為一個序偶，記作<x,y>。x

稱為首元，y

稱為次元。說明：①次序至關(guān)緊要；②x,y

之間無關(guān)聯(lián)要求；③首元和次元允許同一，即<a,a>

是合法的；④注意與{x,y}的區(qū)別。[序偶的集合性定義]<x,y>={{x},{x,y}}1.6序偶[定理]

<x,y>=<u,v>

當(dāng)且僅當(dāng)x=u,y=v[證明]引入序偶的集合性定義引用集合相等的外延性公理推廣定義：<x,y,z>=<<x,y>,

z>[定理]

<x,y,z>=<u,v,w>

當(dāng)且僅當(dāng)x=u,y=v,z=w推廣定義：<x1,x2,…,

xn

>=<<x1,x2,…,xn-1>,

xn

>[定理]

<x1,x2,…,

xn

>=<u1,u2,…,un>當(dāng)且僅當(dāng)xi=ui,

i=1,2