第5章推理与证明技术讲述.ppt

第5章 推理与证明技术 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→Ｈ为永真公式。 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 (二难推论) 3 演绎法 演绎法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。 演绎的定义 定义5.2.2 从前提集合Г推出结论H的一个演绎是构造命题公式的一个有限序列： H1，H2，……，Hn 其中，Hi或者是Г中的某个前提，或者是前面的某些Hj（ji）的有效结论，并且Hn就是H，则称公式H为该演绎的有效结论，或者称从前提Г能够演绎出结论H来。 推理规则 规则P（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提； 规则T（逻辑结果引用规则）：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。 规则CP（附加前提规则）：如果能从给定的前提集合Г与公式P推导出S，则能从此前提集合Г推导出P→S。 例5.2.2 证明1：⑴　P∨Q P 　 ⑵　┐P→Q T,(1),E 　 ⑶　Q→S P 　 ⑷　┐P→S T,⑵,⑶,I 　 ⑸　┐S→P T,⑷,E 　 ⑹　P?R P ⑺ (P→R)?(R→P) T,⑹,E ⑻ P→R T,⑺,I 　 ⑼ ┐S→R T,⑸,⑻,I 　 ⑽ S∨R T,⑺,E 例5.31(续) 证明2：⑴　┐S P(附加) ⑵　Q→S P ⑶　┐Q T,⑴,⑵,I ⑷　P∨Q P ⑸　P T,⑶,⑷,I ⑹ P?R P ⑺ (P→R)?(R→P) T,⑹,E ⑻ P→R T,⑺,I ⑼ R T,⑸,⑻,I ⑽ ┐S→R CP,⑴,⑼ ⑾ S∨R T,⑽,E 例5.2.3 证：⑴　R P(附加) 　　⑵　┐R∨P P 　　⑶　P T,⑴,⑵,I 　　⑷　P→(Q→S) P　 　　⑸　Q→S T,⑶,⑷,I 　　⑹　Q P 　　⑺　S T,⑸,⑹,I 　　⑻　R→S CP,⑴,⑺ 4 间接证明法(反证法) 前面使用过的一些证明方法都是正向推理。但在数学领域中，经常会遇到一些问题，当采用正向推理时很难从前提为真推出结论为真。 定义5.2.3 假设G1,G2,…,Gn是一组命题公式，P1,P2,…,P