阶逻辑等值式与置换规则1ppt课件

1、第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理5.1 5.1 一阶逻辑等值式与置换规那一阶逻辑等值式与置换规那么么 定义定义5.15.1等值式等值式 设设A A，B B是一阶逻辑中恣意两是一阶逻辑中恣意两个公式，假设个公式，假设A AB B是永真式，那么称是永真式，那么称A A和和B B是等值的，是等值的，记作记作A AB B，称，称A AB B是等值式。是等值式。 下面给出一阶逻辑中的一些根本而重要的等值式： 由于命题逻辑的重言式的代换实例都是一阶逻辑的永真式，所以命题逻辑中24个等值式方式p.24给出的代换实例都是一阶逻辑的等值式方式。例如：xFxxFx xyFx，yGx，y

2、xyFx，yGx，y 等都是AA的代换实例。 下面引见一些一阶逻辑固有的等值式，这些等值式都与量词有关。 1、消去量词等值式 设个体域为有限集D=a1，a2，an，那么有 1xAx Aa1Aa2Aan 2xAx Aa1Aa2Aan 2、量词否认等值式 对于恣意的公式Ax： 1xAxxAx 2xAxxAx 3、量词辖域收缩与扩张等值式 设Ax是恣意的含自在出现个体变项x的公式，B是不含x的公式，那么 1xAxBxAxB xAxBxAxB xAxBxAxB xB Ax BxAx 2xAxB xAxB xAxB xAxB xAxB xAxB xBAx BxAx 4、量词分配等值式 对于恣意的公式Ax

3、和Bx： 1xAxBxxAxx Bx 2xAxBx xAxx Bx 阐明：量词分配等值式中，只需阐明：量词分配等值式中，只需对对的分配和的分配和对对的分配的等值式。而的分配的等值式。而对对和和对对无分配律。无分配律。5、同种量词顺序置换等值式 对于恣意的公式Ax，y (1)xyAx，y yxAx，y (2)xyAx，y yxAx，y一阶逻辑的等值演算一阶逻辑的等值演算一阶逻辑的等值演算中三条重要的规那么：一阶逻辑的等值演算中三条重要的规那么： 1 1、置换规那么、置换规那么 设设(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)是用公是用公式式B B置换了置换了(A)(A)中一切的

4、中一切的A A后得到的公式，假后得到的公式，假设设A AB B，那么，那么(A) (A) (B)(B)。例例 设个体域为设个体域为D=aD=a，b b，cc，将下面公式的量词消去。，将下面公式的量词消去。1 1x xF Fx xGGx x2 2x xF Fx xyGyGy y3 3x xyFyFx x，y y解：解：1 1x xF Fx xGGx x F Fa aGGa a F Fb bGGb b F Fc cGGc c 2 2x xF Fx xyGyGy y xFxFx xyGyGy y F Fa aFFb bFFc c G Ga aGGb bGGc c3 3x xyFyFx x，y y x

5、 xF Fx x，a aFFx x，b bFFx x，c c F Fa a，a aFFa a，b bFFa a，c c F Fb b，a aFFb b，b bFFb b，c c F Fc c，a aFFc c，b bFFc c，c c例例 给定解释给定解释I I如下：如下：a a个体域个体域D=2D=2，33； b bD D中特定元素中特定元素a=2a=2c cD D上特定函数上特定函数f fx x为：为：f f2 2=3=3，f f3 3=2=2d dD D上特定谓词上特定谓词 G Gx x，y y为：为：G G2 2，2 2= G= G2 2，3 3= G= G3 3，2 2=1=1， G

6、 G3 3，3 3=0=0。 L Lx x，y y为：为：L L2 2，2 2= L= L3 3，3 3=1=1， L L2 2，3 3= L= L3 3，2 2=0=0。 F Fx x为：为：F F2 2=0=0，F F3 3=1=1。 在在I I下求以下各式的真值。下求以下各式的真值。1 1x x F Fx x G Gx x，a a2 2x x F Ff fx x G Gx x，f fx x3 3x x y Ly Lx x，y y4 4y y x Lx Lx x，y y解：解：1 1x xF Fx xGGx x，a aF F2 2GG2 2，a aF F3 3GG3 3，a aF F2 2

