离散数学---推理理论ppt课件

1 6推理理论 一 有效论证推理规则二 基本蕴涵式三 自然推理系统P四 推理证明的方法 一 有效论证与推理规则 定义 A1 A2 An A 其为永真式 则称由前提A1 A2 An得到有效结论A 从前提公式得到有效结论的过程称为正确推理 若A B是永真式 则记为A B 若A B是永真式 则记为A B 前提一致和不一致 如果前提A1 A2 An为可满足式 则称为前提A1 A2 An一致 实例分析 判断推理是否正确 张红不管有无空闲都不看电影 张红看了电影 所以张红有空闲时间又没有空闲时间 解 P 张红有空闲时间 Q 张红看电影 前提 A1 P P QA2 Q结论 A P P问题 该结论是否有效结论 该推理是否正确 所以 结论A是有效结论 该推理是正确的 而前提是不一致的 基本蕴涵式 A B B A的证明 法一 真值表法 A B B的证明 第三种方法 自然推理系统P 形式系统 自然推理系统 公理系统 特点 只能从几个给定的公理出发 应用系统中的推理规则进行推演 得到的结论是系统中的定理 特点 可以从任意给定的前提出发 应用系统中的推理进行推演 得到的结论在系统中被认为是有效的 自然推理系统P 自然推理系统P定义如下 1 字母表 1 命题常元 命题变元 P Q R Pi Qi 1 0 T F 2 命题联结词 3 括号 2 合式公式 略 3 推理规则 1 前提引入规则 P规则 在证明的任何步上 都可引入前提 2 结论引用规则 T规则 在证明的任何步上 所得的结论都可作为证明得前提 3 置换规则 在证明的任何步上 命题公式的任何子命题公式都可以用与之等价的命题公式置换 4 永真蕴涵规则 使用基本蕴涵式 常常将条件用 分开 基本蕴涵式证明的另一种方法 A B B的证明证明 A B A B A B A B B 简化式 A B B的证明 推理过程的证明形式 规范化的形式 序号公式理由 B1E或I或P或 的合取或cp B2 B3 注意 1 并非B1 B2 B32 Bi的获取 前提 中间结论 构造下列的推理的证明 前提 P Q P R S M S R M结论 Q 证 MP S MP S I拒取式 S RP R I假言推理 P RP P I拒取式 P QP Q I析取三段式 一公安人员审查一件案件 一致的事实如下 1 张三或李四盗窃了录像机 2 如果张三盗窃了录像机 则作案时间不能在午夜前 3 如果李四证词正确 则午夜时屋内灯光未灭 4 如果李四证词不正确 则作案时间在午夜前 5 午夜时屋内灯灭了 MP S MP S I拒取式 S RP R I假言推理 P RP P I拒取式 P QP Q I析取三段式 解 将已知事实符号化 设P 张三盗窃录像机 Q 李四盗窃录像机 R 作案时间发生在午夜前 S 李四证词正确 M 午夜时灯光未灭 则前提为 1 P Q 2 P R 3 S M 4 S R 5 M 结论未定 所以 可以得出是李四盗了录像机 例如 前提 p r s q p s结论 q 证明 pp规则 p r s q p规则 r s q I sp规则 s r I r s E q I 演示文稿后等 八达国际官网八达国际官网汆莒旻 推理证明的方法 前提的合取 结论是永真式 间接证明法 推理证明 演绎证明 归纳证明 直接证明法 附加前提证法 CP 归谬法 反证法 附加前提证法 CP 针对这种情况 前提 A1 A2 An结论 A B 前提 A1 A2 An A结论 B 例 前提 P P Q R S 结论 Q S 证明 1 Pcp规则 2 P Q R S cp规则 3 Q R S 1 2 I 4 Qcp规则 5 R S 3 4 I 6 S 5 I 课堂作业 前提 P Q R S P Q结论 S R 归谬法 反证法 针对这种情况 前提 A1 A2 An结论 A 前提 A1 A2 An A结论 0 F 例 前提 R Q R S S Q P Q结论 P 证明 P 否定结论引入 CP规则 P E P Q