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

1、n集合的概念与表示 n集合的运算 nVenn氏图及容斥原理 n集合的划分 4.1 集合的概念与表示集合的概念与表示 将一个确定的，可以区分的事物的全体 称为集合集合，而这些事物称为集合的元素。元素。 若a是A的元素 称a属于A，记作a a A A。 若a不是A的元素 称a不属于A，记作a a A A。 集合用大写字母A，B,来表示，而集 合的元素一般用小写字母表示 元素个数有限的集合称为有限集有限集。元素 个数无限的集合称为无限集。无限集。有限集的元 素的个数记作A或#A，称为A的基数。基数。 4.1 集合的概念与表示集合的概念与表示 关于集合，有两点特别注意关于集合，有两点特别注意： 1）集

2、合元素的无序性无序性 2）集合中的元素不计重度不计重度 n集合的表示方法： n列举法 例如：A=a,b,c,d N=0,1,2 Zm=0,1,2,m-1 4.1 集合的概念与表示集合的概念与表示 n集合的表示方法： n谓词描述法： A= x x具有某种性质 例如： B= x 1x5,xR C= x x2-1=0, xR D=(x,y)x2+y21，x,yR 4.1 集合的概念与表示集合的概念与表示 n集合的表示方法： n递归法： (1)基本项 (2)递归项 (3)极小化 例如：集合Ck=0,k,2k,.的递归定义： 1）0Ck 2）若nCk,则n+kCk 4.1 集合的概念与表示集合的概念与表

