第1章集合的概念与运算

1、1周二：周二：4 5 (10:4512:25)/C203周五：周五：4 5 (10:4512:25)/C203中山大学计算机科学系中山大学计算机科学系 蔡国扬蔡国扬email: 课件下载：课件下载：dm_cs2010_2绪论离散数学的研究目标离散数学的研究目标 离散量的结构及相互关系离散数学是离散数学是“计算机数学计算机数学” 计算机只能处理离散结构的数据。信息的编码结构是离散的。连续的、复杂的应用结构只能通过适当的离散化，分解抽象出离散的计算模型，才能由计算机进行处理。离散数学是计算机科学与技术的理论基础，而且随着计算机科学与技术的发展不断形成新的应用体系。3绪论离散数学是在符号处理的通用层

2、面上谈论满足构造性思维的通用结构，其研究对象是符号化、结构化与可构造的数学对象，相应地需要采用符号化、结构化与可构造的思维方法。归纳原理与公理化方法：归纳原理提供了一种使用有限步骤证明具有无限元素的离散结构的性质的基本方法。公理化方法则在结构元素一些基本性质的基础上进行演绎，考察系统的内在规律。4绪论离散数学是计算机专业的核心课程离散数学是计算机专业的核心课程 通过离散数学的学习提高抽象思维和逻辑推理能力，形成基本的离散思维方法。离散数学也是后续课程（数据结构、编译系统、操作系统、数据库原理、人工智能等）的数学基础。5绪论离散数学（离散数学（II）课程的主要内容）课程的主要内容 集合论(数学语

3、言)、图论及其应用离散数学的应用体系举例离散数学的应用体系举例命题逻辑布尔代数：数字逻辑理论，逻辑设计谓词逻辑： 程序正确性证明图论： 大量实际应用模型代数结构：编码理论6耿素云, 屈婉玲, 集合论与图论（离散数学二分册）集合论与图论（离散数学二分册）石纯一, 数理逻辑与集合论数理逻辑与集合论, 清华大学出版社, 2000.戴一奇, 图论与代数结构图论与代数结构, 清华大学出版社, 1995.卢开澄, 图论及其应用图论及其应用, 清华大学出版社, 2001 王树禾, 图论图论, 科学出版社, 2004.李盘林等, 离散数学离散数学, 高等教育出版社, 1999.Kenneth H. Rosen

4、, Discrete Mathematics and its Applications (Sixth Edition), 机械工业出版社（影印版）, 2008.D.S.Malik, Discrete Mathematical Structures Theory and Applications, 高等教育出版社（影印版）, 2005.D.B.West, Introduction to Graph Theory (Second Edition), 机械工业出版社（影印版）, 2004.参考书目参考书目7第一篇第一篇 集合与关系集合与关系 8第一章第一章 集合的概念与运算集合的概念与运算1.1 1

5、.1 集合和元素集合和元素集合集合 集合是由一些可相互区分的客观对象汇集在一 起构成的一个整体。这些对象称为构成集合的元素。 集合是一个描述性的原始概念。 对象是广义的，无性质、数量上的限制； 对象之间无必然联系，只需满足可区分性； 对象之间是无序的； 外延性原则：一个集合仅由组成它的元素所确定91.1 集合和元素成员关系成员关系 构成集合的元素与集合之间的关系。若 a 是构成集合 A 的元素之一，可记为 aA，否则记为 aA。集合 A 确定之后，对任意事物 a，aA 或 aA 两者必居其一。集合的表示法集合的表示法列举法 （外延原则）和部分列举法命题/谓词刻划法 （抽象原则）：使用谓词符号：

6、，归纳法（基本项+归纳项+极小化）101.1 集合和元素归纳表示法的例归纳表示法的例 设 N 是所有自然数的集合，Ak 表示一个能被自然数 k 整除的自然数集合。(1) 0Ak；(2) 若 nAk 则 (n+k) Ak，这里 nN。111.1 集合和元素有限集合与无限集合有限集合与无限集合基数(阶)：集合A中元素的个数，记为 |A| 或 n(A)有限集合：基数为一个自然数的集合。无限集合： 无限可数集：集合元素可与自然数集N中元素建立一一对应关系。 无限不可数集合空集空集 ： |=0，集合中没有元素存在。完全集合完全集合 E：与论域有关121.2 集合的相等与蕴含集合相等的外延性公理集合相等的

7、外延性公理 集合 A 和 B 相等，当且仅当它们由相同的元素所构成，记作 A=B。包含包含 A、B 是任意集合，若A中的每一元素都属于B，则说 A 包含于 B 或说 A 是 B 的一个子集，记为 AB。 谓词描述：AB iff (x)(xAxB)131.2 集合的相等与蕴含v 讨论： 与：概念上的区别 与=：A=B iff AB and BA。 与：是任何集合的子集。 是唯一的。 AA定理定理 对集合 A 和 B，A=B iff AB 且 BA。定理定理 对集合 A，B 和 C，若 AB 且 BC 则 AC。141.2 集合的相等与蕴含真包含真包含 对集合 A 和 B，若 AB 且 AB，则说

