离散数学集合的概念和表示法

1、第三章 集合与关系3-1 集合的概念和表示法授课人：李朔Email:chn.nj.1一、集合的概念 集合是不能精确定义的数学基本概念, 当我们讨论某一类对象时，就把这一类对象的全体称为集合。这些对象称为集合中元素。元素也是抽象的，无法精确定义，可以认为是存在于世界上的一切客观物体。 例如：地球上的人。 公园里的花。 坐标平面上的点。 2一、集合的概念 通常用大写字母表示一个集合，例A，B，。用小写字母表示一个集合的元素，例a, b, x, y, 。若元素a属于集合A，记作aA, 否则记aA。若一个集的元素个数是有限，称有限集，否则称为无限集。有限集合的元素个数称为该集合的基数，集合A的基数记为

2、|A|。3一、集合的概念 本书通常用N表示自然数集（包含0），Z代表整数数集，Q代表有理数集，R代表实数集，C代表复数集。集合的表示通常有二种方法：1）列举法：把集合的元素在花括号内列出例 A=a, b, c, dN=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 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 5二集合之间的关系集合之间有二种基本关系：1）相等：两个集A，B称作相等，当且仅当A，B的元素完全相同，记A=B，否则AB。(P82外延性原理）例 1, 2, 4 1, 2, 4 1

4、, 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；(传递性）6二集合之间的关系定理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

5、为两个集合，若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，但 AA7三、空集84 定义3-1.3 不含任何元素的集合称为空集，记为，即= 。 =x | P(x)P(x) 其中，P(x)为任意谓词空集是不包含任何元素的集合，所以，|=0。注： ， 。定理3-1.2 对任一个集合A， A。证：设不是A的子集，则必有x 而xA，这与的定义矛盾。根据本定理，空集是任意集合的子集，即 A；对任意集合A，AA。一

6、般地说，任意集合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,b9例：求出下列集合的全部子集：(a) ,(b)a,b,a,a,b,b,a,b, a,b10四、全集定义3-1.4全集若在特定条件下考虑的对象均属于E，则称E为全集。全集概念相当于论域。如讨论宇宙万物的集合时一切客体都属于全集。而讨论一个班级，则该班级的全部学生组成了全集。以一个集合的所有子集为元素，可

7、以组成另外一种集合。11五、幂集 定义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，可以有多少个不同的子集？即它的幂集的基数 12五、幂集P85 定理3-1.3：如果有限集合A有n个元素,则其幂集P(n)有2n个元素。证明：A的所有由k个元素组成的子集为从n个元素中取k个元素的组合数。另外，因 ，故P(A)的总数N可表示为：又因 令x=y=1，故P(A)的元素个数是2n13六、子集编码引进一种编码，用来唯一地表示有限集幂集的元素。以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是二进制数且 14本课小结集合，有