离散数学集合

1、2020/7/5,zhengjin ,csu,1,第二章 集 合（set) 集合的概念在现代数学中是一个非常重要的概念。本节主要介绍集合及其表示、集合的运算，序偶，集合的笛卡尔乘积。,2020/7/5,zhengjin ,csu,2,个体和集合之间的关系,集合不能精确定义，只能直观描述： 一个集合就是若干事物的全体。 组成集合的每个事物叫做这个集合的元素。 小写拉丁字母表示个体：a、b、c、d 大写拉丁字母表示集合：a、b、c、d,2020/7/5,zhengjin ,csu,3,个体与集合之间的关系：属于关系。 对于某个个体 a 和某个集合 a 而言，a 只有两种可能 1）a属于a，记为 a

2、a，同时称 a 是 a 中的元素。 2）a 不属于 a，记为 aa ，称 a 不是 a 中的元素。 个体a属于a或者a不属于a，二者居其一且只居其一。,2020/7/5,zhengjin ,csu,4,集合的表示法,(1)文字表示法 用文字表示集合的元素，两端加上花括号。 在座的同学 高等数学中的积分公式 (2) 元素列举法 将集合中的元素逐一列出，两端加上花括号。 1，2，3，4，5， 风，马，牛 2，4，6，8，10， ,2020/7/5,zhengjin ,csu,5,(3)谓词表示法 xp(x) p表示x所满足的性质 例如： xx2=1=1，-1 yy是开区间(a，b)上的连续函数 ,

3、2020/7/5,zhengjin ,csu,6,（4）归纳定义法,用归纳法定义一个非空集合a时，包括以下三步： 1)基本项（保证a不空) 已知某些元素属于a 2)归纳项（生成规则） 给出一组规则，从a中的元素出发，依据这些规则所获得的元素，仍然都是a中的元素。（这是构造a的关键步骤） 3）极小化（通常省略） 如果集合s也满足（1）和（2），且sa，则s=a。这一点保证集合a的唯一性。,2020/7/5,zhengjin ,csu,7,例1 如果论域是整数集i，那么能被3整除的正整数集合s用归纳法可定义如下： （1）（基础）3s， （2）（归纳）如果xs和ys，则x+ys,2020/7/5,z

4、hengjin ,csu,8,集合的特殊情况,1、不含任何元素的集合称为空集，记为 2、含讨论问题所需全部元素的集合称为全集，记为 3、 称含有有限个元素的集合为有限集合 4、 含有无限个元素的的集合称为无限集合或无限集 5、 集合a中元素的个数（或基数或集合的势）记为:|a| 提醒:一个集合也可以是别的集合的元素，如： a， b， a，b a，b， ，a，b,2020/7/5,zhengjin ,csu,9,集合与集合之间的关系,设a，b是两个集合 1）若对于a中的每个元素x，都有x属于b， 则称a包含在b中，记为:a b。同时称a是b的子集。 2）若a中的每个元素都属于b，且b中的每个元素

5、都属于a，则称a等于b，记为a=b。 (a=b 当且仅当ab 且 ba） 3)集合的包含关系具有传递性:即 若a b且b c，则a c,2020/7/5,zhengjin ,csu,10,子集的两种特殊情况（平凡子集）： 1）空集是任一集合的子集。 2）任何集合都是它自己的子集。,2020/7/5,zhengjin ,csu,11,例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)

6、a，b，a，a，b，b，a，b,2020/7/5,zhengjin ,csu,12,集合上的运算,定义2 设a，b是两个集合 1）ab = xxaxb ，称ab为a与b的交集，称为集合交运算。 2）ab = xxaxb ，称ab为a与b的并集，称为集合并运算。 3) ab= xxa x b ， 称ab为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 ab=1，3，4,2020/7/5,zhengjin ,csu,13,定理1 设u是全集，a，b，c是u的三个子集 1）aa=a， aa=a 2）au=a， au=u 3）a =

7、 ， a =a 4）ab= ba， ab= ba 5）(ab) c = a (bc)， (ab) c = a (bc) 6）a(b c) = (ab) (ac) a(b c) = (ab) (ac),2020/7/5,zhengjin ,csu,14,定理2 设a，b，c为三个集合，则 1）a ab， ab a； 2）若 a c 且 b c，则 ab c； 3）若 c a 且 c b，则 c ab 。 4) a-b a 5) a- =a 6) a(b-c)= (ab)-( ac) ； 定理3 设a，b为两个集合，则下面三式等价。 1）a b 2）ab = b 3) ab=a 图形表示：,202

