离散数学 集合初步

1、第1章 数学语言与证明方法1第1章 数学语言与证明方法1.1 逻辑符号逻辑符号1.2 集合及其运算集合及其运算1.3 证明方法概述证明方法概述21.1 逻辑符号3命题与真值命题与真值联结词联结词(, , , ,)命题公式命题公式(重言式重言式,矛盾式矛盾式,可满足式可满足式)重要等值式重要等值式重要推理规则重要推理规则个体个体,个体域与谓词个体域与谓词全称量词与存在量词全称量词与存在量词联结词真值真值:真真, 假假 或或 1, 0命题命题:具有确定真值的陈述句具有确定真值的陈述句, 通常用通常用p,q,r等表示等表示真命题真命题:真值为真的命题真值为真的命题假命题假命题:真值为假的命题真值为假

2、的命题例如例如, p:2+2=4, q:3是偶数是偶数它们都是命题它们都是命题, p是真命题是真命题, q是假命题是假命题.否定联结词否定联结词 否定式否定式 p: 非非p (p的否定的否定) ) p 为真当且仅当为真当且仅当p为假为假4联结词(续)5合取联结词合取联结词 合取式合取式p q: :p并且并且q ( (p与与q) p q为真当且仅当为真当且仅当p与与q同时为真同时为真析取联结词析取联结词 析取式析取式p q: p或或q p q为假当且仅当为假当且仅当p与与q同时为假同时为假排斥或联结词排斥或联结词排斥或排斥或p q: p并且非并且非q, 或者或者q并且非并且非p p q为真当且仅

3、当为真当且仅当p与与q中一个为真中一个为真,另一个为假另一个为假联结词(续)蕴涵联结词蕴涵联结词蕴涵式蕴涵式pq:如果如果p,则则q pq为假当且仅当为假当且仅当 p 为真为真 q 为假为假等价联结词等价联结词等价式等价式pq:p当且仅当当且仅当q pq为真当且仅当为真当且仅当p与与q同时为真或同时为假同时为真或同时为假6实例 设设p:2是偶数是偶数, q:1+1=3, 则则7p的真值为的真值为 1q的真值为的真值为p的真值为的真值为q的真值为的真值为p q的真值为的真值为p q的真值为的真值为p q的真值为的真值为 p q的真值为的真值为p q的真值为的真值为p q的真值为的真值为p q的真

4、值为的真值为p q的真值为的真值为p q的真值为的真值为p q的真值为的真值为0010110111001 p q的真值为的真值为 p q的真值为的真值为00实例(续) pq的真值为的真值为8pq的真值为的真值为pq的真值为的真值为pq的真值为的真值为0111又设又设 r:今天是星期一今天是星期一, s:明天是星期二明天是星期二, t:明天是星期三明天是星期三rs的真值为的真值为rt的真值为的真值为1不定不定命题公式命题变项命题变项:取值为取值为0或或1的变元的变元, 也用也用p,q,r等表示等表示.命题公式命题公式:用联结词和圆括号把命题和命题变项按照一定用联结词和圆括号把命题和命题变项按照一

5、定规则连接起来的符号串规则连接起来的符号串, 常用常用A,B,C等表示等表示.例如例如, A=( p q)(r p)公式的赋值公式的赋值:对公式中每一个命题变项给定一个值对公式中每一个命题变项给定一个值(0或或1).公式的公式的成真赋值成真赋值:使公式为真的赋值使公式为真的赋值.公式的公式的成假赋值成假赋值:使公式为假的赋值使公式为假的赋值.例如例如, p=1,q=1,r=1是是A的成真赋值的成真赋值, p=0,q=1,r=0是是A的成假赋值的成假赋值.9重言式,矛盾式与可满足式重言式重言式( (永真式永真式) ): :无成假赋值的命题公式无成假赋值的命题公式矛盾式矛盾式( (永假式永假式)

6、): :无成真赋值的命题公式无成真赋值的命题公式可满足式可满足式: :不是矛盾式的命题公式不是矛盾式的命题公式例如例如, , A= ( p q)(r p)是可满足式是可满足式, 但不是重言式但不是重言式, B= (p q) ( p q) (p q) ( p q)是重言式是重言式, C= p (p q) (p q)是矛盾式是矛盾式. .AB: :蕴涵式蕴涵式AB B是重言式的简记是重言式的简记. .AB:等价式等价式AB是重言式的简记，是重言式的简记， 称称A与与B等值等值，AB是是等值式等值式. . 10基本等值式双重否定律双重否定律 AA幂等律幂等律 A AA, A AA交换律交换律 A B

7、B A, A BB A结合律结合律 (A B) CA (B C) (A B) CA (B C)分配律分配律 A (B C)(A B) (A C) A (B C) (A B) (A C)德德摩根律摩根律 (A B)AB (A B)AB11基本等值式(续)吸收律吸收律 A (A B)A, A (A B)A零律零律 A 11, A 00 同一律同一律 A 0A, A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 AB A B等价等值式等价等值式 AB(AB) (BA)假言易位等值式假言易位等值式 AB B A等价否定等值式等价否定等值式 AB A B归谬论归谬论 (AB) (AB

8、) A12重要推理规则(推理定律)附加律附加律 A (A B) 化简律化简律 (A B) A假言推理假言推理 (AB) A B拒取式拒取式 (AB)B A析取三段论析取三段论 (A B)B A假言三段论假言三段论 (AB) (BC) (AC)等价三段论等价三段论 (AB) (BC) (AC)构造性二难构造性二难 (AB) (CD) (A C) (B D) 破坏性二难破坏性二难 (AB) (CD) ( BD) ( AC) 13谓词与量词个体域个体域:被研究对象的全体被研究对象的全体, 如自然数集如自然数集, 人类等人类等.个体词个体词:个体域中的一个元素个体域中的一个元素.全称量词全称量词 :

9、表示任意的表示任意的, 所有的所有的, 一切的等一切的等.存在量词存在量词 : 表示存在表示存在, 有的有的, 至少有一个等至少有一个等.谓词谓词: 表示个体词性质或相互之间关系的词表示个体词性质或相互之间关系的词例如例如, 谓词谓词P(x)表示表示x具有性质具有性质P x P(x) 表示个体域中所有的表示个体域中所有的x具有性质具有性质P x P(x) 表示个体域中存在表示个体域中存在x具有性质具有性质P141.2 集合及其运算集合及其表示法集合及其表示法包含包含(子集子集)与相等与相等空集与全集空集与全集集合运算集合运算( , , - , , )基本集合恒等式基本集合恒等式包含与相等的证明

10、方法包含与相等的证明方法15集合的概念朴素集合论朴素集合论(康托康托, G.Cantor), 罗素罗素(Russell)悖论悖论集合集合是数学中最基本的概念是数学中最基本的概念,没有严格的定义没有严格的定义 理解成理解成某些个体组成的整体某些个体组成的整体, 常用常用A,B,C等表示等表示元素元素:集合中的个体集合中的个体无穷集无穷集:元素个数无限的集合元素个数无限的集合有穷集有穷集(有限集有限集):元素个数有限的集合元素个数有限的集合. |A|:A中元素个数中元素个数k元集元集:k个元素的集合个元素的集合, k 016集合的表示法列举法列举法 如如 A= a, b, c, d , N=0,1

11、,2,描述法描述法 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) 有时两种方法都适用有时两种方法都适用, 可根据需要选用可根据需要选用.常用集合常用集合 自然数集自然数集N, 整数集整数集Z, 正整数集正整数集Z+, 有理数集有理数集Q, 非零有理数集非零有理数集Q*, 实数集实数集R, 非零实数集非零实数集R*, 复数集复数集C, 区间区间a,b,(a,b)等等17包含与相等包

