离散数学1.11.2数学语言与证明方法.ppt

第第1章章 数学语言与证明方法数学语言与证明方法1第第1章章 数学语言与证明方法数学语言与证明方法•1.1 逻辑符号逻辑符号•1.2 集合及其运算集合及其运算•1.3 证明方法概述证明方法概述21.1 逻辑符号逻辑符号•命题与真值命题与真值•联结词联结词(¬, , , ,,)•命题公式命题公式(重言式重言式,矛盾式矛盾式,可满足式可满足式)•重要等值式重要等值式•重要推理规则重要推理规则•个体个体,个体域与谓词个体域与谓词•全称量词与存在量词全称量词与存在量词3联结词联结词真值真值:真真, 假假 或或 1, 0命题命题:具有确定真值的陈述句具有确定真值的陈述句, 通常用通常用p,q,r等表示等表示真命题真命题:真值为真的命题真值为真的命题假命题假命题:真值为假的命题真值为假的命题例如例如, p:2+2=4, q:3是偶数是偶数它们都是命题它们都是命题, p是真命题是真命题, q是假命题是假命题.否定联结词否定联结词 否定式否定式 p: 非非p (p的否定的否定) )  p 为真当且仅当为真当且仅当p为假为假4联结词联结词(续续)合取联结词合取联结词 合取式合取式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为真当且仅当为真当且仅当p与与q中一个为真中一个为真,另一个为假另一个为假5联结词联结词(续续)蕴涵联结词蕴涵联结词蕴涵式蕴涵式pq:如果如果p,则则q pq为假当且仅当为假当且仅当 p 为真为真 q 为假为假等价联结词等价联结词等价式等价式pq:p当且仅当当且仅当q pq为真当且仅当为真当且仅当p与与q同时为真或同时为假同时为真或同时为假6实例实例 设设p:2是偶数是偶数, q:1+1=3, 则则p的真值为的真值为 1q的真值为的真值为¬p的真值为的真值为¬q的真值为的真值为p q的真值为的真值为p ¬q的真值为的真值为p q的真值为的真值为¬ p q的真值为的真值为p ¬q的真值为的真值为¬p ¬q的真值为的真值为p q的真值为的真值为¬p q的真值为的真值为p ¬q的真值为的真值为¬p ¬q的真值为的真值为0010110111001 p q的真值为的真值为 p ¬q的真值为的真值为007实例实例(续续) pq的真值为的真值为p¬q的真值为的真值为¬pq的真值为的真值为¬p¬q的真值为的真值为0111又设又设 r:今天是星期一今天是星期一, s:明天是星期二明天是星期二, t:明天是星期明天是星期三三rs的真值为的真值为rt的真值为的真值为1不定不定8命题公式命题公式命题变项命题变项:取值为取值为0或或1的变元的变元, 也用也用p,q,r等表示等表示.命题公式命题公式:用联结词和圆括号把命题和命题变项按照一定用联结词和圆括号把命题和命题变项按照一定规则连接起来的符号串规则连接起来的符号串, 常用常用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重言式重言式, ,矛盾式与可满足式矛盾式与可满足式重言式重言式( (永真式永真式) ): :无成假赋值的命题公式无成假赋值的命题公式矛盾式矛盾式( (永假式永假式) ): :无成真赋值的命题公式无成真赋值的命题公式可满足式可满足式: :不是矛盾式的命题公式不是矛盾式的命题公式例如例如, , A= ( p q)(r p)是可满足式是可满足式, 但不是重言式但不是重言式, B= (p q) ( p q) (p  q) ( p  q)是是重重言言式式, C=  p (p q) (p  q)是矛盾式是矛盾式. .AB: :蕴涵式蕴涵式AB B是重言式的简记是重言式的简记. .AB:等价式等价式AB是重言式的简记，是重言式的简记， 称称A与与B等值等值，，AB是是等值式等值式. . 10基本等值式基本等值式双重否定律双重否定律 AA幂等律幂等律 A AA, A AA交换律交换律 A BB A, A BB A结合律结合律 (A B) CA (B C) (A B) CA (B C)分配律分配律 A (B C)(A B) (A C) A (B C) (A B) (A C)德德·摩根律摩根律  (A B)AB  (A B)AB11基本等值式基本等值式( (续续) )吸收律吸收律 A (A B)A, A (A B)A零律零律 A 11, A 00 同一律同一律 A 0A, A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 AB  A B等价等值式等价等值式 AB(AB) (BA)假言易位等值式假言易位等值式 AB  B  A等价否定等值式等价否定等值式 AB  A  B归谬论归谬论 (AB) (AB)   A12重要推理规则重要推理规则( (推理定律推理定律) )附加律附加律 A  (A B) 化简律化简律 (A B)  A假言推理假言推理 (AB) A  B拒取式拒取式 (AB)B   A析取三段论析取三段论 (A B)B  A假言三段论假言三段论 (AB) (BC)  (AC)等价三段论等价三段论 (AB) (BC)  (AC)构造性二难构造性二难 (AB) (CD) (A C)  (B D) 破坏性二难破坏性二难 (AB) (CD) (  BD)  ( AC) 13谓词与量词谓词与量词个体域个体域:被研究对象的全体被研究对象的全体, 如自然数集如自然数集, 人类等人类等.个体词个体词:个体域中的一个元素个体域中的一个元素.全称量词全称量词 : 表示任意的表示任意的, 所有的所有的, 一切的等一切的等.存在量词存在量词 : 表示存在表示存在, 有的有的, 至少有一个等至少有一个等.谓词谓词: 表示个体词性质或相互之间关系的词表示个体词性质或相互之间关系的词例如例如, 谓词谓词P(x)表示表示x具有性质具有性质P  x P(x) 表示个体域中所有的表示个体域中所有的x具有性质具有性质P  x P(x) 表示个体域中存在表示个体域中存在x具有性质具有性质P141.2 集合及其运算集合及其运算•集合及其表示法集合及其表示法•包含包含(子集子集)与相等与相等•空集与全集空集与全集•集合运算集合运算( , , - , ~ ,  )•基本集合恒等式基本集合恒等式•包含与相等的证明方法包含与相等的证明方法15集合的概念集合的概念朴素集合论朴素集合论(康托康托, G.Cantor), 罗素罗素(Russell)悖论悖论集合集合是数学中最基本的概念是数学中最基本的概念,没有严格的定义没有严格的定义 理解成某些个体组成的整体理解成某些个体组成的整体, 常用常用A,B,C等表示等表示元素元素:集合中的个体集合中的个体x A(x属于属于A): x是是A的元素的元素 x A(x不不属于属于A): x不不是是A的元素的元素无穷集无穷集:元素个数无限的集合元素个数无限的集合有穷集有穷集(有限集有限集):元素个数有限的集合元素个数有限的集合. |A|:A中元素个中元素个数数k元集元集:k个元素的集合个元素的集合, k   016集合的表示法集合的表示法列举法列举法 如如 A={ a, b, c, d }, N={0,1,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包含与相等包含与相等包含包含(子集子集) 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 | x2<0 x R}=定理定理1.1 空集是任何集合的子集空集是任何集合的子集证证 用归谬法用归谬法. 假设不然假设不然, 则存在集合则存在集合A, 使得使得 ⊈ ⊈ A, 即存在即存在x, x 且且x A, 矛盾矛盾. 推论推论 空集是惟一的空集是惟一的.证证 假设存在假设存在1和和2，则，则12 且且12，因此，因此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元子集元子集: {a,b,c} P(A) ={, {a}, {b}, {c}, {a,b}. {a,c}, {b,c}, {a,b,c}}定理定理1.2 如果如果 |A| = n，，则则 |P(A)| = 2n 证证20集合运算集合运算并并 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,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,8}说明说明:1. 只使用圆括号只使用圆括号2. 运算顺序运算顺序: 优先级别为优先级别为(1)括号括号, (2) 和幂集和幂集, (3)其他其他.同级别的按从左到右运算同级别的按从左到右运算21实例实例例例1 设设E={ x | x是北京某大学学生是北京某大学学生}, A,B,C,D是是E的子集的子集,A= { x | x是北京人是北京人}, B= { x | x是走读生是走读生},C= { x | x是数学系学生是数学系学生}, D= { x | x是喜欢听音乐的学生是喜欢听音乐的学生}.试描述下列各集合中学生的特征试描述下列各集合中学生的特征:(A D)   ~ C=~ A B=(A-B)   D=~ D   ~ B={ x | x是北京人或喜欢听音乐是北京人或喜欢听音乐, 但不是数学系学生但不是数学系学生}{ x | x是外地走读生是外地走读生}{ x | x是北京住校生是北京住校生, 并且喜欢听音乐并且喜欢听音乐}{ x | x是不喜欢听音乐的住校生是不喜欢听音乐的住校生}22文氏图表示文氏图表示23集合运算集合运算(续续)并和交运算可以推广到有穷个集合上并和交运算可以推广到有穷个集合上 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 }24实例实例例例2 设设Ai=[0, 1/i ), Bi=(0, i ), i=1,2, …, 则则[0, 1)[0, 1)[0, 1/n ){ 0 }(0, n)(0, +∞)(0, 1)(0, 1)25基本集合恒等式基本集合恒等式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. 德摩根律德摩根律 绝对形式绝对形式 (B C)= BC,  (B C)= BC 相对形式相对形式 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. 排中排中律律 AA=E10. 矛盾律矛盾律 AA=11. 余补律余补律 =E,  E=12. 双重否定双重否定律律    A=A13. 补交转换律补交转换律 A-B= AB27基本集合恒等式基本集合恒等式(续续)14. 关于对称差的恒等式关于对称差的恒等式 (1) 交换律交换律 A B=B A (2) 结合律结合律 (A B) C=A (B C) (3)  对对 的分配律的分配律 A (B C)=(A B) (A C) (4) A =A, A E= ~ A (5) A A=, A  ~ A= E注意注意:  对对 没有分配律没有分配律, 反例如下反例如下 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}, 两者不等两者不等28证明集合包含或相等证明集合包含或相等方法一方法一. 根据定义根据定义, 通过逻辑等值演算证明通过逻辑等值演算证明方法二方法二. 利用已知集合等式或包含式利用已知集合等式或包含式, 通过集合演算证明通过集合演算证明例例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 (并的定义并的定义)  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)-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 (补交转换律补交转换律)33实例实例例例6 证明证明 (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) - A34实例实例例例7 设设A,B为任意集合为任意集合, 证明证明:(1) A A B证证  x x A  x A x B (附加律附加律)  x A B(2) A B A证证  x x A B  x A x B  x A (化简律化简律)35实例实例(续续)(3) A-B A证证  x x A-B  x A x B  x A (化简律化简律)(4) 若若A B, 则则P(A) P(B)证证  x x P(A)  x A  x B (已知已知A B)  x P(B)36实例实例例例8 证明证明 A B=A B-A B.证证 A B=(A ~B) (~A B) =(A ~A) (A B) (~B ~A) (~B B) =(A B) (~B ~A) =(A B) ~(A B) =A B-A B 37。