命题逻辑的推理证明.ppt

1主要内容第一节推理的形式结构?推理的正确与错误?推理的形式结构?判断推理正确的方法?推理定律第二节自然推理系统P?形式系统的定义与分类?自然推理系统P?在P中构造证明:直接证明法、附加前提证明法、 , A2, …, Ak, B为命题公式. 若对于每组赋值,A1?A2?…?Ak为假,或当A1?A2?…?Ak为真时,B也为真,则称由前提A1, A2, …, Ak推出结论B的推理是有效的或正确的, , A2, …, Ak推B的推理正确当且仅当A1?A2?…?Ak?B为重言式注意: 推理正确不能保证结论一定正确3推理的形式结构2. A1?A2?…?Ak?B若推理正确, 记为A1 ?A2 ?…?Ak ?B推理的形式结构1. {A1, A2, …, Ak} B若推理正确, 记为{A1,A2,?,An} B判断推理是否正确的方法:真值表法等值演算法主析取范式法3. 前提:A1, A2, …, Ak结论:B4推理实例例1判断下面推理是否正确(1) 若今天是1号,则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号,则明天是5号. 明天是5号. 所以, 今天是1号. 解设p:今天是1号,q:明天是5号. (1) 推理的形式结构:(p?q)?p?q用等值演算法(p?q)?p?q??((?p?q)?p)?q??p??q?q? (2) 推理的形式结构:(p?q)?q?p用主析取范式法(p?q)?q?p?(?p?q)?q?p??((?p?q)?q)?p??q?p?(?p??q)?(p??q)?(p??q)?(p?q) ?m0?m2?m3结果不含m1, 故01是成假赋值,所以推理不正确6推理定律——重言蕴涵式一些重要的重言蕴含式,称为推理定律。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) ?B 构造性二难(特殊形式)9. (A?B)?(C?D)?( ?B??D) ?(?A??C) 破坏性二难每个等值式可产生两个推理定律如, 由A???A可产生A???A和??A? 由下面四个部分组成:(1) 非空的字母表,记作A(I). (2) A(I) 中符号构造的合式公式集,记作E(I). (3) E(I) 中一些特殊的公式组成的公理集,记作AX(I). (4) 推理规则集,记作R(I).记I=<A(I),E(I),AX(I),R(I)>, 其中<A(I),E(I)>是I 的形式语言系统, <AX(I),R(I)> 是I :自然推理系统: 无公理, 即AX(I)=?公理推理系统推出的结论是系统中的重言式, 自然推理系统P 定义如下:(1) 命题变项符号:p, q, r, …, pi, qi, ri, … (2) 联结词符号:?, ?, ?, ?, ? (3) 括号与逗号:(, ), ,2. 合式公式()(1) 前提引入规则:在证明的任何步骤都可以引入前提。(2) 结论引入规则:在证明的任何步骤所得到的结论都可以作为后继证明的前提。(3) 置换规则:在证明的任何步骤,命题公式中的子公式都可以用等值的公式置换,得到公式序列中又一个公式。9推理规则(4) 假言推理规则(6) 化简规则(8) 假言三段论规则A?B A∴BA∴A?BA?B∴A(5) 附加规则(7) 拒取式规则(9) 析取三段论规则A?B?B∴?AA?B B?C∴A?CA?B?B∴A10推理规则(10) 构造性二难推理规则(11) 破坏性二难推理规则(12) 合取引入规则A?B C?D A?C ∴B?DA?B C?D?B??D ∴?A??CA B∴A?B