《05一阶逻辑等值演算与推理.ppt》由会员分享，可在线阅读，更多相关《05一阶逻辑等值演算与推理.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第5 5章章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容一阶逻辑等值式与基本等值式一阶逻辑等值式与基本等值式置换规则、换名规则、代替规则置换规则、换名规则、代替规则前束范式前束范式一阶逻辑推理理论一阶逻辑推理理论q本章与其他各章的关系本章与其他各章的关系本章先行基础是前四章本章先行基础是前四章本章是集合论各章的先行基础本章是集合论各章的先行基础本章主要内容本章主要内容本章主要内容本章主要内容 5.1 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则5.2
2、5.2 一阶逻辑前束范式一阶逻辑前束范式5.3 5.3 一阶逻辑的推理理论一阶逻辑的推理理论5.1 5.1 5.1 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则q在一阶逻辑中，有些命题可以有不同的符号化形式。在一阶逻辑中，有些命题可以有不同的符号化形式。q例如：没有不犯错误的人例如：没有不犯错误的人令令 M(x):xM(x):x是人。是人。F(x):xF(x):x犯错误。犯错误。则将上述命题的符号化有以下两种正确形式：则将上述命题的符号化有以下两种正确形式：(1)(1)x(M(x)x(M(x)F(x)F(x)(2)(2)x(M(x)F
3、(x)x(M(x)F(x)q我们称我们称(1)(1)和和(2)(2)是等值的。是等值的。说说明明等值式的定义等值式的定义等值式的定义等值式的定义定义定义5.15.1 设设A A，B B是一阶逻辑中任意两个公式，若是一阶逻辑中任意两个公式，若 A AB B是永是永真式，则称真式，则称A A与与B B是是等值等值的。的。记做记做A AB B，称，称 A AB B 是是等值式等值式。例如：例如：q判断公式判断公式A A与与B B是否等值，等价于判断公式是否等值，等价于判断公式A AB B是否为永真式。是否为永真式。q谓词逻辑中关于联结词的等值式与命题逻辑谓词逻辑中关于联结词的等值式与命题逻辑中相关等
4、值式类似。中相关等值式类似。说说明明一阶逻辑中的一些基本而重要等值式一阶逻辑中的一些基本而重要等值式一阶逻辑中的一些基本而重要等值式一阶逻辑中的一些基本而重要等值式q代换实例代换实例q消去量词等值式消去量词等值式 q量词否定等值式量词否定等值式 q量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 q量词分配等值式量词分配等值式 代换实例代换实例代换实例代换实例q由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的真式，因而第二章的1616组等值式模式给出的代换实例都是组等值式模式给出的代换实例都是一阶逻辑的等值式的模式。一阶逻辑
5、的等值式的模式。q例如：例如：(1)(1)xF(x)xF(x)xF(x)xF(x)（双重否定律）（双重否定律）(2)F(x)G(y)(2)F(x)G(y)F(x)G(y)F(x)G(y)（蕴涵等值式）（蕴涵等值式）(3)(3)x(F(x)G(y)x(F(x)G(y)zH(z)zH(z)x(F(x)G(y)x(F(x)G(y)zH(z)zH(z)（蕴涵等值式）（蕴涵等值式）消消消消去量词等值式去量词等值式去量词等值式去量词等值式设个体域为有限集设个体域为有限集D=aD=a1 1,a,a2 2,a,an n,则有则有（1 1）xA(x)xA(x)A(aA(a1 1)A(a)A(a2 2)A(aA(
6、an n)（2 2）xA(x)xA(x)A(aA(a1 1)A(a)A(a2 2)A(aA(an n)（5.15.1）量词否定等值式量词否定等值式量词否定等值式量词否定等值式设设A(x)A(x)是任意的含自由出现个体变项是任意的含自由出现个体变项x x的公式，则的公式，则（1 1）xA(x)xA(x)xA(x)xA(x)（2 2）xA(x)xA(x)xA(x)xA(x)说明说明q“并不是所有的并不是所有的x x都有性质都有性质A A”与与“存在存在x x没有没有性质性质A A”是一回事。是一回事。q”不存在有性质不存在有性质A A的的x x”与与”所有所有X X都没有性质都没有性质A A”是一
7、回事。是一回事。（5.25.2）量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式设设A(x)A(x)是任意的含自由出现个体变项是任意的含自由出现个体变项x x的公式，的公式，B B中不含中不含x x的出现的出现，则，则（1 1）x(A(x)B)x(A(x)B)xA(x)BxA(x)B x(A(x)B)x(A(x)B)xA(x)BxA(x)B x(A(x)B)x(A(x)B)xA(x)BxA(x)B x(BA(x)x(BA(x)B B xA(x)xA(x)（2 2）x(A(x)B)x(A(x)B)xA(x)BxA(x)B x(A(x)B)x(A(x
8、)B)xA(x)BxA(x)B x(A(x)B)x(A(x)B)xA(x)BxA(x)B x(BA(x)x(BA(x)B B xA(x)xA(x)（5.35.3）（5.45.4）证明证明证明证明:xA(x)B xA(x)B xA(x)B xA(x)B x(A(x)B)x(A(x)B)x(A(x)B)x(A(x)B)xA(x)B xA(x)B xA(x)BxA(x)B x xA(x)BA(x)B x(x(A(x)B)A(x)B)x(A(x)B)x(A(x)B)量词分配等值式量词分配等值式量词分配等值式量词分配等值式设设A(x)A(x)，B(x)B(x)是任意的含自由出现个体变项是任意的含自由出现
9、个体变项x x的公式，则的公式，则（1 1）x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)（2 2）x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)（5.55.5）q例如，例如，“联欢会上所有人既唱歌又跳舞联欢会上所有人既唱歌又跳舞”和和“联欢会上所联欢会上所有人唱歌且所有人跳舞有人唱歌且所有人跳舞”，这两个语句意义相同。故有，这两个语句意义相同。故有(1)(1)式。式。q由由(1)(1)式推导式推导(2)(2)式式 x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)x(x(A(x)A(x)B(x)
10、B(x)x xA(x)A(x)x xB(x)B(x)x(A(x)B(x)x(A(x)B(x)(xA(x)xA(x)xB(x)xB(x)x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)一阶逻辑等值演算的三条原则一阶逻辑等值演算的三条原则一阶逻辑等值演算的三条原则一阶逻辑等值演算的三条原则q置换规则置换规则：设：设(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)是用公式是用公式B B取代取代(A)(A)中所有的中所有的A A之后的公式，若之后的公式，若A AB B，则，则(A)(A)(B)(B)。q换名规则换名规则：设设A A为一公式，将为一公式，将A
11、 A中某量词辖域中某约束变项的中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为某个体变项符号，公式的其余部分不变，设所得公式为AA，则则AAA A。q代替规则代替规则：设设A A为一公式，将为一公式，将A A中某个自由出现的个体变项的中某个自由出现的个体变项的所有出现用所有出现用A A中未曾出现过的个体变项符号代替，中未曾出现过的个体变项符号代替，A A中其余部中其余部分不变，设所得公式为分不变，设所得公式为AA，则，则AAA A。说明说明q一阶逻辑中的置换规则与命
12、题逻辑中的置换一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里规则形式上完全相同，只是在这里A A，B B是一是一阶逻辑公式。阶逻辑公式。例例例例5.15.15.15.1例例5.15.1 将下面公式化成与之等值的公式，使其将下面公式化成与之等值的公式，使其没有既是约束没有既是约束出现又是自由出现的个体变项出现又是自由出现的个体变项。(1)(1)xF(x,y,z)xF(x,y,z)yG(x,y,z)yG(x,y,z)(2)(2)x(F(x,y)x(F(x,y)yG(x,y,z)yG(x,y,z)(1)(1)x xF(F(x x,y,z),y,z)yG(x,y,z)yG(x,y
13、,z)tF(t,y,z)tF(t,y,z)y yG(x,G(x,y y,z),z)(换名规则换名规则)tF(t,y,z)tF(t,y,z)wG(x,w,z)wG(x,w,z)(换名规则换名规则)或或 xF(x,xF(x,y y,z),z)yG(x,y,z)yG(x,y,z)xF(x,t,z)xF(x,t,z)y yG(G(x x,y y,z),z)(代替规则代替规则)x xF(x,t,z)F(x,t,z)y yG(w,y,z)G(w,y,z)(代替规则代替规则)解答解答例例例例5.15.15.15.1的解答的解答的解答的解答(2)(2)x(F(x,x(F(x,y y)yG(x,y,z)yG(x
14、,y,z)x(F(x,t)x(F(x,t)yG(x,y,z)yG(x,y,z)(代替规则代替规则)或或 x(F(x,y)x(F(x,y)y yG(x,y,z)G(x,y,z)x(F(x,y)x(F(x,y)tG(x,t,z)tG(x,t,z)(换名规则换名规则)解答解答换名规换名规换名规换名规则和代替规则的关系则和代替规则的关系则和代替规则的关系则和代替规则的关系换名规则和代替规则之间的换名规则和代替规则之间的共同点共同点都是都是不能改变原有的约束关不能改变原有的约束关系系，而，而不同点不同点是：是：（1 1）施行的对象不同施行的对象不同：换名规则是对：换名规则是对约束变元约束变元施行，代替规
15、施行，代替规则是对则是对自由变元自由变元施行；施行；（2 2）施行的范围不同施行的范围不同：换名规则可以只对公式中的一个量词：换名规则可以只对公式中的一个量词及其辖域内施行，即只及其辖域内施行，即只对公式的一个子公式施行对公式的一个子公式施行；而代替；而代替规则必须对整个公式同一个自由变元的所有自由出现同时规则必须对整个公式同一个自由变元的所有自由出现同时施行，即必须施行，即必须对整个公式施行对整个公式施行；换名规则和代替规则的关系（续）换名规则和代替规则的关系（续）换名规则和代替规则的关系（续）换名规则和代替规则的关系（续）（3 3）施行后的结果不同施行后的结果不同：换名后，公式含义不变，因
16、为：换名后，公式含义不变，因为约约束变元只改名为另一个个体变元，束变元只改名为另一个个体变元，约束关系不改变，约约束关系不改变，约束变元不能改名为个体常量；代替后，不仅可用另一个束变元不能改名为个体常量；代替后，不仅可用另一个个体变元进行代入，并且也可用个体变元进行代入，并且也可用个体常量个体常量去代入，从而去代入，从而使公式由具有普遍意义变为仅对该个体常量有意义，即使公式由具有普遍意义变为仅对该个体常量有意义，即公式的含义改变了。公式的含义改变了。例例例例5.25.25.25.2例例5.25.2 证明证明（1 1）x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x
17、)（2 2）x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)其中其中A(x)A(x)，B(x)B(x)为含为含x x自由出现的公式。自由出现的公式。只要证明在某个解释下两边的式子不等值。只要证明在某个解释下两边的式子不等值。取解释取解释I I：个体域为自然数集合：个体域为自然数集合N N；(1)(1)取取F(x)F(x)：x x是奇数，代替是奇数，代替A(x)A(x)；取取G(x)G(x)：x x是偶数，代替是偶数，代替B(x)B(x)。则则 x(F(x)G(x)x(F(x)G(x)为真命题，为真命题，而而 xF(x)xF(x)xG(x)xG(x)为假命题。为假
18、命题。两边不等值。两边不等值。证明证明例例例例5.25.25.25.2(2)(2)x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)x(F(x)G(x)x(F(x)G(x)：有些：有些x x既是奇数又是偶数为假命题；既是奇数又是偶数为假命题；而而 xF(x)xF(x)xG(x)xG(x)：有些：有些x x是奇数并且有些是奇数并且有些x x是偶数为真是偶数为真命题。命题。两边不等值。两边不等值。证明证明说明说明q全称量词全称量词“”对对“”无分配律。无分配律。q存在量词存在量词“”对对“”无分配律。无分配律。q当当B(x)B(x)换成没有换成没有x x出现的出现的B
19、 B时，则有时，则有 x(A(x)B)x(A(x)B)xA(x)BxA(x)B x(A(x)B)x(A(x)B)xA(x)BxA(x)B例例例例5.35.35.35.3消消消消去量词去量词去量词去量词例例5.3 5.3 设个体域为设个体域为D Da,b,ca,b,c，将下面各公式的量词消去：，将下面各公式的量词消去：(1)(1)x(F(x)G(x)x(F(x)G(x)(2)(2)x(F(x)x(F(x)yG(y)yG(y)(3)(3)x x yF(x,y)yF(x,y)说明说明q如果不用公式如果不用公式(5.3)(5.3)将量词的辖域缩小，演算过程较将量词的辖域缩小，演算过程较长。注意，此时长
20、。注意，此时 yG(y)yG(y)是与是与x x无关的公式无关的公式B B。解答解答(1)(1)x(F(x)G(x)x(F(x)G(x)(F(a)G(a)(F(b)G(b)(F(c)G(c)(F(a)G(a)(F(b)G(b)(F(c)G(c)(2)(2)x(F(x)x(F(x)yG(y)yG(y)xF(x)xF(x)yG(y)yG(y)(公式公式5.3)5.3)(F(a)F(b)F(c)(G(a)G(b)G(c)(F(a)F(b)F(c)(G(a)G(b)G(c)例例例例5.35.35.35.3消消消消去量词去量词去量词去量词(3)(3)x x yF(x,y)yF(x,y)x(F(x,a)F
21、(x,b)F(x,c)x(F(x,a)F(x,b)F(x,c)(F(a,a)F(a,b)F(a,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c)(F(c,a)F(c,b)F(c,c)在演算中先消去存在量词也可以，得到结果是等值的。在演算中先消去存在量词也可以，得到结果是等值的。x x yF(x,y)yF(x,y)yF(a,y)yF(a,y)yF(b,y)yF(b,y)yF(c,y)yF(c,y)(F(a,a)F(a,b)F(a,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(
22、b,b)F(b,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c)(F(c,a)F(c,b)F(c,c)例例例例5.45.45.45.4例例5.45.4 给定解释给定解释I I如下：如下：（a a）个体域）个体域 D D2,32,3（b b）D D中特定元素中特定元素（c c）D D上的特定函数上的特定函数(x)(x)为：为：（d d）D D的特定谓词的特定谓词在解释在解释I I下求下列各式的值：下求下列各式的值：（1 1）x(F(x)G(x,a)x(F(x)G(x,a)（2 2）x(F(f(x)G(x,f(x)x(F(f(x)G(x,f(x)（3 3）x x y
23、L(x,y)yL(x,y)（4 4）y y xL(x,y)xL(x,y)例例例例5.45.45.45.4的解答的解答的解答的解答（1 1）x(F(x)G(x,a)x(F(x)G(x,a)(F(2)G(2,2)(F(3)G(3,2)(F(2)G(2,2)(F(3)G(3,2)(01)(11)(01)(11)0 0（2 2）x(F(f(x)G(x,f(x)x(F(f(x)G(x,f(x)(F(f(2)G(2,f(2)(F(f(3)G(3,f(3)(F(f(2)G(2,f(2)(F(f(3)G(3,f(3)(F(3)G(2,3)(F(2)G(3,2)(F(3)G(2,3)(F(2)G(3,2)(11
24、)(01)(11)(01)1 1例例例例5.45.45.45.4的解答的解答的解答的解答（3 3）x x yL(x,y)yL(x,y)(L(2,2)L(2,3)(L(3,2)L(3,3)(L(2,2)L(2,3)(L(3,2)L(3,3)(10)(01)(10)(01)1 1（4 4）y y xL(x,y)xL(x,y)y(L(2,y)L(3,y)y(L(2,y)L(3,y)(L(2,2)L(3,2)(L(2,3)L(3,3)(L(2,2)L(3,2)(L(2,3)L(3,3)(10)(01)(10)(01)0 0说明说明q由由(3)(3)，(4)(4)的结果进一步可以说明量词的次的结果进一步
25、可以说明量词的次序不能随意颠倒。序不能随意颠倒。例例例例5.55.55.55.5例例5.55.5 证明下列等值式。证明下列等值式。（1 1）x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)（2 2）x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)（3 3）x x y(F(x)G(y)H(xy(F(x)G(y)H(x，y)y)x x y(F(x)G(y)H(x,y)y(F(x)G(y)H(x,y)（4 4）x x y(F(x)G(y)L(xy(F(x)G(y)L(x，y)y)x x y(F(x)G(y)L(x,y)y(F(x)G(y
26、)L(x,y)例例例例5.55.55.55.5的证明的证明的证明的证明（1 1）x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)（2 2）x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)例例例例5.55.55.55.
27、5的证明的证明的证明的证明（3 3）x x y(F(x)G(y)H(xy(F(x)G(y)H(x，y)y)x x y(F(x)G(y)H(x,y)y(F(x)G(y)H(x,y)x x y y(F(x)G(y)H(xF(x)G(y)H(x，y)y)xx(y y(F(x)G(y)H(xF(x)G(y)H(x，y)y)x x yy(F(x)G(y)H(x(F(x)G(y)H(x，y)y)x x y(F(x)G(y)H(x,y)y(F(x)G(y)H(x,y)例例例例5.55.55.55.5的证明的证明的证明的证明（4 4）x x y(F(x)G(y)L(xy(F(x)G(y)L(x，y)y)x x
28、 y(F(x)G(y)L(x,y)y(F(x)G(y)L(x,y)x x y(F(x)G(y)L(xy(F(x)G(y)L(x，y)y)x x(y(F(x)G(y)L(xy(F(x)G(y)L(x，y)y)x x y(F(x)G(y)L(xy(F(x)G(y)L(x，y)y)x x y(F(x)G(y)L(x,y)y(F(x)G(y)L(x,y)x x y(F(x)G(y)L(x,y)y(F(x)G(y)L(x,y)5.2 5.2 5.2 5.2 一阶逻辑前束范式一阶逻辑前束范式一阶逻辑前束范式一阶逻辑前束范式定义定义5.25.2 设设A A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A A具
29、有如下形式具有如下形式Q Q1 1x x1 1Q Q2 2x x2 2 Q Qk kx xk kB B则称则称A A为为前束范式前束范式，其中，其中Q Qi i(1ik)(1ik)为为 或或，B B为不含量词为不含量词的公式。的公式。q前束范式的例子：前束范式的例子：x x y(F(x)G(y)H(xy(F(x)G(y)H(x，y)y)x x y y z(F(x)G(y)H(z)L(xz(F(x)G(y)H(z)L(x，y y，z)z)q不是前束范式的例子：不是前束范式的例子：x x(F(x)F(x)y y(G(y)H(x(G(y)H(x，y)y)x x(F(x)F(x)y y(G(y)H(x
30、(G(y)H(x，y)y)前束范式存在定理前束范式存在定理前束范式存在定理前束范式存在定理定理定理5.1 5.1 一阶逻辑中的任何公式都存在与之等值的前束范式。一阶逻辑中的任何公式都存在与之等值的前束范式。说明说明q求前束范式的过程，就是制造量词辖域可以扩大的求前束范式的过程，就是制造量词辖域可以扩大的条件，进行量词辖域扩大。条件，进行量词辖域扩大。q任何公式的前束范式都是存在的，但一般说来，并任何公式的前束范式都是存在的，但一般说来，并不唯一。不唯一。q利用一阶逻辑等值式以及三条变换规则（置换规则、利用一阶逻辑等值式以及三条变换规则（置换规则、换名规则、代替规则）就可以求出与公式等值的前换名
31、规则、代替规则）就可以求出与公式等值的前束范式，或所谓公式的前束范式。束范式，或所谓公式的前束范式。(1)(1)利用量词转化公式，把否定深入到指导变元的后面。利用量词转化公式，把否定深入到指导变元的后面。xA(x)xA(x)xA(x)xA(x)xA(x)xA(x)xA(x)xA(x)(2)(2)利用利用 x(A(x)B)x(A(x)B)xA(x)BxA(x)B和和 x(A(x)B)x(A(x)B)xA(x)BxA(x)B把把量词移到全式的最前面，这样便得到前束范式。量词移到全式的最前面，这样便得到前束范式。例例例例5.6 5.6 5.6 5.6 求公式的前束范式求公式的前束范式求公式的前束范式
32、求公式的前束范式（1 1）xF(x)xF(x)x xG(G(x x)xF(x)xF(x)yG(y)yG(y)(换名规则换名规则)xF(x)xF(x)yG(y)yG(y)(5.2)(5.2)第二式第二式)x(F(x)x(F(x)yG(y)yG(y)(5.3)(5.3)第二式第二式)x x y(F(x)G(y)y(F(x)G(y)(5.3)(5.3)第二式第二式)（y y x(F(x)G(y)x(F(x)G(y)）或者或者 xF(x)xF(x)xG(x)xG(x)xF(x)xF(x)xG(x)xG(x)(5.2)(5.2)第二式第二式)x(F(x)G(x)x(F(x)G(x)(5.5)(5.5)第
33、一式第一式)例例例例5.6 5.6 5.6 5.6 求公式的前束范式求公式的前束范式求公式的前束范式求公式的前束范式（2 2）xF(x)xF(x)xG(x)xG(x)xF(x)xF(x)xG(xG(x x)(5.2)(5.2)第二式第二式)xF(x)xF(x)yG(y)yG(y)(换名规则换名规则)x(F(x)x(F(x)yG(y)yG(y)(5.3)(5.3)第一式第一式)x x y(F(x)G(y)y(F(x)G(y)(5.3)(5.3)第一式第一式)说明说明q公式的前束范式是不唯一的。公式的前束范式是不唯一的。例例例例5.7 5.7 5.7 5.7 求前束范式求前束范式求前束范式求前束范
34、式(1)(1)xF(xF(x x)xG(x)xG(x)yF(y)yF(y)xG(x)xG(x)y y x(F(y)G(x)x(F(y)G(x)(2)(2)xF(xF(x x)xG(x)xG(x)y yF(y)F(y)xG(x)xG(x)y y x(x(F(y)G(x)F(y)G(x)(3)(3)xF(xF(x x)xG(x)xG(x)y yF(y)F(y)xG(x)xG(x)y y x(x(F(y)G(x)F(y)G(x)(4)(4)xF(x)xF(x)y yG(y)G(y)x x y(y(F(x)G(x)F(x)G(x)例例例例5.8 5.8 5.8 5.8 求公式的前束范式求公式的前束范式
35、求公式的前束范式求公式的前束范式(1)(1)xF(xF(x,x,y)y)yG(x,yG(x,y y)tF(t,y)tF(t,y)wG(x,w)(wG(x,w)(换名规则换名规则)t t w(F(t,y)G(x,w)(5.3),(5.4)w(F(t,y)G(x,w)(5.3),(5.4)或者或者 xF(x,xF(x,y y)yG(yG(x x,y),y)xF(x,t)xF(x,t)yG(w,y)(yG(w,y)(代替规则代替规则)x x y(F(x,t)G(w,y)(5.3),(5.4)y(F(x,t)G(w,y)(5.3),(5.4)说明说明q解本题时一定注意，哪些个体变项是约束出现，解本题时
36、一定注意，哪些个体变项是约束出现，哪些是自由出现，特别要注意那些既是约束出哪些是自由出现，特别要注意那些既是约束出现又是自由出现的个体变项。不能混淆现又是自由出现的个体变项。不能混淆。例例例例5.8 5.8 5.8 5.8 求公式的前束范式求公式的前束范式求公式的前束范式求公式的前束范式(2)(2)(x x1 1F(F(x x1 1,x,x2 2)x x2 2G(G(x x2 2)x x1 1H(xH(x1 1,x,x2 2,x,x3 3)(x x4 4F(F(x x4 4,x,x2 2)x x5 5G(G(x x5 5)x x1 1H(xH(x1 1,x,x2 2,x,x3 3)x x4 4
37、 x x5 5(F(F(x x4 4,x,x2 2)G()G(x x5 5)x x1 1H(xH(x1 1,x,x2 2,x,x3 3)x x4 4 x x5 5 x x1 1(F(F(x x4 4,x,x2 2)G()G(x x5 5)H(x H(x1 1,x,x2 2,x,x3 3)5.3 5.3 5.3 5.3 一阶逻辑的推理理论一阶逻辑的推理理论一阶逻辑的推理理论一阶逻辑的推理理论q在一阶逻辑中，从前提在一阶逻辑中，从前提A A1 1,A,A2 2,A Ak k出发推结论出发推结论B B的推理形式结的推理形式结构，依然采用如下的蕴涵式形式构，依然采用如下的蕴涵式形式A A1 1,A,A
38、2 2,A,Ak k B B（5.65.6）若式（若式（5.65.6）为永真式，则称）为永真式，则称推理正确推理正确，否则称推理不正确。，否则称推理不正确。q于是，在一阶逻辑中判断推理是否正确也归结为判断（于是，在一阶逻辑中判断推理是否正确也归结为判断（5.65.6）式是否为永真式了。式是否为永真式了。q在一阶逻辑中称永真式的蕴涵式为在一阶逻辑中称永真式的蕴涵式为推理定律推理定律，若一个推理的，若一个推理的形式结构正是某条推理定律，则这个推理显然是正确的。形式结构正是某条推理定律，则这个推理显然是正确的。q在一阶逻辑的推理中，某些前提与结论可能是受量词限制，在一阶逻辑的推理中，某些前提与结论可
39、能是受量词限制，为了使用命题逻辑中的等值式和推理定律，为了使用命题逻辑中的等值式和推理定律，必须在推理过程必须在推理过程中有消去和添加量词的规则中有消去和添加量词的规则，以便使谓词演算公式的推理过，以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。程可类似于命题演算中推理理论那样进行。推理定律的来源推理定律的来源推理定律的来源推理定律的来源q命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例q由基本等值式生成的推理定律由基本等值式生成的推理定律q量词分配等值式量词分配等值式q推理规则推理规则量量词消去和引入规则词消去和引入规则命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例
40、命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例q xF(x)xF(x)yG(y)yG(y)xF(x)xF(x)（化简律的代换实例）（化简律的代换实例）q xF(x)xF(x)xF(x)xF(x)yG(y)yG(y)（附加律的代换实例）（附加律的代换实例）q 由基本等值式生成的推理定律由基本等值式生成的推理定律由基本等值式生成的推理定律由基本等值式生成的推理定律q xF(x)xF(x)xF(x)xF(x)q xF(x)xF(x)xF(x)xF(x)q xF(x)xF(x)xF(x)xF(x)q xF(x)xF(x)xF(x)xF(x)q 其他推理定律其他推理定律其他推理定律其他推理定律q
41、xA(x)xA(x)xB(x)xB(x)x(A(x)B(x)x(A(x)B(x)q x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)q x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)q x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)q q对对 x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)的讨论的讨论若若 x(A(x)B(x)x(A(x)B(x)为真，则有一个客体为真，则有一个客体c c，使得，使得A(c)B(c)A(c)B(c)为真，即为真，即A(c)A(c)
42、和和B(c)B(c)都为真，所以都为真，所以 xA(x)xA(x)xB(x)xB(x)也为真。也为真。推理规律推理规律推理规律推理规律（1 1）I I1616：(x)G(x)x)G(x)(x)G(x)x)G(x)；（2 2）I I1717：(x)G(x)(x)G(x)(x)H(x)x)H(x)(x)(G(x)H(x)x)(G(x)H(x)；I I1818：(x)(G(x)H(x)x)(G(x)H(x)(x)G(x)(x)G(x)(x)H(x)x)H(x)；（3 3）I I1919：(x)(G(x)H(x)x)(G(x)H(x)(x)G(x)(x)G(x)(x)H(x)x)H(x)；I I202
43、0：(x)(G(x)H(x)x)(G(x)H(x)(x)G(x)(x)G(x)(x)H(x)x)H(x)。推理规律（续）推理规律（续）推理规律（续）推理规律（续）（4 4）I I2121：(x)(x)(y)G(x,y)y)G(x,y)(y)(y)(x)G(x,y)x)G(x,y)；I I2222：(x)(x)(y)G(x,y)y)G(x,y)(y)(y)(x)G(x,y)x)G(x,y)；I I2323：(y)(y)(x)G(x,y)x)G(x,y)(x)(x)(y)G(x,y)y)G(x,y)；I I2424：(y)(y)(x)G(x,y)x)G(x,y)(x)(x)(y)G(x,y)y)G
44、(x,y)；I I2525：(x)(x)(y)G(x,y)y)G(x,y)(y)(y)(x)G(x,y)x)G(x,y)；I I2626：(y)(y)(x)G(x,y)x)G(x,y)(x)(x)(y)G(x,y)y)G(x,y)；量词关系图量词关系图量词关系图量词关系图等价公式等价公式(x)(x)(y)y)(y)(y)(x)x)I I2222I I2323(y)(y)(x)x)(x)(x)(y)y)I I2424I I2121(x)x)(y)y)(y)y)(x)x)I I2525I I2626(y)y)(x)x)(x)x)(y)y)等价公式等价公式推理规则推理规则推理规则推理规则q为了构造推
45、理系统，还要给出为了构造推理系统，还要给出4 4条重要的推理规则条重要的推理规则,即消去量词和引入量词的规则：即消去量词和引入量词的规则：1 1全称量词消去规则全称量词消去规则(简记为简记为UIUI规则或规则或-)2 2全称量词引入规则全称量词引入规则(简记为简记为UGUG规则或规则或+)3 3存在量词引入规则存在量词引入规则(简称简称EGEG规则或规则或+)4 4存在量词消去规则存在量词消去规则(简记为简记为EIEI规则或规则或-)全称量词消去规则全称量词消去规则全称量词消去规则全称量词消去规则(简记为简记为简记为简记为UIUIUIUI规则或规则或规则或规则或UI)UI)UI)UI)含含义义
46、：如如果果个个体体域域的的所所有有元元素素都都具具有有性性质质A A，则则个个体体域域中中的的任任一元素具有性质一元素具有性质A A。两式成立的条件两式成立的条件：(1)(1)在在第第一一式式中中，取取代代x x的的y y应应为为任任意意的的不不在在A(x)A(x)中中约约束束出出现现的的个体变项。个体变项。(2)(2)在第二式中，在第二式中，c c为任意个体变项。为任意个体变项。(3)(3)用用y y或或c c去去取取代代A(x)A(x)中中自自由由出出现现的的x x时时，一一定定要要在在x x自自由由出出现现的一切地方进行取代。的一切地方进行取代。全称量词消去规则全称量词消去规则全称量词消
47、去规则全称量词消去规则(简记为简记为简记为简记为UIUIUIUI规则或规则或规则或规则或UI)UI)UI)UI)举例举例当当A(x)A(x)为原子公式时，比如为原子公式时，比如A(x)=F(x)A(x)=F(x)，则当，则当 xA(x)xA(x)为为真时，对于个体域中任意的个体变项真时，对于个体域中任意的个体变项y y，不会出现，不会出现F(y)F(y)为为假的情况。假的情况。当当A(x)A(x)不是原子公式时，如不是原子公式时，如y y已在已在A(x)A(x)中约束出现了，就中约束出现了，就不能用不能用y y取代取代x x，否则会出现，否则会出现 xA(x)xA(x)为真而为真而A(y)A(
48、y)为假的情为假的情况。况。考虑个体域为实数集合，公式考虑个体域为实数集合，公式A(x)=A(x)=yF(x,y)yF(x,y)为为xyxy。当对公式当对公式 xA(x)=xA(x)=x x yF(x,y)yF(x,y)使用使用UIUI规则时，用规则时，用y y取代取代x x，就会得到，就会得到A(y)=A(y)=yF(y,y)yF(y,y)，即，即 y(yy)y(yy)，这显然是假，这显然是假命题。原因是违背了条件命题。原因是违背了条件(1)(1)。若用若用z z取代取代x x，得，得A(z)=A(z)=yF(z,y)=yF(z,y)=y(zy)y(zy)就不会产生就不会产生这种错误。这种错
49、误。全称量词引入规则全称量词引入规则全称量词引入规则全称量词引入规则(简记为简记为简记为简记为UGUGUGUG规则或规则或规则或规则或UG)UG)UG)UG)该式成立的条件是：该式成立的条件是：(1)(1)无论无论A(y)A(y)中自由出现的个体变项中自由出现的个体变项y y取何值，取何值，A(y)A(y)应该均为真。应该均为真。(2)(2)取代自由出现的取代自由出现的y y的的x x也不能在也不能在A(y)A(y)中约束出现。中约束出现。举例举例取个体域为实数集，取个体域为实数集，F(x,y)F(x,y)为为xyxy，A(y)=A(y)=xF(x,y)xF(x,y)。显然显然A(y)A(y)
50、满足条件满足条件(1)(1)。对对A(y)A(y)应用应用UGUG规则时，若取已约束出现的规则时，若取已约束出现的x x取代取代y y，会得，会得到到 xA(x)=xA(x)=x x x(xx)x(xx)，这是假命题。，这是假命题。产生这种错误的原因是违背了条件产生这种错误的原因是违背了条件(2)(2)。若取若取z z取代取代y y，得，得 zA(z)=zA(z)=z z x(xz)x(xz)为真命题。为真命题。存在量词引入规则存在量词引入规则存在量词引入规则存在量词引入规则(简称简称简称简称EGEGEGEG规则或规则或规则或规则或EG)EG)EG)EG)该式成立的条件是：该式成立的条件是：(