《离散数学-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
2、的基数记为|A|。,4,一、集合的概念,本书通常用N表示自然数集（包含0），Z代表整数数集，Q代表有理数集，R代表实数集，C代表复数集。 集合的表示通常有二种方法： 1）列举法：把集合的元素在花括号内列出 例 A=a, b, c, d N=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是教室中所有听课的同学 集合的元素必须是确定的。所谓确定的，是指任何一个对象是
3、不是集合的元素是明确的、确定的，不能模棱两可。即对于集合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,6,二集合之间的关系,集合之间有二种基本关系： 1）相等：两个集A，B称作相等，当且仅当A，B的元素完全相同，记A=B，否则AB。(P82外延性
4、原理） 例 1, 2, 4 1, 2, 4 1, 3, 5 =x x是正奇数 2）子集（83 定义3-1.1）：A，B为两个集合，若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）矛盾。 *本定理结论是我们以后证明两个集合
5、相等的主要判定方法。(互为子集法） 定义3-1.2:真子集。A，B为两个集合，若A的每个元素都是B的元素，但B中至少有一个元素不属于A，则称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 而
6、xA，这与的定义矛盾。 根据本定理，空集是任意集合的子集，即 A；对任意集合A，AA。一般地说，任意集合A至少有两个子集，一个是空集 ，另一个是它本身A。 (称与为的平凡子集） 推论 空集是惟一的。,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为全集。 全集概念相
7、当于论域。如讨论宇宙万物的集合时一切客体都属于全集。而讨论一个班级，则该班级的全部学生组成了全集。 以一个集合的所有子集为元素，可以组成另外一种集合。,12,五、幂集,定义3-1.5 给定集合A，由A的所有子集为元素组成的集合称为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
8、(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分钟,
离散数学-3-1集合的概念和表示法.ppt
