离散数学-耿素云(第5版)课件

1、离散数学-耿素云(第5版)1 集合论集合论离散数学-耿素云(第5版)2集合论部分集合论部分n第第3章章 集合的基本概念和运算集合的基本概念和运算n第第4章章 二元关系和函数二元关系和函数离散数学-耿素云(第5版)3第第3章章 集合的基本概念和运算集合的基本概念和运算n3.1 集合的基本概念集合的基本概念n3.2 集合的基本运算集合的基本运算n3.3 集合中元素的计数集合中元素的计数离散数学-耿素云(第5版)43.1 集合的基本概念集合的基本概念n 集合的定义与表示集合的定义与表示n 集合与元素集合与元素n 集合之间的关系集合之间的关系n 空集空集n 全集全集n 幂集幂集离散数学-耿素云(第5版

2、)5集合定义与表示集合定义与表示集合集合 没有精确的数学定义没有精确的数学定义 理解：一些离散个体组成的全体理解：一些离散个体组成的全体 组成集合的个体称为它的元素或成员组成集合的个体称为它的元素或成员 集合的表示集合的表示 列元素法列元素法 A= a, b, c, d 谓词表示法谓词表示法 B= x | P(x) B 由使得由使得 P(x) 为真的为真的 x 构成构成 常用数集常用数集 N, Z, Q, R, C 分别表示自然数、整数、有理数、分别表示自然数、整数、有理数、 实数和复数集合，注意实数和复数集合，注意 0 是自然数是自然数. 离散数学-耿素云(第5版)6集合与元素集合与元素元素

3、与集合的关系：隶属关系元素与集合的关系：隶属关系 属于属于 ，不属于不属于 实例实例 A= x | x R x2-1=0 , A=-1,1 1 A, 2 A注意：对于任何集合注意：对于任何集合 A 和元素和元素 x (可以是集合可以是集合)， x A和和 x A 两者成立其一，且仅成立其一两者成立其一，且仅成立其一. 离散数学-耿素云(第5版)7隶属关系的层次结构隶属关系的层次结构例例 3.1A= a, b,c, d, d b,c Ab Ad Ad Ad A 离散数学-耿素云(第5版)8集合之间的关系集合之间的关系 包含（子集）包含（子集） A B x (x A x B) 不包含不包含 A B

4、 x (x A x B) 相等相等 A = B A B B A 不相等不相等 A B 真包含真包含 A B A B A B 不真包含不真包含 A B 思考：思考： 和和 的定义的定义 注意注意 和和 是不同层次的问题是不同层次的问题离散数学-耿素云(第5版)9空集与全集空集与全集空集空集 不含任何元素的集合不含任何元素的集合实例实例 x | x2+1=0 x R 就是空集就是空集定理定理 空集是任何集合的子集空集是任何集合的子集 A x (xx A) T 推论推论 空集是惟一的空集是惟一的.证证 假设存在假设存在1和和2，则，则12 且且12，因此，因此1=2全集全集 E 相对性相对性 在给定

5、问题中，全集包含任何集合，即在给定问题中，全集包含任何集合，即 A (A E )离散数学-耿素云(第5版)10幂集幂集定义定义 P(A) = x | x A 实例实例 P() = ， P() = , P(1,2,3)=,1,2,3,1,2,3计数计数 如果如果 |A| = n，则，则 |P(A)| = 2n 离散数学-耿素云(第5版)113.2 集合的基本运算集合的基本运算n集合基本运算的定义集合基本运算的定义 n文氏图（文氏图（John Venn）n例题例题n集合运算的算律集合运算的算律n集合包含或恒等式的证明集合包含或恒等式的证明离散数学-耿素云(第5版)12集合基本运算的定义集合基本运算