12、含包含(子集子集) A B x (x A x B)不包含不包含 A B x (x A x B) 相等相等 A = B A B B A不相等不相等 A B A B B A真包含真包含(真子集真子集) A B A B A B 例如例如, A=1,2,3, B= x | x R |x| 1 , C= x | x R x2=1 , D=-1,1, C B, C B, C A, A B, B A, C = D性质性质 (1) A A (2) A B B C A C18空集与全集空集空集: 不含任何元素的集合不含任何元素的集合例如例如, x | x20 x R=定理定理1.1 空集是任何集合的子集空集是任

13、何集合的子集证证 用归谬法用归谬法. 假设不然假设不然, 则存在集合则存在集合A, 使得使得 A, 即存在即存在x, x 且且x A, 矛盾矛盾. 推论推论 空集是惟一的空集是惟一的.证证 假设存在假设存在1和和2，则，则12 且且12，因此，因此1=2全集全集E:限定所讨论的集合都是限定所讨论的集合都是E的子集的子集. 相对性相对性 19幂集幂集幂集P(A):A的所有子集组成的集合的所有子集组成的集合, 即即 P(A) = x | x A 例如例如, 设设A=a,b,c A的的0元子集元子集: A的的1元子集元子集: a, b, c A的的2元子集元子集:a,b,a,c,b,c A的的3元子