7、GG2 2，2 2F F3 3GG3 3，2 201011111 0 02 2x xF Ff fx xGGx x，f fx xF Ff f2 2GG2 2，f f2 2 F Ff f3 3GG3 3，f f3 3F F3 3GG2 2，3 3F F2 2GG3 3，2 211110101 1 13 3x x y Ly Lx x，y yx xL Lx x，2 2LLx x，3 3L L2 2，2 2LL2 2，3 3 L L3 3，2 2LL3 3，3 310100101 1 14 4y y x Lx Lx x，y y y yL L2 2，y yLL3 3，y yL L2 2，2 2LL3 3，

8、2 2 L L2 2，3 3LL3 3，3 310100101 0 0留意：留意：x xyLyLx x，y yy yx Lx Lx x，y y，阐明量词的次序不能随意颠，阐明量词的次序不能随意颠倒。倒。 例例 证明以下各等值式。证明以下各等值式。1 1x x M Mx xFFx x x x M Mx xFFx x2 2x x F Fx xGGx x x x F Fx xGGx x3 3x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y4 4x x y y F Fx xGGy yLLx x，y y x x y y F Fx xGGy

9、 yLLx x，y y证明：证明： 1 1x xM Mx xFFx xx xM Mx xFFx x x xM Mx xFFx x x x M Mx xFFx x x xMMx xFFx x x xM Mx xFFx x 2 2x xF Fx xGGx xx xF Fx xGGx x x xF Fx xGGx x x x F Fx xGGx x x x FFx xGGx x x xF Fx xGGx x 3 3x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y 证明：证明： x x y y F Fx xGGy yHHx x，y y

10、x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y4 4x x y y F Fx xGGy yLLx x，y y x x y y F Fx xGGy yLLx x，y y 证明与证明与3 3类似，略类似，略 一阶逻辑的等值演算一阶逻辑的等值演算一阶逻辑的等值演算中三条重要的规那么：一阶逻辑的等值演算中三条重要的规那么： 1 1、置换规那么、置换规那么 设设(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)

11、是用公是用公式式B B置换了置换了(A)(A)中一切的中一切的A A后得到的公式，假后得到的公式，假设设A AB B，那么，那么(A) (A) (B)(B)。 2 2、换名规那么、换名规那么 设设A A为一公式，将为一公式，将A A中某量词辖域中某约束中某量词辖域中某约束变项的一切出现及相应的指点变元，改成该量变项的一切出现及相应的指点变元，改成该量词辖域中未曾出现过的某个体变项符号，公式词辖域中未曾出现过的某个体变项符号，公式中其他部分不变，设所得公式为中其他部分不变，设所得公式为A A，那么，那么A AA A。解：解： xFx，y，zyGx，y，z sFs，y，zyGx，y，z换名规那么换

12、名规那么 sFs，y，ztGx，t，z换名规那么换名规那么 例例 将下面公式化成与之等值的公式，使其没有既是将下面公式化成与之等值的公式，使其没有既是约束出现的又是自在出现的个体变项。约束出现的又是自在出现的个体变项。 xFxFx x，y y，z zyGyGx x，y y，z z一阶逻辑的等值演算中三条重要的规那么： 1、置换规那么 设(A)是含公式A的公式，(B)是用公式B置换了(A)中一切的A后得到的公式，假设AB，那么(A) (B)。 2、换名规那么 设A为一公式，将A中某量词辖域中某约束变项的一切出现及相应的指点变元，改成该量词辖域中未曾出现过的某个体变项符号，公式中其他部分不变，设所

13、得公式为A，那么AA。 3、替代规那么 设A为一公式，将A中某个自在出现的个体变项的一切出现用A中未曾出现过的个体变项符号替代，公式中其他部分不变，设所得公式为A，那么AA。解：解： 1xFx，y，zyGx，y，z sFs，y，zyGx，y，z换名规那么换名规那么 sFs，y，ztGx，t，z换名规那么换名规那么 xFx，y，zyGx，y，z xFx，s，zyGx，y，z替代规那么替代规那么 xFx，s，zyGt，y，z替代规那么替代规那么 例例 将下面公式化成与之等值的公式，使其没有既是将下面公式化成与之等值的公式，使其没有既是约束出现的又是自在出现的个体变项。约束出现的又是自在出现的个体变

