《离散数学集合》PPT课件.ppt

《《离散数学集合》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《离散数学集合》PPT课件.ppt（35页珍藏版）》请在三一办公上搜索。

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

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

3、,CSU,6,（4）归纳定义法,用归纳法定义一个非空集合A时，包括以下三步：1)基本项（保证A不空)已知某些元素属于A2)归纳项（生成规则）给出一组规则，从A中的元素出发，依据这些规则所获得的元素，仍然都是A中的元素。（这是构造A的关键步骤）3）极小化（通常省略）如果集合S也满足（1）和（2），且SA，则S=A。这一点保证集合A的唯一性。,2023/7/31,Zhengjin,CSU,7,例1 如果论域是整数集I，那么能被3整除的正整数集合S用归纳法可定义如下：（1）（基础）3S，（2）（归纳）如果xS和yS，则x+yS,2023/7/31,Zhengjin,CSU,8,集合的特殊情况,1、不

4、含任何元素的集合称为空集，记为2、含讨论问题所需全部元素的集合称为全集，记为 3、称含有有限个元素的集合为有限集合4、含有无限个元素的的集合称为无限集合或无限集5、集合A中元素的个数（或基数或集合的势）记为:|A|提醒:一个集合也可以是别的集合的元素，如：a，b，a，b a，b，a，b,2023/7/31,Zhengjin,CSU,9,集合与集合之间的关系,设A，B是两个集合 1）若对于A中的每个元素x，都有x属于B，则称A包含在B中，记为:A B。同时称A是B的子集。2）若A中的每个元素都属于B，且B中的每个元素都属于A，则称A等于B，记为A=B。(A=B 当且仅当AB 且 BA）3)集合的

5、包含关系具有传递性:即 若A B且B C，则A C,2023/7/31,Zhengjin,CSU,10,子集的两种特殊情况（平凡子集）：1）空集是任一集合的子集。2）任何集合都是它自己的子集。,2023/7/31,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)a，b，a，a，b，b，a，b,2023/7/31,Zhengjin,CSU,12,集合上的运算,定义2 设A，B是两个集

6、合 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,2023/7/31,Zhengjin,CSU,13,定理1 设U是全集，A，B，C是U的三个子集 1）AA=A，AA=A 2）AU=A，AU=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),

7、2023/7/31,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 图形表示：,2023/7/31,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是全

8、 集，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=,2023/7/31,Zhengjin,CSU,16,定理5 设A，B为两个集合，则 1）(AB)=A B 2）(AB)=A B,2023/7/31,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，则,2023/7/31,

9、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=2 A 定理2 设A，B是两个集合。那么，A=B当且仅当 2A=2B。,2023/7/31,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 A

10、2 A3|,2023/7/31,Zhengjin,CSU,20,有限集计数原理,P68,2023/7/31,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,2023/7/31,Zhengjin,CSU,22,数学归

11、纳法,对于以自然数为论域的 x P(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)再根据数学归纳法第一原理得出 x P(x)。,2023/7/31,Zhengjin,CSU,23,第二数学归纳法原理 n kk0，如果P(k)对一切kn 成立，那么P(n)成立。,数学归纳法,2023/7/31,Zhengjin,CSU,24,集合的笛卡尔乘积,由任意两个元素x

12、和y组成的集合x，y为偶集。因为x，y=y，x，所以这种偶集只能叫无序偶集，简称无序偶。有序偶:它不仅与含有的元素x，y有关，还与x，y出现的次序有关。这样的偶集称为有序偶，并记为：例如，用表示平面直角坐标系下的横坐标为x且纵坐标为y的点时，则和在xy时就代表不同的点，因而就不相同。,2023/7/31,Zhengjin,CSU,25,定义1 有序偶的集合定义：若x，y为任意两个元素，令=x，x，y称为由x，y组成的二元序偶，简称有序偶或序偶。提醒：此种定义显然体现了二元元素的有序性。但有序偶的定义不只一种，还有别的定义方法，只要能体现有序性就可以了,用集合定义有序偶,2023/7/31,Zh

13、engjin,CSU,26,定理1=当且仅当 x=u且y=v（根据序偶的定义即可得出。）定义2 设n是正整数，x1，x2，xn是任意的元素。若n=1，则令=x1 若n=2，则令=x1,x1，x2 若n2，则令=,xn 我们称为由x1，x2，xn 组成的n元序偶，并称每个xi为它的第i个分量。（这样就定义了n元序偶）,2023/7/31,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中的序偶

14、的集合)称AB是A与B的叉积（笛卡儿积）集合。记:AA=A2,2023/7/31,Zhengjin,CSU,28,（1）在AB中，A称为前集，B称为后集。前集与后集可以相同，也可以不同。若前集与后集相同，则记为AA=A2。（2）规定A=B。若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集。（3）由于偶对中的元素是有序的，因此一般地说ABBA。(除非A=B，或者A、B中至少有一个为空集),2023/7/31,Zhengjin,CSU,29,例1 A=a，b，c，B=0，1 AB=，BA=，A2=，,2023/7/31,Zhengjin,CSU,30,定理2：设A，B是两

15、集合，则 AB=A*B(即AB中元素的个数等于A中元素个数乘以B中元素个数)。定理3 设A，B，C，D是四个非空集合，那么AB=CD当且仅当A=C且B=D。,2023/7/31,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),2023/7/31,Zhengjin,CSU,32,本章主要掌握集合的谓词表示法，和集合的基本运算，以及序偶的概念，集合的笛卡尔集，及相关定理。定理的证明相对简单，所以证

16、明略。对于数学归纳法，由于中学就已学过，所以这里就省略。,2023/7/31,Zhengjin,CSU,33,1 AB与AB能同时成立吗？2 何为一个集合的幂集，含有n个元素的集合，其幂集有多少个元素？不用组合的方法，能否得出你的结论？3 何谓集类，及集类的广义交和广义并？这里介绍的集合与你以前接触过的集合概念有何不同？掌握计数原理(即有限集的计数问题)4 何谓笛卡尔乘积集合，对于二维笛卡尔积集合而言，其中的元素是什么形式？元素个数与什么有关？,思考题：,2023/7/31,Zhengjin,CSU,34,本章回顾,本章主要掌握：集合的谓词表示法集合的基本运算序偶的概念集合的笛卡尔乘积及相关定理。定理的证明相对简单。本章作业（可都做在书上）：第一节：5，9，12，14 第二节：8，14，18，22 第五节:2，3，4,2023/7/31,Zhengjin,CSU,35,课件邮箱,password:computer11,