5.3一阶逻辑推理理论ppt课件

1、第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理第第3节节 一阶逻辑推理理论一阶逻辑推理理论 第一组第一组 命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例 ( )( )( ) xF xyG yxF x ( )( )( )xF xxF xyG y 分别为命题逻辑中化简律和附加律的代换实例分别为命题逻辑中化简律和附加律的代换实例. 例如：例如： 第二组第二组 由基本等值式生成的推理定律由基本等值式生成的推理定律 上一节给出的两组等值式中的每个等值式可生成上一节给出的两组等值式中的每个等值式可生成两个推理定律两个推理定律.( )( )xF xxF x ( )( )xF xxF x 和

2、和 ( )( )xF xx F x ( )( )x F xxF x 分别由双重否定律和量词否定等值式生成分别由双重否定律和量词否定等值式生成. 例如：例如： 第三组第三组 其他重要推理定律其他重要推理定律( )( )( ( )( )xA xxB xx A xB x (1)( ( )( )( )( )x A xB xxA xxB x (2)( ( )( )( )( )x A xB xxA xxB x (3)( ( )( )( )( ) x A xB xxA xxB x (4)例如：例如： 1全称量词消去规则全称量词消去规则 ( 简记为简记为 UI 规则或规则或 UI )( )( )xA xA y

3、 ( )( )xA xA c 或或两式成立的条件是：两式成立的条件是：（2在第二式中，在第二式中，c 为任意个体变项。为任意个体变项。 （3用用 y 或或 c 去取代去取代 中自由出现的中自由出现的 x 时，一定时，一定 要在要在x自由出现的一切地方进行取代自由出现的一切地方进行取代. ( )A x（1在第一式中，取代在第一式中，取代 x 的的 y 应为任意的不在应为任意的不在 中约束出现的个体变项中约束出现的个体变项.( )A x 2全称量词引入规则全称量词引入规则 ( 简记为简记为UG 规则或规则或UG )( )( )A yxA x（2取代自由出现的取代自由出现的 y 的的 x 也不能在也

4、不能在 中约束出现中约束出现. ( )A y该式成立的条件是：该式成立的条件是：( )A y( )A y（1无论无论 中自由出现的个体变项中自由出现的个体变项 y 取何值，取何值， 应该均为真应该均为真. 3存在量词引入规则 ( 简称 EG 规则或 EG )( )( )A cxA x （2取代取代 c 的的 x 不能在不能在 中出现过中出现过. ( )A c（1c 是特定的个体常项是特定的个体常项.该式成立的条件是：该式成立的条件是： 4存在量词消去规则 ( 简记为EI 规则或 EI )( )( )xA xA c （3若若A(x)中除自由出现的中除自由出现的 x 外，还有其它自由出现外，还有其

5、它自由出现 的个体变项，此规则不能使用的个体变项，此规则不能使用. 该式成立的条件是：该式成立的条件是：（1c 是使是使 A 为真的特定的个体常项为真的特定的个体常项. （2c 不在不在 中出现中出现. ( )A x 3. 推理规则：推理规则：定义定义5.3 自然推理系统自然推理系统 F 定义如下：定义如下：F F 1. 字母表字母表. 同一阶语言同一阶语言 的字母表的字母表 (见定义见定义4.1). F F2. 合式公式合式公式. 同同 合式公式的定义合式公式的定义 (见定义见定义4.1). （1） 前提引入规则前提引入规则.（2） 结论引入规则结论引入规则.（3） 置换规则置换规则. （4

6、） 假言推理规则假言推理规则. （5） 附加规则附加规则. （6） 化简规则化简规则. （7） 拒取式规则拒取式规则.（8） 假言三段论规则假言三段论规则. （15EG规则规则. F 中的推理过程类似命题演算自然推理系统中的推理过程类似命题演算自然推理系统 P. （9） 析取三段论规则析取三段论规则. （10构造性二难推理规则构造性二难推理规则. （11合取引入规则合取引入规则.（12UI规则规则. （14EI规则规则. （13UG规则规则.( , )x yF x y 前提引入前提引入( , )yF z y UI规则规则( , )F z cEI规则规则( , )xF x c UG规则规则 例例

7、5.8 设个体域为实数集合，设个体域为实数集合， 为为指出在推理系统指出在推理系统F 中，以中，以 (真命题真命题)为为前提，推出前提，推出 (假命题假命题) 的下述推理证明中的下述推理证明中的错误的错误. ( , )x yF x y ( , )xF x c ( , )F x y.xy 解解 由于由于 c 为特定的个体常项，所以为特定的个体常项，所以(即为即为 )为假命题为假命题. ( , )xF x c ()x xc 如果按如果按F 中推理规则进行推理，中推理规则进行推理，不会从真命题推出假命题不会从真命题推出假命题.在以上推理证明中，第三步错了，由于在以上推理证明中，第三步错了，由于 中中

8、除有自由出现的除有自由出现的 y ，还有自由出现的，还有自由出现的 z ，按，按 EI 规则规则应该满足的条件应该满足的条件(3)，此处不能用，此处不能用EI 规则规则.用了用了EI 规则，导致了从真命题推出假命题的错误规则，导致了从真命题推出假命题的错误. ( , )F z y例例5.9 在自然推理系统在自然推理系统F 中，构造下面推理的证明：中，构造下面推理的证明： 任何自然数都是整数；存在着自然数任何自然数都是整数；存在着自然数. 所以存在所以存在 着整数着整数. 个体域为实数集合个体域为实数集合R. 解解 先将原子命题符号化先将原子命题符号化. 结论：结论：( )xG x ( )( )

9、, ( )x F xG xxF x 前提：前提： 设设 为自然数，为自然数， 为整数为整数. ( ):G xx( ):F xx证明：证明：前提引入前提引入( )xF x 前提引入前提引入 ( )( )x F xG x ( )( )F cG cUI规则规则( ) xG x EG规则规则 假言推理假言推理( )G c EI规则规则( )F c 以上证明的每一步都是严格按推理规则及应满足的条件以上证明的每一步都是严格按推理规则及应满足的条件进行的。因此，前提的合取为真时，结论必为真。但如果进行的。因此，前提的合取为真时，结论必为真。但如果改变命题序列的顺序会产生由真前提推出假结论的错误。改变命题序列

10、的顺序会产生由真前提推出假结论的错误。如果证明如下进行：如果证明如下进行： 前提引入前提引入 ( )( )x F xG x ( )( )F cG c UI规则规则前提引入前提引入( )xF x EI规则规则( )F c 在在中取中取 , 那么那么 为真前件假）为真前件假）,于是于是中中 为假，这样从前件真推出了假的中间结果为假，这样从前件真推出了假的中间结果.2c)2()2(GF)2(F 例例5.10在自然推理系统在自然推理系统F中，构造下面推理的证明：中，构造下面推理的证明：前提前提:( )( ),( )( )x F xG xx F xH x 结论结论:( ( )( )x G xH x例例5.11 在自然推