《离散数学-集合及其运算》由会员分享，可在线阅读，更多相关《离散数学-集合及其运算（46页珍藏版）》请在金锄头文库上搜索。
1、离散数学（一）离散数学（一） 上海上海大学大学谢谢 江江 离散数学（第3版） 屈婉玲 耿素云 张立昂 编著 清华大学出版社出版 第第1章章 数学语言与证明方法数学语言与证明方法 3 第第1章章 数学语言与证明方法数学语言与证明方法 1.1 常用的数学符号常用的数学符号 1.2 集合及其运算集合及其运算 1.3 证明方法概述证明方法概述 4 1.2 集合及其运算集合及其运算 集合及其表示法集合及其表示法 包含包含(子集子集)与相等与相等 空集与全集空集与全集 集合运算集合运算( , , - , , ) 基本集合恒等式基本集合恒等式 包含与相等的证明方法包含与相等的证明方法 5 集合的概念集合的概
2、念 朴素集合论朴素集合论(康托康托, G.Cantor), 集合集合是数学中最基本的概念是数学中最基本的概念,没有严格的定义没有严格的定义 满足某条性质的个体放在一起组成集合满足某条性质的个体放在一起组成集合 元素元素:集合中的个体集合中的个体 隐含的矛盾：隐含的矛盾：罗素罗素(Russell)悖论悖论 1901年提出；年提出； 第三次数学危机第三次数学危机 公理集合论体系公理集合论体系：属于数理逻辑范畴. 透过建立一阶逻辑的严谨重整，使用明确的公理列表，透过建立一阶逻辑的严谨重整，使用明确的公理列表， 以解决朴素集合论中的悖论以解决朴素集合论中的悖论 1.2.1 集合及其表示法集合及其表示法
3、 6 集合的集合的记法记法 集合：集合： 常用大写英文字母常用大写英文字母A,B,C等表示等表示 元素：元素：小写英文字母小写英文字母 x, y, z, 元素与集合的关系：元素与集合的关系： x A(x属于属于A): x是是A的元素的元素 x A(x不不属于属于A): x不不是是A的元素的元素 无穷集无穷集: 元素个数无限的集合元素个数无限的集合 有穷集有穷集(有限集有限集):元素个数有限的集合元素个数有限的集合. |A|:A中元素个数中元素个数 k元集元集:k个元素的集合个元素的集合, k 0 1.2.1 集合及其表示法集合及其表示法 7 集合的表示法集合的表示法 列举法：列举法：列出集合中
4、的全体元素列出集合中的全体元素 ， 如如 A= a, b, c, d , N=0,1,2, 描述法（元素性质法）描述法（元素性质法） x | P(x) 具有性质具有性质P 的的x的全体的全体 如如N= x | x是自然数是自然数 说明说明: (1) 集合中的元素各不相同集合中的元素各不相同. 如如, 1,2,3=1,1,2,3 (2) 集合中的元素没有次序集合中的元素没有次序. 如如, 1,2,3=3,1,2=1,3,1,2,2 (3) 有时两种方法都适用有时两种方法都适用, 可根据需要选用可根据需要选用. 1.2.1 集合及其表示法集合及其表示法 8 常用集合的表示法常用集合的表示法 自然数
5、集自然数集N, N = x | x是自然数 = 0，1，2， 整数集整数集Z, Z = x | x是整数 = , 2, 1, 0, 1, 2, 正整数集正整数集Z+, Z+= x | xZ x 0 = 1, 2, 3, 有理数集有理数集Q, Q = x | x是有理数 非零有理数集非零有理数集Q*, Q*= x | xQ x 0 实数集实数集R, R = x | x是实数 非零实数集非零实数集R*, R*= x | xR x 0 复数集复数集C, C = x | x是复数 区间区间a,b, a, b = x | x R a x b 区间区间(a,b), (a, b) = x | x R a A
6、=B 33 例例3(续续) (2) A (B C)=(A B) (A C) (分配分配律律) 证证 xx A (B C) x A或或(x B且且 x C) (x A或或x B)且且(x A或或x C) x (A B) (A C) 得证得证 A (B C) (A B) (A C). 类似可证类似可证 (A B) (A C) A (B C). (3) A E=E (E为全集，为全集，零律零律) 证证 根据并的定义根据并的定义, 有有E A E. 根据全集的定义根据全集的定义, 又有又有A E E. 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应用 34 例例3(续续) (4) A E=A
7、(E为全集，为全集，同一同一律律) 证证 根据交的定义根据交的定义, 有有A E A. 又又, x x A, 根据全集根据全集E的定义的定义, x E, 从而从而 x A且且x E, x A E 得证得证 A A E. 所以所以 A E=A 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应用 35 例例3(续续) (5) A A= （矛盾律）（矛盾律） 证证 x,x AA （交运算的定义）（交运算的定义） （绝对补的定义）（绝对补的定义） F （逻辑演算的矛盾律）（逻辑演算的矛盾律） （ 是假命题）是假命题） 由上可知，由上可知， = 1.2.4 基本集合恒等式及其应用基本集合恒等式及其
8、应用 36 例例3(续续) (6) A-B=A B （补交转换律）（补交转换律） 证证 x,x A-B （相对补的定义）（相对补的定义） （绝对补的定义）（绝对补的定义） (A(A ) （ 交运算的定义）交运算的定义） 由上可知，由上可知， = 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应用 补补交转换律是非常重要的运算律交转换律是非常重要的运算律. . 因为交运算有交因为交运算有交 换律、结合律、分配律等，而补运算没有这些运算律，换律、结合律、分配律等，而补运算没有这些运算律， 一旦使用了补交转换律，就将补运算转换成交运算，就一旦使用了补交转换律，就将补运算转换成交运算，就 可以用
9、上这些运算律了可以用上这些运算律了. . 37 实例实例 例例4 证明证明 A (A B)=A （吸收律）吸收律） 证证 方法一：用定义证明方法一：用定义证明 , ( ( ) （并、交运算的定义）（并、交运算的定义） （逻辑演算的吸收律）（逻辑演算的吸收律） 由上可知，由上可知，A (A B)= A 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应用 38 实例实例 例例4（续）（续） 证明证明 A (A B)=A （吸收律）吸收律） 证证 方法二：利用例方法二：利用例3证明的证明的4条等式证明条等式证明 A (A B) = (A E) (A B) (同一律同一律) = A (E B)
10、(分配律分配律) = A (B E) (交换律交换律) = A E (零律零律) = A (同一律同一律) 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应用 39 实例实例 例例5 用方法二证明用方法二证明德摩根律相对形式中的一个公式：德摩根律相对形式中的一个公式： = ( ) ( ) 证证 = ( )（补交转换律）（补交转换律） = ( )（德摩根律的绝对形式）（德摩根律的绝对形式） = ( ) ( ) （幂等律）（幂等律） = ( ) ( ) （交换律，结合律）（交换律，结合律） = ( ) ( )（补交转换律）（补交转换律） 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应
11、用 40 实例实例 例例6 证明证明 (A-B)-C=(A-C)-(B-C) 证证(A-C)-(B-C) = (A C) (B C) (补交转换律补交转换律) = (A C) (B C) (德摩根律德摩根律) = (A C) (B C) (双重否定律双重否定律) = (A C B) (A C C) (分配律分配律) = (A C B) (A ) (矛盾律矛盾律) = A C B (零律零律,同一律同一律) = (A B) C (交换律交换律,结合律结合律) = (A B) C (补交转换律补交转换律) 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应用 41 实例实例 例例7 证明证明
12、(A B) (A C)= (B C) A 证证(A B) (A C) =(A B) - (A C) (A C) - (A B) =(A B) A C) (A C) A B) = (B A C) (C A B) =(B C) (C B) A =(B-C) (C-B) A = (B C) - A 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应用 42 实例实例 例例8 设设A,B为任意集合为任意集合, 证明证明: 若若A B, 则则P(A) P(B) 证证 x x P(A) x A x B(已知已知A B) x P(B) 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应用 43 实例
13、实例 例例9 证明证明 A B=(A B)-(A B) 证证A B=(A-B)(B B- -A A) ) （定义）（定义） = =(A B) (B A) （补交转换律）（补交转换律） =(A B) B) (A B) A) ( 对对 分配律分配律) =(A B) (B B) (A A) (B A) ( 对对 分配律分配律) =(A B) (A B) （同一律）（同一律） =(A B) (A B) （德摩根律）（德摩根律） =(A B)-(A B) （补交转换律）（补交转换律） 1.2.4 基本集合恒等式及其应用基本集合恒等式及其应用 44 1.3 证明方法概述（自学）证明方法概述（自学） 直接证明法直接证明法 间接证明法间
