离散数学-- 集合代数

1、计算机科学学院计算机科学学院 刘芳刘芳2022-3-201第二部分第二部分 集合论集合论引言引言第第6章章 集合代数集合代数第第7章章 二元关系二元关系第第8章章 函数函数计算机科学学院计算机科学学院 刘芳刘芳2022-3-202集合论集合论集合论：集合论：研究集合的数学理论研究集合的数学理论起源起源George Cantor (1845-1918，德国德国) 重要性重要性它是数学的一个基本分支，在数学中占据着一个极其它是数学的一个基本分支，在数学中占据着一个极其独特的地位，其基本概念已渗透到数学的所有领域。独特的地位，其基本概念已渗透到数学的所有领域。集合论广泛地应用于计算机科学领域集合论广

2、泛地应用于计算机科学领域如：形式语言、自动机理论、人工智能、数据库等。如：形式语言、自动机理论、人工智能、数据库等。如果把现代数学比作一座无比辉煌的大厦，那么可以如果把现代数学比作一座无比辉煌的大厦，那么可以说集合论正是构成这座大厦的基石。说集合论正是构成这座大厦的基石。计算机科学学院计算机科学学院 刘芳刘芳2022-3-203第第6章章 集合代数集合代数6.1 集合的基本概念集合的基本概念6.2 集合的基本运算及恒等式集合的基本运算及恒等式6.3 集合中元素的计数集合中元素的计数本章小结本章小结计算机科学学院计算机科学学院 刘芳刘芳2022-3-2046.1 集合的基本概念集合的基本概念集合

3、集合集合是数学中的一个基本概念，一般地，由一些可区集合是数学中的一个基本概念，一般地，由一些可区分的对象组成的一个整体，称为集合。分的对象组成的一个整体，称为集合。通常用大写字母通常用大写字母A、B、表示集合。表示集合。集合的元素集合的元素集合中的对象称为集合的元素。集合中的对象称为集合的元素。通常用小写字母通常用小写字母a、b、c、表示集合的元素。表示集合的元素。注：注：集合由它的元素所决定。集合由它的元素所决定。计算机科学学院计算机科学学院 刘芳刘芳2022-3-2056.1 集合的基本概念集合的基本概念集合表示方法集合表示方法列举法列举法A1，2，3，4N0，1，2，3，谓词表示法谓词表

4、示法: 用谓词描述出集合元素的属性（特征）形如：用谓词描述出集合元素的属性（特征）形如： Sx|P(x)如：如：Bx|xRx210 树形图表示法树形图表示法如：如：A a, b,c , d, d 计算机科学学院计算机科学学院 刘芳刘芳2022-3-2066.1 集合的基本概念集合的基本概念集合的元素的性质集合的元素的性质:确定性确定性设设a为任意元素，为任意元素，S为任意集合，为任意集合，则则aS或或a S，二者必居其一，且只居其一。二者必居其一，且只居其一。集合中的元素是互异的集合中的元素是互异的;集合中的元素无次序和大小之分集合中的元素无次序和大小之分;抽象性抽象性计算机科学学院计算机科学

5、学院 刘芳刘芳2022-3-2076.1 集合的基本概念集合的基本概念练习练习:求使得下列集合等式成立时，求使得下列集合等式成立时，a, b, c, d应该满足的条件：应该满足的条件：(1) a , b a, b, c(2) a, b, a a,b(3) a, , b, c 答答： (1) ac或或cb (2) 任意任意a, b (3) ac,且且b计算机科学学院计算机科学学院 刘芳刘芳2022-3-2086.1 集合的基本概念集合的基本概念集合的基数集合的基数集合集合A中的不同元素个数称为集合中的不同元素个数称为集合A的基数，记做的基数，记做|A|。集合的分类：集合的分类：有限集合有限集合无

