自然推理系统1.ppt

第三章命题逻辑的推理理论 第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记为四元组 为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 AB可知 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结论 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 s前提引入 s 化简 p q r 前提引入 p 化简 q r 假言推理 r 析取三段论 s q前提引入 q 假言推理 P中证明的两个常用技巧 1 附加前提证明法 2 归谬法 有时推理的形式结构具有如下形式 A1 A2 Ak A B 3 5 3 5 式中结论也为蕴涵式 此时可将结论中的前件也作为推理的前提 使结论只为B 即 3 5 化为下述形式 A1 A2 Ak A B 3 6 四附加前提法 其正确性证明如下 A1 A2 Ak A B A1 A2 Ak A B A1 A2 Ak A B A1 A2 Ak A B A1 A2 Ak A B 可见 3 5 式与 3 6 式是等值的 用形式结构 3 6 式证明 将A称为附加前提 并称此证明法为附加前提证明法 例3 5在自然推理系统P中构造下面推理的证明 如果小张和小王去看电影 则小李也去看电影 小赵不去看电影或小张去看电影 小王去看电影 所以 当小赵去看电影时 小李也去看电影 解 将简单命题符号化 设p 小张去看电影 q 小王去看电影 r 小李去看电影 s 小赵去看电影 前提 p q r s p q 结论 s r 证明 用附加前提证明法 s p前提引入 s附加前提引入 p 析取三段论 p q 合取 p q r前提引入 q前提引入 r 假言推理 在构造形式结构为 A1 A2 Ak B的推理证明中 如果将 B作为前提能推出矛盾来 比如说得出 A A 则说明推理正确 其原因如下 A1 A2 Ak B A1 A2 Ak B A1 A2 Ak B 五归谬法 若 A1 A2 Ak B 为矛盾式 正说明 A1 A2 Ak B为重言式 即 A1 A2 Ak B 故推理正确 例3 6在自然推理系统P中构造下面推理的证明 如果小张守第一垒并且小李向B队投球 则A队将取胜 或者A队未取胜 或者A队获得联赛第一名 A队没有获得联赛的第一名 小张守第一垒 因此 小李没有向B队投球 解先将简单命题符号化 设p 小张守第一垒 q 小李向B队投球 r A队取胜 s A队获得联赛第一名 前提 p q r r s s p 结论 q 证明 用归谬法 p q 拒取式 q结论的否定引入