8、A真包含于 B 或说 A 是 B 的一个真子集，记作 AB。定理定理 对集合 A，B 和 C，若 AB 且 BC 则 AC。151.3 幂集幂集幂集 设任一集合 A，A 的全部子集构成的集合称为 A的幂集，记作 (A)。 描述：(A)=X|X A定理定理 (A) A(A) 若 AB，则 (A)(B) 若 AB，则 (A)(B) 若 |A|=n+ ，则 |(A)|=Cn0+ Cn1+ Cnn =2n161.4 集合的运算(1) (1) 交集与交运算交集与交运算交集交集 称 AB=x|xA xB为集合 A 和 B 的交集，求交集的过程称为交运算。定理定理 AA=A幂等律 AB= BA交换律 (AB

9、)C= A(BC)结合律 A = 零律 AE =A 同一律定理定理 |AB| min(|A|, |B| )171.4 集合的运算(2) 并集与并运算并集与并运算并集并集 称 AB=x|xAxB为集合 A 和 B 的并集，求并集的过程称为并运算。定理定理 AA=A幂等律 AB= BA交换律 (AB) C= A(BC)结合律 A =A 同一律 AE =E 零律定理定理 |AB| |A|+|B|181.4 集合的运算定理定理 A(BC)=(AB)(AC) A(BC)=(AB)(AC) 分配律定理定理 A(AB)=A， A(AB)=A 吸收律(3) 相对补集相对补集相对补相对补 称 AB=x|xAxB

10、 为集合 A 和 B 的相对补集。定理定理 |AB| |A|B|191.4 集合的运算(4) 补集（绝对补集）补集（绝对补集）补集补集 称 A=EA=x|xExA=x|xA 为集合 A 的补集。这里 E 是论域的全集。定理定理 (A)=A E=, =E AA=,AA=E A-B=A(B)=A-(AB) (AB)= AB，(AB)= AB201.4 集合的运算(5) 对称差对称差对称差对称差 称 AB=(AB) (AB) 为集合 A 和 B 的对称差。定理定理 AB=BA (AB)C = A(BC) AA= A=A定理定理 |AB| = |A|+|B|2|AB|211.4 集合的运算(6) 容斥

11、原理容斥原理定理定理 对有限集合 A 和 B，有 |AB| = |A|+|B|AB|证明 （作业：证明定理）推广 对有限集合 A，B 和 C，有|ABC| = |A|+|B|+|C|AB|BC|AC|+|ABC| 221.4 集合的运算例例 10名同学中有5人选修物理，7人选修生物，其中有3人既选修物理又选修生物，问有几名同学既没有选修物理又没有选修生物？解 设选修物理的集合为 A，选修生物的集合为 B，则 |A|=5，|B|=7，且|AB|=3。 将10名同学分解为两部分：有选修的和没有选修的，即 |AB|+|AB|=10 故 |AB| = 10|AB| = 10 (|A|+|B|AB|)

12、= 10 (5+73) = 1231.5 文氏图 Venn Diagram 文氏图提供了一种关于集合的形象化的表示。在 Venn 图中，用一个矩形表示全集，用圆表示全集的一个子集 A，圆的内部表示该子集的成员。A241.5 文氏图 v Venn Diagram 可用于表示集合的运算。（如图，蓝色部分为运算结果）ABAB251.5 文氏图 A-BAAB261.5 文氏图 例 165个学生选修课程 A、B、C，已知有79人选A，83人选 B，63人选 C；33人选 A 和 C，20人选 A和 B，24人选 B 和 C；8人选了 A、B 和 C。问：有多少人没有选修任何课程？通过文氏图的图解分析或容

13、斥原理计算，得到答案是9人。271.5 文氏图 一般相处一般相处 设集合 A、B，若存在元素 p、q、r，使得pApB，qBqA，rArB，则称 A 和 B 一般相处。281.5 文氏图 定理定理 任何两个集合 A、B，只能有五种可能的相处，即 A=B AB BA AB= 一般相处 291.6 序偶序偶序偶 由两个固定次序的对象构成的序列称为一个序偶，记作 。x 称为首元，y 称为次元。v 说明： 次序至关紧要； x, y 之间无关联要求； 首元和次元允许同一，即 是合法的； 注意与 x, y 的区别。序偶的集合性定义序偶的集合性定义 = x,x, y 301.6 序偶定理定理 = 当且仅当 x=u, y=v证明 引入序偶的集合性定义 引用集合相等的外延性公理v 推广定义： = , z定理定理 = 当且仅当 x=u, y=v, z=wv 推广定义： = , xn 定理定理 = 当且仅当 xi=ui, i=1,2,n311