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