6、的定义并并 A B = x | x A x B 交交 A B = x | x A x B 相对补相对补 A B = x | x A x B 对称差对称差 A B = (A B) (B A) = (A B) (A B) 绝对补绝对补 A = E A 离散数学-耿素云(第5版)13文氏图表示文氏图表示离散数学-耿素云(第5版)14关于运算的说明关于运算的说明n运算顺序：运算顺序： 和幂集优先，其他由括号确定和幂集优先，其他由括号确定n并和交运算可以推广到有穷个集合上，即并和交运算可以推广到有穷个集合上，即 A1 A2 An= x | x A1 x A2 x An A1 A2 An= x | x A

7、1 x A2 x Ann某些重要结果某些重要结果 A B A A B A B=（后面证明）（后面证明） A B= A B=A离散数学-耿素云(第5版)15只有一、二年级的学生才爱好体育运动只有一、二年级的学生才爱好体育运动 F:一年级大学生的集合一年级大学生的集合 S：二年级大学生的集合：二年级大学生的集合 R：计算机系学生的集合：计算机系学生的集合 M：数学系学生的集合：数学系学生的集合 T：选修离散数学的学生的集合：选修离散数学的学生的集合 L：爱好文学学生的集合：爱好文学学生的集合 P：爱好体育运动学生的集合：爱好体育运动学生的集合T (M R) SR S T(M F) T=M L PP

8、 F SS (M R) P除去数学和计算机系二年级学生外都不除去数学和计算机系二年级学生外都不选修离散数学选修离散数学例例1 1 所有计算机系二年级学生都选修离散数学所有计算机系二年级学生都选修离散数学数学系一年级的学生都没有选修离散数学数学系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运动数学系学生或爱好文学或爱好体育运动离散数学-耿素云(第5版)16例例2 2 分别对条件分别对条件(1)到到(5)，确定，确定 X 集合与下述那些集合相等。集合与下述那些集合相等。 S1 = 1, 2, , 8, 9 , S2= 2, 4, 6, 8 , S3= 1, 3, 5, 7, 9 ,

9、 S4 = 3, 4, 5 , S5= 3, 5 若若 X S3=, 则则 X 若若 X S4, X S2=, 则则 X 若若 X S1，X S3, 则则 X 若若 X S3=, 则则 X 若若 X S3，X S1, 则则 X= S2= S5= S1, S2, S4= S3, S5与与 S1, . , S5 都不等都不等离散数学-耿素云(第5版)17 交换交换A B=B AA B=B AA B=B A结合结合(A B) C=A (B C)(A B) C=A (B C)(A B) C=A (B C)幂等幂等A A=AA A=A 与与 与与 分配分配A (B C)=(A B) (A C)A (B

10、C)=(A B) (A C)A (B C)=(A B) (A C)吸收吸收A (A B)=AA (A B)=A集合运算的算律集合运算的算律吸收律的前提：吸收律的前提： 、 可交换可交换离散数学-耿素云(第5版)18集合运算的算律（续）集合运算的算律（续） D.M 律律A (B C)=(A B) (A C)A (B C)=(A B) (A C) (B C)= BC (B C)= BC双重否定双重否定A=AE补元律补元律AA=AA=E零律零律A=A E=E同一律同一律A=AA E=A否定否定=E E=离散数学-耿素云(第5版)19集合包含或相等的证明方法集合包含或相等的证明方法n证明证明 X Y命

11、题演算法命题演算法包含传递法包含传递法等价条件法等价条件法反证法反证法并交运算法并交运算法n证明证明 X=Y命题演算法命题演算法等式代入法等式代入法反证法反证法运算法运算法以上的以上的 X, Y 代表集合公式代表集合公式离散数学-耿素云(第5版)20任取任取 x ， x X x Y 命题演算法命题演算法证证 X Y 例例3 证明证明A B P(A) P(B) 任取任取x x P(A) x A x B x P(B) 任取任取x x A x A x P(A) x P(B) x B x B 离散数学-耿素云(第5版)21包含传递法包含传递法证证 X Y找到集合找到集合T 满足满足 X T 且且 T

