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

1、离散数学讲义-第四章集合论离散数学讲义-第四章集合论离散数学讲义-第四章集合论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 Zm

2、=0,1,2,m-14.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+kCk4.1 集合的概念及表示4.1 集合的概念及表示集合间的关系：包含： 相等： AB x(xA xB) AB也可记作BA A=B x(xAxB)(xBxA) ABB A 4.1 集合的概念及表示集合间的关系：真包含： ABx

3、(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，2写出A的全部子集解：A的0元子集：A的1元子集：0，1，2

4、2元子集：0，1，0，2，1，23元子集：0，1，2 定理：如A是有限集，若A=n则(A)=2n4.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是三个集合，则有(1)AAB，BAB(2)ABA，ABB。(3)ABAB(4)若AB则AB=

5、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=A4.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图ABABA-B4.3 Venn图及容斥原理容斥原理|AB|=|A|+|B|-| AB |解 设职员和学生的集合分别是A和B。由已知条件A=10, B =12, AB=5AB=A+B-AB=10+12-5=17则(AB)=E-AB=20-17=3有3名既不是职员又不是学生例 在20名青年有10名是公司职员,12名是学生,其中5名既是职员又是学生,问有几名既不是职员,又不是学生？4.3 Venn图及容斥原理4.3 Venn图及容斥原理 三个集合的容斥定理ABC=A+B+C-AB-AC-BC+ABC n个集合的容斥

7、定理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中的所有元素例 设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

8、 、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的交叉划分。交叉划分及细分12 定理 集合A的划分1 和2的交叉划分是A的划分。4.3 集合的划分4.3 集合的划分 定义4.4.4 设1=A1,A2, .,Ar和2=B1,B2, .,Bt是集合A的两个不同划分，若对于每个Ai 1都存在Bj 2使得AiBj,则称1细分2交叉划分及细分1