推理与证明技术.PPTVIP

第5章 推理与证明技术 5.1 本章学习要求 5.2 命题逻辑的推理理论 推理的有效性和结论的真实性 有效的推理不一定产生真实的结论； 而产生真实结论的推理过程未必是有效的。 有效的推理中可能包含为“假”的前提， 而无效的推理却可能得到为“真”的结论 。 推理的有效性和结论的真实性 5.2.1 推理的基本概念和推理形式 定义5.2.1 设G1, G2, …,Gn,Ｈ是公式，称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 推理定律(续) 6）I10：┐G, G∨H ? H (选言/析取三段论) I11：┐G, G H ? H 7）I12：G, G→H ? H (分离规则) 8）I13：┐H, G→H ? ┐G (否定后件式) 9）I14：G→H, H→I ? G→I (假言三段论) 10）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 演绎法 演绎法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。 引入推理规则 在数理逻辑中，主要的推理规则有： ① P规则（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提； ② 规则Ｔ（逻辑结果引用规则）：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。 ③ 规则ＣＰ（附加前提规则）：如果能从给定的前提集合Г与公式P推导出S，则能从此前提集合Г推导出P→S。 演绎的定义 定义5.2.2 从前提集合Г推出结论H的一个演绎是指构造命题公式的一个有限序列： H1，H2，……，H