命题逻辑的推理证明资料.ppt

1 主要内容第一节推理的形式结构?推理的正确与错误?推理的形式结构?判断推理正确的方法?推理定律第二节自然推理系统 P ?形式系统的定义与分类?自然推理系统 P?在P中构造证明:直接证明法、附加前提证明法、归谬法第三章命题逻辑的推理理论 2 推理的形式结构定义 设A 1, A 2, …, A k, B为命题公式. 若对于每组赋值, A 1?A 2?…?A k为假,或当 A 1?A 2?…?A k为真时, B也为真, 则称由前提 A 1, A 2, …, A k推出结论 B的推理是有效的或正确的, 并称 由命题公式 A 1, A 2, …, A k推B的推理正确当且仅当 A 1?A 2?…?A k?B为重言式注意: 推理正确不能保证结论一定正确 3 推理的形式结构 2. A 1?A 2?…?A k?B 若推理正确, 记为 A 1 ?A 2 ?…?A k ?B 推理的形式结构 1. { A 1, A 2, …, A k } B 若推理正确, 记为{A 1,A 2,?,A n } B 判断推理是否正确的方法:真值表法等值演算法主析取范式法 3. 前提: A 1, A 2, …, A k结论: B 4 推理实例例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? 1 由定理 可知推理正确 5 推理实例(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 ) ?m 0?m 2?m 3结果不含 m 1, 故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?A 7 自然推理系统 P 定义 一个形式系统 I 由下面四个部分组成: (1) 非空的字母表,记作 A(I). (2) A(I ) 中符号构造的合式公式集,记作 E(I). (3) E(I ) 中一些特殊的公式组成的公理集,记作 A X(I). (4) 推理规则集,记作 R(I).记I =< A(I ),E(I ),A X(I ),R(I )>, 其中<A(I ),E(I )>是 I 的形式语言系统, < A X(I ),R(I )> 是 I 的形式演算系统. 形式系统分为: 自然推理系统: 无公理, 即A X(I )=?公理推理系统推出的结论是系统中的重言式, 称作定理 8 自然推理系统 P 定义 自然推理系统 P 定义如下: (1) 命题变项符号: p, q, r, …, p i, q i, r i, … (2) 联结词符号: ?, ?, ?, ?, ? (3) 括号与逗号: (, ), , 2. 合式公式(同定义 ) (1) 前提引入规则:在证明的任何步骤都可以引入前提。(2) 结论引入规则:在证明的任何步骤所得到的结论都可以作为后继证明的前提。(3) 置换规则:在证明的任何步骤,命题公式中的子公式都可以用等值的公式置换,得到公式序列中又一个公式