1、1第 5讲 谓词演算的 推理理论 推理的形式结构 重要的推理定律 推理规则 构造证明 附加前提证明法2推理 推理的形式结构 有两种: 第一种 A1A2 AkB (*)第二种 前提: A1, A2, , Ak结论: B其中 A1,A2, Ak,B为一阶逻辑公式 . 若 (*)为永真式 , 则称 推理正确 , 否则称 推理不正确 .判断方法 : 真值表法 , 等值演算法 , 主析取范式法及构造证明法 . 前 3种方法采用第一种形式结构 , 构造证明法采用第二种形式结构 .3重要的推理定律 第一组 命题逻辑推理定律代换实例如 xF(x)yG(y)xF(x)为化简律代换实例 . xF(x)yG(y)的
2、代换实例为 pq化简律 : (pq) p重要的推理定律A (AB) 附加律 (AB) A 化简律(AB)A B 假言推理(AB)B A 拒取式(AB)B A 析取三段论(AB)(BC) (AC) 假言三段论(AB)(BC) (AC) 等价三段(AB)(CD)(AC) (BD) 构造性二难 4推理定律 重言蕴涵式 5第二组 由基本等值式生成如 由 xA(x)xA(x) 生成xA(x)xA(x), xA(x)xA(x), 第三组 xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)xA(x)xB(x) 6推理规则 (1)前提引入规则 (2)结论引入规则(3)置换规则 (4)假言推理规则(5
3、)附加规则 (6)化简规则(7)拒取式规则 (8)假言三段论规则(9)析取三段论规则 (10)构造性二难推理规则(11)合取引入规则 7推理规则 (续 )(12) 全称量词消去规则(简记为 UI规则或 UI)两式成立的条件是:在第一式中,取代 x的 y应为任意的不在 A(x)中约束出现的个体变项 .在第二式中, c为任意个体常项 .用 y或 c去取代 A(x)中的自由出现的 x时,一定要在 x自由出现的一切地方进行取代 .8/51例 下面推理是否正确?设前提为 x yF( x, y),( 1) x yF( x, y) 前提引入( 2) y F( y, y) 全称量词消去解 推理并 不正确 。如
4、果给定解释 I:个体域为实数集,F( x, y): x y。则 x yF( x, y)意为“对于每个实数 x,均存在着比之更小的实数 y”,这是一个真命题。而 yF( y, y)意为“存在着比自己小的实数 ”,是假命题。之所以出现这样的错误 ,是因为 yF( x, y) 中有 1个自由变元 x, 而 y F( y, y)中无自由变元。9推理规则 (续 )(13) 全称量词引入规则(简记为 UG规则或 UG)该式成立的条件是:无论 A(y)中自由出现的个体变项 y取何值, A(y)应该均为真 .取代自由出现的 y的 x,也不能在 A(y)中约束出现 . 10推理规则 (续 )(14) 存在量词引入规则(简记为 EG规则或 EG)该式成立的条件是:c是使 A为真的特定个体常项 .取代 c的 x不能在 A(c)中出现过 .