12、Y，从而有，从而有X Y例例4 A B A B证证 A B A A A B 所以所以 A B A B 离散数学-耿素云(第5版)22利用包含的等价条件利用包含的等价条件证证 X Y A-BABABBABA例例5 A C B C A B C 证证 A C A C=C B C B C=C (A B) C=A (B C)=A C=C (A B) C=C A B C 命题得证命题得证离散数学-耿素云(第5版)23反证法反证法证证 X Y欲证欲证X Y, 假设命题不成立，必存在假设命题不成立，必存在 x 使得使得 x X 且且 x Y. 然后推出矛盾然后推出矛盾. 例例6 证明证明 A C B C A

13、B C证证 假设假设 A B C 不成立，不成立， 则则 x (x A B x C) 因此因此 x A 或或 x B，且，且 x C 若若 x A, 则与则与 A C 矛盾；矛盾； 若若 x B, 则与则与 B C 矛盾矛盾. 离散数学-耿素云(第5版)24利用已知包含式并交运算利用已知包含式并交运算例例7 证明证明 A C B C A C B C A B证证 A C B C， A C B C 上式两边求并，得上式两边求并，得 (A C) (A C) (B C) (B C) (A C) (A C) (B C) (B C) A (C C) B (C C) A E B E A B由已知包含式通过运

14、算产生新的包含式由已知包含式通过运算产生新的包含式 X Y X Z Y Z, X Z Y Z 离散数学-耿素云(第5版)25 例例8 证明证明 A (A B)=A （吸收律）（吸收律） 证证 任取任取x, x A (A B) x A x A B x A (x A x B) x A 命题演算法证明命题演算法证明X=Y任取任取 x ， x X x Y x Y x X 或者或者 x X x Y 离散数学-耿素云(第5版)26等式替换等式替换证明证明X=Y例例9 证明证明A (A B)=A （吸收律）（吸收律）证证 (假设交换律、分配律、同一律、零律成立假设交换律、分配律、同一律、零律成立) A (A

15、 B) =(A E) (A B) 同一律同一律 =A (E B) 分配律分配律 =A (B E) 交换律交换律 =A E 零律零律 =A 同一律同一律不断进行代入化简，最终得到两边相等不断进行代入化简，最终得到两边相等离散数学-耿素云(第5版)27反证法反证法证明证明X=Y例例10 证明以下等价条件证明以下等价条件 A B A B=B A B=A A B= (1) (2) (3) (4) 证明顺序：证明顺序： (1) (2), (2) (3), (3) (4), (4) (1) 假设假设 X=Y 不成立，则存在不成立，则存在 x 使得使得 x X且且x Y，或者或者存在存在 x 使得使得 x

16、Y且且x X，然后推出矛盾，然后推出矛盾. 离散数学-耿素云(第5版)28(1) (2)显然显然B A B，下面证明，下面证明A B B. 任取任取x， x A B x A x B x B x B x B因此有因此有A B B. 综合上述（综合上述（2）得证）得证. (2) (3) A=A (A B) A=A B （将（将A B用用B代入代入) 离散数学-耿素云(第5版)29(3) (4)假设假设A B, 即即 x A B，那么，那么x A且且x B. 而而 x B x A B. 从而与从而与A B=A矛盾矛盾.(4) (1) 假设假设A B不成立，那么不成立，那么 x (x A x B) x

17、 A B A B与条件（与条件（4）矛盾）矛盾. 离散数学-耿素云(第5版)30集合运算法集合运算法证明证明X=Y例例11 证明证明A C=B C A C=B C A=B证证 由由 A C=B C 和和 A C=B C 得到得到 (A C)-(A C)=(B C)-(B C) 从而有从而有 A C=B C 因此因此 A C=B C (A C) C =(B C) C A (C C) =B (C C) A=B A=B由已知等式通过运算产生新的等式由已知等式通过运算产生新的等式 X=Y X Z=Y Z, X Z=Y Z，X-Z=Y-Z离散数学-耿素云(第5版)31n集合的基数与有穷集合集合的基数与有

