离散数学集合

1、2022-5-25Zhengjin ,CSU1 第二章第二章 集集 合（合（set) 集合的概念在现代数学中是一个非常重要的概念。集合的概念在现代数学中是一个非常重要的概念。本节主要介绍集合及其表示、集合的运算，序偶，本节主要介绍集合及其表示、集合的运算，序偶，集合的笛卡尔乘积。集合的笛卡尔乘积。2022-5-25Zhengjin ,CSU2个体和集合之间的关系个体和集合之间的关系集合不能精确定义，只能直观描述：一个集合就是若干事物的全体一个集合就是若干事物的全体。组成集合的每个事物叫做这个集合的元素。元素。 小写拉丁字母表示个体：a、b、c、d 大写拉丁字母表示集合：A、B、C、D2022-

2、5-25Zhengjin ,CSU3个体与集合之间的关系：属于属于关系关系。 对于某个个体 a 和某个集合 A 而言，a 只有两种可能 1）a属于A，记为 aA，同时称 a 是 A 中的元素。 2）a 不属于 A，记为 aA ，称 a 不是 A 中的元素。个体个体a属于属于A或者或者a不属于不属于A，二者居其一且只居其一。，二者居其一且只居其一。 2022-5-25Zhengjin ,CSU4集合的集合的表示表示法法 (1)文字表示法文字表示法 用文字表示集合的元素，两端加上花括号。 在座的同学 高等数学中的积分公式 (2) 元素列举法元素列举法 将集合中的元素逐一列出，两端加上花括号。 1，

3、2，3，4，5， 风，马，牛 2，4，6，8，10， 2022-5-25Zhengjin ,CSU5(3)谓词表示法谓词表示法 xp(x) p表示x所满足的性质例如： xx2=1=1，-1 yy是开区间(a，b)上的连续函数 2022-5-25Zhengjin ,CSU6（4）归纳定义法）归纳定义法用归纳法定义一个非空集合A时，包括以下三步：1)基本项（保证基本项（保证A不空不空) 已知某些元素属于已知某些元素属于A2)归纳项（生成规则）归纳项（生成规则） 给出一组规则，从给出一组规则，从A中的元素出发，依据这些规则所获得的中的元素出发，依据这些规则所获得的元素，仍然都是元素，仍然都是A中的元

4、素。（这是构造中的元素。（这是构造A的关键步骤）的关键步骤）3）极小化极小化（通常省略通常省略） 如果集合如果集合S也满足（也满足（1）和（）和（2），且），且S A，则，则S=A。这一。这一点保证集合点保证集合A的唯一性。的唯一性。 2022-5-25Zhengjin ,CSU7例例1 1 如果论域是整数集如果论域是整数集I I，那么能被，那么能被3 3整除的正整数集合整除的正整数集合S S用归纳法可定义如下：用归纳法可定义如下：（1 1）（基础）（基础）3 3 S S，（2 2）（）（归纳）如果归纳）如果x x S S和和y y S S，则，则x+yx+y S S 2022-5-25Zhe

5、ngjin ,CSU8集合的特殊情况集合的特殊情况1 1、不含任何元素的集合称为空集，记为、不含任何元素的集合称为空集，记为2 2、含讨论问题所需全部元素的集合称为全集，记为、含讨论问题所需全部元素的集合称为全集，记为 3、 称含有有限个元素的集合为称含有有限个元素的集合为有限集合有限集合4、 含有无限个元素的的集合称为无限集合或无限集含有无限个元素的的集合称为无限集合或无限集5、 集合集合A A中元素的个数（或基数或集合的势）记为中元素的个数（或基数或集合的势）记为: :| |A A| | 提醒提醒:一个集合也可以是别的集合的元素，如：一个集合也可以是别的集合的元素，如： a， b， a，b

6、 a，b， ，a，b 2022-5-25Zhengjin ,CSU9集合与集合之间的关系集合与集合之间的关系 设A，B是两个集合 1）若对于A中的每个元素x，都有x属于B， 则称A包含在B中，记为:A B。同时称A是B的子集。 2）若A中的每个元素都属于B，且B中的每个元素都属于A，则称A等于B，记为A=B。 (A=B A=B 当且仅当当且仅当A A B B 且且 B B A A） 3)3)集合的包含关系具有传递性集合的包含关系具有传递性: :即即 若A B且B C，则A C2022-5-25Zhengjin ,CSU10子集的两种特殊情况（平凡子集）：子集的两种特殊情况（平凡子集）： 1）空

