离散数学集合

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Zhengjin ,CSU,*,第二章 集 合（,set),集合的概念在现代数学中是一个非常重要的概念。本节主要介绍集合及其表示、集合的运算，序偶，集合的笛卡尔乘积。,2024/9/29,1,Zhengjin ,CSU,个体和集合之间的关系,集合不能精确定义，只能直观描述：,一个集合就是若干事物的全体,。,组成集合的每个事物叫做这个集合的,元素。,小写拉丁字母表示个体：,a、b、c、d,大写拉丁字母表示集合：,A、B、C、D,2024/9/29,2,Zhengjin ,CSU,个体与集合之间的关系：,属于,关系,。,对于某个个体,a,和某个集合,A,而言，,a,只有两种可能,1）,a,属于,A,，记为,a,A,，同时称,a,是,A,中的元素。,2）,a,不属于,A,，记为,a,A,，称,a,不是,A,中的元素。,个体,a,属于,A,或者,a,不属于,A,，二者居其一且只居其一。,2024/9/29,3,Zhengjin ,CSU,集合的,表示,法,(1)文字表示法,用文字表示集合的元素，两端加上花括号。,在座的同学,高等数学中的积分公式,(2) 元素列举法,将集合中的元素逐一列出，两端加上花括号。, 1，,2,，,3,，,4,，,5,，,风，马，牛 , 2，,4,，,6,，,8,，,10,，, ,2024/9/29,4,Zhengjin ,CSU,(3)谓词表示法,xp(x) p,表示,x,所满足的性质,例如：,xx,2,=1=1,，,-1,yy,是开区间(,a,，,b),上的连续函数 ,2024/9/29,5,Zhengjin ,CSU,（4,）归纳定义法,用归纳法定义一个非空集合,A,时，包括以下三步：,1,),基本项（保证,A,不空,),已知某些元素属于,A,2,),归纳项（生成规则）,给出一组规则，从,A,中的元素出发，依据这些规则所获得的元素，仍然都是,A,中的元素。（这是构造,A,的关键步骤）,3）,极小化,（,通常省略,）,如果集合,S,也满足（1）和（2），且,S,A,，则,S=A,。这一点保证集合,A,的唯一性。,2024/9/29,6,Zhengjin ,CSU,例1 如果论域是整数集,I,，那么能被3整除的正整数集合,S,用归纳法可定义如下：,（1）（基础）3,S,，,（2）（,归纳）如果,x,S,和,y,S,，则,x+y,S,2024/9/29,7,Zhengjin ,CSU,集合的特殊情况,1,、不含任何元素的集合称为空集，记为,2,、含讨论问题所需全部元素的集合称为全集，记为,3,、,称含有有限个元素的集合为,有限集合,4,、,含有无限个元素的的集合称为无限集合或无限集,5,、,集合,A,中元素的个数（或基数或集合的势）记为:,|,A,|,提醒,:,一个集合也可以是别的集合的元素，如：,a,，,b,，,a,，,b,a,，,b,，,，,a,，,b,2024/9/29,8,Zhengjin ,CSU,集合与集合之间的关系,设,A,，,B,是两个集合,1）若对于,A,中的每个元素,x,，都有,x,属于,B,，,则称,A,包含在,B,中，记为:,A,B,。,同时称,A,是,B,的子集。,2）若,A,中的每个元素都属于,B,，且,B,中的每个元素都属于,A,，则称,A,等于,B,，记为,A,=,B,。,(,A=B,当且仅当,A,B,且,B,A）,3)集合的包含关系具有传递性:即,若,A,B,且,B, C,，则,A, C,2024/9/29,9,Zhengjin ,CSU,子集的两种特殊情况（平凡子集）：,1）空集是任一集合的子集。,2）任何集合都是它自己的子集。,2024/9/29,10,Zhengjin ,CSU,例1：确定下列各命题的真假：,(,a),(b),(c),(,d) ,(e) a,，,b,a,，,b,，,c,，,a,，,b,，,c,(f) a,，,b,a,，,b,，,c,，,a,，,b,，,c,(g) a,，,b,a,，,b,，,c,，,a,，,b,(h) a,，,b,a,，,b,，,c,，,a,，,b,例2,求出下列集合的全部子集：,（,a),，,(b),a,，,b,，,a,，,a,，,b,，,b,，,a,，,b,2024/9/29,11,Zhengjin ,CSU,集合上的运算,定义2,设,A,，,B,是两个集合,1）,A,B,= xxAxB ,，称,A,B,为,A,与,B,的交集，称为集合交运算。,2）,A,B,= xxAxB ,，称,A,B,为,A,与,B,的并集，称为集合并运算。,3),A,B,= xxA x B ,，,称,A,B,为,A,与,B,的差集,例 1,设,A=1,，,2,，,3,，,4,，,5,，,B=2,，,5,，,7,，则,A,B=1,，,2,，,3,，,4,，,5,，,7,A,B=2,，,5,A,B=1,，,3,，,4,2024/9/29,12,Zhengjin ,CSU,定理1,设,U,是全集，,A,，,B,，,C,是,U,的三个子集,1）,A,A=A,，,AA=A,2）A,U=A,，,AU=U,3）A, = ,，,A =A,4）,A,B= BA,，,AB= BA,5）(,A,B) C = A (BC),，,(,A,B) C = A (BC),6）,A,(B C) = (AB) (AC),A,(B C) = (AB) (AC),2024/9/29,13,Zhengjin ,CSU,定理2,设,A,，,B,，,C,为三个集合，则,1）,A,AB,，,A,B,A；,2）,若,A,C,且,B,C,，则,AB,C；,3）,若,C,A,且,C,B,，则,C,A,B 。,4) A-B,A,5) A- =A,6) A,(B-C)= (,A,B)-(,A,C) ；,定理3,设,A,，,B,为两个集合，则下面三式等价。,1）,A,B 2）AB = B 3),A,B=A,图形表示：,2024/9/29,14,Zhengjin ,CSU,集合上的补运算(一元运算）,设,U,是全,集，,A,是,U,的子集。,A,= x xU xA =U-A,称,A,是,A,关于,U,的补集，称,为补运算。,例2,设,U=a,，,b,，,c,，,d,，,e,，,A,=,c,，,d,，则,A=,定理4,设,U,是全,集，,A,，,B,是,U,的子集。则,1,(,A,)=A；,2）,若,A,B,，则,B,A；,3）,若,A =,B,，则,A=,B ；,4）,U=,，,=U。,5) A,A,=U,，,A ,A,= ,2024/9/29,15,Zhengjin ,CSU,定理5,设,A,，,B,为两个集合，则,1）,(,AB) =,A,B,2）,(,A,B) =,A,B,2024/9/29,16,Zhengjin ,CSU,集合的环和（对称差）运算,定义：,设,A,，,B,是两个集合，,A,B =,(A-B),(B-A),=, x(xAxB) (xBxA) ,称,AB,为,A,和,B,的环和，称 为集合环和运算。,由环和运算和并、差运算的定义知,A,B=(A,B),(AB),例,：设,A=a,，,b,，,c,，,d,，,e,，,B=a,，,b,，,c,，,f,，,g,，则,2024/9/29,17,Zhengjin ,CSU,幂 集,定义：设,A,是集合，,A,的所有子集组成的集合称为,A,的幂集，记为 ：2,A,或,p(A),。,2,A,= x, x,A ,例1,：如果,A=a,，,b,，则,2,A,=,，,a,，,b,，,a,，,b,例2：设,A=,，,，则,2,A,=,，, ,，, ,，,，, ,定理1,设集合,A,是有限集合，,A, = n,，则,2,A, = 2, A ,定理2,设,A,，,B,是两个集合。那么，,A=B,当且仅当 2,A,= 2,B,。,2024/9/29,18,Zhengjin ,CSU,有限集的计数原理,设,A,和,B,都是有限集合，则以下公式成立:,|,A,B,|= |,A,|+ |,B,|- |,A,B,|,|,A,B,|= |,A,|- |,B |,|,A1,A2 A3,|= |,A,1|+ |,A2,|+ |,A3,|-,|,A1,A2,|- |,A2,A3,|- |,A1,A3,|+ |,A1,A2,A3,|,2024/9/29,19,Zhengjin ,CSU,有限集计数原理,P68,2024/9/29,20,Zhengjin ,CSU,集合的广义并和广义交,定义6：如果集合,C,中的成员本身又都是集合，则集合,C,称为,集类,(,或称为搜集,),。,设,C=A1,，,A2,，,A3,，,An,(1) C,的成员的并，记为：,C,，称为,C,的广义并,C=A1A2,An,（2）C,的成员的交，记为：,C,，称为,C,的广义交,C=A1A2,An,例：设,A=1,，,2,，,4,，,3,，,4,，,5,，,4,，,6,则,A,广义交：,A=1,，,2,，,43,，,4,，,54,，,6=,A,的广义并：,A=1,，,2,，,43,，,4,，,54,，,6,=1,，,2,，,3,，,4,，,5,，,6,2024/9/29,21,Zhengjin ,CSU,数学归纳法,对于以自然数为论域的,x P(x),形式的归纳证明过程如下:,第一数学归纳法,(1)（基础）先证明,P(0),是真。,(2)（归纳) 再证明,n( P(n),P(n+1),是真,即先假设“,P(n),对任意取定的自然数,n,是真，再由此推出,P(n+1),也真，一旦证明了,P(n),P(n+1),对任意,n,是真，则用全称推广规则得,n( P(n),P(n+1),再根据数学归纳法第一原理得出,x,P(x,),。,2024/9/29,22,Zhengjin ,CSU,第二数学归纳法原理,n,kk0,，如果,P(k),对一切,kn,成立，那么,P(n),成立。,数学归纳法,2024/9/29,23,Zhengjin ,CSU,集合的笛卡尔乘积,由任意两个元素,x,和,y,组成的集合,x,，,y,为偶集。因为,x,，,y=y,，,x,，所以这种偶集只能叫无序偶集，,简称,无序偶,。,有序偶,:,它不仅与含有的元素,x,，,y,有关，还与,x,，,y,出现的次序有关。这样的偶集称为,有序偶,，并记为,：,例如，用,表示平面直角坐标系下的横坐标为,x,且纵坐标为,y,的点时，则,和,在,x,y,时就代表不同的点，因而就不相同。,2024/9/29,24,Zhengjin ,CSU,定义1 有序偶的集合定义：若,x,，,y,为任意两个元素，令 =,x,，,x,，,y,称,为由,x,，,y,组成的二元序偶，简称有序偶或序偶。,提醒,：此种定义显然体现了二元元素的有序性。但有序偶的定义不只一种，还有别的定义方法，只要能体现有序性就可以了,用集合定义有序偶,2024/9/29,25,Zhengjin ,CSU,定理1 = ,当且仅当,x=u,且,y=v,（,根据序偶的定义即可得出。）,定义2,设,n,是正整数，,x1,，,x2,，,，,xn,是任意的元素。,若,n=1,，则令,=x1,若,n=2,，则令,=x,1,x,1,，,x,2,若,n2,，则令,=,x,n,我们称,为由,x,1,，,x,2,，,，,x,n,组成的,n,元序偶，并称每个,x,i,为它的第,i,个分量。,（这样就定义了,n,元序偶）,2024/9/29,26,Zhengjin ,CSU,定义3 设,n,是正整数，,A,1,，,A,2,，,，,A,n,为,n,个任意集合。,A,1,A,2,A,n,=,若1,in,，则,x,i,A,i,称,A,1,A,2,A,n,为,A,1,，,A,2,，,，,A,n,的,n,维,笛卡尔,乘积。,定义4 设,A,，,B,是两个非空集合,AB=a,A b,B,(,即所有第一元素在,A,中，第二元素在,B,中的序偶的集合),称,AB,是,A,与,B,的叉积（笛卡儿积）集合。,记:,AA=A,2,2024/9/29,27,Zhengjin ,CSU,（1）在,AB,中，,A,称为前集，,B,称为后集。前集与后集可以相同，也可以不同。若前集与后集相同，则记为,AA=A,2,。,（2）,规定,A=B,。,若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集。,（3）由于偶对中的元素是有序的，因此一般地说,ABBA。(,除非,A=B,，或者,A、B,中至少有一个为空集),2024/9/29,28,Zhengjin ,CSU,例1,A=a,，,b,，,c,，,B=0,，,1,AB=,，,，,，,，,，,BA=,，,，,，,，,，,A,2,=,，,，,，,，,，,，,，,，,2024/9/29,29,Zhengjin ,CSU,定理2：设,A,，,B,是两集合，则,A,B,=,A,*,B,(,即,A,B,中元素的个数等于,A,中元素个数乘以,B,中元素个数)。,定理3,设,A,，,B,，,C,，,D,是四个非空集合，那么,AB=CD,当且仅当,A=C,且,B=D 。,2024/9/29,30,Zhengjin ,CSU,定理4 设,A,，,B,，,C,是三个集合，则,1）,A(BC)=(AB)(AC),2）A(BC)=(AB)(AC),3）(AB)C=(AC)(BC),4）(AB)C=(AC)(BC),5）(AB)(CD)= (AC)(AD)(BC)(BD),2024/9/29,31,Zhengjin ,CSU,本章主要掌握集合的谓词表示法，和集合的基本运算，以及序偶的概念，集合的笛卡尔集，及相关定理。定理的证明相对简单，所以证明略。,对于数学归纳法，由于中学就已学过，所以这里就省略。,2024/9/29,32,Zhengjin ,CSU,1,A,B,与,A,B,能同时成立吗？,2,何为一个集合的幂集，含有,n,个元素的集合，其幂集有多少个元素？不用组合的方法，能否得出你的结论？,3,何谓集类，及集类的广义交和广义并？这里介绍的集合与你以前接触过的集合概念有何不同？掌握计数原理,(,即有限集的计数问题,),4,何谓笛卡尔乘积集合，对于二维笛卡尔积集合而言，其中的元素是什么形式？元素个数与什么有关？,思考题：,2024/9/29,33,Zhengjin ,CSU,本章回顾,本章主要掌握：,集合的谓词表示法,集合的基本运算,序偶的概念,集合的笛卡尔乘积及相关定理。定理的证明相对简单。,本章作业,（可都做在书上）：,第一节：,5,，,9,，,12,，,14,第二节：,8,，,14,，,18,，,22,第五节,: 2,，,3,，,4,2024/9/29,34,Zhengjin ,CSU,课件邮箱,csu_edu_zheng,password: computer11,2024/9/29,35,Zhengjin ,CSU,