《离散数学集合.PPT.ppt》由会员分享，可在线阅读，更多相关《离散数学集合.PPT.ppt（35页珍藏版）》请在三一文库上搜索。
1、2021/3/16,.,1,第二章 集 合（set) 集合的概念在现代数学中是一个非常重要的概念。本节主要介绍集合及其表示、集合的运算，序偶，集合的笛卡尔乘积。,2021/3/16,.,2,个体和集合之间的关系,集合不能精确定义，只能直观描述： 一个集合就是若干事物的全体。 组成集合的每个事物叫做这个集合的元素。 小写拉丁字母表示个体：a、b、c、d 大写拉丁字母表示集合：A、B、C、D,2021/3/16,.,3,个体与集合之间的关系：属于关系。 对于某个个体 a 和某个集合 A 而言，a 只有两种可能 1）a属于A，记为 aA，同时称 a 是 A 中的元素。 2）a 不属于 A，记为 aA
2、 ，称 a 不是 A 中的元素。 个体a属于A或者a不属于A，二者居其一且只居其一。,2021/3/16,.,4,集合的表示法,(1)文字表示法 用文字表示集合的元素，两端加上花括号。 在座的同学 高等数学中的积分公式 (2) 元素列举法 将集合中的元素逐一列出，两端加上花括号。 1，2，3，4，5， 风，马，牛 2，4，6，8，10， ,2021/3/16,.,5,(3)谓词表示法 xp(x) p表示x所满足的性质 例如： xx2=1=1，-1 yy是开区间(a，b)上的连续函数 ,2021/3/16,.,6,（4）归纳定义法,用归纳法定义一个非空集合A时，包括以下三步： 1)基本项（保证A
3、不空) 已知某些元素属于A 2)归纳项（生成规则） 给出一组规则，从A中的元素出发，依据这些规则所获得的元素，仍然都是A中的元素。（这是构造A的关键步骤） 3）极小化（通常省略） 如果集合S也满足（1）和（2），且SA，则S=A。这一点保证集合A的唯一性。,2021/3/16,.,7,例1 如果论域是整数集I，那么能被3整除的正整数集合S用归纳法可定义如下： （1）（基础）3S， （2）（归纳）如果xS和yS，则x+yS,2021/3/16,.,8,集合的特殊情况,1、不含任何元素的集合称为空集，记为 2、含讨论问题所需全部元素的集合称为全集，记为 3、 称含有有限个元素的集合为有限集合 4、
4、 含有无限个元素的的集合称为无限集合或无限集 5、 集合A中元素的个数（或基数或集合的势）记为:|A| 提醒:一个集合也可以是别的集合的元素，如： a， b， a，b a，b， ，a，b,2021/3/16,.,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)集合的包含关系具有传递性:即 若A B且B C，则A C,2021/3/16,.,10,子集的两种特殊情况（平凡子集）：
5、 1）空集是任一集合的子集。 2）任何集合都是它自己的子集。,2021/3/16,.,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,2021/3/16,.,12,集合上的运算,定义2 设A，B是两个集合 1）AB = xxAxB ，称AB为A与B的交集，称为集合交运算。 2）AB = xxAxB ，称AB为A与B的并集，称为集合并运算。 3
6、) 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,2021/3/16,.,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),2021/3/16,.,14,定理2 设A，B，C为三个集合，则 1）A AB， AB
7、 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 图形表示：,2021/3/16,.,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）若
8、A = B，则 A= B ； 4） U= ， =U。 5) A A =U， A A = ,2021/3/16,.,16,定理5 设A，B为两个集合，则 1） ( AB) = A B 2） ( AB) = A B,2021/3/16,.,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，则,2021/3/16,.,18,幂 集,定义：设A是集合，A的所有子集组成
9、的集合称为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。,2021/3/16,.,19,有限集的计数原理,设A和B都是有限集合，则以下公式成立: | AB |= | A |+ |B |- | A B | | A B |= | A |- | B | | A1A2 A3 |= | A 1|+ | A2 |+ | A3 |- | A1 A2 |- | A2 A3 |- |
10、A1 A3 |+ | A1 A2 A3 |,2021/3/16,.,20,有限集计数原理,P68,2021/3/16,.,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,2021/3/16,.,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)。,2021/3/16,.,23,第二数学归纳法原理 n kk0，如果P(k)对一切kn 成立，那么P(n)成立。,数学归纳法,2021/3/16,.,24,集合的笛卡尔乘积,由任意两个元素x和y组成的集合x，y为偶集。因为x，y=
12、y，x，所以这种偶集只能叫无序偶集， 简称无序偶。 有序偶:它不仅与含有的元素x，y有关，还与x，y出现的次序有关。这样的偶集称为有序偶，并记为： 例如，用表示平面直角坐标系下的横坐标为x且纵坐标为y的点时，则和在xy时就代表不同的点，因而就不相同。,2021/3/16,.,25,定义1 有序偶的集合定义：若x，y为任意两个元素，令 =x，x，y 称为由x，y组成的二元序偶，简称有序偶或序偶。 提醒：此种定义显然体现了二元元素的有序性。但有序偶的定义不只一种，还有别的定义方法，只要能体现有序性就可以了,用集合定义有序偶,2021/3/16,.,26,定理1 = 当且仅当 x=u且y=v （根据
13、序偶的定义即可得出。） 定义2 设n是正整数，x1，x2，xn是任意的元素。 若n=1，则令 =x1 若n=2，则令 =x1,x1，x2 若n2，则令 =,xn 我们称为由x1，x2，xn 组成的n元序偶，并称每个xi为它的第i个分量。 （这样就定义了n元序偶）,2021/3/16,.,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,2
14、021/3/16,.,28,（1）在AB中，A称为前集，B称为后集。前集与后集可以相同，也可以不同。若前集与后集相同，则记为AA=A2 。 （2）规定A=B。若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集。 （3）由于偶对中的元素是有序的，因此一般地说ABBA。(除非A=B，或者A、B中至少有一个为空集),2021/3/16,.,29,例1 A=a，b，c， B=0，1 AB=， BA=， A2=，,2021/3/16,.,30,定理2：设A，B是两集合，则 AB=A*B (即AB中元素的个数等于A中元素个数乘以B中元素个数)。 定理3 设A，B，C，D是四个非空集
15、合，那么AB=CD当且仅当A=C且B=D 。,2021/3/16,.,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),2021/3/16,.,32,本章主要掌握集合的谓词表示法，和集合的基本运算，以及序偶的概念，集合的笛卡尔集，及相关定理。定理的证明相对简单，所以证明略。 对于数学归纳法，由于中学就已学过，所以这里就省略。,2021/3/16,.,33,1 AB与AB能同时成立吗？ 2 何为一个集合的幂集，含
16、有n个元素的集合，其幂集有多少个元素？不用组合的方法，能否得出你的结论？ 3 何谓集类，及集类的广义交和广义并？这里介绍的集合与你以前接触过的集合概念有何不同？掌握计数原理(即有限集的计数问题) 4 何谓笛卡尔乘积集合，对于二维笛卡尔积集合而言，其中的元素是什么形式？元素个数与什么有关？,思考题：,2021/3/16,.,34,本章回顾,本章主要掌握： 集合的谓词表示法 集合的基本运算 序偶的概念 集合的笛卡尔乘积及相关定理。定理的证明相对简单。 本章作业（可都做在书上）： 第一节：5，9，12，14 第二节：8，14，18，22 第五节: 2，3，4,2021/3/16,.,35,课件邮箱,csu_edu_ password: computer11,