《离散数学集合代数》由会员分享，可在线阅读，更多相关《离散数学集合代数（43页珍藏版）》请在金锄头文库上搜索。
1、计计算算机机科科学学学学院院 刘刘 芳芳第二部分第二部分 集合论集合论引言引言第第6章章集合代数集合代数第第7章章二元关系二元关系第第8章章函数函数2024/7/261计计算算机机科科学学学学院院 刘刘 芳芳集合论集合论集合论：集合论：研究集合的数学理论研究集合的数学理论起源起源George Cantor(1845-1918，德国德国)重要性重要性它是数学的一个基本分支，在数学中占据着一个极其它是数学的一个基本分支，在数学中占据着一个极其独特的地位，其基本概念已渗透到数学的所有领域。独特的地位，其基本概念已渗透到数学的所有领域。集合论广泛地应用于计算机科学领域集合论广泛地应用于计算机科学领域如
2、：形式语言、自动机理论、人工智能、数据库等。如：形式语言、自动机理论、人工智能、数据库等。如果把现代数学比作一座无比辉煌的大厦，那么可以说如果把现代数学比作一座无比辉煌的大厦，那么可以说集合论正是构成这座大厦的基石。集合论正是构成这座大厦的基石。2024/7/262计计算算机机科科学学学学院院 刘刘 芳芳第第6章章 集合代数集合代数6.1集合的基本概念集合的基本概念6.2集合的基本运算及恒等式集合的基本运算及恒等式6.3集合中元素的计数集合中元素的计数本章小结本章小结2024/7/263计计算算机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念集合集合集合是数学中的一个基本概
3、念，一般地，由一些可区集合是数学中的一个基本概念，一般地，由一些可区分的对象组成的一个整体，称为集合。分的对象组成的一个整体，称为集合。通常用大写字母通常用大写字母A、B、表示集合。表示集合。集合的元素集合的元素集合中的对象称为集合的元素。集合中的对象称为集合的元素。通常用小写字母通常用小写字母a、b、c、表示集合的元素。表示集合的元素。注：注：集合由它的元素所决定。集合由它的元素所决定。2024/7/264计计算算机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念集合表示方法集合表示方法列举法列举法A1，2，3，4N0，1，2，3，谓词表示法谓词表示法:用谓词描述出集合元素
4、的属性（特征）形如：用谓词描述出集合元素的属性（特征）形如： Sx|P(x)如：如：Bx|xRx210树形图表示法树形图表示法如：如：Aa,b,c,d,d2024/7/265计计算算机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念集合的元素的性质集合的元素的性质:确定性确定性设设a为任意元素，为任意元素，S为任意集合，为任意集合，则则aS或或a S，二者必居其一，且只居其一。二者必居其一，且只居其一。集合中的元素是互异的集合中的元素是互异的;集合中的元素无次序和大小之分集合中的元素无次序和大小之分;抽象性抽象性2024/7/266计计算算机机科科学学学学院院 刘刘 芳芳6.
5、1 集合的基本概念集合的基本概念练习练习:求使得下列集合等式成立时，求使得下列集合等式成立时，a,b,c,d应该满足的条件：应该满足的条件：(1)a,ba,b,c(2)a,b,aa,b(3)a,b,c答答：(1)ac或或cb(2)任意任意a,b(3)ac,且且b2024/7/267计计算算机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念集合的基数集合的基数集合集合A中的不同元素个数称为集合中的不同元素个数称为集合A的基数，记做的基数，记做|A|。集合的分类：集合的分类：有限集合有限集合无限集合无限集合空集空集注意：注意：和和的区别的区别全集全集E2024/7/268计计算算
6、机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念集合间的关系的定义集合间的关系的定义设设A、B是任意两个集合是任意两个集合1.A B x(xAxB)2.ABA BB A x(xAxB)3.AB x(xAx B） x(xBx A）2024/7/269计计算算机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念显然：显然：(1) A(2)A A(3)若若A BB C，那么，那么A C推论：推论：空集是唯一的。空集是唯一的。2024/7/2610计计算算机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念幂集：幂集：设设A为一个集合，为一个集合，A
7、的幂集的幂集(A)是是A的所有子集的集合，的所有子集的集合，即即：(A)B|B A例：例：若若A，则则(A)=；若若Aa，则则(A)=,a；若若Aa,b，则则(A)=,a,b,a,b；若若Aa,b,c，则则(A)=,a,b,c,a,b,a,c,b,c,a,b,c;2024/7/2611计计算算机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念定理：若定理：若|A|n,则则|(A)|2n；证明（方法证明（方法1）对每个对每个i(0in)，A的恰有的恰有i个元素的子集的个数即是从个元素的子集的个数即是从A的的n个元素中选取个元素中选取i个元素的组合数个元素的组合数.2024/7/
8、2612计计算算机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念证明（方法证明（方法2）：）：设设Aa1,a2,，an，则：，则：一方面：对于一方面：对于A的任何子集的任何子集S可以表示为一个可以表示为一个n位二进制数位二进制数b1b2bn，其中，其中2024/7/2613计计算算机机科科学学学学院院 刘刘 芳芳6.1 集合的基本概念集合的基本概念另一方面：另一方面：对于任意一个对于任意一个n位二进制数位二进制数b1b2bn，也可以唯，也可以唯一地对应一个一地对应一个A的子集的子集S因此，因此，n个元素的集合的子集个数与个元素的集合的子集个数与n位二进位二进制的个数相同，即
9、制的个数相同，即|(A)|2n成立。成立。2024/7/2614计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的运算及恒等式集合的运算及恒等式1.交集的定交集的定义义ABx|xAxB性性质质AAAAAEAABBA（AB）CA（BC）BA可以看出可以看出2024/7/2615计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的运算及恒等式集合的运算及恒等式例：证明例：证明 (AB) C A(B C)2024/7/2616计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式证：对任意的元素证：对任意的元素xx(AB ) C x(AB) xC (x A
10、 xB)xC x A (xB xC ) xA x(BC ) xA(B C)由由x的任意性的任意性，知知 (AB) C A(B C)成立成立。2024/7/2617计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式集合的交运算的推广集合的交运算的推广A1A2Anx|xA1xA2xAn记做：记做：也可推广到无穷多个集合也可推广到无穷多个集合：2024/7/2618计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式集合广义交集合广义交定义定义6.11设：设：A=A1,A2,An2024/7/2619计计算算机机科科学
11、学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式2.并集的定义并集的定义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可以看出可以看出2024/7/2620计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式证明：证明：A (B C) (A B) (A C)证明：对于任意的证明：对于任意的x，若，若由由x的任意性知的任意性知:A(B C) (A B ) (AC)成立成立2024/7/26
12、21计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式集合的并运算的推广集合的并运算的推广A1A2Anx|xA1xA2xAn记做：记做：也可推广到无穷多个集合：也可推广到无穷多个集合：2024/7/2622计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式集合广义并集合广义并定义定义6.10设：设：A=A1,A2,An2024/7/2623计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式3.集合的相对补（差集）集合的相对补（差集）ABx|xAx B性质性质AAAAAB
13、AAB2024/7/2624计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式例例1：设设A1，2，4 ，5,B3，4，6计算：计算： ABBAAA AA2024/7/2625计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式例例2：设集合设集合A1,2,1,2,试计算：试计算： A1,2; A; A;1,2A;A;A答答： (1)1,2,(2)A;(3)1,2,1,2；(4);(5);(6)2024/7/2626计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式思考：
14、思考：下列等式可能成立吗？若可能，刻画等式出现的全部下列等式可能成立吗？若可能，刻画等式出现的全部条件。条件。ABAABBABBAAB 答：答：AB ； AB ；AB；A B2024/7/2627计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式4.集合的绝对补的定义：集合的绝对补的定义：x|xEx Ax|x AA2024/7/2628计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式5.对称差的定义：对称差的定义：A B（AB）（BA）BAAB2024/7/2629计计算算机机科科学学学学院院 刘刘 芳芳6.
15、2 集合的基本运算及恒等式集合的基本运算及恒等式例例设设A1，2，5，B2，4，计算计算A B。解：解：AB1，5BA4A B1,4,52024/7/2630计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的基本运算及恒等式集合的基本运算及恒等式集合的恒等式（集合的算律）（集合的恒等式（集合的算律）（P92）集合运算性质的重要结果（集合运算性质的重要结果（P94）证明方法证明方法（1）证明）证明P Q方法方法1：对任意的对任意的x，xPxQ方法方法2：找到一个集合找到一个集合T，满足：满足：P T，T Q则则P Q2024/7/2631计计算算机机科科学学学学院院 刘刘 芳芳6.2 集合的
16、基本运算及恒等式集合的基本运算及恒等式集合的证明方法集合的证明方法2.证明证明 PQ方法方法1：对任意的对任意的x，xPxQ方法方法2：反证法：反证法方法方法3：集合恒等式代入法：集合恒等式代入法2024/7/2632计计算算机机科科学学学学院院 刘刘 芳芳6.3 有穷集的计数有穷集的计数1.设设A，B为任意两个有穷集合，则为任意两个有穷集合，则|AB|A|B|AB| BA2024/7/2633计计算算机机科科学学学学院院 刘刘 芳芳6.3 有穷集的计数有穷集的计数例例1：有有100名程序员，其中名程序员，其中47名熟悉名熟悉C#语言，语言，35名熟悉名熟悉JAVA语言，语言，23名熟悉两种语
17、言。名熟悉两种语言。问：有多少人对这两种语言都不熟悉？问：有多少人对这两种语言都不熟悉？解：解：设设A、B分别表示熟悉分别表示熟悉C#和和JAVA语言的程序员的集合，语言的程序员的集合，则则法法1：根据容斥原理求解：根据容斥原理求解法法2：使用文氏图求解：使用文氏图求解2024/7/2634计计算算机机科科学学学学院院 刘刘 芳芳6.3 有穷集的计数有穷集的计数例例2：设设|A|=3，|P(B)|=64，|P(AB)|=256，求求|B|，|AB|，|AB|，|A B|。例例3：求在求在1到到1000000之间（含之间（含1和和1000000在内）有在内）有多少个整数既不是完全平方数，也不是完
18、全立多少个整数既不是完全平方数，也不是完全立方数方数?2024/7/2635计计算算机机科科学学学学院院 刘刘 芳芳6.3 有穷集的计数有穷集的计数2.对于三个集合，容易看出：对于三个集合，容易看出：|AB C| |A|B| |C| (|AB| |AC| |BC|） |AB C|CBA2024/7/2636计计算算机机科科学学学学院院 刘刘 芳芳6.3 有穷集的计数有穷集的计数例例6.5（P89）习题六习题六2021（P99）22（P99）2024/7/2637计计算算机机科科学学学学院院 刘刘 芳芳6.3 有穷集的计数有穷集的计数一般地，对于一般地，对于n个有限集合个有限集合A1,An,有如
19、下结论：有如下结论：容斥原理容斥原理所谓所谓容斥容斥( (inclusion-exclusion) )是指我们计算某类事物的数目是指我们计算某类事物的数目时时, , 要要排斥排斥那些那些不应包含不应包含在这在这个计数中的数目个计数中的数目; ; 但同时要但同时要包包容容那些那些被错误排斥被错误排斥了的数目了的数目, , 以此补偿。以此补偿。2024/7/2638计计算算机机科科学学学学院院 刘刘 芳芳6.3 有穷集的计数有穷集的计数例例6.4（P88）设：设：E为全集，为全集，A、B、C、D分别表示会英、法、德、日的分别表示会英、法、德、日的人的集合，由题设知：人的集合，由题设知：|E|=24
20、|A|=13,|B|=9，|C|=10,|D|=5|AD|=2,|BD|=|CD|=0|AB|=|AC|=|BC|=4设同时会英、法、德三种语言的有设同时会英、法、德三种语言的有x人，只会英、法、德语人，只会英、法、德语的中一门语言的分别有的中一门语言的分别有y1、y2、y3人，于是可以根据题意画人，于是可以根据题意画出文氏图出文氏图2024/7/2639计计算算机机科科学学学学院院 刘刘 芳芳6.3 有穷集的计数有穷集的计数列方程求解列方程求解解得：x1，y14，y22，y33。 2024/7/2640计计算算机机科科学学学学院院 刘刘 芳芳6.3 集合中元素的计数集合中元素的计数例：例：求
21、求1到到250之间能被之间能被2，3，5和和7中任何一个整除的整数中任何一个整除的整数个数。个数。解：设解：设A1表示表示1到到250之间能被之间能被2整除的整数集合，整除的整数集合，A2表示表示1到到250之间能被之间能被3整除的整数集合，整除的整数集合，A3表示表示1到到250之间能被之间能被5整除的整数集合，整除的整数集合，A4表示表示1到到250之间能被之间能被7整除的整数集合。整除的整数集合。(|x|表示小于或等于表示小于或等于x的最大整数的最大整数)2024/7/2641计计算算机机科科学学学学院院 刘刘 芳芳6.3 集合中元素的计数集合中元素的计数则：则：于是有于是有2024/7/2642计计算算机机科科学学学学院院 刘刘 芳芳本章小结本章小结集合的基本概念集合的基本概念集合的表示方法、元素的性质集合的表示方法、元素的性质集合之间的关系集合之间的关系集合的基本运算及集合恒等式集合的基本运算及集合恒等式并、交、差、补、对称差并、交、差、补、对称差两类问题的证明方法两类问题的证明方法有穷集合的计数问题及应用有穷集合的计数问题及应用容斥原理容斥原理文氏图文氏图2024/7/2643
