离散数学PPT电子教案-第05章_推理与证明技术.ppt

第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 的逻辑结果。记为 G1, G2, …,Gn ?Ｈ, 此时, 称 G1, G2, …,Gn ?Ｈ为有效的。 G1, G2, …,Gn 称为一组前提，有时用集合Г来表示, 记Г= {G1, G2, …,Gn}; H称为结论, 它是前提集合的逻辑结果。记为 Г ? H。 判定定理 定理5.2.1 G1, G2, …,Gn ?Ｈ 当且仅当 G1∧G2∧…∧Gn→Ｈ 为永真公式。 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 推理定律 I1-I15 设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　(假言三段论) 例子(续) 3)、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得 前提: 1. 凶手为王某或陈某;。 P∨Q 2. 如果王某是凶手, 则他在作案当晚必外出; P→R 3.王某案发之晚并未外出。 ┐R 结论：陈某是凶手。 Q 则可描述为：P→R, ┐R ? ┐P (否定后件式) P∨Q, ┐P ? Q (选言三段论) 3 演绎法 演绎法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。 推理规则 在数理逻辑中，主要的推理规则有： ① P 规则 (称为前提引用规则)：在推导的过程中，可随时引入前提集合中的任意一个前提； ② 规则 T (逻辑结果引用规则)：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。 ③ 规则 CP (附加前提规则)：如果能从给定的前提集合Г与公式P推导出S，则能从此前提集合Г推导出 P→S。 演绎的定义 定义5.2.2 从前提集合Г推出结论H的一个演绎是构造命题公式的一个有限序列： H1，H2，……，Hn 其中，Hi 或者是Г中的某个前提，或者是前面的某些Hj（ji）的有效结论，并且Hn就是H，则称公式H为该演绎的有效结论，或者称从前提Г能够演绎出结论H来。 例5.2.2 证明1 ⑴　P∨Q　　　　　 P ⑵　┐P→Q　　　　 T,(1),E ⑶　Q→S　　　　 　P 　 ⑷　┐