6、限集合无限集合空集空集注意：注意： 和和的区别的区别全集全集E计算机科学学院计算机科学学院 刘芳刘芳2022-3-2096.1 集合的基本概念集合的基本概念集合间的关系的定义集合间的关系的定义设设A、B是任意两个集合是任意两个集合1.A B x(x A x B) 2.AB A B B A x(x A x B)3.AB x(x A x B ） x(x B x A ）4.()()()() ABx xAxBy yByAABAB 计算机科学学院计算机科学学院 刘芳刘芳2022-3-20106.1 集合的基本概念集合的基本概念显然：显然：(1) A (2) A A (3) 若若A B B C ，那么，那

7、么A C 推论：推论：空集是唯一的。空集是唯一的。计算机科学学院计算机科学学院 刘芳刘芳2022-3-20116.1 集合的基本概念集合的基本概念幂集：幂集：设设A为一个集合，为一个集合，A的幂集的幂集(A)是是A的所有子集的集合，的所有子集的集合，即即：(A)B|B A例：例：若若A ，则则(A)=；若若A a，则则(A)=,a；若若A a,b，则则(A)=,a,b,a,b；若若A a,b,c，则则(A)=,a,b,c,a,b,a,c,b,c,a,b,c;计算机科学学院计算机科学学院 刘芳刘芳2022-3-20126.1 集合的基本概念集合的基本概念定理：若定理：若|A|n, 则则|(A)|

8、2n；证明（方法证明（方法1）对每个对每个i(0in)，A的恰有的恰有i个元素的子集的个数即是从个元素的子集的个数即是从A的的n个元素中选取个元素中选取i个元素的组合数个元素的组合数.210)(nnnnnCCCA 计算机科学学院计算机科学学院 刘芳刘芳2022-3-20136.1 集合的基本概念集合的基本概念证明（方法证明（方法2）：）： 设设Aa1,a2,，an，则：，则：一方面：对于一方面：对于A的任何子集的任何子集S可以表示为一个可以表示为一个n位二进制数位二进制数b1b2bn，其中，其中01(1,2, )iiiaSbaSin计算机科学学院计算机科学学院 刘芳刘芳2022-3-20146

9、.1 集合的基本概念集合的基本概念另一方面：另一方面：对于任意一个对于任意一个n位二进制数位二进制数b1b2bn，也可以，也可以唯一地对应一个唯一地对应一个A的子集的子集S|1(1,2, )iiSabin因此，因此，n个元素的集合的子集个数与个元素的集合的子集个数与n位二进位二进制的个数相同，即制的个数相同，即|(A)|2n成立。成立。计算机科学学院计算机科学学院 刘芳刘芳2022-3-20156.2 集合的运算及恒等式集合的运算及恒等式1.交集的定交集的定义义ABx|xAxB性性质质AA AAAEAAB BA（AB ） C A（B C）BA可以看出可以看出,ABA ABB计算机科学学院计算机

10、科学学院 刘芳刘芳2022-3-20166.2 集合的运算及恒等式集合的运算及恒等式例：证明例：证明 (AB) C A(B C)() | | |() |) |() =()ABCx xABxCx xAxBxCx xAxBxCx xAxBCx xABCABC证明：计算机科学学院计算机科学学院 刘芳刘芳2022-3-20176.2 集合的基本运算及恒等式集合的基本运算及恒等式证：对任意的元素证：对任意的元素xx(AB ) C x(AB) xC (x A xB) xC x A (xB xC ) xA x(BC ) xA(B C)由由x的任意性的任意性，知知 (AB ) C A(B C)成立成立。计算机

11、科学学院计算机科学学院 刘芳刘芳2022-3-20186.2 集合的基本运算及恒等式集合的基本运算及恒等式集合的交运算的推广集合的交运算的推广A1A2Anx|xA1xA2xAn记做：记做：121niniAAAA 121iiAAA 也可推广到无穷多个集合也可推广到无穷多个集合：计算机科学学院计算机科学学院 刘芳刘芳2022-3-20196.2 集合的基本运算及恒等式集合的基本运算及恒等式集合广义交集合广义交定义定义 6.11设：设：A=A1,A2,An12nAAAA 计算机科学学院计算机科学学院 刘芳刘芳2022-3-20206.2 集合的基本运算及恒等式集合的基本运算及恒等式2.并集的定义并集

12、的定义ABx|xAxB性质性质AA AAAAEEAB BA(AB) C A(B C)A(B C) (A B ) (A C)A(B C) (A B ) (A C)A(A B) AA(A B) ABA可以看出可以看出,AAB BAB计算机科学学院计算机科学学院 刘芳刘芳2022-3-20216.2 集合的基本运算及恒等式集合的基本运算及恒等式证明：证明：A (B C) (A B) (A C)证明：对于任意的证明：对于任意的x，若，若()()()()()()xABCxAxBCxAxBxCxAxBxAxCxABxACxABAC由由x的任意性知的任意性知:A (B C) (A B ) (AC)成立成立计

13、算机科学学院计算机科学学院 刘芳刘芳2022-3-20226.2 集合的基本运算及恒等式集合的基本运算及恒等式集合的并运算的推广集合的并运算的推广A1A2Anx|xA1xA2xAn记做：记做：121niniAAAA 也可推广到无穷多个集合：也可推广到无穷多个集合：121iiAAA 计算机科学学院计算机科学学院 刘芳刘芳2022-3-20236.2 集合的基本运算及恒等式集合的基本运算及恒等式集合广义并集合广义并定义定义 6.10设：设：A=A1,A2,An12nA AAA计算机科学学院计算机科学学院 刘芳刘芳2022-3-20246.2 集合的基本运算及恒等式集合的基本运算及恒等式3.集合的相

14、对补（差集）集合的相对补（差集）ABx|xAx B性质性质A A A AA BAAB计算机科学学院计算机科学学院 刘芳刘芳2022-3-20256.2 集合的基本运算及恒等式集合的基本运算及恒等式例例1：设设 A1，2，4 ，5, B3，4，6计算：计算： AB BA AA AA计算机科学学院计算机科学学院 刘芳刘芳2022-3-20266.2 集合的基本运算及恒等式集合的基本运算及恒等式例例2：设集合设集合A 1 , 2 , 1,2 , , 试计算：试计算： A 1, 2 ; A; A ; 1 ,2 A; A; A答答： (1) 1 , 2, (2) A; (3) 1 , 2, 1,2 ；

15、(4) ; (5) ; (6) 计算机科学学院计算机科学学院 刘芳刘芳2022-3-20276.2 集合的基本运算及恒等式集合的基本运算及恒等式思考：思考：下列等式可能成立吗？若可能，刻画等式出现的全部下列等式可能成立吗？若可能，刻画等式出现的全部条件。条件。ABAABBABBAAB 答：答：AB ； AB ；AB；A B计算机科学学院计算机科学学院 刘芳刘芳2022-3-20286.2 集合的基本运算及恒等式集合的基本运算及恒等式4.集合的绝对补的定义：集合的绝对补的定义： x|xEx A x|x AAAAAAEAAAAABABABAB 计算机科学学院计算机科学学院 刘芳刘芳2022-3-2

16、0296.2 集合的基本运算及恒等式集合的基本运算及恒等式5.对称差的定义：对称差的定义：A B（AB）（BA）BAAB() ()() ()ABA BA BABBAAAAAABCABC 计算机科学学院计算机科学学院 刘芳刘芳2022-3-20306.2 集合的基本运算及恒等式集合的基本运算及恒等式例例设设A1，2，5，B2，4，计算计算A B。解：解：AB 1，5 BA 4 A B1,4,5计算机科学学院计算机科学学院 刘芳刘芳2022-3-20316.2 集合的基本运算及恒等式集合的基本运算及恒等式集合的恒等式（集合的算律）（集合的恒等式（集合的算律）（P92）集合运算性质的重要结果（集合运

17、算性质的重要结果（P94）证明方法证明方法（1）证明）证明P Q方法方法1： 对任意的对任意的x，x P x Q方法方法2： 找到一个集合找到一个集合T，满足：满足：P T，T Q 则则 P Q计算机科学学院计算机科学学院 刘芳刘芳2022-3-20326.2 集合的基本运算及恒等式集合的基本运算及恒等式集合的证明方法集合的证明方法2.证明证明 PQ方法方法1： 对任意的对任意的x，x P x Q方法方法2：反证法：反证法方法方法3：集合恒等式代入法：集合恒等式代入法计算机科学学院计算机科学学院 刘芳刘芳2022-3-20336.3 有穷集的计数有穷集的计数1. 设设A，B为任意两个有穷集合，

18、则为任意两个有穷集合，则|AB|A | |B|AB| BA计算机科学学院计算机科学学院 刘芳刘芳2022-3-20346.3 有穷集的计数有穷集的计数例例1：有有100名程序员，其中名程序员，其中47名熟悉名熟悉C#语言，语言，35名熟悉名熟悉JAVA语言，语言，23名熟悉两种语言。名熟悉两种语言。问：有多少人对这两种语言都不熟悉？问：有多少人对这两种语言都不熟悉？解：解：设设A、B分别表示熟悉分别表示熟悉C#和和JAVA语言的程序员的集合，语言的程序员的集合，则则法法1：根据容斥原理求解：根据容斥原理求解法法2：使用文氏图求解：使用文氏图求解计算机科学学院计算机科学学院 刘芳刘芳2022-3

19、-20356.3 有穷集的计数有穷集的计数例例2：设设|A|=3，|P(B)|=64， |P(AB)|=256，求求|B|，|AB|，|AB|， |A B|。例例3：求在求在1到到1000 000之间（含之间（含1和和1000 000在内）在内）有多少个整数既不是完全平方数，也不是完全有多少个整数既不是完全平方数，也不是完全立方数立方数?计算机科学学院计算机科学学院 刘芳刘芳2022-3-20366.3 有穷集的计数有穷集的计数2.对于三个集合，容易看出：对于三个集合，容易看出：|AB C| |A|B| |C| (|AB| |AC| |BC|） |AB C|CBA计算机科学学院计算机科学学院

20、刘芳刘芳2022-3-20376.3 有穷集的计数有穷集的计数例例6.5（P89）习题六习题六2021 （P99）22 （P99）计算机科学学院计算机科学学院 刘芳刘芳2022-3-20386.3 有穷集的计数有穷集的计数一般地，对于一般地，对于n个有限集合个有限集合A1,An,有如下结论：有如下结论：12111112|( 1)|nniiijij nijkij k nnnAAAAAAAAAAAA 容斥原理容斥原理所谓所谓容斥容斥( (inclusion-exclusion) )是是指我们计算某类事物的数目指我们计算某类事物的数目时时, , 要要排斥排斥那些那些不应包含不应包含在在这个计数中的数

21、目这个计数中的数目; ; 但同时但同时要要包容包容那些那些被错误排斥被错误排斥了的了的数目数目, , 以此补偿。以此补偿。计算机科学学院计算机科学学院 刘芳刘芳2022-3-20396.3 有穷集的计数有穷集的计数例例6.4 （P88）设：设：E为全集，为全集，A、B、C、D分别表示会英、法、德、日的分别表示会英、法、德、日的人的集合，由题设知：人的集合，由题设知：|E|=24|A|=13, |B|=9，|C|=10, |D|=5|AD|=2, |BD|=|CD|=0|AB|= |AC|= |BC|= 4设同时会英、法、德三种语言的有设同时会英、法、德三种语言的有x人，只会英、法、德语人，只会英、法、德语的中一门语言的分别有的中一门语言的分别有y1、 y2、 y3人，于是可以根据题意人，于是可以根据题意画出文氏图画出文氏图计算机科学学院计算机科学学院 刘芳刘芳2022-3-20406.3 有穷集的计数有穷集的计数列方程求解列方程求解解得：x1，y14，y22，y33。 计算机科学学院计算机科学学院 刘芳刘芳2022-3-20416.3 集合中元素的计数集合中元素的计数例：例：求求1到到250之间能被之间能被2，3，5和和7中任何一个整除的整数中任何一个