14、集元子集: a,b,c P(A) =, a, b, c, a,b. a,c, b,c, a,b,c20nnnnnnCCCAP2)11(| )(|10定理定理1.2 如果如果 |A| = n，则则 |P(A)| = 2n 证证集合运算并并 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= x | x A 例如例如 设设E=0,1, ,9, A=0,1,2,3, B=1,3,5,7,9, 则则 A B =0,1,

15、2,3,5,7,9, A B =1,3, A B =0,2, A B =0,2,5,7,9, A =4,5,6,7,8,9, B =0,2,4,6,821实例例例1 设设E= x | x是北京某大学学生是北京某大学学生, A,B,C,D是是E的子集的子集,A= x | x是北京人是北京人, B= x | x是走读生是走读生,C= x | x是数学系学生是数学系学生, D= x | x是喜欢听音乐的学生是喜欢听音乐的学生.试描述下列各集合中学生的特征试描述下列各集合中学生的特征:22(A D) C= A B=(A-B) D= D B= x | x是北京人或喜欢听音乐是北京人或喜欢听音乐, 但不是

16、数学系学生但不是数学系学生 x | x是外地走读生是外地走读生 x | x是北京住校生是北京住校生, 并且喜欢听音乐并且喜欢听音乐 x | x是不喜欢听音乐的住校生是不喜欢听音乐的住校生文氏图表示23集合运算(续)24并和交运算可以推广到有穷个集合上并和交运算可以推广到有穷个集合上 A1 A2 An= x | x A1 x A2 x An A1 A2 An= x | x A1 x A2 x An并和交运算还可以推广到可数无穷个集合上并和交运算还可以推广到可数无穷个集合上 A1 A2 = x | i (i=1,2,) x Ai A1 A2 = x | i (i=1,2,) x Ai niiA1n

17、iiA11iiA1iiA实例例例2 设设Ai=0, 1/i ), Bi=(0, i ), i=1,2, , 则则25niiA11iiAniiA11iiAniiB11iiBnii1B1iiB0, 1)0, 1)0, 1/n ) 0 (0, n)(0, +)(0, 1)(0, 1)基本集合恒等式1. 幂等律幂等律A A=A, A A=A2. 交换律交换律A B=B A, A B=B A3. 结合律结合律(A B) C=A (B C) (A B) C=A (B C)4. 分配律分配律A (B C)=(A B) (A C) A (B C)=(A B) (A C)5. 德摩根律德摩根律 绝对形式绝对形式

18、 (B C)= BC, (B C)= BC 相对形式相对形式 A (B C)=(A B) (A C) A (B C)=(A B) (A C)26基本集合恒等式(续)6. 吸收律吸收律 A (A B)=A, A (A B)=A7. 零律零律 A E=E, A=8. 同一律同一律 A=A,A E=A9. 排中律排中律 AA=E10. 矛盾律矛盾律 AA=11. 余补律余补律 =E, E=12. 双重否定律双重否定律 A=A13. 补交转换律补交转换律 A-B= AB27基本集合恒等式(续)14. 关于对称差的恒等式关于对称差的恒等式 (1) 交换律交换律 A B=B A (2) 结合律结合律 (A

19、 B) C=A (B C) (3) 对对 的分配律的分配律 A (B C)=(A B) (A C) (4) A=A, A E= A (5) A A=, A A= E28注意注意: 对对 没有分配律没有分配律, 反例如下反例如下 A=a,b,c, B=b,c,d, C=c,d,e A (B C)= a,b,c b,e= a,b,c,e (A B) (A C)= a,b,c,d a,b,c,d,e= e, 两者不等两者不等证明集合包含或相等方法一方法一. 根据定义根据定义, 通过逻辑等值演算证明通过逻辑等值演算证明方法二方法二. 利用已知集合等式或包含式利用已知集合等式或包含式, 通过集合演算证明

20、通过集合演算证明例例3 证明证明:(1) A B=B A (交换交换律律)证证 x x A B x A x B (并的定义并的定义) x B x A (逻辑演算的交换律逻辑演算的交换律) x B A (并的定义并的定义)29例3(续)(2) A (B C)=(A B) (A C) (分配律分配律)证证 x x A (B C) x A (x B x C) (并并,交的定义交的定义) (x A x B) (x A x C) (逻辑演算的分配律逻辑演算的分配律) x (A B) (A C) (并并,交的定义交的定义)(3) A E=E (零律零律)证证 x x A E x A x E (并的定义并的

21、定义) x A 1 (全集全集E的定义的定义) 1 (逻辑演算的零律逻辑演算的零律) x E (全集全集E的定义的定义)30例3(续)(4) A E=A (同一同一律律)证证 x x A E x A x E (交的定义交的定义) x A 1 (全集全集E的定义的定义) x A (逻辑演算的同一律逻辑演算的同一律)31实例例例4 证明证明 A (A B)=A （吸收律）吸收律）证证 利用例利用例3证明的证明的4条等式证明条等式证明 A (A B) = (A E) (A B) (同一律同一律) = A (E B) (分配律分配律) = A (B E) (交换律交换律) = A E (零律零律) = A (同一律同一律)对其余的基本集合恒等式不再一一证明对其余的基本集合恒等式不再一一证明,今后把它们作为已知的集合等式使用今后把它们作为已知的集合等式使用.32实例例例5 证明证明 (A-B)-