1、1主要内容l 一阶逻辑等值式与基本的等值式l 置换规则、换名规则、代替规则l 前束范式l 自然推理系统 NL 及其推理规则第五章 一阶逻辑等值演算与推理25.1 一阶逻辑等值式与置换规则定义 5.1 设 A, B是两个谓词公式 , 如果 AB是永真式 , 则称 A与 B等值 , 记作 AB, 并称 AB是 等值式利用永真式判断，与命题公式的等值相同：真值表、演算基本等值式 :1. 第一组 命题逻辑中 16组基本等值式的代换实例例如， xF(x)xF(x),xF(x)yG(y) xF(x)yG(y) 等基本等值式第二组2. 消去量词等值式 （个体域为有穷集合）设 D =a1, a2, , an由
2、前述的量词的定义及所表示的逻辑意义能够得出 xA(x) A(a1)A(a2) A(an)逻辑 意义： 对任何 x具有性质 A， 相当于 对每一个 x都具有 性质 A xA(x) A(a1)A(a2) A(an)逻辑 意义： 对一些 x具有性质 A， 只要存在有 x具有性质 A即可（ 析取的意义）3例：设个体域 D=a,b,c 消去下列公式中的量词1、 x（ F(x) G(x)2、 xF(x) x G(x)3、 x yF(x,y) 45例 给定解释 I如下：(a)个体域 D 2， 3 (b)D中特定元素 a = 2。(c)D上特定函数 f(x)为： f(2)=3， f(3) 2(d)D上的特定谓
3、词G(x， y)为： G(2， 2) G(2， 3) G(3， 2)=1， G(3， 3) 0L(x， y)为： L(2， 2) L(3， 3) 1， L(2， 3)=L(3， 2)=0F(x)为： F(2) 0， F(3) 1在 I下求下列各式的真值(1) x(F(x)G(x ， a) (2) x(F(f(x)G(x ， f(x)(3) x yL(x， y) (4) y xL(x， y)上面两例说明 量词的次序不能随意颠倒 （交换量词的次序，其真值可能改变） 63. 量词否定等值式设 A(x)是任意的含自由出现个体变项 x的公式，则(1) xA(x) x A(x)(2) xA(x) x A(
4、x) (1)式直观解释是： “并不是所有的 x都有性质 A”与 “存在 x没有性质 A”是一回事 (逻辑意义相同 )(2)式， “不存在有性质 A的 x”“所有 x都没有性质 A”是一回事 (逻辑意义相同 ) 该式可理解为是德摩根律在无限项下的推广 如：在自然数集中 “任何自然数均为偶数是不对的 ” x A(x)与 “有不是偶数的自然数 ” x A(x) 逻辑意义是相同的74. 量词辖域收缩与扩张等值式 A(x) 是含 x 自由出现的公式， B 中不含 x 的自由出现(1)关于全称量词的： x( A(x)B ) xA(x) B x( A(x)B ) xA(x) B x( A(x) B ) x
5、A(x) B x( BA(x) ) B xA(x) (2)关于存在量词的： x( A(x) B ) xA(x) B x( A(x)B ) xA(x) B x( A(x) B ) x A(x) B x( B A(x) ) B xA(x)注：其中的 B中不含变元 x ，可以是 B（ y）形式的量词的辖域 可 以扩充（或收缩）到与个体变项无关 的部分量词的辖域不可以扩充（或收缩）到相同 的自由个体 变项的部分5量词分配等值式设 A(x)， B(x)是任意的含自由出现个体变项 x的公式，则(1) x( A(x) B(x) ) x A(x) xB(x)全 称量词对 合 取可分配(2) x( A(x) B
6、(x) ) x A(x) x B(x) 存 在量词对 析 取可分配注：这两个等值式很重要，因为全称量词对析取（ 对 ）不可分配，存在量词对合取（ 对 ） 不可分配例：设： A(x ): x是奇数 B(x) : x是偶数 个体域 D为整数那么 x ( A(x) B(x) ) 是为真的但 xA(x) xB(x) 是为假的 它们是不等值的另外 x(A(x)B(x) 是为假 的， 而 xA(x) xB(x) 是为真的 ，所以它们也不等值。注：前面提出：多个量词出现时，它们的顺序不能随意调换但有 x yA(x， y) y xA(x， y) x yA(x， y) y xA(x， y)二、等值演算规则1、置
7、换规则（ 等值代换 ）设 (A) 是含公式 A的公式，若 A B，则 (A) (B) 一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里 A， B是一阶逻辑公式对于公式中出现有 双重身份的变元 （即自由又约束 )的处理：2、换名规则（约束变元的 换名 ） 目的是使每个变元性质唯一设 A为一公式，将 A中某量词辖域中某 约束变项的所有出现 及相应的指导变元， 改成该量词辖域中未曾出现过的某个体变项 符号，公式中其余部分不变，设所得公式为 A， 则 A A 例： xA(x) B( x) 由于公式中的 x 即是自由的又是约束的 ，可利用此规则进行 换名 为 ： t A(t) B(x
8、) xA(x) B(x) 后可利用量词的扩充得到： t A(t) B(x) t( A(t) B(x) )例： xF(x， y， z) yG(x， y， z) 其中 x,y即是约束又自由 t F(t， y， z) yG(x， y， z) (换名规则 ) 约束的 x换名 t F(t， y， z) wG(x， w， z) (换名规则 )约束的 y换名3) 代替规则 （ 自由变元的代替 ） 设 A为一公式，将 A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替， A中其余部分不变，设所得公式为 A，则 A A注：该规则对后面的演算很重要，特别是对于公式中某个变元x，它即是约束的又是自由的情况，必须利用此规则将该变元换为仅具有一种性质才可进行演算。例： xF(x， y， z) yG(x， y， z) x F(x， t， z) yG(x， y， z) (代替规则 ) 自由的 y用 t代换 x F(x， t， z) yG(w， y， z) (代替规则 ) 自由的 x用 w代换
