第1章 集合的概念與運算

離散數學引論

集合論與圖論

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

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

中山大學計算機科學系蔡國揚

email:isscgy@

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

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

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

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

a，aA

或aA

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

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

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

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

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

E：與論域有關1.2集合的相等與蘊含[集合相等的外延性公理]

集合A和B相等，當且僅當它們由相同的元素所構成，記作A=B。[包含]

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

是唯一的。AA[定理]

對集合A和B，A=BiffAB且BA。[定理]對集合A，B和C，若AB且BC則AC。1.2集合的相等與蘊含[真包含]對集合A和B，若AB且AB，則說A真包含于B或說A是B的一個真子集，記作AB。[定理]對集合A，B和C，若AB且BC則AC。1.3冪集[冪集]設任一集合A，A的全部子集構成的集合稱為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) 結合律④A= 零律⑤AE=A 同一律[定理]|AB|min(|A|,|B|)1.4集合的運算(2)并集與并運算[并集]

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

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

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

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

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

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

稱

~A=E–A={x|xExA}={x|xA}為集合A的補集。這里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名同學中有5人選修物理，7人選修生物，其中有3人既選修物理又選修生物，問有幾名同學既沒有選修物理又沒有選修生物？[解]

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

[VennDiagram]

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

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

VennDiagram

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

A-B~AAB1.5文氏圖

[例]

165個學生選修課程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文氏圖

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

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

一般相處

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

稱為首元，y

稱為次元。說明：①次序至關緊要；②x,y

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

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

<x,y>=<u,v>

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

z>[定理]

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

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

xn

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

xn

>[定理]

<x1,x2,…,

xn

>=<u1,u2,…,un>當且僅當xi=ui,

i=1,2