离散数学-3-1 集合的概念和表示法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第三章 集合与关系,3-1 集合的概念和表示法,授课人：李朔,Email:,chn,.,nj,.,ls,gmail,.com,1,一、集合的概念,集合,是不能精确定义的数学基本概念,当我们讨论某一类对象时，就把这一类对象的全体称为集合。这些对象称为集合中元素。元素也是抽象的，无法精确定义，可以认为是存在于世界上的一切客观物体。,例如：地球上的人。,公园里的花。,坐标平面上的点。,2,一、集合的概念,通常用,大写字母表示一个集合,，例,A,，,B,，,。,用,小写字母表示一个集合的元素,，例,a,b,xy,。,若元素,a,属于集合,A,，,记作,a,A,否则记,a,A,。,若一个集的元素个数是有限，称,有限集,，否则称为,无限集,。,有限集合的元素个数称为该集合的,基数,，集合,A,的基数,记为,|,A|,。,3,一、集合的概念,本书通常用,N,表示自然数集（包含,0,），,Z,代表整数数集，,Q,代表有理数集，,R,代表实数集，,C,代表复数集。,集合的表示通常有二种方法：,1）,列举法,：把集合的元素在花括号内列出,例,A=a,b,c,d,N=0,1,2,W=,风马牛,Z=3，5，6，9（,没有规律，所以不能用列举法）,4,一、集合的概念,2）,描述法：用,谓词,概括该集合元素的属性,B=x,P(x),表示,B,由使,P(x),为真的,x,组成。,例：,B=x,x,R,3,x 6,C=x,x,2,=1（=1，-1）D=y|y,是教室中所有听课的同学,集合的元素必须是,确定,的。所谓确定的，是指任何一个对象是不是集合的元素是明确的、确定的，不能模棱两可。即对于集合,A，,任一元素,a，,要么,a,属于,A，,要么,a,不属于,A，,两者必居其一,。,集合的元素又是,能区分,的，能区分的是指集合中的元素是互不相同的。,如果一个集合中有几个元素相同，算做一个,。例如集合,1,2,3,3,和,1,2,3,是同一集合,a,b,a,a,b,与,a,a,b,b,b,是相同的集合,。,集合的元素又是,无序,的，即,1,2,3,和,3,1,2,是同一集合。,集合的元素还可以允许是一个集合，如,S=,1,2,3,a,a,5,二集合之间的关系,集合之间有二种基本关系：,1,）,相等,：两个集,A,，,B,称作相等，当且仅当,A,，,B,的元素完全相同，记,A=B,，,否则,A,B,。(P82,外延性原理,）,例,1,2,4,1,2,4,1,3,5,=,x,x,是正奇数,2）,子集,（,83 定义3-1.1,）：,A，B,为两个集合，若,A,的每个元素都是,B,的元素，称,A,为,B,的子集，或,A,包含在,B,内，或包含，记,A,B,或,B,A。,即,A,B,x(x,A,x,B)根据子集的定义，可立即有：对任意集合,A，B，C：,1）A,A；（,自反性,）,2）A,B，B,C,则,A,C；(,传递性,）,6,二集合之间的关系,定理3-1.1,A=B,A,B,且,B,A,证,:,设,A=B,，,则,x(x,A,x,B),与,x(x,B,x,A),都为真，故,A,B,且,B,A,。,反之，若,A,B,且,B,A,而,A,B,，,设某一,x,A,但,x,B,（,或,x,B,但,x,A,）,这与,A,B,（,或,B,A,）,矛盾。,*,本定理结论是我们以后证明两个集合相等的主要判定方法,。(互为子集法）,定义3-1.2:,真子集,。,A，B,为两个集合，若,A,的每个元素都是,B,的元素，但,B,中至少有一个元素不属于,A，,则称,A,为,B,的真子集，或,A,包含在,B,内，记,A,B。,即,A,B,x(x,A,x,B),(,x)(x,B,x,A),A,B,A,B,A,B,例如：,Z,Q,又例如：,设,A,=,a,，,B,=,a,b,，,C,=,a,b,c,则,A,B,，,B,C,，,A,C，,但,A,A,7,三、空集,84 定义3-1.3,不含任何元素的集合称为,空集,，记为,，即,=。,=,x|P(x),P(x),其中，,P(x),为任意谓词,空集,是不包含任何元素的集合，所以，,|,|=0,。,注：,，,。,定理3-1.2,对任一个集合,A，,A。,证：设,不是,A,的子集，则必有,x,而,x,A，,这与,的定义矛盾。,根据本定理，空集是任意集合的子集，即,A；,对任意集合,A，A,A。,一般地说，任意集合,A,至少有两个子集，一个是空集,，,另一个是它本身,A。(,称,与为的,平凡子集,）,推论,空集是惟一的,。,8,例：确定下列命题的真假：,(a),(b),(c),(d),(e)a,b a,b,ca,b,c,(f)a,b a,b,ca,b,c,(g)a,b a,b,c,a,b,(h)a,b a,b,c,a,b,9,例：求出下列集合的全部子集：,(a),(b)a,b,a,a,b,b,a,b,a,b,10,四、全集,定义,3-1.4,全集,若在特定条件下考虑的对象均属于,E,，,则称,E,为,全集,。,全集概念相当于论域。如讨论宇宙万物的集合时一切客体都属于全集。而讨论一个班级，则该班级的全部学生组成了全集。,以一个集合的所有子集为元素，可以组成另外一种集合。,11,五、幂集,定义3-1.5,给定集合,A，,由,A,的,所有子集为元素,组成的集合称为,A,的,幂集,，记,P(A)。,即,P(A)=,S|S,A,例如,设,A=,a,b,c,，,是空集，试求,P(A)，P(P(,)。,解：,P(A)=,a,b,c,a,b,a,c,b,c,a,b,c,P(,)=,，,P(P(,)=,*一个有限集,A，,可以有多少个不同的子集？即它的幂集的基数,12,五、幂集,P85,定理3-1.3：,如果有限集合,A,有,n,个元素,则其幂集,P(n),有2,n,个元素。,证明：,A,的所有由,k,个元素组成的子集为从,n,个元素中取,k,个元素的组合数。,另外，因,，故,P(A),的总数,N,可表示为：,又因,令,x=y=1，,故,P(A),的元素个数是2,n,13,六、子集编码,引进一种编码，用来唯一地表示有限集幂集的元素。,以,S=a,b,c,为例：,P(S)=,S,i,|i,J J=i|i,是二进制且,000,J,111,*先元素排列，后各元素与对应位映射。,例如：,S,3,=S,011,=b,c,S,6,=S,110,=a,b,等。,*一般地,P,（,S,）,=S,0,，,S,1,，,S,2,n,-1,即,P(S)=i|I,是二进制数且,14,本课小结,集合，有限集，无限集，集合的基数，集合的表示法。,集合相等及证明方法。,子集,真子集,空集,全集,幂集,子集编码,15,作业,P85(1)a),c),e),(2),注：一种分配情况可用如下方式表示：,表示戏剧，音乐，广告分配时间分别为5分钟，5 分钟，20分钟,16,