7、集是任一集合的子集。）空集是任一集合的子集。 2）任何集合都是它自己的子集。）任何集合都是它自己的子集。2022-5-25Zhengjin ,CSU11例例1：确定下列各命题的真假：确定下列各命题的真假：( (a) a) (b) (b) (c) ( (d) d) (e) a(e) a，b b aa，b b，c c，aa，b b，cc(f) a(f) a，b b aa，b b，c c，aa，b b，cc(g) a(g) a，b b aa，b b，c c，aa，bb(h) a(h) a，bb a a，b b，c c，aa，bb例例2 2 求出下列集合的全部子集：（a) ， (b)(b) aa，bb

8、，aa，a a，bb，bb，a a，bb2022-5-25Zhengjin ,CSU12集合上的运算集合上的运算定义定义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，42022-5-25Zhengjin ,CSU13 定理定理1 设U是全集，A，B，C是U的三个子集 1）AA=A， AA=A 2）AU=A， A

9、U=U 3）A = ， 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) 2022-5-25Zhengjin ,CSU14定理定理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

10、 图形表示：2022-5-25Zhengjin ,CSU15 集合上的补运算集合上的补运算(一元运算）一元运算） 设U是全 集，A是U的子集。 A= x x U x A =U-A称A 是A关于U的补集，称 为补运算。例例2 设U=a，b，c，d，e， A=c，d，则 A=o 定理定理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 = 2022-5-25Zhengjin ,CSU16定理定理5 设A，B为两个集合，则 1） ( AB) = A B 2） ( AB) =

11、 A B 2022-5-25Zhengjin ,CSU17集合的环和（对称差）运算集合的环和（对称差）运算定义：定义： 设A，B是两个集合， AB = (A-B) (B-A) = x(xAxB) (xBxA) 称 AB 为A和B的环和，称 为集合环和运算。由环和运算和并、差运算的定义知 A B=(AB)(A B)例例：设A=a，b，c，d，e，B=a，b，c，f，g，则 2022-5-25Zhengjin ,CSU18 幂幂 集集定义：设定义：设A是集合，是集合，A的所有子集组成的集合称为的所有子集组成的集合称为A的幂集，的幂集，记为记为 ：2A或或p(A)。 2A = x x A 例例1：如

12、果A=a，b，则2A=，a，b，a，b 例例2：设：设A=，则2A=， ， ， ， 定理定理1 设集合A是有限集合， A = n，则 2A = 2 A 定理定理2 设A，B是两个集合。那么， A=B当且仅当 2A = 2B。2022-5-25Zhengjin ,CSU19有限集的计数原理有限集的计数原理设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 |

13、2022-5-25Zhengjin ,CSU20有限集计数原理o P682022-5-25Zhengjin ,CSU21集合的广义并和广义交集合的广义并和广义交 定义定义6 6：如果集合：如果集合C C中的成员本身又都是集合，则集合中的成员本身又都是集合，则集合C C称称为为集类集类( (或称为搜集或称为搜集) )。 设设C=A1C=A1，A2A2，A3A3，AnAn (1) C (1) C的成员的并，记为：的成员的并，记为：C C，称为，称为C C的广义并的广义并 C=A1A2 C=A1A2AnAn（2 2）C C的成员的交，记为：的成员的交，记为：C C，称为，称为C C的广义交的广义交

14、C=A1A2 C=A1A2An An 例：设例：设A=1A=1，2 2，44，33，4 4，55，44，66则则A A广义交：广义交：A=1A=1，2 2，4343，4 4，5454，6=6=A A的广义并：的广义并：A=1A=1，2 2，4343，4 4，5454，66 =1 =1，2 2，3 3，4 4，5 5，662022-5-25Zhengjin ,CSU22数学归纳法数学归纳法对于以自然数为论域的对于以自然数为论域的 x P(x)形式的归纳证明过程形式的归纳证明过程如下如下: 第一数学归纳法第一数学归纳法(1)（基础）先证明P(0)是真。(2)（归纳) 再证明 n( P(n) P(n

15、+1)是真即先假设“P(n) 对任意取定的自然数n是真，再由此推出P(n+1)也真，一旦证明了P(n) P(n+1)对任意n是真，则用全称推广规则得 n( P(n) P(n+1) 再根据数学归纳法第一原理得出 x P(x)。2022-5-25Zhengjin ,CSU23第二数学归纳法原理第二数学归纳法原理 n kk0，如果P(k)对一切kn 成立，那么P(n)成立。数学归纳法数学归纳法2022-5-25Zhengjin ,CSU24集合的笛卡尔乘积集合的笛卡尔乘积 由任意两个元素由任意两个元素x x和和y y组成的集合组成的集合 x x，yy为偶集。因为为偶集。因为 x x，y=yy=y，x

16、x，所以这种偶集只能叫无序偶集，所以这种偶集只能叫无序偶集， 简称简称无序偶无序偶。 有序偶有序偶: :它不仅与含有的元素它不仅与含有的元素x x，y y有关，还与有关，还与x x，y y出现的次序有关。出现的次序有关。这样的偶集称为这样的偶集称为有序偶有序偶，并记为，并记为： 例如，用例如，用 y表示平面直角坐标系下的横坐标为表示平面直角坐标系下的横坐标为x x且纵且纵坐标为坐标为y y的点时，则的点时，则 y和和 x在在x x y y时就代表不时就代表不同的点，因而就不相同。同的点，因而就不相同。 2022-5-25Zhengjin ,CSU25定义定义1 有序偶的集合定义：若有序偶的集合

17、定义：若x，y为任意两个元素，为任意两个元素，令令 =x，x，y称称为由为由x，y组成的二元序偶，简称有序偶或序偶。组成的二元序偶，简称有序偶或序偶。 提醒提醒：此种定义显然体现了二元元素的有序性。但有序：此种定义显然体现了二元元素的有序性。但有序偶的定义不只一种，还有别的定义方法，只要能体现偶的定义不只一种，还有别的定义方法，只要能体现有序性就可以了有序性就可以了用集合定义有序偶用集合定义有序偶2022-5-25Zhengjin ,CSU26定理定理1 1 = = v当且仅当当且仅当 x=ux=u且且y=vy=v （根据序偶的定义即可得出。）根据序偶的定义即可得出。）定义定义2 2 设设n

18、n是正整数，是正整数，x1x1，x2x2，xnxn是任意的元素。是任意的元素。 若若n=1n=1，则令，则令 =x1x1=x1 若若n=2n=2，则令，则令 =x=x1 1,x,x1 1，x x2 2 若若n2n2，则令，则令 =,x xn n 我们称我们称 为由为由x x1 1，x x2 2，x xn n 组成组成的的n n元序偶，并称每个元序偶，并称每个x xi i为它的第为它的第i i个分量。个分量。 （这样就定义了（这样就定义了n n元序偶）元序偶） 2022-5-25Zhengjin ,CSU27定义定义3 3 设设n n是正整数，是正整数，A A1 1，A A2 2，A An n为

19、为n n个任意集合。个任意集合。 A A1 1A A2 2A An n=x= 若若11inin，则，则x xi iAAi i 称称A A1 1A A2 2A An n为为A A1 1，A A2 2，A An n的的n n维维笛卡尔笛卡尔乘积。乘积。 定义定义4 4 设设A A，B B是两个非空集合是两个非空集合 A AB=aB=ba a A bA b B B ( (即所有第一元素在即所有第一元素在A A中，第二元素在中，第二元素在B B中的序偶的集合中的序偶的集合) ) 称称A AB B是是A A与与B B的叉积（笛卡儿积）集合。的叉积（笛卡儿积）集合。 记记: :A AA=AA=A2 2 2

20、022-5-25Zhengjin ,CSU28n （1 1）在）在A AB B中，中，A A称为前集，称为前集，B B称为后集。前集与后称为后集。前集与后集可以相同，也可以不同。若前集与后集相同，则记集可以相同，也可以不同。若前集与后集相同，则记为为A AA=AA=A2 2 。n （2 2）规定规定A A=B B。若偶对的第一分量或第若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集二分量不存在就没有偶对存在，故规定它们的叉积集合为空集。合为空集。n （3 3）由于偶对中的元素是有序的，因此一般地说）由于偶对中的元素是有序的，因此一般地说A ABBBBA A。( (除非除非A=

21、BA=B，或者，或者A A、B B中至少有一个为空中至少有一个为空集集) ) 2022-5-25Zhengjin ,CSU29例例1 1 A=aA=a，b b，cc， B=0B=0，11 A AB=aB=0，a1，b0，b1，c0，c 1 B BA=0A=a，0b，0c，1a，1b，1 c A A2 2=a=a，ab，ac，ba，bb，bc，ca，cb，cc2022-5-25Zhengjin ,CSU30定理定理2 2：设：设A A，B B是两集合，则是两集合，则 A A B B= =A A* *B B ( (即即A A B B中元素的个数等于中元素的个数等于A A中元素个数乘以中元素个数乘以

22、B B中元素个中元素个数数) )。定理定理3 3 设设A A，B B，C C，D D是四个非空集合，那么是四个非空集合，那么A AB=CB=CD D当且仅当当且仅当A=CA=C且且B=D B=D 。2022-5-25Zhengjin ,CSU31定理定理4 4 设设A A，B B，C C是三个集合，则是三个集合，则 1 1）A A(BC)=(A(BC)=(AB)(AB)(AC)C) 2 2）A A(BC)=(A(BC)=(AB)(AB)(AC)C) 3 3）(AB)(AB)C=(AC=(AC)(BC)(BC)C) 4 4）(AB)(AB)C=(AC=(AC)(BC)(BC)C) 5 5 ） ( A B )( A B )