3、示 4.1 集合的概念与表示集合的概念与表示 n集合间的关系： n包含： n相等： A A B B x(xx(x A A x x B)B) AB也可记作BA A A= =B B x(xx(x A Ax x B)(xB)(x B Bx x A A) A A BBBB A A 4.1 集合的概念与表示集合的概念与表示 n集合间的关系： n真包含： A A B Bx(xx(x A Ax x B)B)$ $x(xx(x BB x xA A) ) A A BBBBA A A B也可记作BA 4.1 集合的概念与表示集合的概念与表示 n特殊集合 n空集： 不含任何元素的集合称为空集，记作 性质：性质：空集

4、是任何集合的子集 推论推论：空集是唯一的 给定一个非空集合A,则和A称为A的 平凡子集。 4.1 集合的概念与表示集合的概念与表示 n特殊集合 n全集： 在所研究的同一个问题中，如果涉及到的 集合均是某一个集合的子集，则称该集合是 全集，记作。 4.1 集合的概念与表示集合的概念与表示 n特殊集合 n幂集： 设A是一个集合，由A的所有子集组成 的集合称为A的幂集，记作(A)或2 2A 谓词描述法表示：（A）=uuA 4.1 集合的概念与表示集合的概念与表示 例如：设例如：设A=0A=0，1 1，22写出写出A A的全部子集的全部子集 解：解：A A的的0 0元子集：元子集： A A的的1 1元

5、子集：元子集：00，11，22 2 2元子集：元子集：00，11，00，22，11，22 3 3元子集：元子集：00，1 1，2 2 定理：如定理：如A A是有限集，若是有限集，若 A A =n=n则则 (A)(A) =2=2n n 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是两个集合，定义是两个集合，定义 A A

6、B=xB=x x x A A x x BB A A B=xB=x x x A A x x BB A-B=x A-B=x x x AxAx BB A=xA=x x x A A且且x x EE A A B=xB=x x x A A且且x x B B x x B B且且x x AA 定理：设定理：设A A、B B、C C是三个集合，则有是三个集合，则有 (1)A(1)A A A B B，B B A A B B (2)A(2)A B B A A，A A B B B B。 (3)A(3)A B B A A B B (4)(4)若若A A B B则则A A B=AB=A，A A B=BB=B。 4.2 集

7、合的运算集合的运算 4.2 集合的运算集合的运算 n交换律交换律 A A B=BB=B A A，A A B=BB=B A A n结合律结合律 （A A B B） C=AC=A （B B C C） （A A B B） C=A C=A（B B C C） n分配律分配律 A A （B B C C）= =（A A B B） （A A C C） A A （B B C C）= =（A A B B） （A A C C） n幂等律幂等律 A A A=AA=A，A A A=AA=A n同一律同一律 A A=A,A=A,A E=AE=A 4.2 集合的运算集合的运算 n零一律零一律 A A= =，A A E=EE

8、=E n补余律补余律 A AA=A=，A AA=EA=E n吸收律吸收律 A A （A A B B）=A =A A A （A A B B）=A=A n德摩根律德摩根律 （A A B B）= = A AB B （A A B B）= = A AB B n双重否定律双重否定律 （ A A）=A=A 4.2 集合的运算集合的运算 谓词的等价与集合的相等包含之间的相似谓词的等价与集合的相等包含之间的相似 性讨论：性讨论： 用谓词定义集合的方法称为指定原理。被用谓词定义集合的方法称为指定原理。被 某一谓词指定的子集称为该谓词在全集中的一某一谓词指定的子集称为该谓词在全集中的一 个广延。个广延。 如果两个谓

9、词是等价的，则它们具有相同如果两个谓词是等价的，则它们具有相同 的外延。即等价谓词指定的集合是相等的。的外延。即等价谓词指定的集合是相等的。 4.3 Venn图及容斥原理图及容斥原理 nVennVenn图图 A A B B A A B BA A-B B 4.3 Venn图及容斥原理图及容斥原理 n容斥原理容斥原理 |A|A B|=|A|+|B|-| AB|=|A|+|B|-| A B |B | 解解 设职员和学生的集合分别是设职员和学生的集合分别是A A和和B B。 由已知条件由已知条件 A A =10,=10, B B =12, =12, A A B B =5=5 A A B B = = A

10、 A + + B B - - A A B B =10+12-5=17=10+12-5=17 则则(A(A B)B) = = E E - - A A B B =20-17=3=20-17=3 有有3 3名既不是职员又不是学生名既不是职员又不是学生 例例 在在2020名青年有名青年有1010名是公司职员名是公司职员,12,12名名 是学生是学生, ,其中其中5 5名既是职员又是学生名既是职员又是学生, ,问有问有 几名既不是职员几名既不是职员, ,又不是学生？又不是学生？ 4.3 Venn图及容斥原理图及容斥原理 4.3 Venn图及容斥原理图及容斥原理 n 三个集合的容斥定理三个集合的容斥定理

11、A A B B C C = = A A + + B B + + C C - - A A B B - - A A C C - - B B C C + + A A B B C C n n n个集合的容斥定理个集合的容斥定理 A A1 1 A A2 2 . . A An n = = |A|Ai i|-|- |A|Ai i A Aj j|+|+ |A|Ai i A Aj j A Ak k| | + +.+(-1)+(-1)n-1 n-1|A |A1 1 A A2 2 . A An n| | 4.3 集合的划分集合的划分 定义定义4.4.1 设设A是一非空集合，是一非空集合，是是A的非的非 空子集组成的

12、集合，若空子集组成的集合，若 1 1） S S1 1,S,S2 2，要么，要么S S1 1 S S2 2=，要么要么S S1 1= =S S2 2 2 2） 则称则称是集合是集合A的划分的划分.|称为划分称为划分的秩。的秩。 S SA n集合的划分集合的划分 4.3 集合的划分集合的划分 n关于集合的划分的理解：关于集合的划分的理解： n划分中的每一块是非空的划分中的每一块是非空的 n划分中的任意两块没有公共元素划分中的任意两块没有公共元素 nA的一个划分耗尽了的一个划分耗尽了A中的所有元素中的所有元素 例例 设设A=a,b,c,考察下列由考察下列由A的非空子集组成的非空子集组成 的集合是否是

13、的集合是否是A的划分？的划分？ 1 1=a,b,b,c =a,b,b,c 2 2=a,a,b,a,b,c=a,a,b,a,b,c 3 3=a,b,c =a,b,c 4 4=a,b,c =a,b,c 5 5=a,b,c =a,b,c 6 6=a,a,b =a,a,b 解答：解答： 3 3 、 、4 4 、 、 5 5是是A A的划分。的划分。 4 4称为最小（粗）划分，称为最小（粗）划分， 5 5称为最大称为最大 （细）划分。（细）划分。 4.3 集合的划分集合的划分 4.3 集合的划分集合的划分 设设A是一非空集合，是一非空集合，是是A的非空子集组成的的非空子集组成的 集合，若集合，若 ，则称

14、，则称是集合是集合A的覆的覆 盖盖. n集合的覆盖集合的覆盖 S SA 4.3 集合的划分集合的划分 设设1 1=A1 1,A2 2, .,Ar r和和2 2=B1 1,B2 2, .,Bt t是集是集 合合A的两个不同划分，则称所有使的两个不同划分，则称所有使 Ai i Bj j （i=1,2,.,r;j=1,2,.,t)i=1,2,.,r;j=1,2,.,t)者组成的集合者组成的集合称称 为为1 1和和2 2的交叉划分的交叉划分。 n交叉划分与细分交叉划分与细分 1 12 2 定理定理 集合集合A的划分的划分1 1 和 和2 2的交叉的交叉 划分是划分是A的划分的划分。 4.3 集合的划分集合的划分 4.3 集合的划分集合的划分 设设1 1=A1 1,A2 2, .,Ar