命题逻辑的推理理论5.ppt

命题逻辑的推理理论 福建师范大学数学与计算机科学学院 数理逻辑的主要任务是用数学的方法来研究数学中的推理。 推理是指从前提出发推出结论的思维过程。 前提是已知命题公式集合。 结论是从前提出发应用推理规则推出的命题公式。 证明是描述推理正确或错误的过程。 要研究推理，首先应该明确什么样的推理是有效的或正确的。 有效推理的定义 定义1.24 设A1,A2,…,Ak和B都是命题公式，若对于A1,A2,…,Ak和B中出现的命题变项的任意一组赋值，（1）或者A1∧A2 ∧…∧Ak为假;（2）或者当A1∧A2 ∧…∧Ak为真时，B也为真;则称由前提A1,A2,…,Ak推出B的推理是有效的或正确的，并称B是有效结论。 关于有效推理的说明 ?＝{A1，A2，…，Ak}由 ?推B的推理记为┣B若推理是正确的，记为 ? ╞ B若推理是不正确的，记为 ? B ?(1) {p,p→q}├ q ?(2) {p,q→p}├ q 推理的形式结构 ?={ A1, A2, …, Ak}，记为?┣B。 A1?A2?…?Ak?B 前提： A1, A2, … , Ak 结论： B 判断推理是否正确的方法 例题 下午马芳或去看电影或去游泳。她没去看电影，所以，她 去游泳了。 推理定律--重言蕴含式 (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)??? ????? 构造性二难 (9)(A→B)∧(C→D)∧(┐B∨┐D) ?(┐A∨┐C) 破坏性二难 关于推理定律的几点说明 A,B,C为元语言符号，代表任意的命题公式。 若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。 1.3节给出的24个等值式中的每一个都派生出两条推理定律。例如双重否定律A?? ?A产生两条推理定律A?? ?A和? ?A?A。 由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则。 构造性证明方法 判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。 当推理中包含的命题变项较多时，上述三种方法演算量太大。 对于由前提A1,A2,…,Ak推B的正确推理应该给出严谨的证明。 证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。 常用的推理规则 （1）前提引入规则：在证明的任何步骤上， 都可以引入前提。 （2）结论引入规则：在证明的任何步骤上，所证明的结论都可以作为后续证明的前提。 （3）置换规则：在证明的任何步骤上，命题公式中任何子命题公式都可以用与之等价的命题公式置换。 （4）假言推理规则 A?B A ? B （5）附加规则 A ? A?B （6）化简规则 A?B ?A （7）拒取式规则 A?B ?B  ? ?A （8）?假言三段论规则 A?B B?C  ? A?C （9）析取三段论规则 A?B ?B ? A （10）构造性二难推理规则 A?B C?D A?C ? B?D （11）破坏性二难推理规则 A?B C?D ?B??D ? ?A??C （12） 合取引入规则 A B ? A?B 构造证明 构造证明就是由一组公式作为前提，利用自然推理系统中的规则，推出结论。 构造形式结构A1?A2?…?Ak ? B 的推理的书写方法：前提： A1,A2,…,Ak 结论： B 证明方法： 直接证明法 附加前提法 归谬法（或称反证法） 例3.1 构造下面推理