第1章 集合的概念与运算

离散数学引论

集合论与图论

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

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

中山大学计算机科学系蔡国扬

email:isscgy@

课件下载：dm_cs2010_sysu@163.com绪论离散数学的研究目标离散量的结构及相互关系离散数学是“计算机数学”计算机只能处理离散结构的数据。信息的编码结构是离散的。连续的、复杂的应用结构只能通过适当的离散化，分解抽象出离散的计算模型，才能由计算机进行处理。离散数学是计算机科学与技术的理论基础，而且随着计算机科学与技术的发展不断形成新的应用体系。绪论离散数学是在符号处理的通用层面上谈论满足构造性思维的通用结构，其研究对象是符号化、结构化与可构造的数学对象，相应地需要采用符号化、结构化与可构造的思维方法。归纳原理与公理化方法：归纳原理提供了一种使用有限步骤证明具有无限元素的离散结构的性质的基本方法。公理化方法则在结构元素一些基本性质的基础上进行演绎，考察系统的内在规律。绪论离散数学是计算机专业的核心课程通过离散数学的学习提高抽象思维和逻辑推理能力，形成基本的离散思维方法。离散数学也是后续课程（数据结构、编译系统、操作系统、数据库原理、人工智能等）的数学基础。绪论离散数学（II）课程的主要内容集合论(数学语言)、图论及其应用离散数学的应用体系举例命题逻辑布尔代数：数字逻辑理论，逻辑设计谓词逻辑：程序正确性证明图论：大量实际应用模型代数结构：编码理论耿素云,屈婉玲,集合论与图论（离散数学二分册）石纯一,数理逻辑与集合论,清华大学出版社,2000.戴一奇,图论与代数结构,清华大学出版社,1995.卢开澄,图论及其应用,清华大学出版社,2001王树禾,图论,科学出版社,2004.李盘林等,离散数学,高等教育出版社,1999.KennethH.Rosen,DiscreteMathematicsanditsApplications(SixthEdition),机械工业出版社（影印版）,2008.D.S.Malik,DiscreteMathematicalStructures–TheoryandApplications,高等教育出版社（影印版）,2005.D.B.West,IntroductiontoGraphTheory(SecondEdition),

机械工业出版社（影印版）,2004.参考书目第一篇集合与关系

第一章集合的概念与运算1.1集合和元素[集合]集合是由一些可相互区分的客观对象汇集在一起构成的一个整体。这些对象称为构成集合的元素。集合是一个描述性的原始概念。对象是广义的，无性质、数量上的限制；对象之间无必然联系，只需满足可区分性；对象之间是无序的；外延性原则：一个集合仅由组成它的元素所确定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集合的相等与蕴含讨论：与：概念上的区别与=：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|[证明]（作业：证明定理）[推广]

对有限集合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

之间无关联要求；③首元和次元允许同一，即<a,a>

是合法的；④注意与{x,y}的区别。[序偶的集合性定义]<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