离散数学 第一章 命题逻辑-8节.ppt

1 8 命题推理理论学习要求 2 1 甲在河南工业大学上学 2 甲在郑州上大学 如果 甲在河南工业大学上学 真的 则显然 甲在郑州上大学 也是真的 推理形式 如果甲在河南工业大学上学 则甲在郑州上大学 甲在河南工业大学上学 则可推出甲在郑州上大学 符号化为 P表示 甲在河南工业大学上学 Q表示 甲在郑州上大学 P Q表示 如果甲在河南工业大学上学 则甲在郑州上大学 推理形式可以表示为P Q为真 P为真 则可推出Q为真 可以抽象地写成 P Q P Q 3 如果甲在河南工业大学上学 则甲在郑州上大学 是成立的 命题公式之间的关系 命题公式之间的关系 蕴含关系 等价关系 4 复习 例如 证明 P P Q Q为重言式 重言式的真值表的最后一列全是 T 设A B为两个命题公式 A B当且仅当A B为一重言式 5 方法2 P Q P Q P Q P Q 公式E16 P Q P Q 公式E16 P Q P Q 德 摩根律 P Q P Q 德 摩根律 P P Q P Q 分配律 T Q P Q 否定律 Q P Q 同一律 Q Q P 交换律 Q Q P 结合律 T P 否定律 T 零律 所以 P Q P Q是重言式 6 一 蕴含式 标注 有些重言 永真 式 如 P P Q Q 公式中间是 联结词 是很重要的 称之为蕴含式 1 定义1 5 3 当且仅当A B是一个重言式时 称A蕴含B 记作A B 也称B是A的有效结论 或B可由A逻辑地推出 P40 P P Q Q可以写成 P P Q Q注意 符号 不是联结词 它是表示公式间的 蕴含 关系 也可以看成是 推导 关系 即A B可以理解成由A可推出B 即由A为真 可以推出B也为真 7 2 重要的蕴含式P43 I1 P Q PI2 P Q QI3 P P QI4 Q P QI5 P P QI6 Q P QI7 P Q PI8 P Q QI9 P Q P QI10 P P Q QI11 P P Q QI12 Q P Q PI13 P Q Q R P RI14 P Q P R Q R RI15 A B A C B C I16 A B A C B C 8 化简规则P Q P现在气温在冰点以下并且正在下雨 因此 现在气温在冰点以下 附加规则P P Q现在气温在冰点以下 因此 要么现在气温在冰点以下 要么现在下雨 9 假言推理规则P P Q Q若今天下雪 则将去滑雪 今天下雪 所以去滑雪 假言三段论 P Q Q R P R前提 1 如果我不能起床 则我不能上班 2 如果我不能上班 则我不能得到报酬 结论 如果我不能起床 则我不能得到报酬 10 析取三段论 P P Q Q前提 某人被杀害 凶手为王某或陈某 但王某有不在作案现场证明 结论 陈某为凶手 二难推理 P Q P R Q R R前提 1 如果某同学为省级运动员 则他被大学录取 2 如果某同学高考总分590分以上 则他被大学录取 3 某同学为省级运动员或高考总分590分以上 结论 该同学被大学录取 11 3 蕴含常见的几个性质 性质1 A B为任意命题公式 若A B 且A为重言式 则B必为重言式 性质2 A B C为任意命题公式 若A B B C 则A C 蕴含关系可传递 性质3 A B C为任意命题公式 若A B A C 则A B C 两个蕴含式结论的合并 性质4 A B C为任意命题公式 若A B且C B 则A C B 两个蕴含式前提的合并 12 4 蕴含常见的几个性质 性质1 A B为任意命题公式 若A B 且A为重言式 则B必为重言式 证 因为A B 所以A B为重言式 即A B永真 当A永为T 所以B必永为T T 定义1 5 3 当且仅当A B是一个重言式时 称A蕴含B 记作A B 13 性质2 A B C为任意命题公式 若A B B C 则A C 蕴含关系可传递 证明 因为A B B C 所以 A B 和 B C 为重言式 即永真 所以 A B B C 永真 为重言式 由P21中第11个公式 可得 A B B C A C 由性质1可以 得 A C 也永真 即为重言式 因此 A C T A B B C A C 14 性质3 A B C为任意命题公式 若A B A C 则A B C 两个蕴含式结论的合并 证 若A B A C 即A B A C永真 则 A B A C 为永真 为重言式 A B A C A B A C A B C A B C所以 A B C永真 为重言式 即A B C 15 性质4 A B C为任意命题公式 若A B且C B 则A C B 两个蕴含式前提的合并 证 若A B且C B 即A B C B永真 则 A B C B 为永真 A B C B A B C B A C B A C B A C B所以A C B永真 即是重言式 即A C B 等价式与蕴含式的关系 P Q P Q Q P 17 等价式与蕴含式之间的关系 定理1 5 4设A B为任意两个命题公式 A B的充分必要条件是A B且B A 证明 1 证明 若A B 则A B且B A 若A B 则A B为重言式 即永真 因为A B A B B A 故A B和B A永真 即为重言式 即A B B A成立 2 若A B且B A 则A B 若A B且B A 则A B和B A是重言式 因此 A B B A 是重言式 即A B是重言式 故A B A B A B B A 小结 蕴含式的定义 重要的蕴含式 蕴含式的性质 重点 重要的蕴含式 作业 第23页 1 a b 3 4 9 等价式和蕴含式的关系 认识世界的渐进过程 数理逻辑的主要任务是借助于数学的方法来研究推理的逻辑 推理是从前题推出结论的思维过程 前提是已知的命题公式 结论是从前题出发应用推理规则推出的命题公式 推理理论 如果甲在河南工业大学上学 则甲在郑州上大学 甲在河南工业大学上学 则可推出甲在郑州上大学 若x 0 则x b b 已知a 0 所以 a b b P Q P Q是否为重言式 21 1 有效结论 或逻辑结论 定义1 8 1设A和C是两个命题公式 当且仅当A C为一重言式 即A C 称C是A的有效结论 或C可由A逻辑地推出 该定义可推广到有n个前提的情况 即令H1 H2 Hn是已知的命题公式 前提 若有H1 H2 Hn C则称C是H1 H2 Hn的有效结论 简称结论 实际上 推理的过程就是证明蕴含式的过程 判断有效结论的常用方法即蕴含式证明方法 怎样证明公式是蕴含式 23 一 真值表法 设P1 P2 Pn是出现于前提H1 H2 Hn和结论C中的全部命题变元 假定对P1 P2 Pn作全部的真值指派 就能确定H1 H2 Hn和C的所有真值 列出真值表 判断 1 由前提 前件 为真是否能得到结论 后件 也为真 查看所有H1 H2 Hn都具有真值T的行 表示前提为真的行 如果在每一个这样的行中 C也具有真值T 则C是H1 H2 Hn的逻辑结果 2 由结论 后件 为假 是否能得到前提 前件 为假 查看所有C具有真值为F的行 表示结论为假的行 如果在每一个这样的行中 H1 H2 Hn中至少有一个公式的真值为F 前提也为假 则C是H1 H2 Hn的逻辑结果 缺点 变元多时 列真值表不实际 例如 用真值表法证明 P P Q Q 可以看出 P P Q的真值都为T的情况为第三行 而第三行中Q的真值为T 故有 P P Q Q或者后件Q真值为F的情况为第二和第四行 P和P Q中至少有一个为F 25 二 证明法 在数理逻辑中 从前提推导出结论 要依据事先提供的公认的推理规则 下面先介绍两个推理规则 P规则 前提引入规则 在推理过程中 可以随时引入前提 T规则 结论引入规则 在推理过程的任何步骤上得到的结论都可以在其后的证明中引用 规范化形式重要等价式和蕴含式三种证明的方法 26 一 规范化的形式 可用3列若干行构成的一张表来表示 序号公式理由 注释行 1 B1或P 2 B2或T 序号 3 B3或E 序号 或I 序号 注意 并非B1 B2 B3Bi的获取 前提 中间结论前提 P 结论 T 推理规则 I 等价公式 E 推理的过程实际上是证明条件式是重言式的过程 只不过证明的过程采用另外一种书写格式 27 二 重要的蕴含式 如教材第43页所示 I1 P Q PI2 P Q QI3 P P QI4 Q P QI5 P P QI6 Q P QI7 P Q PI8 P Q QI9 P Q P QI10 P P Q QI11 P P Q QI12 Q P Q PI13 P Q Q R P RI14 P Q P R Q R RI15 A B A C B C I16 A B A C B C 在推理过程中 还要应用教材43页表1 8 3中的蕴含式I1 I16和表1 8 4中等价公式E1 E22 常用的公式要熟记 28 重要的等价公式 对合律E1 P P交换律E2P Q Q PE3P Q Q P结合律E4P Q R P Q RE5P Q R P Q R分配律E6P Q R P Q P R E7P Q R P Q P R 德 摩根定律E8 P Q P QE9 P Q P Q幂等律E10P P PE11P P P同一律E12P F PE13P T P吸收律P P Q PP P Q P互补律P P TP P F 29 重要的等价公式 零律E14P T TE15P F FE16P Q P QE17 P Q P QE18P Q Q PE19P Q R P Q RE20P Q P Q Q P E21P Q P Q P Q E22 P Q P QP Q P Q P Q 三 证明方法1 直接证法2 间接证法 1 CP规则法 2 反证法 31 1 直接证法 直接推理 由一些前提 利用一些公认的推理规则 根据已知等价或蕴含公式 推演得到有效的结论 针对的情况 前提 H1 H2 Hn结论 C 32 例题 求证P Q Q R P R 证明序号公式理由 注释行 P P Q Q 1 PP 2 P QP 3 QT 1 2 I 4 Q RP 5 RT 3 4 I P P Q Q 33 例题 求证 P Q Q R R P P P Q Q P P Q Q P Q P Q 1 Q RP 2 RP 3 QT 1 2 I 4 P Q P 5 P QT 4 E 6 PT 3 5 I 前提 P Q Q R R结论 P 34 例题 用命题逻辑推理方法证明下面推理的有效性 如果我学习 那么我数学不会不及格 如果我不热衷于玩扑克 那么我将学习 但是我数学不及格 因此 我热衷于玩扑克 解 设P 我学习 Q 我数学及格 R 我热衷于玩扑克 于是符号化为 P Q R P Q R 35 证明 P Q R P Q R 1 P QP 2 QP 3 PT 1 2 I 4 R PP 5 RT 3 4 I 6 RT 5 E I Q P Q P E R R 36 例题 求证P Q S R P Q R S P Q Q R P R P Q P Q P Q Q P P Q R P Q R P P Q Q 证明 1 P Q S P 2 P Q S T 1 E 3 P S Q T 2 E 4 P S QT 3 E 5 QP 6 P ST 4 5 I 7 P ST 6 E 8 R PP 9 R PT 8 E 10 R ST 7 9 I 37 2 间接证法 1 条件论证法 CP规则法 2 反证法 1 条件论证法 CP规则法 该定理也称为CP规则 针对情况 前提 H1 H2 Hn结论 R C 解决方法 39 1 条件论证 CP规则 A B C 则 A B C是重言式 根据公式E19 P Q R P Q R 得A B C 是重言式 所以 A B C A B C A B C 问题 由 A B C可以得到A B C 吗 40 1 条件论证 CP规则 定理1 8 1如果H1 H2 Hn R C 则H1 H2 Hn R C 自学 证明 因为H1 H2 Hn R C则 H1 H2 Hn R C是重言式 根据结合律得 H1 H2 Hn R C是重言式 根据公式E19 P Q R P Q R得 H1 H2 Hn R C 是重言式 即H1 H2 Hn R C定理得证 该定理也称为CP规则 重要依据 P Q R P Q R 41 例题 用条件论证 证明例题 P Q S R P Q R S 证明 1 RP 附加前提 2 R PP 3 PT 1 2 I 4 P Q S P 5 Q ST 3 4 I 6 QP 7 ST 5 6 I 8 R SCP与例题 相比 因为它增加了一个附加前提 所以推理就容易些 思路 前提 P Q S R P Q结论 R S将结论中的前项R引入到前提集 最后证明推导出S R就是附加前提 42 例题 用命题逻辑推理方法证明下面推理的有效性 如果体育馆有球赛 青年大街交通就拥挤 在这种情况下 如果小王不提前出发 就会迟到 因此 小王没有提前出发也未迟到 则体育馆没有球赛 证明 先将命题符号化 设P 体育馆有球赛 Q 青年大街交通拥挤 R 小王提前出发 S 小王迟到 P Q Q R S R S P 43 P Q Q R S R S P 证明 1 R SP 附加前提 2 RT 1 I 3 ST 1 I 4 Q R SP 5 Q T 3 4 I 6 Q RT 5 E 7 QT 2 6 I 8 P QP 9 PT 7 8 I 10 R S PCP 2 反证法 针对这种情况 前提 H1 H2 Hn结论 C 解决方法 45 下面先介绍有关概念和定理 相容与不相容的定义 定义1 8 2 设H1 H2 Hn是命题公式 P1 P2 Pm是公式中的命题变元 不相容的 若H1 H2 Hn为永假式 则称公式集合 H1 H2 Hn 是不相容的 也称是不一致的 相容的 若H1 H2 Hn不为永假式 称为相容的 也称是一致的 说明 H1 H2 Hn为永假式 即H1 H2 Hn R R R可为任意公式 46 问题 解 设A B是矛盾式 则 A B 是重言式 A B A B A B是个重言式 所以A B A B是矛盾式 A B 由A B是矛盾式 可以得到A B吗 47 定理1 8 2若要证明相容的公式集合 H1 H2 Hn 可以推出公式C 只要证明H1 H2 Hn C是不相容的 矛盾式 即可 自学 含义 若能证明H1 H2 Hn C是矛盾式 则H1 H2 Hn C 证明 设H1 H2 Hn C是矛盾式 则 H1 H2 Hn C 是个重言式 而 H1 H2 Hn C H1 H2 Hn C H1 H2 Hn C是个重言式 所以H1 H2 Hn C 1 SP 假设前提 2 ST 1 E 3 P S P 4 P ST 3 E 5 PT 2 4 I 6 P QP 7 QT 5 6 I 8 Q R RP 9 Q RT 8 I 10 RT 8 I 11 RT 7 9 I 12 R RT 10 11 I 例 P Q Q R R P S S 补充题 请根据下面事实 找出凶手 1 清洁工