离散数学习题课.pdf

3 1离散数学 Discrete Mathematics 模式识别实验室 离散数学 Discrete Mathematics 主讲 李 春光 模式识别与智能系统实验室 lichunguang 命题逻辑 习题课 3 2离散数学 Discrete Mathematics 模式识别实验室 第一章 简要回顾第一章 简要回顾 命题与联结词命题与联结词 主要内容 主要内容 简单命题 复合命题 简单命题 复合命题 5种基本联结词及复合命题的符号化种基本联结词及复合命题的符号化 基本要求 基本要求 分清简单命题与复合命题 分清简单命题与复合命题 掌握联结词的定义 能够准确 地把基本复合命题和复合命题符号化 并能够迅速求出复 合命题的真值 掌握联结词的定义 能够准确 地把基本复合命题和复合命题符号化 并能够迅速求出复 合命题的真值 命题公式及其赋值命题公式及其赋值 主要内容 主要内容 命题公式的定义 命题公式的层次 命题公式的赋值 真 值表以及公式的类型 命题公式的定义 命题公式的层次 命题公式的赋值 真 值表以及公式的类型 基本要求 深刻理解命题公式的赋值 基本要求 深刻理解命题公式的赋值 掌握命题公式的类型掌握命题公式的类型 重言式 矛盾式 可满足式 重言式 矛盾式 可满足式 能够熟练写出给定命题公式的真值表 从而 准确判断公式的类型 能够熟练写出给定命题公式的真值表 从而 准确判断公式的类型 3 3离散数学 Discrete Mathematics 模式识别实验室 第二章 简要回顾第二章 简要回顾 等值式等值式 主要内容 等值式的概念 主要内容 等值式的概念 16组组 24个个 基本等值式 等值演算 置 换规则 基本等值式 等值演算 置 换规则 重点 重点 16组基本等值式 借助基本等值式和置换规则进行组基本等值式 借助基本等值式和置换规则进行等值演算等值演算 进而判断公式的类型进而判断公式的类型 析取范式与合取范式析取范式与合取范式 主要内容 基本概念主要内容 基本概念 文字 极小项 极大项 析取范式 合取范式 主析取范式 主合取范式 主析取范式和主合取范式存在和唯 一性定理 文字 极小项 极大项 析取范式 合取范式 主析取范式 主合取范式 主析取范式和主合取范式存在和唯 一性定理 重点 重点 求取主析取范式和主合取范式求取主析取范式和主合取范式 以及借此确定公式的成真赋 值或成假赋值 判断公式的类型 判断公式是否等值 以及借此确定公式的成真赋 值或成假赋值 判断公式的类型 判断公式是否等值 难点 求取主析取范式和主合取范式难点 求取主析取范式和主合取范式 真值函数与联结词完备集真值函数与联结词完备集 主要内容 真值函数的定义 主要内容 真值函数的定义 联结词完备集联结词完备集 3 4离散数学 Discrete Mathematics 模式识别实验室 第三章 简要回顾第三章 简要回顾 推理的形式结构推理的形式结构 主要内容 判断推理是否正确的方法 推理定律主要内容 判断推理是否正确的方法 推理定律 重点 理解重点 理解推理的形式结构推理的形式结构 掌握 掌握判断推理正确判断推理正确的方法的方法 难点 难点 自然推理系统自然推理系统P 主要内容 自然推理系统主要内容 自然推理系统P中的证明中的证明 重点 牢记各条重点 牢记各条推理规则的内容和名称推理规则的内容和名称 熟练地掌握 熟练地掌握在 自然推理系统中构造证明 在 自然推理系统中构造证明的方法的方法 直接法 附加前提法 归谬法 直接法 附加前提法 归谬法 难点 将日常生活中某些推理形式化 并判断正确性以 及在自然推理系统 难点 将日常生活中某些推理形式化 并判断正确性以 及在自然推理系统P中证明中证明 3 5离散数学 Discrete Mathematics 模式识别实验室 联结词联结词 联结词联结词 自然语言里的联结词具有二义性自然语言里的联结词具有二义性 张三张三与与李四都是大二的李四都是大二的 张三张三与与李四是同学李四是同学 联结词可将命题联结起来构成复杂的命题 相 当于初等数学里的实数集上定义的 等运算符 联结词可将命题联结起来构成复杂的命题 相 当于初等数学里的实数集上定义的 等运算符 5个常用的逻辑联结词 个常用的逻辑联结词 非非 并且并且 或或 如果 那么如果 那么 当且仅 当 当且仅 当 3 6离散数学 Discrete Mathematics 模式识别实验室 16组等值式模式组等值式模式 双重否定 双重否定 P P 等幂律等幂律P P PP P P 结合律结合律 P Q R P Q R P Q R P Q R 交换律交换律P Q Q P P Q Q P 3 7离散数学 Discrete Mathematics 模式识别实验室 16组等值式模式组等值式模式 分配律分配律 P Q R P Q P R P Q R P Q P R 吸收律吸收律 P P Q P P P Q P 德德 摩根律摩根律 P Q P Q P Q P Q 3 8离散数学 Discrete Mathematics 模式识别实验室 16组等值式模式组等值式模式 同一律同一律 P 0 PP 1 P 零律零律 P 1 1 P 0 0 排中律排中律P P 1 矛盾律矛盾律P P 0 蕴含等值式蕴含等值式P Q P Q 等价等值式等价等值式P Q P Q Q P 3 9离散数学 Discrete Mathematics 模式识别实验室 16组等值式模式组等值式模式 假言易位假言易位 P Q Q P 等价否定等值式等价否定等值式 P Q P Q 归谬论归谬论 P Q P Q P 3 10离散数学 Discrete Mathematics 模式识别实验室 推理定律推理定律 重要的推理定律重要的推理定律 A B A B 假言推理假言推理 A B A 化简式化简式 A A B 附加式附加式 A B B A 拒取式拒取式 A B B C A C 假言三段论假言三段论 A B A B 析取三段论析取三段论 A B B C A C 等价三段论等价三段论 A B C D A C B D 构造性二难推论构造性二难推论 A B C D B D A C 破坏性二难推论破坏性二难推论 3 11离散数学 Discrete Mathematics 模式识别实验室 自然推理系统自然推理系统 自然推理系统自然推理系统P 1 字母表 字母表 命题变项符号 命题变项符号 p q r 联结词符号联结词符号 括号与逗号括号与逗号 2 合式公式 合式公式 3 推理规则 推理规则 前提引入规则 在证明的任何步骤上都可以引入前提前提引入规则 在证明的任何步骤上都可以引入前提 结论引入规则 在证明任何步骤上得到的结论都可以作为 后续证明的前提 结论引入规则 在证明任何步骤上得到的结论都可以作为 后续证明的前提 置换规则 在证明的任何步骤上 命题公式的置换规则 在证明的任何步骤上 命题公式的子公式子公式都可 以用 都可 以用与之等值的公式替换与之等值的公式替换 得到公式序列中的又一个公式 得到公式序列中的又一个公式 3 12离散数学 Discrete Mathematics 模式识别实验室 推理规则推理规则 推理规则还有 推理规则还有 假言推理规则 假言推理规则 附加规则 附加规则 化简规则 化简规则 拒取式规则 拒取式规则 假言三段论规则 假言三段论规则 AB A B A AB AB A AB B A AB BC AC 3 13离散数学 Discrete Mathematics 模式识别实验室 推理规则推理规则 推理规则还有 推理规则还有 析取三段论规则 析取三段论规则 构造性二难推理规则 构造性二难推理规则 破坏性二难推理规则 破坏性二难推理规则 合取引入规则 合取引入规则 AB B A AB CD AC BD AB CD BD AC A B AB 3 14离散数学 Discrete Mathematics 模式识别实验室 基本考察点基本考察点 复合命题的符号化复合命题的符号化 利用真值表判断公式的类型利用真值表判断公式的类型 等值演算等值演算 求主析取范式和主合取范式求主析取范式和主合取范式 推理理论推理理论 推理的形式结构 正确性判断推理的形式结构 正确性判断 在自然推理系统中构造证明在自然推理系统中构造证明 3 15离散数学 Discrete Mathematics 模式识别实验室 第一章作业第一章作业 6 仔细看看仔细看看例例1 4 7 可以符号化为可以符号化为 p q p q 也可以符号化为 也可以符号化为 p q 但并不意味 着 但并不意味 着 p q p q 等值于等值于p q 错误情况 错误情况 通过真值表检验 两者等 值 通过真值表检验 两者等 值 3 16离散数学 Discrete Mathematics 模式识别实验室 第一章作业第一章作业 13 首先符号化 然后观察其真值表首先符号化 然后观察其真值表 p 今天星期一 今天星期一 q 明天星期二 明天星期二 r 明天星期三明天星期三 1 p q 2 q p 3 p q 4 p r p qr p qq pp r 0001 1 1 11 00111 11010 3 17离散数学 Discrete Mathematics 模式识别实验室 第一章作业第一章作业 14 符号化 符号化 4 5 与与 不是命题联结词的不是命题联结词的 析取析取 是 是 简单 命题 简单 命题 50 p 9 只有天下大雨 才乘车上班只有天下大雨 才乘车上班 60 P 天下大雨 天下大雨 Q 他乘车上班 他乘车上班 Q P 或者 或者 P Q 10 除非天下大雨 否则他不乘车上班除非天下大雨 否则他不乘车上班 60 P 天下大雨 天下大雨 Q 他乘车上班 他乘车上班 Q P 或者 或者 P Q 11 下雪路滑 他迟到了下雪路滑 他迟到了 有几个原子命题 有几个原子命题 95 P 下雪 下雪 Q 路滑 路滑 R 他迟到了 他迟到了 P Q R 3 18离散数学 Discrete Mathematics 模式识别实验室 第一章作业第一章作业 14 符号化符号化 12 2与与4 都是素数 这是不对的都是素数 这是不对的 60 两种错误 两种错误 1 p 2是素数 是素数 q 4是素数 是素数 r 这是不对的这是不对的 2 p 2与与4 都是素数都是素数 q 这是不对的 这是不对的 正解 正解 p 2是素数 是素数 q 4是素数是素数 p q 13 2与与4 都是素数 这是不对的都是素数 这是不对的 的判断是 不对的 的判断是 不对的 p 2是素数 是素数 q 4是素数是素数 p q 3 19离散数学 Discrete Mathematics 模式识别实验室 第一章作业第一章作业 符号用法的错误 符号用法的错误 新接触的基本符号新接触的基本符号7个 个 5个联结词符号 个联结词符号 1个等值符号 个等值符号 1个推理正确符号 个推理正确符号 这些符号有何关系呢 这些符号有何关系呢 等值符号 等值符号 A B 即 即A B为重言式 为重言式 推理正确符号 推理正确符号 A B 即 即A B为重言式 为重言式 3 20离散数学 Discrete Mathematics 模式识别实验室 复合命题的符号化复合命题的符号化 复合命题的符号化基本步骤复合命题的符号化基本步骤 1 找出各个简单命题 并逐个符号化找出各个简单命题 并逐个符号化 2 找出自然语言中的联结词 并准确符号 成相应基本联结词 找出自然语言中的联结词 并准确符号 成相应基本联结词 3 用基本联结词把简单命题逐个联结起来用基本联结词把简单命题逐个联结起来 3 21离散数学 Discrete Mathematics 模式识别实验室 复合命题的符号化复合命题的符号化 例 将下列命题符号化例 将下列命题符号化 今夜你若敢去公墓 那么我就咬掉我的鼻 子或咬掉我的耳朵 今夜你若敢去公墓 那么我就咬掉我的鼻 子或咬掉我的耳朵 P 今夜你敢去公墓 今夜你敢去公墓 Q 我咬掉我的鼻子 我咬掉我的鼻子 R 我咬掉我的耳朵我咬掉我的耳朵 P Q R 3 22离散数学 Discrete Mathematics 模式识别实验室 复合命题的符号化复合命题的符号化 例 将下列命题符号化例 将下列命题符号化 王乐是计算机系的学生 生于王乐是计算机系的学生 生于1980年或年或 1981年年 是三好学生 是三好学生 P 王乐是计算机系的学生 王乐是计算机系的学生 Q 王乐生于 王乐生于1980年年 R 王乐生于王乐生于1981年年 S 王乐是三好学生王乐是三好学生 P Q R S 3 23离散数学 Discrete Mathematics 模式识别实验室 复合命题的符号化复合命题的符号化 例 将下列命题符号化例 将下列命题符号化 张三和李四是兄弟 张三和李四是兄弟 P 张三是兄弟 张三是兄弟 Q 李四是兄弟 李四是兄弟 Error P Q P 张三和李四是兄弟 P 原子命题 原子命题 3 24离散数学 Discrete Mathematics 模式识别实验室 复合命题的符号化复合命题的符号化 例 将下列命题符号化例 将下列命题符号化 张三或李四都能做这件事张三或李四都能做这件事 P 张三能做这件事 张三能做这件事 Q 李四能做这件事 李四能做这件事 Wrong P Q P Q 3 25离散数学 Discrete Mathematics 模式识别实验室 复合命题的符号化复合命题的符号化 例 将下列命题符号化例 将下列命题符号化 如果我上街 我就去书店看看 除非我 很累 如果我上街 我就去书店看看 除非我 很累 P 我上街 我上街 Q 我去书店看看 我去书店看看 R 我很累 我很累 P Q R 表示1表示1 表示2表示2 R P Q 3 26离散数学 Discrete Mathematics 模式识别实验室 蕴涵联结词蕴涵联结词 与日常语言的区别 与日常语言的区别 下列表达均用下列表达均用p q符号化 符号化 如果如果p 那么那么q 只要只要p 就就q p 仅当仅当q 只有只有 q 才才p 除非除非q 才才p 除非除非q 否则非 否则非p p q是无关的命题时是无关的命题时 逻辑上允许讨论逻辑上允许讨论p q 规定规定p为为F时 则时 则p q为为T 这在自然用语中是 不常使用的 这在自然用语中是 不常使用的 3 27离散数学 Discrete Mathematics 模式识别实验室 蕴涵联结词蕴涵联结词 例 例 1 只要今天不下雨 我就骑自行车上班只要今天不下雨 我就骑自行车上班 2 除非今天下雨 否则我就骑自行车上班除非今天下雨 否则我就骑自行车上班 3 只有今天不下雨 我才骑自行车上班只有今天不下雨 我才骑自行车上班 4 如果今天下雨 我就不骑自行车上班如果今天下雨 我就不骑自行车上班 令令p 今天下雨 今天下雨 q 我骑车上班我骑车上班 1 p q 2 p q 3 q p 4 p q 3 28离散数学 Discrete Mathematics 模式识别实验室 第二章 习题第二章 习题 27 列出成真赋值 构造主析取范式列出成真赋值 构造主析取范式 28 根据题意 列出真值表 针对成真赋值写 出主析取范式 根据题意 列出真值表 针对成真赋值写 出主析取范式 难点在于正确列出真值表难点在于正确列出真值表 3 29离散数学 Discrete Mathematics 模式识别实验室 第二章 习题第二章 习题 29 用等值演算求解用等值演算求解 设设p 王小红为班长 王小红为班长 q 丁金生为班长 丁金生为班长 r 李强 为班长 李强 为班长 s 李强为生活委员 李强为生活委员 t 王小红为生活 委员 王小红为生活 委员 u 王小红为学习委员 王小红为学习委员 甲乙丙都对了一半 甲乙丙都对了一半 甲对了一半 甲对了一半 p s p s 乙对了一半 乙对了一半 q t q t 丙对了一半 丙对了一半 r u r u F p s p s q t q t r u r u 等值演算 等值演算 3 30离散数学 Discrete Mathematics 模式识别实验室 第二章 习题第二章 习题 等值演算得到 等值演算得到 F p q r s t u p q r s t u p q r s t u p q r s t u p q r s t u p q r s t u p q r s t u p q r s t u 含有含有8个极小项 但是能得到合理解释的只有个极小项 但是能得到合理解释的只有1个极小项个极小项 注意 每人只能任一职 每职只能任一人注意 每人只能任一职 每职只能任一人 p 王小红为班长 王小红为班长 q 丁金生为班长 丁金生为班长 r 李强为班长 李强为班长 s 李强为生活委员 李强为生活委员 t 王小红为生活委员 王小红为生活委员 u 王小红为 学习委员 王小红为 学习委员 所以 所以 q s u为真 即丁金生为班长 李强为生活委员 王小红为学习委员 为真 即丁金生为班长 李强为生活委员 王小红为学习委员 3 31离散数学 Discrete Mathematics 模式识别实验室 第二章 习题第二章 习题 30 用等值演算求解用等值演算求解 符号化符号化 A 赵去 赵去 B 钱去 钱去 C 孙去 孙去 D 李去 李去 E 周去 周去 A B D E B C B C C D E A B F A B D E B C B C C D E A B 可以有三种方式解决这种问题 可以有三种方式解决这种问题 1 真值表法 真值表法 2 5 32种可能情况 一一检验种可能情况 一一检验 2 等值演算法 处理含有等值演算法 处理含有5个命题变项的公式个命题变项的公式 3 推理规则法推理规则法 提出假设 构造推理提出假设 构造推理 3 32离散数学 Discrete Mathematics 模式识别实验室 第二章 习题第二章 习题 2 等值演算法等值演算法 F A B C D E A B C D E 3 推理规则法推理规则法 提出假设 构造推理提出假设 构造推理 前提 前提 A B D E B C B C C D E A B 结论结论 3 33离散数学 Discrete Mathematics 模式识别实验室 第三章 习题第三章 习题 推理的形式结构和推理正确性判断推理的形式结构和推理正确性判断 6 1 3 6 推理正确 其余均错误推理正确 其余均错误 8 写出推理的形式结构 利用推理规则 构 造有效结论 写出推理的形式结构 利用推理规则 构 造有效结论 3 34离散数学 Discrete Mathematics 模式识别实验室 解决生活中的判断问题解决生活中的判断问题 例 小李或小张是先进工作者例 小李或小张是先进工作者 如果小李是先进 工作者 你是会知道的 如果小李是先进 工作者 你是会知道的 如果小张是先进工作者 小赵也是 如果小张是先进工作者 小赵也是 你不知道小李是先进工作者 问 你不知道小李是先进工作者 问 谁是先进工作者 解 谁是先进工作者 解 1 首先找出原子命题首先找出原子命题 完成符号化完成符号化 p 小李是先进工作者小李是先进工作者q 小张是先进工作者小张是先进工作者 r 我知道小李是先进工作者我知道小李是先进工作者 s 小赵是先进工作者小赵是先进工作者 2 把复合命题符号化为 把复合命题符号化为 p q p r q s r 3 用等值演算化简 求成真赋值 用等值演算化简 求成真赋值 3 35离散数学 Discrete Mathematics 模式识别实验室 解决生活中的判断问题解决生活中的判断问题 p q p r q s r p q q s p r r p q q s p r p q q q p s q s p r p q p r p s p r q s p r 0 0 q s p r q s p r p q r s m5 解释 解释 q与与s为真 也就是说 小张和小赵是先进工作者为真 也就是说 小张和小赵是先进工作者 0101 3 36离散数学 Discrete Mathematics 模式识别实验室 求解实际应用问题求解实际应用问题 例例9 张先生手中有代号为 张先生手中有代号为A B C D E的五种 股票 根据当前股市情况及张先生的经济需求 需 要将若干股票抛出 但又须满足如下要求 的五种 股票 根据当前股市情况及张先生的经济需求 需 要将若干股票抛出 但又须满足如下要求 1 若 若A抛出 则抛出 则B也抛出 也抛出 2 B和和C要留一种股票且只能留一种 要留一种股票且只能留一种 3 C和和D要么全抛 要么都不抛 要么全抛 要么都不抛 4 D和和E两种股票中必然有一种或两种要抛出 两种股票中必然有一种或两种要抛出 5 若 若E抛出 则抛出 则A B也抛出 也抛出 上述五种条件全部满足 问有几种合理的方案供张先生选择 上述五种条件全部满足 问有几种合理的方案供张先生选择 3 37离散数学 Discrete Mathematics 模式识别实验室 求解实际应用问题求解实际应用问题 找出原子命题 进行符号化 找出原子命题 进行符号化 A A抛出 抛出 B B抛出 抛出 C C抛出 抛出 D D抛出 抛出 E E 抛出抛出 5个条件依次可以符号化为 个条件依次可以符号化为 A B B C B C C D D E E A B 对整个复合命题的符号化 对整个复合命题的符号化 A B B C B C C D D E E A B 通过等值演算 得出通过等值演算 得出 略略 3 38离散数学 Discrete Mathematics 模式识别实验室 综合例题综合例题 例例8 如果如果a是奇数 则是奇数 则a不能被不能被2整除整除 如果如果a是偶数 则是偶数 则a 能被能被2整除整除 因此因此 如果如果a是偶数 则是偶数 则a不是奇数 不是奇数 试用不同方法证明试用不同方法证明 解 符号化解 符号化 P a是奇数是奇数 Q a是偶数是偶数 R a能被能被2整除整除 前提前提 P R Q R 结论结论 Q P 验证 验证 P R Q R Q P 为重言式 为重言式 1 真值表法真值表法 2 等值演算法等值演算法 3 主范式法主范式法 4 证明的方法证明的方法 3 39离散数学 Discre