14、项。 1 1xFxFx x，y y，z zyGyGx x，y y，z z 2 2x xF Fx x，y yyGyGx x，y y，z z2 2x xF Fx x，y yyGyGx x，y y，z z x xF Fx x，t tyGyGx x，y y，z z替代规那么替代规那么 x xF Fx x，y yyGyGx x，y y，z z x xF Fx x，y ytGtGx x，t t，z z换名规那么换名规那么第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理5.2 5.2 一阶逻辑前束范式一阶逻辑前束范式 定义定义5.25.2前束范式前束范式 设设A A为一个一阶逻为一个一阶逻辑公式，

15、假设辑公式，假设A A具有如下方式具有如下方式Q1x1Q2x2QkxkBQ1x1Q2x2QkxkB，那么称那么称A A为前束范式为前束范式,Qi,Qi1ik1ik为为或或，B B为不含量词的公式。为不含量词的公式。例如：x yFxGyHx，yx y zFxGyHzLx，y，z 等公式都是前束范式。x Fxx GxxFxyGyHx，y 等公式都不是前束范式。 留意：前束范式中不存在既是自在出现的，又是约束出现的个体变项。定理5.1前束范式存在定理 一阶逻辑中的任何公式都存在与之等值的前束范式。 阐明： 1定理阐明任何公式的前束范式都是存在的，但并不独一。 2可利用上节的等值式和三条变换规那么来求

16、公式的前束范式。例5.6 求下面公式的前束范式。 1x Fxx Gx 2x Fxx Gx 3x Fxx Gx 4x Fxx Gx 5x Fx，yy Gx，y 6x Fx，yy Gyx Hx，y，z 1 1x Fx Fx xx Gx Gx x方法一：方法一： x Fx Fx xxGxGx x等值置换等值置换 x xF Fx xGGx x方法二：方法二： x Fx Fx xy Gy Gy y换名规那换名规那么么 x Fx Fx xy Gy Gy y x xF Fx xy Gy Gy y x x y yF Fx x G Gy y2 2xFxFx xxGxGx x xFxFx xxGxGx x x x

17、F Fx xGGx x 错误！错误！ 由于由于对对没有分配律！没有分配律！ 正确解法如下：正确解法如下： xFxFx xxGxGx x xFxFx xxGxGx x xFxFx x yGyGy y x xy yF Fx x G Gy y3 3xFxFx xxGxGx x方法一：方法一： yFyFy yxGxGx x y(Fy(Fy yxGxGx x) ) y yx(Fx(Fy yGGx x) )方法二：方法二： xFxFx xxGxGx x xFxFx xxGxGx x x xFFx xGGx x方法三：方法三： x xy(Fy(Fx xGGy y) )4 4x Fx Fx xx Gx Gx

18、x方法一：方法一： x Fx Fx xy Gy Gy y x (Fx (Fx xy Gy Gy y) ) x xy (Fy (Fx xGGy y) )方法二：方法二： y yx(Fx(Fy yGGx x) )方法三：方法三： x Fx Fx x x Gx Gx x xFxFx x x Gx Gx x xFxFx x y Gy Gy y x xy(Fy(Fx x G Gy y) ) x xy (Fy (Fx xGGy y) )5 5x Fx Fx x，y yy Gy Gx x，y y方法一：方法一： t Ft Ft t，y ys Gs Gx x，s s换名规那么换名规那么 t ts s F Ft t，y yGGx x，s s方法二：方法二： x Fx Fx x，y yy Gy Gx x，y y x Fx Fx x，t ty Gy Gs s，y y 替代规那么替代规那么 x xy yF Fx x，t tGGs s，y y6 6x Fx Fx x，y yy Gy Gy yx Hx Hx x，y y，z z方法一：方法一： sFsFs s，y yt Gt Gt txHxHx x，y y，