命题逻辑2.ppt

命题逻辑的推理理论  公式的蕴涵关系 重言蕴涵式 形式证明 直接证明法 间接证明法 附加前提证明法 归谬法 3.1 命题逻辑的推理理论 一、推理 推理是由已知的命题得到新命题的思维过程。 定义 设A和B是两个命题公式，如果命题公式A?B为重言式，记为A?B，则称B是前提A的结论或从A推出结论B。一般地，设H1，H2，…,Hn和C是一些命题公式,若蕴涵式 H1∧H2∧…∧Hn ? C 成立，则称C是前提集合{ H1，H2，…,Hn}的结论，或称从前提H1，H2，…,Hn能推出结论C。有时也记作H1，H2，…,Hn ? C 　1、真值表法 对于命题公式 　　　中所有命题变元的每一组真值指派作出该公式的真值表，看是否为永真。 p q 0 0 0 1 1 0 1 1 解 构造其真值表如下： p→q （p→q）∧p ( ( p→q )∧p ) →q 1 0 1 1 0 1 0 0 1 1 1 1 例 考察结论C是否是下列前提H1，H2的结论。 （1）H1：p→q，H2：p，C：q 二、如何判断由一个前提集合能否推出某个结论 （2）H1：p→q， H2：? p ， C：? q 解 构造其真值表如下： ?p ?q p→q （p→q）∧?p 1 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 (（p→q）∧?p) →?q 1 0 1 1 p q 0 0 0 1 1 0 1 1 在这里，我们没有关心结论是真还是假，而主要关心由给定的前提是否能推出这个结论来。 　　 2、等值演算方法 　例 证明 　　分析　　根据题意，需证明 证明 重要的重言蕴涵式及其名称 1.A ?(A∨B) ?????????????????????? ??????附加律 2.(A∧B) ? A ????????????????????????????? 化简律 3.(A→B)∧A ? B ?????????????????????????? 假言推理 4.(A→B)∧┐B ? ┐A ????????????? ????? ???拒取式 5.(A∨B)∧┐B ? A ??????????????????????? ?析取三段论 6.(A→B)∧(B→C) ?(A→C) ?????????? ?? ???假言三段论 7.(A ? B)∧(B ? C) ?(A ? C) ?????????? ?等价三段论 8.(A→B)∧(C→D)∧(A∨C) ?(B∨D)??? ????? 构造性二难  (A→B)∧(┐A→B)∧(A∨┐A) ? B?? ??????? (特殊形式) 9.(A→B)∧(C→D)∧(┐B∨┐D)? ?(┐A∨┐C) ???????????????????????????破坏性二难 3、“形式证明”方法 （1）基本术语 形式证明：一个描述推理过程的命题序列，其中每个 命题或者是已知的命题，或者是由某些前提所推得的结论， 序列中最后一个命题就是所要求的结论，这样的命题序列称 为形式证明。 有效的证明：如果证明过程中的每一步所得到的结论 都是根据推理规则得到的，则这样的证明称作是有效的。 有效的结论：通过有效的证明而得到结论，称作是有效的结论。 合理的证明：一个证明是否有效与前提的真假没有关系。如果所有的前提都是真的，那么通过有效的证明所得到的结论也是真的。这样的证明称作是合理的。 合理的结论：一个结论是否有效与它自身的真假没有关 系。通过合理证明而得到的结论称作合理的结论。 ( 2) 推理规则  前提引入规则：在证明的任何步骤上都可以引用前提。 结论引入规则：在证明的任何步骤上所得到的结论都可以在其后的证明中引用。 置换规则：在证明的任何步骤上，命题公式的子公式都可以用与它等值的其它命题公式置换。 推理规则 1.A |=(A∨B) ?????????????????????? ??????附加规则 2.(A∧B) |= A ????????????????????????????? 化简规则 3.(A→B)∧A |= B ?????????????????????????? 假言推理规则 4.(A→B)∧┐B |= ┐A ????????????? ????? ???拒取式规则 5.(A∨B)∧