1.1-2离散数学课件及复习资料.ppt

1 第1章数学语言与证明方法 2 第1章数学语言与证明方法 1 1逻辑符号1 2集合及其运算1 3证明方法概述 3 1 1逻辑符号 命题与真值联结词 命题公式 重言式 矛盾式 可满足式 重要等值式重要推理规则个体 个体域与谓词全称量词与存在量词 4 联结词 真值 真 假或1 0命题 具有确定真值的陈述句 通常用p q r等表示真命题 真值为真的命题假命题 真值为假的命题例如 p 2 2 4 q 3是偶数它们都是命题 p是真命题 q是假命题 否定联结词 否定式 p 非p p的否定 p为真当且仅当p为假 5 联结词 续 合取联结词 合取式p q p并且q p与q p q为真当且仅当p与q同时为真析取联结词 析取式p q p或qp q为假当且仅当p与q同时为假排斥或联结词排斥或pq p并且非q 或者q并且非ppq为真当且仅当p与q中一个为真 另一个为假 6 联结词 续 蕴涵联结词 蕴涵式p q 如果p 则qp q为假当且仅当p为真q为假等价联结词 等价式p q p当且仅当qp q为真当且仅当p与q同时为真或同时为假 7 实例 设p 2是偶数 q 1 1 3 则 p的真值为 1 q的真值为 p的真值为 q的真值为 p q的真值为 p q的真值为 p q的真值为 p q的真值为 p q的真值为 p q的真值为 pq的真值为 pq的真值为 p q的真值为 p q的真值为 0 0 1 0 1 1 0 1 1 1 0 0 1 p q的真值为 p q的真值为 0 0 8 实例 续 p q的真值为 p q的真值为 p q的真值为 p q的真值为 0 1 1 1 又设r 今天是星期一 s 明天是星期二 t 明天是星期三 r s的真值为 r t的真值为 1 不定 9 命题公式 命题变项 取值为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的成假赋值 10 重言式 矛盾式与可满足式 重言式 永真式 无成假赋值的命题公式矛盾式 永假式 无成真赋值的命题公式可满足式 不是矛盾式的命题公式例如 A p q r p 是可满足式 但不是重言式 B p q p q p q p q 是重言式 C p p q p q 是矛盾式 A B 蕴涵式A B是重言式的简记 A B 等价式A B是重言式的简记 称A与B等值 A B是等值式 11 基本等值式 双重否定律 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 B 12 基本等值式 续 吸收律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 A 13 重要推理规则 推理定律 附加律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 14 谓词与量词 个体域 被研究对象的全体 如自然数集 人类等 个体词 个体域中的一个元素 全称量词 表示任意的 所有的 一切的等 存在量词 表示存在 有的 至少有一个等 谓词 表示个体词性质或相互之间关系的词例如 谓词P x 表示x具有性质P xP x 表示个体域中所有的x具有性质P xP x 表示个体域中存在x具有性质P 15 1 2集合及其运算 集合及其表示法包含 子集 与相等空集与全集集合运算 基本集合恒等式包含与相等的证明方法 16 集合的概念 朴素集合论 康托 G Cantor 罗素 Russell 悖论集合是数学中最基本的概念 没有严格的定义理解成某些个体组成的整体 常用A B C等表示元素 集合中的个体x A x属于A x是A的元素x A x不属于A x不是A的元素无穷集 元素个数无限的集合有穷集 有限集 元素个数有限的集合 A A中元素个数k元集 k个元素的集合 k 0 17 集合的表示法 列举法如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 等 18 包含与相等 包含 子集 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 C 19 空集与全集 空集 不含任何元素的集合例如 x x2 0 x R 定理1 1空集是任何集合的子集证用归谬法 假设不然 则存在集合A 使得 A 即存在x x 且x A 矛盾 推论空集是惟一的 证假设存在 1和 2 则 1 2且 1 2 因此 1 2全集E 限定所讨论的集合都是E的子集 相对性 20 幂集 幂集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证 21 集合运算 并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 其他 同级别的按从左到右运算 22 实例 例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是不喜欢听音乐的住校生 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 25 实例 例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 26 基本集合恒等式 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 27 基本集合恒等式 续 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 B 28 基本集合恒等式 续 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 两者不等 29 证明集合包含或相等 方法一 根据定义 通过逻辑等值演算证明方法二 利用已知集合等式或包含式 通过集合演算证明例3证明 1 A B B A 交换律 证 xx A B x A x B 并的定义 x B x A 逻辑演算的交换律 x B A 并的定义 30 例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 并 交的定义 3 A E E 零律 证 xx A E x A x E 并的定义 x A 1 全集E的定义 1 逻辑演算的零律 x E 全集E的定义 31 例3 续 4 A E A 同一律 证 xx A E x A x E 交的定义 x A 1 全集E的定义 x A 逻辑演算的同一律 32 实例 例4证明A A B A 吸收律 证利用例3证明的4条等式证明A A B A E A B 同一律 A E B 分配律 A B E 交换律 A E 零律 A 同一律 对其余的基本集合恒等式不再一一证明 请自行证明 今后把它们作为已知的集合等式使用 33 实例 例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 补交转换律 34 实例 例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 A 35 实例 例7设