18、穷集合n包含排斥原理包含排斥原理n有穷集的计数有穷集的计数3.3 集合中元素的计数集合中元素的计数离散数学-耿素云(第5版)32集合集合 A 的的基数基数：集合：集合A中的元素数，记作中的元素数，记作 cardA有穷集有穷集 A： cardA=|A|=n，n为自然数为自然数.有穷集的实例：有穷集的实例： A= a,b,c, cardA=|A|=3； B= x | x2+1=0, x R, cardB=|B|=0 无穷集的实例：无穷集的实例： N, Z, Q, R, C 等等 集合的基数与有穷集合集合的基数与有穷集合离散数学-耿素云(第5版)33包含排斥原理包含排斥原理定理定理 设设 S 为有穷

19、集，为有穷集，P1, P2, , Pm 是是 m 种性质，种性质，Ai 是是 S 中具有性质中具有性质 Pi 的元素构成的子集，的元素构成的子集，i=1, 2, , m.则则 S 中不具有性质中不具有性质 P1, P2, , Pm 的元素数为的元素数为|.|)1(.|.|2111121mmmkjikjimimjijiimAAAAAAAAASAAA 离散数学-耿素云(第5版)34证明证明证证 设设 x不具有性质不具有性质 P1, P2, , Pm , x Ai , i = 1, 2, , m x Ai Aj , 1 i j m x A1 A2 Am , x 对右边计数贡献为对右边计数贡献为 1

20、0 + 0 0 + + ( 1)m 0 = 1 证明要点：任何元素证明要点：任何元素 x，如果不具有任何性质，如果不具有任何性质，则对等式右边计数贡献为，否则为则对等式右边计数贡献为，否则为离散数学-耿素云(第5版)35证明（续）证明（续） miiA1| mjijiAA1|1Cn2CnmnC0)1(.1021 niinmnmnnCCCC设设 x具有具有 n 条性质，条性质，1 n m x 对对 |S| 贡献为贡献为 1 x 对对 贡献为贡献为 x 对对 贡献为贡献为 . x 对对 | A1 A2 Am| 贡献为贡献为 x 对右边计数贡献为对右边计数贡献为离散数学-耿素云(第5版)36|.|)1

21、(.|.|21111121mmmkjikjimimjijiimAAAAAAAAAAAA S S中至少具有一条性质的元素数为中至少具有一条性质的元素数为证明证明 |.|.|.|212121mmmAAASAAASAAA 将定理将定理 1 1 代入即可代入即可推论推论离散数学-耿素云(第5版)37解：解：S = x | x Z, 1 x 1000 , 如下定义如下定义 S 的的 3 个子集个子集 A, B, C： A= x | x S, 5 | x ， B= x | x S, 6 | x ， C= x | x S, 8 | x 例例1 求求1到到1000之间（包含之间（包含1和和1000在内）既不能

22、在内）既不能被被 5 和和6 整除，也不能被整除，也不能被 8 整除的数有多少个？整除的数有多少个？应用应用离散数学-耿素云(第5版)38对上述子集计数：对上述子集计数： |S|=1000, |A|= 1000/5 =200, |B|= 1000/6 =133， |C|= 1000/8 =125, |A B|= 1000/30 =33, |B C| = 1000/40 =25, |B C|= 1000/24 =41, |A B C| = 1000/120 =8, 代入公式代入公式 N = 1000 (200+133+125)+(33+25+41) 8=600例例1（续）（续）离散数学-耿素云(第5版)39文氏图法文氏图法 求求1到到1000之间（包含之间（包含1和和1000在内）既不能被在内）既不能被 5 和和6 整除，也不能被整除，也不能被 8 整除的数有多少个？整除的数