lecture4推理的形式结构.ppt

一 有效推理数理逻辑的主要任务是用数学的方法来研究数学中的推理 所谓推理是指从前提出发推出结论的思维过程 而前提是已知命题公式集合 结论是从前提出发应用推理规则推出的命题公式 要研究推理就应该给出推理的形式结构 为此 首先应该明确什么样的推理是有效的或正确的 定义3 1设A1 A2 Ak和B都是命题公式 若对于A1 A2 Ak和B中出现的命题变项的任意一组赋值 或者A1 A2 Ak为假 或者当A1 A2 Ak为真时 B也为真 则称由前提A1 A2 Ak推出B的推理是有效的或正确的 并称B是有效结论 关于定义3 1还需要做以下几点说明 1 由前提A1 A2 Ak推结论B的推理是否正确与诸前提的排列次序无关 因而前提的公式不一定是序列 而是一个有限的公式集合 若将这个集合记为 可将由 推B的推理记为 B 若推理是正确的 则记为 B 否则记为 B 这里 可以称 B和 A1 A2 Ak B为推理的形式结构 2 设A1 A2 Ak B中共出现n个命题变项 对于任何一组赋值 1 2 n i 0或者1 i 1 2 n 前提和结论的取值情况有以下四种 1 A1 A2 Ak为0 B为0 2 A1 A2 Ak为0 B为1 3 A1 A2 Ak为1 B为0 4 A1 A2 Ak为1 B为1 3 由以上的讨论可知 推理正确 并不能保证结论B一定为真 这与数学中的推理是不同的 定理3 1命题公式A1 A2 Ak推B的推理正确当且仅当 A1 A2 Ak B为重言式 于是 推理正确 A1 A2 Ak B可记为A1 A2 Ak B其中 同一样是一种元语言符号 用来表示蕴涵式为重言式 若A B为重言式 则称B为A的推论 记为A B 下面是几个重要的重言蕴涵式及其名称 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 破坏性二难 3 2自然推理系统P 可以将I记为 其中是I的形式语言系统 为I的形式演算系统 定义3 2一个形式系统I由下面四个部分组成 1 非空的字符表集 记作A I 2 A I 中符号构造的合式公式集 记作E I 3 E I 中一些特殊的公式组成的公理集 记作AX I 4 推理规则集 记作R I 形式系统一般分为两类 一类是自然推理系统 它的特点是从任意给定的前提出发 应用系统中的推理规则进行推理演算 得到的最后命题公式是推理的结论 有时称为有效的结论 它可能是重言式 也可能不是 另一类是公理推理系统 它只能从若干给定的公理出发 应用系统中推理规则进行推理演算 得到的结论是系统中的重言式 称为系统中的定理 P是一个自然推理系统 因而没有公理 故P只有三个部分 定义3 3自然推理系统P定义如下 1 字母表 1 命题变项符号 p q r pi qi ri 2 联结词符号 3 括号和逗号 2 合式公式 3 推理规则 1 前提引入规则 在证明的任何步骤上都可以引入前提 2 结论引入规则 在证明的任何步骤上所得到的结论都可以作为后继证明的前提 3 置换规则 在证明的任何步骤上 命题公式中的子公式都可以用与之等值的公式置换 得到公式序列中的又一个公式 由九条推理定律和结论引入规则还可以导出以下各条推理定律 4 假言推理规则 或称分离规则 若证明的公式序列中已出现过A B和A 则由假言推理定律 A B AB可知 B是A B和A的有效结论 由结论引入规则可知 可将B引入到命题序列中来 用图式表示为如下形式 5 附加规则 6 化简规则 7 拒取式规则 8 假言三段论规则 9 析取三段论规则 10 构造性二难推理 11 破坏性二难推理规则 12 合取引入规则 这就完成了P的定义 三 P中的证明P中的证明就是由一组P中公式作为前提 利用P中的规则 推出结论 当然此结论也为P中公式 例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 q q r p s s结论 r p q 解 1 证明 p s前提引入 s前提引入 p 拒取式 p q前提引入 q 析取三段论 q r前提引入 r 假言推理 r p q 合取 此证明的序列长为8 最后一步为推理的结论 所以推理正确 r p q 是有效结论 2 前提 p q r q r s结论 p s 2 证明 p q前提引入 p q 置换 r q前提引入 q r 置换 p r 假言三段论 r s前提引入 p s 假言三段论 从最后一步可知推理正确 p s是有效结论 例3 4在自然推理系统P中构造下面推理的证明 若数a是实数 则它不是有理数就是无理数 若a不能表示成分数 则它不是有理数 a是实数且它不能表示成分数 所以a是无理数 解首先将简单命题符号化 设p a是实数 q a是有理数 r a是无理数 s a能表示成分数 前提 p q r s q p s结论 r 前提 p q r s q p s结论 r证明 p s前提引入 p 化简 s 化简 p q r 前提引入 q r 假言推理 s q前提引入 q 假言推理 从最后一步可知推理正确 r是有效结论 r 析取三段论