离散数学集合ppt课件

2020/4/29,Zhengjin,CSU,1,第二章集合（set)集合的概念在现代数学中是一个非常重要的概念。本节主要介绍集合及其表示、集合的运算，序偶，集合的笛卡尔乘积。,2020/4/29,Zhengjin,CSU,2,个体和集合之间的关系,集合不能精确定义，只能直观描述：一个集合就是若干事物的全体。组成集合的每个事物叫做这个集合的元素。小写拉丁字母表示个体：a、b、c、d大写拉丁字母表示集合：A、B、C、D,2020/4/29,Zhengjin,CSU,3,个体与集合之间的关系：属于关系。对于某个个体a和某个集合A而言，a只有两种可能1）a属于A，记为aA，同时称a是A中的元素。2）a不属于A，记为aA，称a不是A中的元素。个体a属于A或者a不属于A，二者居其一且只居其一。,2020/4/29,Zhengjin,CSU,4,集合的表示法,(1)文字表示法用文字表示集合的元素，两端加上花括号。在座的同学高等数学中的积分公式(2)元素列举法将集合中的元素逐一列出，两端加上花括号。1，2，3，4，5，风，马，牛2，4，6，8，10，,2020/4/29,Zhengjin,CSU,5,(3)谓词表示法xp(x)p表示x所满足的性质例如：xx2=1=1，-1yy是开区间(a，b)上的连续函数,2020/4/29,Zhengjin,CSU,6,（4）归纳定义法,用归纳法定义一个非空集合A时，包括以下三步：1)基本项（保证A不空)已知某些元素属于A2)归纳项（生成规则）给出一组规则，从A中的元素出发，依据这些规则所获得的元素，仍然都是A中的元素。（这是构造A的关键步骤）3）极小化（通常省略）如果集合S也满足（1）和（2），且SA，则S=A。这一点保证集合A的唯一性。,2020/4/29,Zhengjin,CSU,7,例1如果论域是整数集I，那么能被3整除的正整数集合S用归纳法可定义如下：（1）（基础）3S，（2）（归纳）如果xS和yS，则x+yS,2020/4/29,Zhengjin,CSU,8,集合的特殊情况,1、不含任何元素的集合称为空集，记为2、含讨论问题所需全部元素的集合称为全集，记为3、称含有有限个元素的集合为有限集合4、含有无限个元素的的集合称为无限集合或无限集5、集合A中元素的个数（或基数或集合的势）记为:|A|提醒:一个集合也可以是别的集合的元素，如：a，b，a，ba，b，a，b,2020/4/29,Zhengjin,CSU,9,集合与集合之间的关系,设A，B是两个集合1）若对于A中的每个元素x，都有x属于B，则称A包含在B中，记为:AB。同时称A是B的子集。2）若A中的每个元素都属于B，且B中的每个元素都属于A，则称A等于B，记为A=B。(A=B当且仅当AB且BA）3)集合的包含关系具有传递性:即若AB且BC，则AC,2020/4/29,Zhengjin,CSU,10,子集的两种特殊情况（平凡子集）：1）空集是任一集合的子集。2）任何集合都是它自己的子集。,2020/4/29,Zhengjin,CSU,11,例1：确定下列各命题的真假：(a)(b)(c)(d)(e)a，ba，b，c，a，b，c(f)a，ba，b，c，a，b，c(g)a，ba，b，c，a，b(h)a，ba，b，c，a，b例2求出下列集合的全部子集：（a)，(b)a，b，a，a，b，b，a，b,2020/4/29,Zhengjin,CSU,12,集合上的运算,定义2设A，B是两个集合1）AB=xxAxB，称AB为A与B的交集，称为集合交运算。2）AB=xxAxB，称AB为A与B的并集，称为集合并运算。3)AB=xxAxB，称AB为A与B的差集例1设A=1，2，3，4，5，B=2，5，7，则AB=1，2，3，4，5，7AB=2，5AB=1，3，4,2020/4/29,Zhengjin,CSU,13,定理1设U是全集，A，B，C是U的三个子集1）AA=A，AA=A2）AU=A，AU=U3）A=，A=A4）AB=BA，AB=BA5）(AB)C=A(BC)，(AB)C=A(BC)6）A(BC)=(AB)(AC)A(BC)=(AB)(AC),2020/4/29,Zhengjin,CSU,14,定理2设A，B，C为三个集合，则1）AAB，ABA；2）若AC且BC，则ABC；3）若CA且CB，则CAB。4)A-BA5)A-=A6)A(B-C)=(AB)-(AC)；定理3设A，B为两个集合，则下面三式等价。1）AB2）AB=B3)AB=A图形表示：,2020/4/29,Zhengjin,CSU,15,集合上的补运算(一元运算）,设U是全集，A是U的子集。A=xxUxA=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）若AB，则BA；3）若A=B，则A=B；4）U=，=U。5)AA=U，AA=,2020/4/29,Zhengjin,CSU,16,定理5设A，B为两个集合，则1）(AB)=AB2）(AB)=AB,2020/4/29,Zhengjin,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/4/29,Zhengjin,CSU,18,幂集,定义：设A是集合，A的所有子集组成的集合称为A的幂集，记为：2A或p(A)。2A=xxA例1：如果A=a，b，则2A=，a，b，a，b例2：设A=，则2A=，定理1设集合A是有限集合，A=n，则2A=2A定理2设A，B是两个集合。那么，A=B当且仅当2A=2B。,2020/4/29,Zhengjin,CSU,19,有限集的计数原理,设A和B都是有限集合，则以下公式成立:|AB|=|A|+|B|-|AB|AB|=|A|-|B|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A2A3|-|A1A3|+|A1A2A3|,2020/4/29,Zhengjin,CSU,20,有限集计数原理,P68,2020/4/29,Zhengjin,CSU,21,集合的广义并和广义交,定义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/4/29,Zhengjin,CSU,22,数学归纳法,对于以自然数为论域的xP(x)形式的归纳证明过程如下:第一数学归纳法(1)（基础）先证明P(0)是真。(2)（归纳)再证明n(P(n)P(n+1)是真即先假设“P(n)对任意取定的自然数n是真，再由此推出P(n+1)也真，一旦证明了P(n)P(n+1)对任意n是真，则用全称推广规则得n(P(n)P(n+1)再根据数学归纳法第一原理得出xP(x)。,2020/4/29,Zhengjin,CSU,23,第二数学归纳法原理nkk0，如果P(k)对一切k2，则令=,xn我们称为由x1，x2，xn组成的n元序偶，并称每个xi为它的第i个分量。（这样就定义了n元序偶）,2020/4/29,Zhengjin,CSU,27,定义3设n是正整数，A1，A2，An为n个任意集合。A1A2An=若1in，则xiAi称A1A2An为A1，A2，An的n维笛卡尔乘积。定义4设A，B是两个非空集合AB=aAbB(即所有第一元素在A中，第二元素在B中的序偶的集合)称AB是A与B的叉积（笛卡儿积）集合。记:AA=A2,2020/4/29,Zhengjin,CSU,28,（1）在AB中，A称为前集，B称为后集。前集与后集可以相同，也可以不同。若前集与后集相同，则记为AA=A2。（2）规定A=B。若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集。（3）由于偶对中的元素是有序的，因此一般地说ABBA。(除非A=B，或者A、B中至少有一个为空集),2020/4/29,Zhengjin,CSU,29,例1A=a，b，c，B=0，1AB=，BA=，A2=，,2020/4/29,Zhengjin,CSU,30,定理2：设A，B是两集合，则AB=A*B(即AB中元素的个数等于A中元素个数乘以B中元素个数)。定理3设A，B，C，D是四个非空集合，那么AB=CD当且仅当A=C且B=D。,2020/4/29,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/4/29,Zhengjin,CSU,32,本章主要掌握集合的谓词表示法，和集合的基本运算，以及序偶的概念，集合的笛卡尔集，及相关定理。定理的证明相对简单，所以证明略。对于数学归纳法，由于中学就已学过，所以这里就省略。,2020/4/29,Zhengjin,CSU,33,1AB与AB能同时成立吗？2何为一个集合的幂集，含有n个元素的集合，其幂集有多少个元素？不用组合的方法，能否得出你的结论？3何谓集类，及集类的广义交和广义并？这里介绍的集合与你以前接触过的集合概念有何不同？掌握计数原理(即有限集的计数问题)4何谓笛卡尔乘积集合，对于二维笛卡尔积集合而言，其中的元素是什么