[工学]20100319_命题逻辑的推理理论_2.ppt

第三章 命题逻辑的推理理论 上一节课的复习 推理的形式结构 (1) {A1,A2,…,Ak}├ B (2) (A1∧A2 ∧…∧Ak)→B 有效推理 命题公式A1,A2,…,Ak推B的推理正确当且仅当 (A1∧A2 ∧…∧Ak)→B 为重言式。 上一节课的复习（续） 推理形式： ????前提： A1,A2,…,Ak????????结论：B 是有效的当且仅当 (A1∧A2 ∧…∧Ak)→B 为重言式。 3.2. 自然推理系统P 判断推理是否正确的三种方法： 真值表法; 等值演算法; 主析取范式法. 演算量大，比较繁琐. 用更严谨的形式推理系统描述推理 形式推理系统 定义3.2 一个形式系统I由下面四个部分组成： ????（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的形式演算系统。 形式系统的种类 自然推理系统 它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论。 公理推理系统 它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。 自然推理系统 P P是一个自然推理系统，因而没有公理。故P只有三个部分。 自然推理系统 P（续） 定义3.3 自然推理系统P定义如下： 1．字母表????（1） 命题变项符号：p，q，r，…,pi，qi，ri，… ????（2） 联结词符号：┐,∧,∨,→, ? ????（3） 括号和逗号：( , )，， 2．合式公式 同定义1.6 自然推理系统 P（续） 3．推理规则 （1） 前提引入规则：在证明的任何步骤上都可以引入前提。 ?（2） 结论引入规则：在证明的任何步骤上所得到的结论都可以作为后继证明的前提。 ?（3） 置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。 自然推理系统 P（续） 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. 在自然推理系统P中构造下面推理的证明 (1) 前提：p∨q, q→r, p→s, ┐s ?????? 结论：r∧(p∨q) 证明: ① p→s??? ??前提引入 ????② ┐s ????? 前提引入 ????③ ┐p ????? ?①②拒取式 ????④ p∨q?? ??? 前提引入 ????⑤ q ??????? ?③④析取三段论 ????⑥ q→r??? ?? 前提引入 ????⑦ r ???????? ⑤⑥假言推理 ????⑧ r∧(p∨q) ⑦④合取 得证r∧(p∨q)为有效结论. 例3.3（续，练习） (2) 前提：┐p∨q, r∨┐q ,r→s ??????结论：p→s P的简单实际应用 可以在自然推理系统P中构造数学和日常生活中的一些推理，所得结论都是有效的，即当各前提的合取式为真时，结论必为真。 例3.4 在自然推理系统P中构造下面推理的证明 若数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是