离散数学课件03命题逻辑的推理理论.ppt

第3章命题逻辑的推理理论 离散数学 中国地质大学本科生课程 本章说明 本章的主要内容推理的形式结构自然推理系统P本章与后续各章的关系本章是第五章的特殊情况和先行准备 3 1推理的形式结构3 2自然推理系统P本章小结习题作业 3 1推理的形式结构 数理逻辑的主要任务是用数学的方法来研究数学中的推理 推理是指从前提出发推出结论的思维过程 前提是已知命题公式集合 结论是从前提出发应用推理规则推出的命题公式 证明是描述推理正确或错误的过程 要研究推理 首先应该明确什么样的推理是有效的或正确的 命题逻辑的推理理论 认识世界的渐进过程 定义3 1设A1 A2 Ak和B都是命题公式 若对于A1 A2 Ak和B中出现的命题变项的任意一组赋值 1 或者A1 A2 Ak为假 2 或者当A1 A2 Ak为真时 B也为真 则称由前提A1 A2 Ak推出B的推理是有效的或正确的 并称B是有效结论 有效推理的定义 关于有效推理的说明 A1 A2 Ak 由 推B的推理记为 B若推理是正确的 记为 B若推理是不正确的 记为 B 由前提A1 A2 Ak推结论B的推理是否正确与诸前提的排列次序无关 关于有效推理的说明 设A1 A2 Ak B中共出现n个命题变项 对于任何一组赋值 1 2 n i 0或者1 i 1 2 n 前提和结论的取值情况有以下四种 1 A1 A2 Ak为0 B为0 2 A1 A2 Ak为0 B为1 3 A1 A2 Ak为1 B为0 4 A1 A2 Ak为1 B为1 只要不出现 3 中的情况 推理就是正确的 因而判断推理是否正确 就是判断是否会出现 3 中的情况 推理正确 并不能保证结论B一定为真 1 p p q q 2 p q p q 例3 1判断下列推理是否正确 真值表法 例题 正确 不正确 定理3 1命题公式A1 A2 Ak推B的推理正确当且仅当 A1 A2 Ak B为重言式 该定理是判断推理是否正确的另一种方法 说明 有效推理的等价定理 定理3 1的证明 1 证明必要性 若A1 A2 Ak推B的推理正确 则对于A1 A2 Ak B中所含命题变项的任意一组赋值 不会出现A1 A2 Ak为真 而B为假的情况 因而在任何赋值下 蕴涵式 A1 A2 Ak B均为真 故它为重言式 2 证明充分性 若蕴涵式 A1 A2 Ak B为重言式 则对于任何赋值此蕴涵式均为真 因而不会出现前件为真后件为假的情况 即在任何赋值下 或者A1 A2 Ak为假 或者A1 A2 Ak和B同时为真 这正符合推理正确的定义 当推理正确时 形式 1 记为 B 形式 2 记为A1 A2 Ak B 表示蕴涵式为重言式 设 A1 A2 Ak 记为 B A1 A2 Ak B前提 A1 A2 Ak结论 B 说明 推理的形式结构 判断有效结论的常用方法 真值表法等值演算法主析取范式法 判断推理是否正确的方法 是否有其他的证明方法 思考 当命题变项较少时 这三种方法比较方便 说明 1 下午马芳或去看电影或去游泳 她没去看电影 所以 她去游泳了 例3 2判断下列推理是否正确 等值演算法 解 设p 马芳下午去看电影 q 马芳下午去游泳 前提 p q p结论 q推理的形式结构 p q p q p q p q p q p q p q p q p p q p q q p q 1 由定理3 1可知 推理正确 例题 1 A A B 附加律 2 A B A化简律 3 A B A B假言推理 4 A B B A拒取式 5 A B B A析取三段论 6 A B B C A C 假言三段论 7 A B B C A C 等价三段论 8 A B C D A C B D 构造性二难 A B A B A A B构造性二难 特殊形式 9 A B C D B D A C 破坏性二难 推理定律 重言蕴含式 小节结束 关于推理定律的几点说明 A B C为元语言符号 代表任意的命题公式 若一个推理的形式结构与某条推理定律对应的蕴涵式一致 则不用证明就可断定这个推理是正确的 2 1节给出的24个等值式中的每一个都派生出两条推理定律 例如双重否定律A A产生两条推理定律A A和 A A 由九条推理定律可以产生九条推理规则 它们构成了推理系统中的推理规则 3 2自然推理系统P 判断推理是否正确的三种方法 真值表法 等值演算法和主析取范式法 当推理中包含的命题变项较多时 上述三种方法演算量太大 对于由前提A1 A2 Ak推B的正确推理应该给出严谨的证明 证明是一个描述推理过程的命题公式序列 其中的每个公式或者是前提 或者是由某些前提应用推理规则得到的结论 中间结论或推理中的结论 要构造出严谨的证明就必须在形式系统中进行 自然推理系统P 自然推理系统P由下述3部分组成 1 字母表 1 命题变项符号 p q r pi qi ri 2 联结词 3 括号与逗号 2 合式公式3 推理规则 1 前提引入规则 2 结论引入规则 3 置换规则 自然推理系统的定义 4 假言推理规则A BA B 5 附加规则A A B 6 化简规则A B A 4 若今天下雪 则将去滑雪 今天下雪 所以去滑雪 5 现在气温在冰点以下 因此 要么现在气温在冰点以下 要么现在下雨 6 现在气温在冰点以下并且正在下雨 因此 现在气温在冰点以下 自然推理系统的定义 7 拒取式规则A B B A 8 假言三段论规则A BB C A C 9 析取三段论规则A B B A 自然推理系统的定义 10 构造性二难推理规则A BC DA C B D 11 破坏性二难推理规则A BC D B D A C 12 合取引入规则AB A B 在自然推理系统P中构造证明 P中构造证明就是由一组P中公式作为前提 利用P中的规则 推出结论 构造形式结构A1 A2 Ak B的推理的书写方法 前提 A1 A2 Ak结论 B证明方法 直接证明法附加前提法归谬法 或称反证法 命题逻辑推理的难点 弄清楚蕴涵式P Q的逻辑关系及其真值 这里Q是P的必要条件 无论蕴涵关系如何表述 都要仔细地区分出蕴涵式的前件和后件 推理过程中推理规则 基本等值式和逻辑蕴涵式的引用要适当 逻辑思维要清晰 弄清楚几种推理方法的区别与联系 对于命题逻辑推理而言 任何一个问题的推理 都可以采取三种推理方法中的任何一种来证明 针对不同的问题选用不同的推理方法 一般而言 对于结论是蕴涵式或析取式的 大多可以采取带附加前提的直接证明方法 例题 例3 3在自然推理系统P中构造下面推理的证明 前提 p q r q r s结论 p s p q前提引入 p q 置换 r q前提引入 q r 置换 p r 假言三段论 r s前提引入 p s 假言三段论 例题 例3 3在自然推理系统P中构造下面推理的证明 前提 p q r p q结论 r s p q r 前提引入 p q前提引入 p 化简 q 化简 q r 假言推理 r 假言推理 r s 附加 r s 置换 例题 例3 4在自然推理系统P中构造下面推理的证明 若数a是实数 则它不是有理数就是无理数 若a不能表示成分数 则它不是有理数 a是实数且它不能表示成分数 所以a是无理数 构造证明 1 将简单命题符号化 设p a是实数 q a是有理数 r a是无理数 s a能表示成分数 2 形式结构 前提 p q r s q p s结论 r p s前提引入 p 化简 s 化简 p q r 前提引入 q r 假言推理 s q前提引入 q 假言推理 r 析取三段论 例题 例题 例3 5在自然推理系统P中构造下面推理的证明 如果小张和小王去看电影 则小李也去看电影 小赵不去看电影或小张去看电影 小王去看电影 所以 当小赵去看电影时 小李也去看电影 构造证明 1 将简单命题符号化 设p 小张去看电影 q 小王去看电影 r 小李去看电影 s 小赵去看电影 例题 2 形式结构 前提 p q r s p q结论 s r 3 证明 用附加前提证明法 s附加前提引入 s p前提引入 p 析取三段论 p q r前提引入 q前提引入 p q 合取 r 假言推理 例题 例3 6在自然推理系统P中构造下面推理的证明 如果小张守第一垒并且小李向B队投球 则A队将取胜 或者A队未取胜 或者A队获得联赛第一名 A队没有获得联赛的第一名 小张守第一垒 因此 小李没有向B队投球 构造证明 1 将简单命题符号化 设p 小张守第一垒 q 小李向B队投球 r A队取胜 s A队获得联赛第一名 2 形式结构 前提 p q r r s s p结论 q 例题 3 证明 用归谬法 q结论的否定引入 r s前提引入 s前提引入 r 析取三段论 p q r前提引人 p q 拒取式 p q 置换 p前提引入 q 析取三段论 q q 合取由于最后一步为矛盾式 所以推理正确 小节结束 本章主要内容 推理的形式结构 推理的前提 推理的结论 推理正确判断推理是否正确的方法 真值表法 等值演算法 主析取范式法对于正确的推理 在自然推理系统P中构造证明 自然推理系统P的定义 自然推理系统P的推理规则 附加前提证明法 归谬法 本章学习要求 理解并记住推理的形式结构的三种等价形式 即 A1 A2 Ak B A1 A2 Ak B 前提 A1 A2 Ak结论 B在判断推理是否正确时 用 在P系统中构造证明时用 熟练掌握判断推理是否正确的三种方法 真值表法 等值演算法 主析取范式法 牢记P系统中的各条推理规则 对于给定的正确推理 要求在P系统中给出严谨的证明序列 会用附加前提证明法和归谬法 小节结束 习题 1 用不同的方法验证下面推理是否正确 对于正确的推理还要在P系统中给出证明 1 前提 p q q结论 p 2 前提 q r p r结论 q p 1 不正确 验证答案 只需证明 p q q p不是重言式 方法一等值演算 p q q p p q q p p q q p p q q q p p q易知10是成假赋值 故 p q q p不是重言式 所以推理不正确 方法二主析取范式法经过演算后可知 p q q p m0 m1 m3未含m2 故 p q q p不是重言式 方法三直接观察出10是成假赋值 方法四真值表法 p q q p的真值表为 结论 不正确 是对的 2 推理正确方法一真值表法 自己做 方法二等值演算法 自己做 方法三主析取范式法 自己做 方法四P系统中构造证明证明 直接证明法 p r 前提引入 r p 置换 q r 前提引入 q p 假言三段论 2 在P系统中构造下面推理的证明 如果今天是周六 我们就到颐和园或圆明园玩 如果颐和园游人太多 就不去颐和园 今天是周六 并且颐和园游人太多 所以我们去圆明园或动物园玩 构造证明 1 设p 今天是周六 q 到颐和园玩 r 到圆明园玩 s 颐和园游人太多 t 到动物园玩 2 前提 p q r s q p s结论 r t 3 证明 p q r 前提引入 p前提引入 q r 假言推理 s q前提引入 s前提引入 q 假言推理 r 析取三段论 r t 附加 小节结束 例子 续1 3 某女子在某日晚归家途中被杀害 据多方调查确证 凶手必为王某或陈某 但后又查证 作案之晚王某在工厂值夜班 没有外出 根据上述案情可得前提 1 凶手为王某或陈某 P Q2 如果王某是凶手 则他在作案当晚必外出P R3 王某案发之晚并未外出 R结论 陈某是凶手 Q则可描述为 P R R P 否定后件式 P Q P Q 选言三段论 例4 一个公安人员审查一件盗窃案 已知的事实如下 A或B盗窃了x 若A盗窃了x 则作案时间不能发生在午夜前 若B证词正确 则在午夜时屋里灯光未灭 若B证词不正确 则作案时间发生在午夜前 午夜时屋里灯光灭了 B盗窃了x 设P A盗窃了x Q B盗窃了x R 作案时间发生在午夜前 S B证词正确 T 在午夜时屋里灯光未灭 则上述命题可符号化为 P Q P R S T S R T Q 例4 续 证明1采用直接证明方法 反证法请学生完成 1 T前提引入 2 S T前提引入 3 S 1 2 拒取式 4 S R前提引入 5 R 3 4 假言推理 6 P R前提引入 7 P 5 6 拒取式 8 P Q前提引入 9 Q 7 8 析取三段论 分析 令P 马会飞 Q 羊吃草 R 母鸡是飞鸟 S 烤熟的鸭子还会跑 符号化上述语句为 P Q R R S S G Q 证明 G 如果马会飞或羊吃草 则母鸡就会是飞鸟 如果母鸡是飞鸟 那么烤熟的鸭子还会跑 烤熟的鸭子不会跑 所以羊不吃草 例5 例5证明 S前提引入 R S前提引入 R 拒取式 P Q R前提引入 P Q 拒取式 P Q 置换 Q 化简 思考题 考试佯谬 逻辑课老师在周末放学时对学生说 条件一 下周要进行一次考试 条件二 到底哪天考试 你们在考试之前的任何一天都不能确知 注 每周上课5天 周一至周五 每天都上一节逻辑课 只有在逻辑课时才可能考试 一个聪明的学生运用逻辑知识做出了以下推理 推论一 周五不可能考试 考试时间一定是周一至周四的某一天 因为如果周一至周四都不考 那么周四下课时我们就事先知道了明天一定考试 这不符合条件二 但根据条件一 下周肯定考试 因此考试时间只能是周一至周四的某一天 周五可以排除 思考题 考试佯谬 推论二 周四也不可能考试 考试时间一定是周一至周三的某一天 因为如果周一至周三都不考 那么周三放学时我们就事先知道了明天考试 这不符合条件二 但根据条件一 下周肯定考试 因此考试时间只能是周一至周三的某一天 周四可以排除 推论三 周三也不可能考试 推理过程同上 推论四 周二也不可能考试 推理过程同上 推论五 周一也不可能考试 推理过程同上 结论 下周就不可能考试 思考题 考试佯谬 但是老师确实在下周的某一天考试了 这个聪明同学感到非常意外 问题究竟出在哪里呢 提示 将推理过程形式化不失一般性 考虑简化问题的版本 每周只有两次逻辑课 分别在周一和周四 教师在本周四下课时宣布下周将有一次逻辑考试 思考题 考试佯谬 考试佯谬的一个形式表述命题常元ExamB 考试在下周一的逻辑课上进行ExamD 考试在下周四的逻辑课上进行Know 学生在考试所在的那天之前知道考试的时间系统公理 A1 ExamB ExamD ExamB ExamD A2 KnowA3 ExamB KnowA4 ExamD Know 思考题 考试佯谬 论证过程 用间接证法1证明A1 A4和ExamD矛盾 推出 ExamD 再用间接证法1证明A1 A4和ExamB矛盾 推出 ExamB 1 1ExamD附加前提2 ExamB ExamD ExamB ExamD P3 ExamB ExamD ExamB ExamD T 2 4 ExamB ExamDT 3 5 ExamBT 1 4 6 ExamB KnowP7KnowT 5 6 8 KnowP所以 有 ExamD 思考题 考试佯谬 2 1ExamB附加前提2 ExamB ExamD ExamB ExamD P3 ExamB ExamD ExamB ExamD T 2 4 ExamB ExamDT 3 5 ExamDT 1 4 6 ExamD KnowP7KnowT 5 6 8 KnowP所有 有 ExamB综合 1 和 2 有 ExamB ExamD 思考题 考试佯谬 两个结论 1学生推理的没有错误2教师的两个条件符合事实 故应视为真命题问题 似乎正确的前提和正确的推理导致了错误的结论 即与教师宣称的真命题矛盾的结论 为什么 回答 佯谬之所以出现 是因为试图将一个广义哥德尔型命题 可粗略地理解为涉及系统元知识的命题 显式地作为系统公理 来建构系统的完备性 不幸的是 一旦这个原本是直觉真的广义哥德尔型命题在系统中被作为公理显式地表达出来 系统在一致性方面就产生了新的问题 Therearetruthsofsilence whenspoken nolongertrueanymore LudwigWittgenstein 形式化命题逻辑系统 考试佯谬这类逻辑悖论促使人们深入省思逻辑系统的本质 它的能力和局限 对形式化的逻辑系统的研究有助于实现这个目的 在理论方面 形式化逻辑系统帮助人们澄清逻辑系统的元性质 一致性 完全性 澄清基本的数学哲学问题 例如 数学是否可以形式化 希尔伯特方案 在应