离散数学---集合代数

1、第二部分 集合论引言第6章 集合代数第7章 二元关系第8章 函数2022/7/211集合论集合论：研究集合的数学理论起源George Cantor (1845-1918，德国) 重要性它是数学的一个基本分支，在数学中占据着一个极其独特的地位，其基本概念已渗透到数学的所有领域。集合论广泛地应用于计算机科学领域如：形式语言、自动机理论、人工智能、数据库等。如果把现代数学比作一座无比辉煌的大厦，那么可以说集合论正是构成这座大厦的基石。2022/7/212第6章 集合代数6.1 集合的基本概念6.2 集合的基本运算及恒等式6.3 集合中元素的计数本章小结2022/7/2136.1 集合的基本概念集合集

2、合是数学中的一个基本概念，一般地，由一些可区分的对象组成的一个整体，称为集合。通常用大写字母A、B、表示集合。集合的元素集合中的对象称为集合的元素。通常用小写字母a、b、c、表示集合的元素。注：集合由它的元素所决定。2022/7/2146.1 集合的基本概念集合表示方法列举法A1，2，3，4N0，1，2，3，谓词表示法: 用谓词描述出集合元素的属性（特征）形如： Sx|P(x)如：Bx|xRx210 树形图表示法如：A a, b,c , d, d 2022/7/2156.1 集合的基本概念集合的元素的性质:确定性设a为任意元素，S为任意集合，则aS或a S，二者必居其一，且只居其一。集合中的元

3、素是互异的;集合中的元素无次序和大小之分;抽象性2022/7/2166.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,且b2022/7/2176.1 集合的基本概念集合的基数集合A中的不同元素个数称为集合A的基数，记做|A|。集合的分类：有限集合无限集合空集注意： 和的区别全集E2022/7/2186.1 集合的基本概念集合间的关系的定义设A、B是任意两个集合A B x(x A x B) AB A B B

4、A x(x A x B)AB x(x A x B ） x(x B x A ）2022/7/2196.1 集合的基本概念显然：(1) A (2) A A (3) 若A B BC ，那么A C 推论：空集是唯一的。2022/7/21106.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/7/21116.1 集合的基本概念定理：若|A|n, 则|(A)|2n；证明（方法1）对

5、每个i(0in)，A的恰有i个元素的子集的个数即是从A的n个元素中选取i个元素的组合数.2022/7/21126.1 集合的基本概念证明（方法2）： 设Aa1,a2,，an，则：一方面：对于A的任何子集S可以表示为一个n位二进制数b1b2bn，其中2022/7/21136.1 集合的基本概念另一方面：对于任意一个n位二进制数b1b2bn，也可以唯一地对应一个A的子集S因此，n个元素的集合的子集个数与n位二进制的个数相同，即|(A)|2n成立。2022/7/21146.2 集合的运算及恒等式1.交集的定义ABx|xAxB性质AA AAAEAAB BA（AB ） C A（B C）BA可以看出202

6、2/7/21156.2 集合的运算及恒等式例：证明 (AB) C A(B C)2022/7/21166.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)成立。2022/7/21176.2 集合的基本运算及恒等式集合的交运算的推广A1A2Anx|xA1xA2xAn记做：也可推广到无穷多个集合：2022/7/21186.2 集合的基本运算及恒等式集合广义交定义 6.11设：A=A1,A2,An2022/7/21196.2 集合的基本运算及

7、恒等式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可以看出2022/7/21206.2 集合的基本运算及恒等式证明：A (B C) (A B) (A C)证明：对于任意的x，若由x的任意性知:A (B C) (A B ) (AC)成立2022/7/21216.2 集合的基本运算及恒等式集合的并运算的推广A1A2Anx|xA1xA2xAn记做：也可推广到无穷多个集合：2022/7/21226.2 集合的基本运算及恒等式集合广义并定义 6.10

8、设：A=A1,A2,An2022/7/21236.2 集合的基本运算及恒等式3.集合的相对补（差集）ABx|xAx B性质A A A AA BAAB2022/7/21246.2 集合的基本运算及恒等式例1：设 A1，2，4 ，5, B3，4，6计算： AB BA AA AA2022/7/21256.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 ； (4) ; (5) ; (6) 2022/7/21266.2 集合的基本运算及恒等式

9、思考：下列等式可能成立吗？若可能，刻画等式出现的全部条件。ABAABBABBAAB 答：AB ； AB ；AB；A B2022/7/21276.2 集合的基本运算及恒等式4.集合的绝对补的定义： x|xEx A x|x AA2022/7/21286.2 集合的基本运算及恒等式5.对称差的定义：AB（AB）（BA）BAAB2022/7/21296.2 集合的基本运算及恒等式例设A1，2，5，B2，4，计算AB。解：AB 1，5 BA 4 AB1,4,52022/7/21306.2 集合的基本运算及恒等式集合的恒等式（集合的算律）（P92）集合运算性质的重要结果（P94）证明方法（1）证明P Q方

10、法1： 对任意的x，x P x Q方法2： 找到一个集合T，满足：P T，T Q 则 P Q2022/7/21316.2 集合的基本运算及恒等式集合的证明方法2.证明PQ方法1： 对任意的x，x P x Q方法2：反证法方法3：集合恒等式代入法2022/7/21326.3 有穷集的计数1. 设A，B为任意两个有穷集合，则|AB|A | |B|AB| BA2022/7/21336.3 有穷集的计数例1：有100名程序员，其中47名熟悉C#语言，35名熟悉JAVA语言，23名熟悉两种语言。问：有多少人对这两种语言都不熟悉？解：设A、B分别表示熟悉C#和JAVA语言的程序员的集合，则法1：根据容斥原

11、理求解法2：使用文氏图求解2022/7/21346.3 有穷集的计数例2：设|A|=3，|P(B)|=64， |P(AB)|=256，求|B|，|AB|，|AB|， |AB|。例3：求在1到1000 000之间（含1和1000 000在内）有多少个整数既不是完全平方数，也不是完全立方数?2022/7/21356.3 有穷集的计数2.对于三个集合，容易看出：|AB C| |A|B| |C| (|AB| |AC| |BC|） |AB C|CBA2022/7/21366.3 有穷集的计数例6.5（P89）习题六2021 （P99）22 （P99）2022/7/21376.3 有穷集的计数一般地，对于

12、n个有限集合A1,An,有如下结论：容斥原理所谓容斥(inclusion-exclusion)是指我们计算某类事物的数目时, 要排斥那些不应包含在这个计数中的数目; 但同时要包容那些被错误排斥了的数目, 以此补偿。2022/7/21386.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/7/21396.3 有穷集的计数列方程求解解得：x1，y14，y22，y33。 2022/7/21406.3 集合中元素的计数例：求1到250之间能被2，3，5和7中任何一个整除的整数个数。解：设A1表示1到250之间能被2整除的整数集合，A2表示1到250之间能被3整除的整数集合