数据结构课件_第5章_推理与证明技术.ppt

第5章 推理与证明技术 1.1 本章学习要求 5.2 命题逻辑的推理理论 推理的有效性和结论的真实性 有效的推理不一定产生真实的结论；而产生真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提，而无效的推理却可能得到为“真”的结论 。 5.2.1 推理的基本概念和推理形式 定义5.2.0 设G,H是公式，对任意解释I，如果I满足G，那么I满足H，则称H是G的逻辑结果(或称G蕴涵H),记为G?Ｈ，此时称G为前提，H为结论。 判定定理 定理5.2.0 设G,H是公式，H是G的逻辑结果当且仅当G→Ｈ为永真公式。 推广 定义5.2.1 设G1,G2,…,Gn,H是公式，称H是G1,G2,…, Gn的逻辑结果(G1,G2,…,Gn共同蕴涵H),当且仅当H是G1∧G2∧…∧Gn的逻辑结果(logic conclusion)。记为G1,G2,…,Gn?Ｈ，此时称G1,G2,…,Gn?Ｈ为有效的(efficacious),否则称为无效的(inefficacious)。G1,G2,…,Gn称为一组前提(Premise),有时用集合Г来表示，记Г={G1,G2,…,Gn}。H称为结论(conclusion)。又称H是前提集合Г的逻辑结果。记为Г?H。 判定定理 定理5.2.1 公式H是前提集合Г={G1,G2,…,Gn}的逻辑结果当且仅当G1∧G2∧…∧Gn→Ｈ为永真公式。 “?”与“→”的不同 1.“→”仅是一般的蕴涵联结词，G→H的结果仍是一个公式，而“?”却描述了两个公式G，H之间的一种逻辑蕴涵关系，G ? H的“结果”，是非命题公式； 5.2.2 判断有效结论的常用方法 1、真值表技术 设P1,P2,…,Pn是出现在前提G1,G2,…,Gn和结论H中的一切命题变元，如果将P1,P2,…,Pn中所有可能的解释及G1,G2,…,Gn，H的对应真值结果都列在一个表中，根据“→”的定义，则有判断方法如下： 例5.2.1 判断下列H是否是前提G1,G2的逻辑结果 (1)　H：Q； G1：P；G2：P→Q；　 (2)　H：┐P； G1：P→Q；G2：┐Q； (3)　H：Q； G1：┐P；G2：P→Q。 2 推理定律 设G，H，I，J是任意的命题公式，则有： 2 推理定律(续) I10：┐G，G∨H?H (选言三段论) I11：┐G，G H?H I12：G，G→H?H (分离规则) I13：┐H，G→H?┐G (否定后件式) I14：G→H，H→I?G→I (假言三段论) I15：G∨H，G→I，H→I?I (二难推论) 例子 1)、前提： 　1.　如果明天天晴，我们准备外出旅游。 P→Q 　2．明天的确天晴。　　　　　　　　 P 　　结论：我们外出旅游。　　　　 Q 　可描述为：P→Q，P?Q　(分离规则) 2)、前提： 　1.　如果一个人是单身汉，则他不幸福。 P→Q 　2.　如果一个人不幸福，则他死得早。 Q→R 　　结论：单身汉死得早。 P→R 　可描述为：P→Q，Q→R?P→R　(假言三段论) 例子(续1) 3)、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得前提： 1.凶手为王某或陈某。 P∨Q 2.如果王某是凶手，则他在作案当晚必外出P→R 3.王某案发之晚并未外出。 ┐R 结论：陈某是凶手。 Q 则可描述为：P→R，┐R?┐P (否定后件式) P∨Q，┐P?Q (选言三段论) 例子(续2) 4)、前提： 1.如果某同学为省二级以上运动员，则他将被大学录取。 P→R 2.如果某同学高考总分在560分以上，则将被大学录取。 Q→R 3.某同学高考总分在560分以上或者是省二级运动员。 P∨Q 结论：该同学被大学录取。 R 则上述例子可描述为： P∨Q，P→R，Q→R?R　(二难推论) 3 演绎法 演绎法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。 演绎的定义 定义5.2.2 从前提集合Г推出结论H的一个演绎是构造命题公式的一个有限序列： H1，H2，……，Hn 其中，Hi或者是Г中的某个前提，或者是前面的某些Hj（ji）的有效结论，并且Hn就是H，则称公式H为该演绎的有效结论，或者称从前提Г能够演绎出结论H来。 推理规则 规则P（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提； 规则T（逻辑结果引用规则）：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。 规则CP（附加前提