离散数学.pdf

Discrete Math 离 散 数 学 MSC DUT CAGD 邮件 qrn 答疑 周四晚上 19 30 21 00 办公室 N549 试卷80 作业 出勤率20 上世纪40年代伟大的数学家R 科朗曾经用一本书 来讲述数学是什么 专业的数学对一般人来讲似 乎过于艰深和抽象 数学大概可以按连续数学和离散数学来分类 连 续数学以微积分思想为基础的连续分析为中心 离散数学以发展代数学工具为中心 代数学是一切数学的基础和工具 代数学以古典 的方程理论发展起来 形成现代数学的基础群 论 模形式理论 范畴论 代数结构等 数论研究数的本质 数论研究自然数 可以说是 最自然的数学 某数学家说上帝创造了自然数 其他的数才是人类发明的 数学是什么 三次数学危机 第一次数学危机 无理数的发现 引起了第一次数学危机 第二次数学危机 关键问题就是无穷小量究竞是不是零 无穷小及其 分析是否合理 由此而引起了数学界甚至哲学界长达一 个半世纪的争论 第三次数学危机 这次危机是由于在康托的一般集合理论的边缘发现 悖论造成的 由于集合概念已经渗透到众多的数学分 支 并且实际上集合论已经成了数学的基础 因此集合 论中悖论的发现自然地引起了对数学的整个基本结构的 有效性的怀疑 数学中的一些美丽定理具有这样的特性 它们极易从 事实中归纳出来 但证明却隐藏的极深 数学是科学之 王 高斯 在数学的领域中 提出问题的艺术比解答问题的艺术 更为重要 康扥尔 只要一门科学分支能提出大量的问题 它就充满着生 命力 而问题缺乏则预示独立发展的终止或衰亡 希尔伯特 在数学的天地里 重要的不是我们知道什么 而是我 们怎么知道什么 毕达哥拉斯 数学家名言 数学是无穷的科学 赫尔曼外尔 数是一种离散的数量 线是一种连续的数量 研究数及其属性的学科叫做算术 研究量及其属性的学科叫做几何 研究数和量的学科叫做数学 亚里士多得 本身已如此一目了然 以致于没有任何词汇能够 把他解说得更清楚的事物 绝不要试图给他下定 义 以免被所使用的含混不清的词汇所欺骗 帕斯卡 法 17世纪 数学家名言 数学家名言 数学 逻辑 罗素 逻辑是数学的少年时代 数学是逻辑的成年时代 数学是研究结构的科学 布尔巴基学派 30年代 宇宙是一个由数学和逻辑原则所统率的和谐的整 体 莱布尼茨 一门科学 只有当它成功地运用数学时 才能达 到真正完善的地步 马克思 离散数学 研究离散对象及其相互间关系的一门数学学科 研究离散结构的数学分支 辞海 离散数学是数学的几个分支的总称 以研究离 散量的结构和相互间的关系为主要目标 其研 究对象一般地是有限个或可数无穷个元素 因此 它充分描述了计算机科学离散性的特点 内容 包含 数理逻辑 集合论 代数结构 图论 组合学 数论等 维基百科 Wikipedia 离散数学的由来与发展 一一 古老 古老 历史 计数 自然数 发展 图论 Konigsberg七桥问题 1736 Euler 二 年青 二 年青 新生 计算机 二进制运算 0 1 基础部分基础部分 逻辑 Logic 集合 Sets 算法 Algorithms 数论 Number Theory 原理部分原理部分 数学推理 Reasoning 计数原理 Counting 关系 Relations 应用部分应用部分 图 Graphs 树 Trees 代数系统 布尔代数 Boolean Algbra 群 Group Discrete Math 离散数学 第1 2 3 4 7 8 9章 第一部分 数理逻辑 逻辑是不可战胜的 因为要反对逻辑还得使用 逻辑 P boutroux 数学在过去几乎完全与科学相连接 而逻辑则 与希腊哲学相联系 但二者都随时代发展了 逻辑变得更数学了 而数学变得更逻辑了 无 法在二者之间划分界限 D Vira 逻辑推理题是大公司招聘中最为常见的一类试 题 看重应聘者的逻辑思维能力 并相信这 种能力是漂亮地完成工作的基础 第一章 命题逻辑 1 1 命题符号化及联结词 1 2 命题公式及分类 1 3 等值演算 1 4 联结词全功能集 1 5 对偶与范式 1 6 推理理论 1 7 题例分析 1 1 命题符号化及联结词 一 命题 数理逻辑研究的中心是推理 推理的前提和结论都是表达判断的陈述句 称能判断真假的陈述句为命题 propositions or statements 真值 真假的结果 命题 具有唯一真值的陈述句 注 1 唯一的 确定的 指判断的结果唯一 不可以 有似是而非的情况发生 2 真值仅有两种 即 结果为真 true 和 结果为假 false 例 判断下列语句是否是命题 1 请你回答一个问题 2 明天会下雨吗 3 地球是圆的 4 雪是黑色的 5 明年10月1日是晴天 6 3能被2整除 7 2 3 5 8 地球外的星球上也有人 9 x y 5 注 真值是否唯一与是否知道它的真值是两回事 否 祈使句否 祈使句 否 疑问句否 疑问句 是 真值为是 真值为 真真 是 真值为是 真值为 假假 是 真值唯一 但待定是 真值唯一 但待定 是 真值为是 真值为 假假 是 真值为是 真值为 真真 是 真值唯一 但待定是 真值唯一 但待定 否 命题真值不确定 命题变项否 命题真值不确定 命题变项 判断一个句子是否为命题 1 是否为陈述句 2 真值是否唯一 二 命题的分类 简单命题 原子命题 不能分解成更简单的命题 即具有确定真值的 简单陈述句 通常采用符号p q r p i q i r i 等小写字母形式 来表示某个命题 例 p 地球是圆的 q 雪是黑色的 复合命题 compound statement 由简单命题通过联结词来构成的新命题 在命题逻辑中 主要研究的是复合命题 一般的 简单命题中不应该含有联结词 命题常项 proposition constants 对于简单命题 真值是确定的 命题变项 proposition variable 真值可以变化的简单陈述句 也采用的符号是p q r p i q i r i 等小写字母形式来 表示 如 x y 5 注 命题变项不是命题 因为真值不确定 真值符号化 运算结果符号化 真 T 1 假 F 0 1 否定否定 negation 设p为任一命题 复合命题 p p的否定 称为p的 否定式 记作 p 常见否定词 并非 不是 没有 等 运算特性 单目运算 p 为真 当且仅当 p为假 1 0 0 1 p p 例 p 地球不是圆的 真值为F q 雪不是黑色的 真值为T 2 合取合取 conjunction 设p q为两命题 复合命题 p并且q p和q 称作p与q 的合取式 记作p q 常见合取词 和 与 且 既 又 不 是 而是 虽然 但是 不但 而且 等 p q 为真 当且仅当 p q同时为真 0 0 0 1 0 1 0 1 0 0 1 1 p q q p 例 p q 地球是圆的并且雪是黑色的 p q 地球是圆的并且雪不是黑色的 真值表 注 不能见到 和 与 就用合取词 1 李文和李武是学生 2 李文和李武是兄弟 1 p q 2 P 注 2 中的 和 表示的是李文 李武之间的关 系 而不是两命题的联结 3 析取词析取词 disjunction 设p q为两命题 复合命题 p或q 称作p与q的析取 式 记作p q p q 为真 当且仅当 p与q中至少一个为真 p q 为假 当且仅当 p q同时为假 例 地球是圆的或者雪是黑色的 p q 地球不是圆的或者雪是黑色的 p q 0 1 1 1 0 1 0 1 0 0 1 1 p q q p 注 关于析取 或 的二义性 相容性或 指p与q可同时为真 例 1 张晓静爱唱歌或爱听音乐 令p 张爱唱歌 q 张爱听音乐 则1 中 或 为相容或 即p与q可以同时为真 符号化为p q 不相容性或 排斥或 指p与q不可同时为真 不相容性或 排斥或 指p与q不可同时为真 例 2 张晓静是江西人或安徽人 令r 张是江西人 s 张是安徽人 则2 中 或 应为排斥或 但r与s不能同时为 真 因而也可以符号化为r s 例 3 张晓静只能挑选202或203房间之一 令t 张挑选202房间 u 张挑选203房间 则3 中 或 应为排斥或 t u有4种取值 同真 同假 一真一假 两种情 况 如果也符号化为t u 张就可能同时得到 两个房间 违背题意 不相容性或 排斥或 指p与q不可同时为真 例 3 张晓静只能挑选202或203房间之一 令t 张挑选202房间 u 张挑选203房间 如何达到只能挑一个房间的要求呢 可以使用 多个联结词 符号化为 t u t u 此命题为真当且仅当t u中一个为真 一个为 假 准确地表达了3 的要求 当t真u假时 张 得到202房间 t假u真时 张得到203房间 其它情况下 她得不到任何房间 相斥或可由相容或表示 问 相容或能否由相 斥或表示呢 4 蕴涵词蕴涵词 implication 设p q为两命题 复合命题 如果p 则q 称作p与q的 蕴涵式 记作p q 常见蕴涵词 如果 那么 只要 就 仅 当 p q 为假 当且仅当 p为真且q为假 例 p q 如果地球是圆的那么雪是黑色的 p q 如果地球不是圆的那么雪是黑色的 1 1 0 1 0 1 0 1 0 0 1 1 p q q p 注 关于蕴涵 p q p与q不一定有内在的联系 仅是形式结构的推理 p与q表示的基本逻辑关系是 p是q的充分条件 q是p的必要条件 复合命题 如果p则q 因为p所以q 只要p就 q p仅当q 只有q才p 除非q才p 除非q 否则非p 等均可符号化为p q p q 只要不下雨 我就骑自行车上班 q p 只有不下雨 我才骑自行车上班 当p为假时 p q为真 即 善意的推定 A false hypothesis implies any conclusion 在数学或其它自然科学中 如果p 则q 往往表达的是 前件p为真 后件q也为真的推理关系 5 等价等价 设p q为两命题 复合命题 p当且仅当q 称作p与q的 等价式 记作p q p q 为真 当且仅当 p q真值相同 1 0 0 1 0 1 0 1 0 0 1 1 p q q p 逻辑上 等值 复合命题符号化的基本步骤 分析出各简单命题 将其符号化 使用合适的联结词 联结 各简单命题 注 符号化要按逻辑关系进行 而不能仅凭字面翻译 联结词的优先级 命题公式外层的括号可以省略 联结词的优先级 由高到低 规定 各个命题联结符的优先级别为 大于 大于 大于 大于 利用加括号的方法可以提高优先级 例 如 P Q R 1 1 0 练习 将下列命题符号化 1 我今天进城 除非下雨 2 仅当你走 我将留下 3 如果你来了 那么他唱不唱歌将看你是否伴奏 而定 例 选小王或小李中的一人当班长 p 选小王一人当班长 q 选小李一人当班长 符号化为 p q 正确的符号化 p 选小王当班长 q 选小李当班长 p q p q 理发师的头由谁来理 在一个小镇上 有一个理发师公开宣布 他给而且 只给小镇上所有不给自己理发的人理发 现在要问 这位理发师的头由谁来理 如果理发师由别人给他理发 即理发师自己不给自 己理发 那么按规定这位理发师应该自己理发 如果理发师由他自己理发 按规定他只给那些不给 自己理发的人理发 那么理发师不能由他自己理发 即理发师应该由别人来理发 这就产生了矛盾 理发师既不能由别人理发 也不 能他自己理发 这位理发师的规定是一个悖论 一般地 只有陈述句才可分辨真假 凡是可以判 别真假的陈述句叫做命题 陈述句中有两种形式不是命题 第一种形式 如陈述句 这道题很难 那个人很年轻 很难 很年轻 等概念没有清晰的界限 属于模 糊命题 这类命题不属于我们讨论范围 秃子 第二种形式 就陈述句本身而言 确实很明确 唯一真值 但与其 他命题联合起来 就无法判定其真假 如在一张空白的双面卡片上 写着 正面 A 这张卡片背面的句子是真的 背面 B 这张卡片背面的句子是假的 试问卡片上哪面的叙述为真 为什么 若A真 则B真 即 B 背面的句子是假的 真 A假 若A假 则B假 即 B 背面的句子是假的 假 A真 两句子在一起 不断改变着彼此的真实性 就无法判断 出任何一句的真假性 这不是诡辩 这是命题悖论 我正在说谎 是否为命题 为什么 说谎者悖论 若是谎话 则陈述的事实为假 因而 我 说的就不是谎话 若不是谎话 则陈述的事实为真 因而 我 说的又是谎话 悖论有三种主要形式 1 一种论断看起来好像肯定错了 但实际上却是对的 佯 谬 2 一种论断看起来好像肯定是对的 但实际上却错了 似 是而非的理论 3 一系列推理看起来好像无懈可击 可是却导致逻辑上 自相矛盾 思考 聪明的囚徒 古希腊有个国王 对处死囚徒的方法作了两种规 定 一种是砍头 一种是绞刑 他自恃聪明的做 出一种规定 囚徒可以说一句话 并且这句话是 马上可以验证其真假 如果囚徒说的是真话 那 么处以绞刑 如果囚徒说的是假话 那么处以砍 头 许多囚徒或者是因为说了假话而被砍头或者 因为说了真话而被处以绞刑 有一位极其聪明的囚徒 当轮到他来选择处死方 法时 他说出一句巧妙的话 结果使这个国王按 照哪种方法处死他 都违背自己的决定 只得将 他放了 试问 这囚徒说的是句什么话 聪明的囚徒所说的话 应使国王无论怎么处置他 都带来矛盾 这句话就是 国王决定砍我的头 如果这和国王规定一致 是说真话 因而按国 王决定的处死方法 讲真话应处以绞刑 这样 就造成了国王的规定 砍头 同国王决定的处死 方法相矛盾 如果这和国王的规定不一致 是说的假话 因 而按照国王决定的处死方法 讲假话予以砍 头 这样又造成了国王的规定 绞刑 同国王决 定的处死方法相矛盾 国王处于进退维谷的处境 只好免于处死 将 囚徒放掉 第一章 命题逻辑 1 1 命题符号化及联结词 1 2 命题公式及分类 1 3 等值演算 1 4 联结词全功能集 1 5 对偶与范式 1 6 推理理论 1 7 题例分析 1 2 命题公式及分类 命题公式 合式公式Wellformedformula 1 单个的命题常项或变项 0 1是命题公式 也叫 原子公式 2 若A B是命题公式 则 A A B A B A B A B是命题公式 3 有限次使用 1 和 2 生成的公式才是命题公 式 注 命题公式不是命题 其真值一般不确定 进行真值指派后成命题 例 p p q 是命题公式 而pq r p q r等都不是命题公式 层 1 单个的命题常项或变项 0 1是0层公式 2 称A是n 1层公式是指A符合下列情况之一 A B B是n层公式 A B C A B C A B C A B C 其中B C分别为i j层公式 且n max i j 3 若A的最高层次为k 则称A是k层公式 deg A k 例 p q r s 真值指派的概念 解释 赋值 成真赋值 使命题公式A值为真对应的变项赋值 成假赋值 使命题公式A值为假对应的变项赋值 P Q R 0 1 0成假 0 1 1成真 注 n个命题变项将对应有2 n 种真值指派 即真值表 有2 n 行 n个命题变项只能生成2 2 n 个真值不同的命题公 式 命题公式的真值表 Truth table Def 对n n 1 个命题变项的命题公式 共有2 n 组赋值 将命题公式A在所有赋值之下取值的情 况列成表 称为A的真值表 命题公式真值表的构造步骤 1 找出命题公式中涉及到的所有命题变项作为真值表的 前n列 列出所有可能的赋值 2 按从低到高的顺序写出各层次 3 对应每个赋值 计算命题公式各层次的值 直到最后 计算出命题公式的值 例 利用真值表 求命题公式在变元相应赋值下的 真值 1 p q 2 p q p q 3 p q p