离散数学自考第一章课后习题和答案ppt课件.ppt

离散数学 1 杨老师yangjj 2 离散数学 又称计算机数学 是现代数学的重要分支 是计算机专业课程中的核心基础课程之一 离散数学以是研究 离散量的结构和相互之间的关系为主要目标 其研究对象一般为 有限或可数个元素 例如 自然数 整数 真假值 有限个结点等 而离散性也是计算机科学的显著特点 3 离散数学 离散数学与计算机科学的其他课程如 数据结构 操作系统 编译原理 算法分析 逻辑设计 系统结构 容错技术 人工智能等有密切的联系 它是这些课程的先导和基础课程 第一部分 数理逻辑第二部分 集合论第三部分 代数系统第四部分 图论 4 第一章命题演算 命题概念基本连接词与复合命题合式公式与联结词优先顺序命题公式的等价变化 命题符号化构造真值表证明等价式不构造真值表证明蕴含式范式与主范式 互化应用P T规则的推理证明CP规则与间接推理证明 5 1 1命题概念 命题 具有唯一真值的陈述句叫命题 亦可简称为语句 1 命题可以是真的 或者是假的 但不能同时为真又为假 2 命题所用符号 常用大写 个英文字母表示命题 用 表示 3 命题中所有的 真 用 表示 命题中所有的 假 用 表示 4 命令句 感叹句 疑问句均不是命题 6 判断下列句子中哪些构成命题8是偶数 雪是黑的 明年国庆节是个春天 3 8 9我是大学生 火星上有生物 星期五下午开会吗 请勿吸烟 这束花多么的好看啊 x y 5 命题命题命题命题命题命题疑问句不是命题祈使句不是命题感叹句不是命题无法确定真值不是命题 7 表示命题的符号称为命题标示符 例 P 今天中午十点下雨 24 今天上午十点下雨 此处的P 24 就是标示符 一个命题标示符如表示确定命题 就称为命题常量 如果命题标示符只标志命题的位置 就称为命题变元 因为命题变元可以表示任意命题 他不能确定真值因此不是命题 8 1 2复合命题与联结词 原子命题 不能再分解的命题 不包含任何联结词的命题 复合命题 经过一些联结词复合而成的命题 在命题演算中也有类似的日常生活中的联结词称做 命题联结词 下面先介绍五个常用的命题联结词 9 否定词 否定运算 非运算 符号 读作 非 否定 设命题为 则在 的前面加否定词 变成 读做 的否定 或 非 例 北京是一座城市 北京不是一座城市 每一种生物均是动物 F 有一些生物不是动物 T这里 不能讲成 每一种生物都不是动物 为假命题了 对量化命题的否定 除对动词进行否定外 同时对量化词也要加以否定 2 的真值由P的真值来确定 10 合取词 合取 积 与 运算 符号 设 为两个命题 则 称 与 的合取 读作 与 与 的合取 并且 等 定义 由真值表给出 11 当且仅当 和 的真值均为 则 的真值为 否则 其真值为 注意 和 是互为独立的 地位是平等的 和 的位置可以交换而不会影响 的结果 在日常生活中 合取词应用在二个有关系的命题之间 而在逻辑学中 合取词可以用在二个毫不相干的命题之间举例 a P 王华的成绩很好Q 王华的品德很好 则 王华的成绩很好并且品德很好 bP 我们去种树Q 房间里有一台电视机则 我们去种树与房间里有一台电视机 c P 今天下大雨Q 3 3 6则 今天下大雨和3 3 6 12 析取词 或运算 符号 设 为二个命题 则 称作 与 的 析取 读作 或 定义 由真值表给出 13 当且仅当 均为 时 为 否则 其真值为 区分 可兼或 与 不可兼或 异或 排斥或 析取词为可兼或即 P和Q均为 T 时 P Q 为 T 不可兼或 中当P和Q均为 T 时 则P异或Q为 F 可兼 或 灯泡有故障或开关有故障 今晚写字或看书 今天下雨或打雷 不可兼 或 他通过电视看杂技或到剧场看杂技 他乘火车去北京或乘飞机去北京 14 单条件联结词 符号 读作 如果 则 如果 那么 为二个命题 为新的命题 读作 如果 则 仅当 当且 是 的充分条件 定义 由真值表定义 15 当 为 为 时 则 为 否则 均为 称为前件 条件 前提 假设 称为后件 结论 举例 a P 我拿起一本书Q 我一口气读完了这本书P Q 如果我拿起一本书 则我一口气读完了这本书 b P 月亮出来了Q 3 3 9P Q 如果月亮出来了 则3 3 9 善意推定 16 双条件联结词 等价 词 同 联结词 等同 词 符号 设 为二个命题 则 读作 当且仅当 等价 是 的充分必要条件 定义 见真值表 17 每当 和 的真值相同时 则 的真值为 否则 的真值为 举例 春天来了当且仅当燕子飞回来了 平面上二直线平行 当且仅当这二直线不相交 当且仅当雪是白色的 两者没有关系 但是确实命题 中 的地位是平等的 交换位置不会改变真值表中的值 18 命题联结词在使用中的优先级 先括号内 后括号外 运算时联结词的优先次序为 由高到低 联结词按从左到右的次序进行运算 可省去括号 因为 运算是可结合的 可省去括号 因为符合上述规定而 中的括号不能省去 因为 不满足结合律 最外层的括号一律均可省去 可写成 19 命题联结词小结 1 五个联结词的含义与日常生活中的联结词的含义大致相同 2 或 可分为可兼或 和异或 不可兼或 3 除 为一元运算外 其余四个均为二元运算 4 当前件为 时 不论后件怎样 则单条件命题的真值均为 5 命题联结词是命题或命题之间的联结词 而不是名词之间 数字之间和动词之间的联结词 20 以上介绍了五种常用的联结词及其相应的复合命题形式 数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算 为此 首先要把推理所涉及到的各命题符号化 步骤如下 找出各简单命题 分别符号化 找出各联结词 把简单命题逐个联结起来 约定 1 我们只注意命题的真假值 而不再去注意命题的汉语意义 2 对命题联结词 我们只注意真值表的定义 而不注意它日常生活中的含义 21 例 将下列命题符号化 1 李明是计算机系的学生 他住在312室或313室 2 张三和李四是朋友 3 虽然交通堵塞 但是老王还是准时到达了车站 4 只有一个角是直角的三角形才是直角三角形 5 老王或小李中有一个去上海出差 22 解 1 首先用字母表示简单命题 P 李明是计算机系的学生 Q 李明住在312室 该命题符号化为 P Q 2 张三和李四是朋友 是一个简单句该命题符号化为 P 3 首先用字母表示简单命题 P 交通堵塞 Q 老王准时到达了车站 该命题符号化为 P Q 23 4 首先用字母表示简单命题 P 三角形的一个角是直角 Q 三角形是直角三角形 该命题符号化为 P Q 5 首先用字母表示简单命题 P 老王去上海出差 Q 小李去上海出差 也可符号化为 P Q P Q 或者 P Q P Q 24 作业 P61 a c d g i k3 a c e4 b d 25 1 3命题公式与真值表 命题公式命题常元 表示确定的命题 T F 命题变元 以真假为其变域之变元 或没有指定真值的命题 常用大写英文字母 表示 命题公式 由命题变元 常元 联结词 括号 以规定的格式联结起来的字符串 命题公式亦可称为合式公式 26 定义 命题演算的合式公式规定为 单个命题变元是一个合式公式 若 是合式公式 也为合式公式 若 是合式公式 则 均为合式公式 当且仅当有限次使用 所生成的公式才是命题公式 2 3 即为关于联结词的运算是封闭的 子公式 设Ai为公式的A的一部分 且Ai是一个子公式 称Ai是A的子公式 27 命题公式的真值表 定义 命题变元用特定的命题来取代 这一过程称为对该命题变元进行指派 真指派 指定的指派使得命题变元为真 假指派 指定的指派使得命题变元为真 命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数 写成 x 例如 公式P Q R 定义三元函数Y P Q R P Q R 28 定义 命题公式A在其所有可能的赋值下取得的值列成的表称为A的真值表 真值表中 真值T F可分别用1 0代替构造真值表的步骤如下 1 找出给定命题公式中所有的命题变元 列出所有可能的赋值 2 按照从低到高的顺序写出命题公式的各层次 3 对应每个赋值 计算命题公式各层次的值 直到最后计算出整个命题公式的值 29 例 构造命题公式 的真值表 个命题变元有 组真值指派 个命题变元有23 组真值指派 个则有个2n个真值指派 30 命题公式的永真式 永假式和可满足式 定义 设A为一命题公式 若A在它的各种指派情况下 其取值均为真 则称公式A为重言式或永真式 定义 设A为一命题公式 若A在它的各种指派情况下 其取值均为假 则称公式A为矛盾式或永假式定义 设A为一命题公式 若A在各种真值指派下至少存在一组成真指派 则称A为可满足式 可满足式为既不是永真式又不是永假式的命题公式 讨论 永真式的否定为永假式 永假式的否定为永真式 二个永真式的析取 合取 蕴含 等价均为永真式 31 列出A P Q P Q 与B P R P R 的真值表 32 1 4 1等价式 定义 如果对两个公式 不论作何种指派 它们真值均相同 则称 是逻辑等价的 亦说 等价于 并记作 33 定理 设X是合式公式A的子公式 若有Y也是一个合式公式 且X Y 如果将A中的X用Y置换 得到公式B 则A B 例1 证明Q P P Q Q P 设 A Q P P Q 因为P P Q P故B Q P 即A BP12例2 3 4P14题2a P Q P P Q P 等值公式 P Q P 等值公式 P P Q 交换律 P P Q 等值公式 P P Q 等值公式 得证 34 定理 命题公式 的充要条件是 为永真式证明 充分性 为永真式 即 有相同的真值 所以 必要性 即 有相同的真值表 所以 为永真式 说明 为等价关系符 表示 和 有等价关系 不为命题公式 为等价联结词 运算符 为命题公式 则 也为一命题公式 35 1 4 2蕴含式 定义 命题公式P称为永真蕴含命题公式Q 当且仅当P Q是一个永真式 记作 P Q 称P蕴含Q 是关系符 不为命题公式例 证明 P 列出真值表证明 和 为永真式 可用等价公式证 T T 36 定理 设P Q为任意两个命题公式 P Q的充分必要条件是P Q Q P 证明 若P Q 则P Q为一永真式由定律 P Q P Q Q P P Q 且 Q P 也为一永真式即 P Q且Q P成立反之P Q且Q P则P Q也成立此定理把 和 之间建立了相应的关系 说明若是要证明P Q 只需证明P Q且Q P 37 证明上述永真蕴含式的方法有三种 把 关系符改为 联结词 证明它为永真式 a 真值表法 b 命题演算法 若前件为真 则命题公式为 只需找出使单条件命题前件为 的所有真值指派 试看能否导致后件均为 若为 则永真蕴含关系成立 由于 P Q Q P 找出使单条件命题的后件均为 的所有真值指派 试看前件的所有真值是否为 若是 则蕴含成立 38 例 前件为 的所有指派为 均为 为 为 也应为 成立 例 后件为 的所有条件是 为 代入前件得 若 为 则 为 若 为 则 为 成立 39 讨论一下永真式可得出三个结论 若一个命题公式等价于一个永真式 则该公式一定为永真式 若一个永真的命题公式永真蕴含一个命题公式 则此命题公式一定也为永真式 若一个永假的命题公式永真蕴含一个命题公式 则该公式可能是永真式 永假式或可满足的 40 常用的蕴含式如下 化简式 附加式 P 变形附加式 变形简化式 假言推论 拒取式 析取三段论 条件三段论 双条件三段论 合取构造二难 析取构造二难 前后件附加 前后件附加 41 作业 P14b d fa c e 42 1 5 最小联结词与范式 任何一个命题公式都可由五个联结词进行等价代换 由上式公式说明五个联结词均可以转化为 或 定义 我们把 或 称为命题公式或者最小联结词 一个命题公式的等价变换 可以有多种不同的形式表达 那如何能化成标准形式及范式的呢 定义 把命题公式化归为一种标准的形式 称此标准形式为范式 43 定义 一个命题公式称为合取范式 当且仅当他具有形式 A1 A2 An A1 A2 An为命题变元及其否定的所组成的析取式 定义 一个命题公式称析取范式 当且仅当他具有形式 A1 A2 An A1 A2 An为命题变元及其否定的所组成的合取式 命题变元的析取式亦称为 和 合取式亦称为 积 所以 合取范式为命题变元及其否定的和之积 析取方式为命题变元及其否定的积之和 44 求命题公式的析取范式方法可按下列三步 或四步 进行 利用等价公式 化去 联结词 把命题公式变为与其等价的用 表达的公式 例 将 深入到原子命题变元之前 并使变元之前最多只有一个 词 例 利用 对 的分配 将公式化成为析取范式 除去永假项得最简析取范式 45 例 求 的析取范式 解 原式 1 化去 词 2 将 深入到变元前面 并最多保留一个 3 对 的分配 化成为析取范式 4 最简析取范式 46 求一个命题公式的合取范式的方法和求析取范式的方法类同 第 步相同 第 利用 对 的分配就行 第 去掉永真的析取项 47 例 求 的合取范式原式 化去 词 深入到变元前 并最多保留一个 对 的分配 最简合取范式 48 定义 在 个命题变元的合取式中 若每个变元及其否定并不同时存在 且二者之一出现一次且仅出现一次 称为布尔合取或小项 例 命题变元P和Q 其小项为 P Q P Q P Q P Q对三个命题变元讲 其小项为 49 有上式可知 若是有2个变元 小项有22 4个 若是有3个变元 小项有23 8个 推广到一般 个命题变元构成的不同小项有2n个 n I 使得每个极小项为真的赋值仅有一个 可以用二进制编码表示 与 分别用1 0表示 例 对三个命题变元讲 其小项为 m111 m110 m101 m100 m011 m010 m001 m000 50 根据书本P17 表1 5 1可知 1 每个小项具有一个相应编码 只有编码与其真是指派相同时 该小项真值为T 在其余2n 1种指派情况下为F m011 只有当 的真值分布为F T T是 小项m011 真值为1 其余7种指派均为F 2 任意两个小项的的合取式永假 m100 m010 T 3 全体小项的析取式为用真 51 定义 对给定的命题公式来讲 仅含有小项的析取的等价式称为给定命题公式的主析取范式 即小项之 和 为主析取范式 定理 在真值表中 一个公式的真值为 的指派所对应的小项的析取 即为此公式的主析取范式 定理 任意含n个命题变元的非永假式命题公式 其主析取式是唯一的 52 例 求出 的主析取范式 53 讨论此定理 1 只要命题公式不是永假式 则一定可以根据该命题公式的真值表直接写出其主析取范式 其方法是找出该公式为 的行 对应写出小项的析取式 且一定是唯一的 2 若命题公式是含有n个变元的永真式 则它的主析取范式一定含有2n个极小项 3 若二个命题公式对应的主析取范式相同 则此二个命题公式一定是等价的 4 命题公式的主析取范式中小项的个数一定等于对应真值表中真值为 的个数 54 下面介绍不用真值表 直接求命题公式主析取范式的方法 分四步 将命题公式化归为与其等价的析取范式 除去永假项 合并基本积中相同项 例 变为最简析取范式 利用添变元的方法 将所有析取范式变为小项 例 二个变元 利用 对或 的分配添项 合并相同的极小项变为一项 55 例1 求 的主析取范式解 原式 1 化为析取范式 2 消去永假项 变为最简析取范式 3 添项 4 合并相同最小项 56 例2 证明 证明方法是写出二个命题公式的主析范式 看其是否相同 而 主析范式相同 有 57 定义 在 个命题变元的析取式中 若每个变元与其否定 并不同时存在 且二者之一出现一次且仅出现一次 则称这种布尔析取或大项 与 分别用0 1表示例 命题变元P和Q 其大项为 P Q P Q P Q P Q对三个命题变元讲 其大项为 M000 M001 M010 M011 M100 M101 M110 M111 推广到一般 个命题变元构成的不同大项有2n个 n I 使得每个大项为真的赋值仅有一个 58 定理 在真值表中 一个公式的真值为F的指派所对应的大项的合取 即为此公式的主合取范式 在真值表中真值为 的个数等于主合取范式中大项的个数 定理 任意含有n个命题变元的非永真命题公式A 其主合取范式是唯一的 59 例 求出 的主合取范式 直接写出其主合取范式 大项 60 讨论 与命题公式等价的主合范式中大项的个数等于其真值表中真值为 的个数 由真值表找大项的方法为 将表中值为 的对应真值指派中 把变元写成否定 把变元的否定写成变元 只要命题公式不是永真式 则一定可以写出对应与其等价的唯一的主合取范式 若命题公式为含有 个变元的永假式 则主合取范式包含了2n个大项的合取式 可用主合取范式判定二个命题公式是否等价 61 已知一个命题公式的主析取范式 则一定可以直接写出与其等价的主合取范式来 反之也行 例 主析范式 主合取范式 对应于有 个变元的命题公式 则一定有 主析范式极小项数 主合范式极大项数 2n 62 下面介绍不用真值表求一命题公式主合取范式的方法 1 化为与命题公式等价的合取范式 2 除去真值为 T 的析取项和除去析取项中相同变元且只保留一个 变为最简合取式 3 添项 使析取项均变为极大项 例如 为二个变元 即 4 合并相同的极大项 保留一项 例 求 的主合取范式解 原式 63 根据小项与大项的刚好相反的编码规则 主析取式与主合取式可以写成统一的编码 主析取式 m11 m01 1 3 主合取式 M00 M10 0 2 主析取式 m00 m01 m10 0 1 2 主合取式 m11 3 m M的小标为二进制 而 的小标为对应的十进制 64 已知A主析取式范式 如何求主合取式范式 求出A的主析取式中为包含小项的小标 把1的求出的小标写成与之相反的对应大项 把2中写成的大项合取 几位A的主合式范式 65 1 6 推理理论 按公认的推论规则 从前提集合中推导出一个结论来 这样的推导过程称为演绎 或者叫形式证明 在任何论证中 若认定前提是真的 且从前提集合推导出结论的论证是遵守了逻辑规则的 则我们称此结论是合法的 根据逻辑规则推导出来的任何结论称为有效结论 推论规则就是指确定论证的有效性的判据 常是用命题形式表示这些规则 而不涉及实际命题和它的真值 66 本节介绍的证明方法 归纳分成三类 一 真值表技术 二 主范式方法及等值演算法 三 构造论证 真值表技术的主要依据是 的真值表定义 若 当且仅当 为永真式 67 1 6 1真值表技术 定义 设H1 H2 Hm 都是命题公式 当且仅当H1 H2 Hm 才可以说 是前提集合 H1 H2 Hm 的有效结论 从给定真值表常用的判断方法有二种 检查真值表中H1 H2 Hm全部为 的所有行 看结论 是否也均为 若 均为 则结论有效 否则结论无效 看结论 为 的所有行 检查每行前提H1 H2 Hm中是否至少有一个为 若有 则结论有效 若有均为 的行 则结论无效 68 例 试证明下列结论是否有效 画出真值表 由真值表可见 有效 无效 有效 有效 无效 69 例 H1 如果大连是一个大城市 则大寨是一个乡村 H2 大寨是一个乡村 大连是一个大城市 则 无效或者称 不能从前提集合中推导出来 70 1 6 2主范式方法及等值演算法 表1 6 2及表1 6 3是常用的等值公式及蕴含公式在推理过程中 如果命题变元较多 会多次使用表1 6 2及表1 6 3 每一个推理过程就是一系列命题公式序列 其中命题公式或者是已知的前提 或者是由某些前提应用推理规则得到的结论 常用的推理规则有 P规则 在推导的任何步骤上都可以引入前提 条件 T规则 1 在证明的任何步骤上 所证明的结论都可以作为后续证明的前提 2 等价的命题公式置换 71 例2证明 P Q P R Q S S R步骤推理过程规则根据 1 P Q P 2 P QT 1 E16 3 Q SP 4 P ST 2 3 I6 5 S PT 4 E18 6 P RP 7 S RT 6 I6 8 S RT 7 E16 72 1 6 3间接证明 反证法 归谬法 定义 由一组前提H1 H2 Hn 利用一些公认的推理 根据已知的等价或蕴含公式推演得到的一个结论 级命题公式C 记作 H1 H2 Hn C定理 推理H1 H2 Hn C为有效推理的充分必要条件是H1 H2 Hn C为永真式 定义 设H1 H2 Hn是可满足式 则称H1 H2 H