8、0/7/5,zhengjin ,csu,15,集合上的补运算(一元运算）,设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 = ,2020/7/5,zhengjin ,csu,16,定理5 设a，b为两个集合，则 1） ( ab) = a b 2） ( ab) = a b,2020/7/5,zhengjin

9、,csu,17,集合的环和（对称差）运算,定义： 设a，b是两个集合， ab = (a-b) (b-a) = x(xaxb) (xbxa) 称 ab 为a和b的环和，称 为集合环和运算。 由环和运算和并、差运算的定义知 ab=(ab)(ab) 例：设a=a，b，c，d，e，b=a，b，c，f，g，则,2020/7/5,zhengjin ,csu,18,幂 集,定义：设a是集合，a的所有子集组成的集合称为a的幂集，记为 ：2a或p(a)。 2a = x x a 例1：如果a=a，b，则2a=，a，b，a，b 例2：设a=，则2a=， ， ， ， 定理1 设集合a是有限集合， a = n，则 2a

10、 = 2 a 定理2 设a，b是两个集合。那么， a=b当且仅当 2a = 2b。,2020/7/5,zhengjin ,csu,19,有限集的计数原理,设a和b都是有限集合，则以下公式成立: | ab |= | a |+ |b |- | a b | | a b |= | a |- | b | | a1a2 a3 |= | a 1|+ | a2 |+ | a3 |- | a1 a2 |- | a2 a3 |- | a1 a3 |+ | a1 a2 a3 |,2020/7/5,zhengjin ,csu,20,有限集计数原理,p68,2020/7/5,zhengjin ,csu,21,集合的广义

11、并和广义交,定义6：如果集合c中的成员本身又都是集合，则集合c称为集类(或称为搜集)。 设c=a1，a2，a3，an (1) c的成员的并，记为：c，称为c的广义并 c=a1a2an （2）c的成员的交，记为：c，称为c的广义交 c=a1a2an 例：设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,2020/7/5,zhengjin ,csu,22,数学归纳法,对于以自然数为论域的 x p(x)形式的归纳证明过程如下: 第一数学归纳法 (1)（基础）先证明p(0)是真。 (2)（归纳) 再

12、证明 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)。,2020/7/5,zhengjin ,csu,23,第二数学归纳法原理 n kk0，如果p(k)对一切kn 成立，那么p(n)成立。,数学归纳法,2020/7/5,zhengjin ,csu,24,集合的笛卡尔乘积,由任意两个元素x和y组成的集合x，y为偶集。因为x，y=y，x，所以这种偶集只能叫无序偶集， 简称无序偶。 有序偶:它不仅与含有

13、的元素x，y有关，还与x，y出现的次序有关。这样的偶集称为有序偶，并记为： 例如，用表示平面直角坐标系下的横坐标为x且纵坐标为y的点时，则和在xy时就代表不同的点，因而就不相同。,2020/7/5,zhengjin ,csu,25,定义1 有序偶的集合定义：若x，y为任意两个元素，令 =x，x，y 称为由x，y组成的二元序偶，简称有序偶或序偶。 提醒：此种定义显然体现了二元元素的有序性。但有序偶的定义不只一种，还有别的定义方法，只要能体现有序性就可以了,用集合定义有序偶,2020/7/5,zhengjin ,csu,26,定理1 = 当且仅当 x=u且y=v （根据序偶的定义即可得出。） 定义

14、2 设n是正整数，x1，x2，xn是任意的元素。 若n=1，则令 =x1 若n=2，则令 =x1,x1，x2 若n2，则令 =,xn 我们称为由x1，x2，xn 组成的n元序偶，并称每个xi为它的第i个分量。 （这样就定义了n元序偶）,2020/7/5,zhengjin ,csu,27,定义3 设n是正整数，a1，a2，an为n个任意集合。 a1a2an=若1in，则xiai 称a1a2an为a1，a2，an的n维笛卡尔乘积。 定义4 设a，b是两个非空集合 ab=aa bb (即所有第一元素在a中，第二元素在b中的序偶的集合) 称ab是a与b的叉积（笛卡儿积）集合。 记:aa=a2,2020

15、/7/5,zhengjin ,csu,28,（1）在ab中，a称为前集，b称为后集。前集与后集可以相同，也可以不同。若前集与后集相同，则记为aa=a2 。 （2）规定a=b。若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集。 （3）由于偶对中的元素是有序的，因此一般地说abba。(除非a=b，或者a、b中至少有一个为空集),2020/7/5,zhengjin ,csu,29,例1 a=a，b，c， b=0，1 ab=， ba=， a2=，,2020/7/5,zhengjin ,csu,30,定理2：设a，b是两集合，则 ab=a*b (即ab中元素的个数等于a中元素个

16、数乘以b中元素个数)。 定理3 设a，b，c，d是四个非空集合，那么ab=cd当且仅当a=c且b=d 。,2020/7/5,zhengjin ,csu,31,定理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),2020/7/5,zhengjin ,csu,32,本章主要掌握集合的谓词表示法，和集合的基本运算，以及序偶的概念，集合的笛卡尔集，及相关定理。定理的证明相对简单，所以证明略。 对于数学归纳法，由于中学就已学过，所以这里就省略。,2020/7/5,zhengjin ,csu,33,1 ab与ab能同时成立吗？ 2 何为一个集合的幂集，含有n个元素的集合，其幂集有多少个元素？不用组合的方法，能否得出你的结论？ 3 何谓集类，及集类的广义交和广义并？这里介绍的集合与你以前接触过的集合概念有何不同？掌握计数原理(即有限集的