一-3命题逻辑的推理理论.pptVIP

第3章 命题逻辑的推理理论 本章说明 第一节 推理的形式结构 数理逻辑的主要任务：是用数学的方法来研究 推理问题。 推理：是指从前提出发推出结论的思维过程。 前提：是已知命题公式的集合。 结论：是从前提出发应用推理规则推出的命题公式。 要研究推理，首先应该明确什么样的 推理是有效的或正确的。 有效推理的定义 定义3.1： 设A1,A2,…,Ak和B都是命题公式，若对于 A1,A2,…,Ak和B中出现的命题变项的任意一组赋值，（1）或者A1∧A2 ∧…∧Ak为假;（2）或者当A1∧A2 ∧…∧Ak为真时，B也为真;则称由前提A1,A2,…,Ak推出B的推理是有效的或正确的，并称B是有效结论。 关于有效推理的说明 2.?＝{A1，A2，…，Ak}由 ?推B的推理记为 ?┣B若推理是正确的，记为 ? ╞ B若推理是不正确的，记为 ? B 关于有效推理的说明 例题 ?(1) {p,p→q}├ q ?(2) {p,q→p}├ q 有效推理的等价定理 定理3.1： 命题公式A1,A2,…,Ak推B的推理正确当且仅 当(A1∧A2∧…∧Ak )→B 为重言式。 定理3.1的证明 (1)证明必要性。若A1,A2,…,Ak推B的推理正确， 则对于A1,A2,…,Ak,B中所含命题变项的任意一组赋值，不会出现 A1∧A2∧…∧Ak为真，而B为假的情况， 因而在任何赋值下，蕴涵式(A1∧A2∧…∧Ak )→B均为真， 故它为重言式。 (2)证明充分性。若蕴涵式(A1∧A2∧…∧Ak)→B为重言式， 则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件 为假的情况， 即在任何赋值下，或者A1∧A2∧…∧Ak为假， 或者A1∧A2∧…∧Ak和B同时为真，这正符合推理正确的定义。 推理的形式结构 前提： A1, A2, … , Ak 结论： B 判断推理是否正确的方法 例题 （1） 下午马芳或去看电影或去游泳.她没去看电影， 所以，她去游泳了。 例题 （2）若今天是1号，则明天是5号;明天是5号，所以今天是1号。 推理定律--重言蕴含式 (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) 破坏性二难 关于推理定律的几点说明 A,B,C为元语言符号，代表任意的命题公式。 若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。 2.1节给出的16个等值式中的每一个都派生出两条推理定律。例如双重否定律A?? ?A产生两条推理定律A?? ?A和? ?A?A。 第二节 自然推理系统P 复习：判断推理是否正确的三种方法：真值表法、等值演算法和 主析取范式法。 问题：当推理中包含的命题变项较多时，上述三种方法演算量太 大。 解决：对于由前提A1,A2,…,Ak推B的正确推理应该给出严谨的证 明。 方法：?“证明”是一个描述推理过程的命题公式序列，其中的每 个公式或者是前提，或者是由某些前提应用推理规则得到 的结论（中间结论或推理中的结论），给出公式序列。 ?要构造出严谨的证明就必须在形式系统中进行。 形式系统的定义 形式系统的分类 自然推理系统的定义 自然推理系统的定义 自然推理系统的定义 （4）假言推理规则 A?B A ? B （5）附加规则 A ? A?B （6）化简规则