离散数学第五版第三章(耿素云、屈婉玲、张立昂编著).ppt

1 离散数学 2 第三章 集合代数 1. 集合的基本概念 2. 集合的运算 3. 集合恒等式 3 1.集合的基本概念 1. 定义 一、集合、元素（成员） 集合是不能精确定义的概念。直观的说，将一些事物汇 集到一起组成一个整体就叫集合，而这些事物就是这个 集合的元素或成员。 例如：26个英文字母的集合； C语言中关键字的集合； 方程x*x-1=0的实数解集合； 坐标平面上所有点的集合； 全体中国人的集合； 4 1.集合的基本概念 2. 集合的标记方法 集合通常用大写的英文字母来标记。 数学中常见集合的标记方法： 自然数集合N； 整数集合Z； 有理数集合Q； 实数集合R； 复数集合C； 5 1.集合的基本概念 3. 集合的表示方法 （1）列元素法:列出集合中的所有元素，元素之间用逗 号分隔，并用花括号将他们括起来。 例如：A=1,2,3,4,7； B=A,B,C,Z； N=0,1,2,； （2）谓词表示法：用谓词来概括集合中元素的属性 B=x|P(x) 例如： B=x|xR x*x-1=0 B=x|xZ 6=x=3 6 1.集合的基本概念 4. 集合的特点 （1）无重复性：集合中的元素是彼此不同的，如果同一 元素在集合中出现多次应该认为是一个元素。 例如：1,2,3,4,7=1,1,2,2,3,4,7； （2）无序性：集合中的元素是无序的。 例如： 1,2,3=2,3,1 集合中的元素本身也可以是一个集合，在本书中规定集合 的元素都是集合。 7 1.集合的基本概念 二、元素与集合的关系（属于或不属于） 元素和集合之间的关系是隶属关系，即属于或不属于， 属于记作，不属于记作。 例如：A=a,b,c,d,d 注意：对任何集合A都有A A。 8 1.集合的基本概念 1. 包含（子集）定义 二、集合之间关系 设A,B为集合，如果B中的每个元素都是A中的元素，则称 B是A的子集合，简称子集。这时也称B被A包含，或A包含 B，记作BA。 BAx(xBxA) 注意：对任何集合A都有AA。 例如：NZQRC a,a与a的关系？ 9 1.集合的基本概念 2. 相等定义 二、集合之间关系 设A,B为集合，如果AB且BA，则称A与B相等，记作 A=B。如果A与B不相等，则记作AB。 A=B AB BA 例如：A=x|x是小于等于3的素数 B=x|x=2 x=3 则 A=B 10 1.集合的基本概念 3. 真子集定义 二、集合之间关系 设A,B为集合，如果BA且BA，则称B是A的真子集，记作 BA。如果B不是A的真子集，则记作BA。 BABA BA 例如：NZQRC AA 11 1.集合的基本概念 1. 定义 三、空集 不含任何元素的集合叫做空集，记作。 =x|xx 例如：x|xR x*x+1=0= 2. 定理 空集是一切集合的子集。 12 1.集合的基本概念 三、空集 3. 推论：空集是唯一的。 例1：判断下列命题是否为真 (1) (2) (3) (4) 真 真 真 真 13 1.集合的基本概念 问题：含有n个元素的集合简称n元集，它的含有 m(m=n)个元素的子集叫做它的m元子集。 任何一个n元集，如何求出它的全部子集？ 例2：A=a,b,c，求A的全部子集。 0元子集，即空集，只有1个:。 1元子集，即单元集，有 个：a、b、c。 2元子集，有 个：a,b、a,c、b,c。 3元子集，有 个：a,b,c。 所以：共有 个子集，即 个子集。 14 1.集合的基本概念 四、幂集 设A为集合，把A的全体子集构成的集合叫做A的幂集， 记作P(A)。 符号化为：P(A)=x|xA 所以例2的幂集为： 、a、b、c、a,b、a,c、b,c、a,b,c 注意：集合A的幂集中元素的个数为 。 15 1.集合的基本概念 例3：计算以下幂集： （1）P() （2）P() （3）P(,) （4）P(1,2,3) , , , ,1,2,3,1,2,3 16 1.集合的基本概念 五、全集 在一个具体问题中，如果所涉及的集合都是某个集合的 子集，则称这个集合为全集，记作E。 17 第三章 集合代数 1. 集合的基本概念 2. 集合的运算 3. 集合恒等式 18 2. 集合的运算 1. 交、并、相对补 设A，B为集合，A与B的并集AB，交集AB，B对 A的相对补集A-B分别定义如下： （1） AB=x|xA xB （2） AB=x|xA xB （3） A-B=x|xA xB 例4：A=1,2,3,B=1,4,C=3 求： AB、AB、A-B、B-A、C-A、CB 19 2. 集合的运算 2. 对称差 设A，B为集合，A与B的对称差集AB定义如下： AB=(A-B)(B-A) 例5：A=0,1,2,B=2,3 求：AB AB=(AB)- (AB) 20 2. 集合的运算 3. 绝对补 A=E-A=x|xE xA 例6：E=a,b,c,d,A=a,b,c 求：A 例7：对24名会外语的科技人员进行掌握外语情况的调 查。其统计结果如下：会英、日、德和法语的人 分别为13、5、10和9人，其中同时会英语和日语 的有2人，会英、德和法语中任两种语言的都是4 人。已知会日语的人既不懂法语也不懂德语，分 别求只会一种语言的人数和会三种语言的人数。 21 2. 集合的运算 例7：对24名会外语的科技人员进行掌握外语情况的调 查。其统计结果如下：会英、日、德和法语的人 分别为13、5、10和9人，其中同时会英语和日语 的有2人，会英、德和法语中任两种语言的都是4 人。已知会日语的人既不懂法语也不懂德语，分 别求只会一种语言的人数和会三种语言的人数。 4. 文氏图 可以使用文氏图来描述集合的关系、运算以及计数。 22 2. 集合的运算 例8：求11000之间（包含1和1000在内）既不能被5和6 ，也不能被8整除的数有多少个。 S=x|xZ 1=x=1000 A=x|xS x可被5整除 B=x|xS x可被6整除 C=x|xS x可被8整除 |S|=1000 |A|=1000/5=200 |B|=1000/6=166 |C|=1000/8=125 |AB|=1000/lcm(5,6)=33 |AC|=1000/lcm(5,8)=25 |BC|=1000/lcm(6,8)=41 |ABC|=1000/lcm(5,6,8)=8 23 2. 集合的运算 例8：求11000之间（包含1和1000在内）既不能被5和6 ，也不能被8整除的数有多少个。 25 8 100 S AB C 17 33 150 67 1000 所以既不能被5、6，也不能被8整数的数有： 1000-(100+200+33+67)=600 24 2. 集合的运算 5. 包含排斥定理 设S为有穷集，P1，P2Pm是m个性质。S中的任何元素x 或者具有性质Pi，或者不具有性质Pi，两种情况必居其一 。令Ai表示S中具有性质Pi的元素构成的子集，则S中不具 有性质P1，P2，Pm的元素为 25 2. 集合的运算 推论：S中至少具有一条性质的元素为 26 2. 集合的运算 例9：某班有25个学生，其中14人会打篮球，12人会打 排球，6人会打篮球和排球，5人会打篮球和网球， 还有2人会打这三种球。而6个会打网球的人都会 打另外一种球（指篮球或排球），求不会打这三 种球的人数。 S：班级的25个学生集合 A：会打篮球的学生集合 B：会打网球的学生集合 C：会打排球的学生集合 27 2. 集合的运算 例10：一个班有50个学生，在第一次考试中有26个人得 5分，在第二次考试中有21人得5分。如果两次考 试中都没得5分的有17人，那么两次考试都得5分 的有多少人？ S：50个学生集合 A：第一次考试中得5分的学生集合 B：第二次考试得5分的学生集合 28 2. 集合的运算 6. 广义并 设A为集合，A的元素的元素构成的集合称为A的广义并， 记为A。符号化表示为： A=x|z(zA x z) 例11：A=a,b,c,a,c,d,a,e,f B=a C=a,c,d 则求A、B、C、 29 2. 集合的运算 7. 广义交 设A为非空集合，A的所有元素的公共元素构成的集合称为 A的广义交，记为A。符号化表示为： A=x|z(zA x z) 例12：A=a,b,c,a,c,d,a,e,f B=a C=a,c,d 则求A、B、C 30 2. 集合的运算 8. 集合运算的优先级 称广义并、广义交、幂集、绝对补运算为一类运算； 并、交、相对补、对称差运算为二类运算； 一类运算优先于二类运算； 一类运算之间由右向左顺序进行； 二类运算之间由括号决定先后顺序。 例13：A=a,a,b 请计算 A、A、A(A-A) 31 第三章 集合代数 1. 集合的基本概念 2. 集合的运算 3. 集合恒等式 32 3. 集合恒等式 1. 集合恒等式（33条） 1) 等幂律AA=A AA=A 证明：对任意的x， x(AA) xAxA xA 所以：AA=A 33 3. 集合恒等式 2) 结合律(AB)C=A(BC) (AB)C=A(BC ) 证明：对任意的x， x(AB)C x(AB)xC (xAxB)xC xA(xBxC) xA(BC) 所以：(AB)C=A(BC) 34 3. 集合恒等式 3) 交换律AB= BA AB= BA 4) 分配律A(BC)=(AB)(AC) A(BC)=(AB)(AC) 5) 同一律A E= A A = A 6) 同一律A = A E= E 35 3. 集合恒等式 7) 排中律AA= E AA= 8) 矛盾律 9) 吸收律A(AB)=A A(AB)=A 10)德摩根律A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) (BC)=BC (BC)=BC =E E= 36 3. 集合恒等式 例13 A-(BC)=(A-B)(A-C) 证明：对任意的x， xA-(BC) xA A(BC) xA (ABAC) xA AB AC) (xA AB) (xA AC) x(A-B) x(A-C) x(A-B)(A-C) 37 3. 集合恒等式 13)排中律A=A 14)排中律ABA, ABB AAB, BAB A-BA AB=BABAB=AA-B= AB=BA (AB)C=A(BC) A=A AA= AB=ACB=C 38 3. 集合恒等式 例14 (A-B)B=AB