1、离散数学Discrete Mathematics,第三章 集合与关系,本章主要讲授集合论的基本知识，包括集合运算、包含排斥原理、笛卡尔积、关系及其性质、关系的运算、特殊关系(包括等价关系、相容关系、序关系)等。重点是集合的运算、关系及其表示、关系的性质、关系的闭包、等价关系、偏序关系。难点是关系的性质、等价关系、偏序关系的证明。,学习集合与关系这章的要求,一、学习目的与要求 本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系运算方法，为学习后续章节打下良好基础。,二、知识点1集合的基本概念与表示方
2、法；2集合的运算；3序偶与笛卡尔积；4关系及其表示、关系矩阵、关系图；,5关系的性质，符合关系、逆关系；6关系的闭包运算；7集合的划分与覆盖、等价 关系与等价类；相容关系；8序关系、偏序集、哈斯图。,三、要求1识记 集合的层次关系、集合与其元素间的关系，自反关系、对称关系、传递关系的识别，复合关系、逆关系的识别。2领会 领会下列概念：两个集合相等的概念几证明方法，关系的闭包运算，关系等价性证明。,学时分配,3-1 集合的概念和表示法,要求：1、掌握如下概念： 集合、有限集、无限集、集合相等2、掌握集合之间的关系(相等、包含、真包含)3、会证明两个集合相等，求集合的幂集。,组成集合的对象称为集合
3、的成员（member）或元素（elements）。,集合是一些确定的、作为整体识别的、互相区别的对象的总体。,一、集合的基本概念,一般用大写字母表示集合，用小写字母表示元素。 例如A表示一个集合，a表示元素，如果a是A的元素，记为：aA，读作“a属于A”、“a是A的元素”、“a是A的成员”、 “a在A之中”、“A 包含a”。 如果A不是A的元素，记为： aA ，读作“a不属于A ”、,空集和只含有有限多个元素的集合称为有限集（finite sets），否则称为无限集（infinite sets）。有限集合中元素的个数称为集合的基数（cardinality）集合A的基数表示为 A。,二、集合的表
4、示方式有三种：,（l）列举法 将集合的元素列举出来。,（2）描述法 利用一项规则（一个谓词公式），描述集合中的元素的共同性质，以便决定某一物体是否属于该集合。,（3）归纳法用递归方法定义集合。,1、列举法：将集合的元素列举出来例：A=a，b，c，d，A1=1，3，5，7，9，使用列举法，须列出足够多的元素以反映集合中成员的特征。如：B=2，4，8，若x=2n，则 B=2，4，8，16，32，若x=2+n(n-1)，则 B=2，4，8，14，22，2、叙述法：A=x|P(x)或A=x：P(x)例： C=x|1x5，xR， D=(x，y)|x2+y21，x，yR F=x|x是中国的一个省,说明：1
5、、描述法中C=x|1x5，xR与C=y|1y5，xR表示同一个集合。2、集合中元素是无序的。a，b，c，b，c，a，c，a，b表示同一个集合。3、集合中的元素可能也是集合，例：A=1，2，1，1，2，3，1A，1A。,三、集合的关系相等(外延性公理)：两个集合是相等的，当且仅当它们有相同的成员。 两个集合A和B相等，记作A=B，两个集合不相等，记作AB。0，1=x|x(x2-2x+1)=0，x I0，11，2,抽象原理 对任意谓词公式P(x)，均存在集合S，使得 S = xP(x),两个集合 A和 B相等当且仅当它们具有相同的元素。即对任意集合A、B, A=B x(xAxB),外延公理,概括公
6、理 对任意个体域，任一谓词公式都确定一个以该域中的对象为元素的集合。即对给定个体域U，对任意谓词公式P(x)，存在集合S，使得 Sx xUP(x),定义3-1.1 设A、B是任意两个集合，如果A的每一个元素都是B的元素，则称集合A是集合B的子集合（或子集，subsets），或称A包含在B内，记为AB ；或称B包含A，记为BA 。 即 AB x(xAxB),设A，B，C为任意集合，根据定义，显然有： 包含关系具有自反性：A A 包含关系具有传递性：若A B且B C，则A C。,注：可能AB或BA ，也可能两者均不成立，不是两者必居其一。,含n有个元素的集合称为n元集。它的含有m个元素的子集称为它
7、的m元子集。,四、特殊的集合1、空集定义3-1.3：不含任何元素的集合称为空集，记作。=x|p(x)p(x)例如：X=x|x2+1=0，xR是空集。注意：，定理3-1.2：对于任意一个集合A，A。证明：反证法，假设存在一个集合A，使得A为假。则存在x且xA，这与空集的定义矛盾，所以A，空集是任意集合的子集。推论：空集是唯一的。证明：设1，2是两个空集，则12，21，得1=2，所以空集是唯一的。,2、全集定义3-1.4：在一定范围内，如果所有集合均是某一集合的子集，则称该集合为全集。记作E。 E=x|p(x)p(x)3、幂集定义3-1.5：给定集合A，由A的所有子集为元素组成的集合称为A的幂集，
8、记作(A)或2A。 (A)=u|uA例：设A=1，2，3，写出A的幂集(A)。解：(A)=，1，2，3，1，2，1，3，2，3，1，2，3,一般地如果|A|=n，则A的0元子集有Cn0=1个，即空集，1元子集有Cn1个，2元子集有Cn2个，n-1元子集有Cnn-1个，n元子集有Cnn个。所以A的子集个数为：Cn0+Cn1+Cn2+Cnn=2n。有：定理3-1.3：如果有限集A有n个元素，其幂集(A)有2n个元素。,例：A=a, ，判断下列结论是否正确。,（1） A，（2） A，（3）A（4）A，（5）aA， （6） aA，（7）aA， （8）aA，,结论（1）、（2）、（3）、（5）、（8）正
9、确。,练习86页(1)-(10),3-2 集合的运算及其性质,要求：1、掌握如下概念： 交集、并集、补集、绝对补、对称差2、熟练掌握集合运算定律，会使用运算定律证明两个集合相等。,一、集合的运算1、交定义3-2.1：设任意两个集合A和B，由A和B的所有共同元素组成的集合，称为A和B的交集，记为AB。 AB=x|xAxB文氏图,例1：A=0，2，4，6，8，10，12，B=1，2，3，4，5，6，AB=2，4，6例2：设A是平面上所有矩形的集合，B是平面上所有菱形的集合，AB是所有正方形的集合。例3：设A是所有能被K整除的整数的集合，B是所有能被L整除的整数的集合，AB是所有能被K与L最小公倍数
10、整除的整数的集合。,性质：a)AA=Ab)A=c)AE=Ad)AB=BAe)(AB)C=A(BC)f)ABA，ABB,例题4：设AB，求证ACBC。证明：对任一x AC，则x A且x C， 因为有若x A，则x B， 所以x B且x C，故x BC。 因此ACBC。,2、并集定义3-2.2：设任意两个集合A和B，所有属于A或属于B的元素组成的集合，称为A和B的并集，记作AB。 AB=x|x Ax B文氏图,例1：A=1，2，3，4，B=2，4，5，AB=1，2，3，4，5例2：设A是奇数集合，B是偶数集合，AB是整数集合，AB=。,性质：a)AA=Ab)AE=Ec)A=Ad)AB=BAe)(A
11、B)C=A(BC)f)AAB，BAB,例题3：设AB，CD，求证ACBD。证明：对任一x AC，则x A或x C， 若x A，则x B，故x BD； 若x C，则x D，故x BD。因此ACBD。,定理3-2.1 设A，B，C为三个集合，则下列分配律成立。a)A(BC)=(AB)(AC)b)A(BC)=(AB)(AC),证明：a)设S= A(BC)，T= (AB)(AC)，若x S，则x A且x BC，即x A且 x B或 x A且 x C，x AB或x AC即x T，所以S T。反之，若x T，则x AB或x AC， x A且 x B或 x A且 x C，即x A且x BC，于是x S，所以
12、TS。因此，S=T。b)证明完全与a)类似。,定理3-2.2 设A，B为任意两个集合，则下列吸收律成立。a)A(AB)=Ab)A(AB)=A,证明：a)A(AB)=(AE)(AB) =A(EB)=AE=Ab)A(AB)=(AA)(AB) =A(AB)=A,定理3-2.3 AB，当且仅当AB=B或AB=A。,证明：若AB，对任意x A必有x B，对任意x AB，则x A或x B，即x B，所以AB B。又B AB ，因此得到AB=B 。反之，若AB=B，因为A AB ，所以A B 。同理可证得AB=A,3、差集、补集定义3-2.3：设A、B是任意两个集合，所有属于A而不属于B的元素组成的集合称为
13、B对A的补集，或相对补，(或A和B差集)记作A-B。 A-B=x|xAxB文氏图,定义3-2.4：设E为全集，任一集合A关于E的补，称为A的绝对补，记作A。 A=E-A=x|xExA文氏图,性质：a)(A)=Ab)E=c)=Ed)AA=Ee)AA=,定理3-2.4 设A，B为任意两个集合，则下列关系式成立。a)(AB)=ABb)(AB)=AB定理3-2.5 设A，B为任意两个集合，则下列关系式成立。a)A-B=ABb)A-B=A-(AB)定理3-2.6 设A，B，C为三个集合，则A(B-C)=(AB)-(AC)定理3-2.7 设A，B为任意两个集合，若AB，则a)BAb)(B-A)A=B,4、对称差定义3-2.5：设A、B是任意两个集合，集合A和B的对称差，其元素或属于A，或属于B，但不能既属于A又属于B，记作AB。 AB=(A-B)(B-A)文氏图,性质：a)AB=BAb)A=Ac)AA=d)AB=(AB)(AB)e)(AB)C=A(BC),作业95页(5)，(11),
