第2节 自与然推理系统P .pptVIP

* * 第三章 命题逻辑的推理理论 第1节 推理的形式结构 第2节 自然推理系统 P 一、推理形式系统 二、自然推理系统 P 第2节 自然推理系统 P 三、P 中的证明 定义 3.2 一个推理系统I由下面四个部分组成： 1. 定义 （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) ， AX (I), R(I) 为 I 的形式演算系统. 其中 A(I), E(I) 是 I 的形式语言系统， 2. 形式系统一般分类. 一类是自然推理系统, 它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）. 另一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理. 我们只介绍自然推理系统?P，它的定义中无公理部分. P是一个自然推理系统，因而没有公理. 故P只有三个部分。 定义3.3 自然推理系统P定义如下： 1．字母表 二、自然推理系统 P （1） 命题变项符号：p，q，r，…,pi，qi，ri，… （2） 联结词符号：┐,∧,∨,→, （3） 括号和逗号：( )，， ???2．合式公式 同定义1.6 3．推理规则? (1) 前提引入规则：在证明的任何步骤上都可以引入前提. (2) 结论引入规则：在证明的任何步骤上所得到 的结论都可以作为后继证明的前提. (3) 置换规则：在证明的任何步骤上，命题公式 中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式. 由九条推理定律和结论引入规则还可以导出以下各条推理定律。 (4) 假言推理规则（或称分离规则）：若证明的公 式序列中已出现过A→B和A，则由假言推理定律 (A→B)∧A B 可知，B是A→B和A的有效结论. 由结论引入规则可知，可将B引入到命题序列中来. 用图式表示为如下形式： 以下各条推理定律直接以图式给出. （5） 附加规则： ?（6） 化简规则： （7） 拒取式规则： ?（8） 假言三段论规则： ?（9） 析取三段论规则： ??（10） 构造性二难推理： （11） 破坏性二难推理规则： ????（12） 合取引入规则： 本条规则说明，若证明的公式序列中已出现 A 和B , 则可将 A∧B 引入序列中。 P中的证明就是由一组P中公式作为前提，利用P中的规则，推出结论.在自然推理系统P中，构造形式结构为 三、P中的证明 的推理，在对其证明时，首先写出： 前提： 结论： 然后用定义3.3中给出的推理规则进行证明. 例3.3 在自然推理系统P中构造下面推理的证明： ????(1) 前提：p∨q, q→r, p→s, ┐s 结论：r∧(p∨q) ?(2) 前提：┐p∨q, r∨┐q , r→s 结论：p→s 解??(1) 证明： ① p→s??? ? ?前提引入 ② ┐s ?????? 前提引入 ③ ┐p ?????? ①②拒取式 ??④ p∨q?? ??? 前提引入 ⑤ q ???????? ③④析取三段论 ⑥ q→r??? ?? 前提引入 ??⑦ r ???????? ⑤⑥假言推理 ⑧ r∧(p∨q) ⑦④合取 此证明的序列长为8,最后一步为推理的结论,所以推理正确，即 r∧(p∨q) 是有效结论. ????(1) 前提：p∨q,q→r, p→s, ┐s 结论：r∧(p∨q) ?⑤ p→r ???? ? ②④假言三段论 ③ r∨┐q? ?? 前提引入 ④ q→r ??? ?③置换 ⑥ r→s ???? 前提引入 ⑦ p→s ???? ⑤⑥假言三段论 ?(2) 证明： ① ┐p∨q? ?? 前提引入 ?? ② p→q ??? ①置换 从最后一步可知推理正确，p→s 是有效结论 . ? (2) 前提：┐p∨q, r∨┐q , r→s