离散数学讲义--第四章集合论.ppt

1、第四章 集合,集合的概念与表示 集合的运算 Venn氏图及容斥原理 集合的划分,4.1 集合的概念与表示,将一个确定的，可以区分的事物的全体称为集合，而这些事物称为集合的元素。,若a是A的元素 称a属于A，记作aA。 若a不是A的元素 称a不属于A，记作aA。,集合用大写字母A，B,来表示，而集合的元素一般用小写字母表示,元素个数有限的集合称为有限集。元素 个数无限的集合称为无限集。有限集的元 素的个数记作A或#A，称为A的基数。,4.1 集合的概念与表示,关于集合，有两点特别注意： 1）集合元素的无序性 2）集合中的元素不计重度,集合的表示方法：,列举法,例如：A=a,b,c,d N=0,1

2、,2 Zm=0,1,2,m-1,4.1 集合的概念与表示,集合的表示方法：,谓词描述法： A= x x具有某种性质,例如： B= x 1x5,xR C= x x2-1=0, xR D=(x,y)x2+y21，x,yR,4.1 集合的概念与表示,集合的表示方法：,递归法： (1)基本项 (2)递归项 (3)极小化,例如：集合Ck=0,k,2k,.的递归定义： 1）0Ck 2）若nCk,则n+kCk,4.1 集合的概念与表示,4.1 集合的概念与表示,集合间的关系：,包含：,相等：,AB x(xA xB) AB也可记作BA,A=B x(xAxB)(xBxA) ABB A ,4.1 集合的概念与表示

3、,集合间的关系：,真包含：,ABx(xAxB)$x(xB xA) ABBA AB也可记作BA ,4.1 集合的概念与表示,特殊集合,空集： 不含任何元素的集合称为空集，记作,性质：空集是任何集合的子集,推论：空集是唯一的,给定一个非空集合A,则和A称为A的 平凡子集。,4.1 集合的概念与表示,特殊集合,全集： 在所研究的同一个问题中，如果涉及到的 集合均是某一个集合的子集，则称该集合是 全集，记作。,4.1 集合的概念与表示,特殊集合,幂集： 设A是一个集合，由A的所有子集组成 的集合称为A的幂集，记作(A)或2A 谓词描述法表示：（A）=uuA,4.1 集合的概念与表示,例如：设A=0，1

4、，2写出A的全部子集,解：A的0元子集： A的1元子集：0，1，2 2元子集：0，1，0，2，1，2 3元子集：0，1，2,定理：如A是有限集，若A=n则(A)=2n,4.1 集合的概念与表示,例：A=a,b,写 （A）,解: （A）=，a,b,a,b,例：设A=a, 判断下列结论是否正确 (1)A，(2)A，(3)A， (4)A,(5)aA,(6)aA, (7)aA,(8)aA,解：1)，2），3），5），8）是正确的,4.2 集合的运算,设A和B是两个集合，定义 AB=xxA xB AB=xxA xB A-B=xxAxB A=xxA且xE AB=xxA且xBxB且xA,定理：设A、B、C是

5、三个集合，则有 (1)AAB，BAB (2)ABA，ABB。 (3)ABAB (4)若AB则AB=A，AB=B。,4.2 集合的运算,4.2 集合的运算,交换律 AB=BA，AB=BA 结合律 （AB）C=A（BC） （AB） C=A（B C） 分配律 A（BC）=（AB）（AC） A（BC）=（AB）（AC） 幂等律 AA=A，AA=A 同一律 A=A,AE=A,4.2 集合的运算,零一律 A=，AE=E 补余律 AA=，AA=E 吸收律 A（AB）=A A（AB）=A 德摩根律 （AB）=AB （AB）=AB 双重否定律 （A）=A,4.2 集合的运算,谓词的等价与集合的相等包含之间的相似

6、 性讨论：,用谓词定义集合的方法称为指定原理。被 某一谓词指定的子集称为该谓词在全集中的一 个广延。,如果两个谓词是等价的，则它们具有相同的外延。即等价谓词指定的集合是相等的。,4.3 Venn图及容斥原理,Venn图,AB,AB,A-B,4.3 Venn图及容斥原理,容斥原理,|AB|=|A|+|B|-| AB |,解 设职员和学生的集合分别是A和B。 由已知条件A=10, B =12, AB=5 AB=A+B-AB=10+12-5=17 则(AB)=E-AB=20-17=3 有3名既不是职员又不是学生,例 在20名青年有10名是公司职员,12名 是学生,其中5名既是职员又是学生,问有 几名

7、既不是职员,又不是学生？,4.3 Venn图及容斥原理,4.3 Venn图及容斥原理,三个集合的容斥定理,ABC=A+B+C-AB-AC-BC+ABC,n个集合的容斥定理,A1A2 . An=|Ai|-|AiAj|+|AiAjAk| +.+(-1)n-1|A1A2.An|,4.3 集合的划分,定义4.4.1 设A是一非空集合，是A的非空子集组成的集合，若 1）S1,S2，要么S1S2=，要么S1=S2 2） 则称是集合A的划分.|称为划分的秩。,集合的划分,4.3 集合的划分,关于集合的划分的理解：,划分中的每一块是非空的,划分中的任意两块没有公共元素,A的一个划分耗尽了A中的所有元素,例 设

8、A=a,b,c,考察下列由A的非空子集组成 的集合是否是A的划分？ 1=a,b,b,c 2=a,a,b,a,b,c 3=a,b,c 4=a,b,c 5=a,b,c 6=a,a,b,解答： 3 、4 、 5是A的划分。 4称为最小（粗）划分， 5称为最大（细）划分。,4.3 集合的划分,4.3 集合的划分,定义4.4.2 设A是一非空集合，是A的非空子集组成的集合，若 ，则称是集合A的覆盖.,集合的覆盖,4.3 集合的划分,定义4.4.3 设1=A1,A2, .,Ar和2=B1,B2, .,Bt是集合A的两个不同划分，则称所有使 Ai Bj（i=1,2,.,r;j=1,2,.,t)者组成的集合称为1和2的交叉划分。,交叉划分与细分,定理 集合A的划分1 和2的交叉划分是A的划分。,4.3 集合的划分,4.3 集合的划分,定义4.4.4 设1=A1,A2, .,Ar和2=B1,B2, .,Bt是集合A的两个不同划分，若对于每个Ai 1都存在