一阶逻辑等值演算与.ppt

《一阶逻辑等值演算与.ppt》由会员分享，可在线阅读，更多相关《一阶逻辑等值演算与.ppt（60页珍藏版）》请在三一办公上搜索。

1、第五章 一阶逻辑等值演算与推理,离 散 数 学,厦门理工学院,本章说明,本章的主要内容一阶逻辑等值式与基本等值式置换规则、换名规则、代替规则前束范式一阶逻辑推理理论本章与其他各章的关系本章先行基础是前四章本章是集合论各章的先行基础,本章主要内容,5.1 一阶逻辑等值式与置换规则5.2 一阶逻辑前束范式5.3 一阶逻辑的推理理论,5.1 一阶逻辑等值式与置换规则,在一阶逻辑中，有些命题可以有不同的符号化形式。例如：没有不犯错误的人令 M(x):x是人。F(x):x犯错误。则将上述命题的符号化有以下两种正确形式：(1)x(M(x)F(x)(2)x(M(x)F(x),我们称(1)和(2)是等值的。,

2、说明,等值式的定义,定义5.1 设A，B是一阶逻辑中任意两个公式，若 AB是永真式，则称A与B是等值的。（这里A,B是谓词公式）记做AB，称 AB 是等值式。,例如：,判断公式A与B是否等值，等价于判断公式AB是否为永真式。谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。,说明,一阶逻辑中的一些基本而重要等值式,代换实例消去量词等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式,代换实例,由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式（P17）模式给出的代换实例都是一阶逻辑的等值式的模式。例如：(1)xF(x)xF(x)（双重否定律）(2

3、)F(x)G(y)F(x)G(y)（蕴涵等值式）(3)x(F(x)G(y)zH(z)（x(F(x)G(y)zH(z)（蕴涵等值式）,消去量词等值式,设个体域为有限集D=a1,a2,an,则有（1）xA(x)A(a1)A(a2)A(an)（2）xA(x)A(a1)A(a2)A(an),（5.1）,量词否定等值式,设A(x)是任意的含自由出现个体变项x的公式，则（1）xA(x)xA(x)（2）xA(x)xA(x),说明,“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。”不存在有性质A的x”与”所有X都没有性质A”是一回事。,（5.2）,量词辖域收缩与扩张等值式,设A(x)是任意的含自由

4、出现个体变项x的公式，B中不含x的出现，则（1）x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x)（2）x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x),（5.3）,（5.4）,证明:xA(x)B x(A(x)B),xA(x)B xA(x)B xA(x)B x(A(x)B)x(A(x)B),量词分配等值式,设A(x)，B(x)是任意的含自由出现个体变项x的公式，则（1）x(A(x)B(x)xA(x)xB(x)（2）x(A(x)B(x)xA(x)xB(x),（5.5）,例如，

5、“联欢会上所有人既唱歌又跳舞”和“联欢会上所有人唱歌且所有人跳舞”，这两个语句意义相同。故有(1)式。由(1)式推导(2)式x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)(xA(x)xB(x)x(A(x)B(x)xA(x)xB(x),一阶逻辑等值演算的三条原则,置换规则：设(A)是含公式A的公式，(B)是用公式B取代(A)中所有的A之后的公式，若AB，则(A)(B)。换名规则：设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A，则AA。代替规则：

6、设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A，则AA。,说明,一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B是一阶逻辑公式。,例5.1,例5.1 将下面公式化成与之等值的公式，使其没有既是约束出现又是自由出现的个体变项。(1)xF(x,y,z)yG(x,y,z)(2)x(F(x,y)yG(x,y,z),(1)xF(x,y,z)yG(x,y,z),tF(t,y,z)yG(x,y,z),(换名规则),tF(t,y,z)wG(x,w,z),(换名规则),或xF(x,y,z)yG(x,y,z),xF

7、(x,t,z)yG(x,y,z),(代替规则),xF(x,t,z)yG(w,y,z),(代替规则),解答,例5.1的解答,(2)x(F(x,y)yG(x,y,z),x(F(x,t)yG(x,y,z),(代替规则),或x(F(x,y)yG(x,y,z),x(F(x,y)tG(x,t,z),(换名规则),解答,例5.2,例5.2 证明（1）x(A(x)B(x)xA(x)xB(x)（2）x(A(x)B(x)xA(x)xB(x)其中A(x)，B(x)为含x自由出现的公式。,只要证明在某个解释下两边的式子不等值。取解释I：个体域为自然数集合N；(1)取F(x)：x是奇数，代替A(x)；取G(x)：x是偶

8、数，代替B(x)。则x(F(x)G(x)为真命题，而xF(x)xG(x)为假命题。两边不等值。,证明,例5.2,(2)x(A(x)B(x)xA(x)xB(x)x(F(x)G(x)：有些x既是奇数又是偶数为假命题；而xF(x)xG(x)：有些x是奇数并且有些x是偶数为真命题。两边不等值。,证明,说明,全称量词“”对“”无分配律。存在量词“”对“”无分配律。当B(x)换成没有x出现的B时，则有 x(A(x)B)xA(x)B x(A(x)B)xA(x)B,例5.3消去量词,例5.3 设个体域为Da,b,c，将下面各公式的量词消去：(1)x(F(x)G(x)(2)x(F(x)yG(y)（方法）(3)x

9、yF(x,y),说明,如果不用公式(5.3)将量词的辖域缩小，演算过程较长。注意，此时yG(y)是与x无关的公式B。,解答,(1)x(F(x)G(x)(F(a)G(a)(F(b)G(b)(F(c)G(c)(2)x(F(x)yG(y)xF(x)yG(y)(公式5.3)(F(a)F(b)F(c)(G(a)G(b)G(c),例5.3消去量词,(3)xyF(x,y)x(F(x,a)F(x,b)F(x,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c)在演算中先消去存在量词也可以，得到结果是等值的。xyF(x,y)yF(a,y)yF(b

10、,y)yF(c,y)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c),例5.4,在解释I下求下列各式的值：（1）x(F(x)G(x,a)（2）x(F(f(x)G(x,f(x)（3）xyL(x,y)（4）yxL(x,y),例5.4 给定解释I如下：,（a）个体域 D2,3,（b）D中特定元素：,（c）D上的特定函数(x)为：,（d）D的特定谓词,例5.4的解答,（1）x(F(x)G(x,a)(F(2)G(2,2)(F(3)G(3,2)(01)(11)0（2）x(F(f(x)G(x,f(x)(F(f(2)G(2,f(2)(F(f(3

11、)G(3,f(3)(F(3)G(2,3)(F(2)G(3,2)(11)(01)1,例5.4的解答,（3）xyL(x,y)(L(2,2)L(2,3)(L(3,2)L(3,3)(10)(01)1（4）yxL(x,y)y(L(2,y)L(3,y)(L(2,2)L(3,2)(L(2,3)L(3,3)(10)(01)0,说明,由(3)，(4)的结果进一步可以说明量词的次序不能随意颠倒。,例5.5,例5.5 证明下列等值式。（1）x(M(x)F(x)x(M(x)F(x)（2）x(F(x)G(x)x(F(x)G(x)（3）xy(F(x)G(y)H(x，y)xy(F(x)G(y)H(x,y)（4）xy(F(x

12、)G(y)L(x，y)xy(F(x)G(y)L(x,y),例5.5的证明,（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)（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),例5.5的证明,（3）xy(F(x)G(y)H(x，y)xy(F(x)G(y)H(x,y)xy(F(x)G(y)H(x，y)x(y(F(x)G(y)H(x，y)xy(F(x)G(y)H(x，y)xy(F(x)G(y)H(x,y),例5.5的证明,（4）xy(F(x)G(y

13、)L(x，y)xy(F(x)G(y)L(x,y)xy(F(x)G(y)L(x，y)x(y(F(x)G(y)L(x，y)xy(F(x)G(y)L(x，y)xy(F(x)G(y)L(x,y)xy(F(x)G(y)L(x,y),5.2 一阶逻辑前束范式,定义5.2 设A为一个一阶逻辑公式，若A具有如下形式Q1x1Q2x2 QkxkB则称A为前束范式，其中Qi(1ik)为或，B为不含量词的公式。前束范式的例子：xy(F(x)G(y)H(x，y)xyz(F(x)G(y)H(z)L(x，y，z)不是前束范式的例子：x(F(x)y(G(y)H(x，y)x(F(x)y(G(y)H(x，y),前束范式存在定理,

14、定理5.1 一阶逻辑中的任何公式都存在与之等值的前束范式。,说明,求前束范式的过程，就是制造量词辖域可以扩大的条件，进行量词辖域扩大。任何公式的前束范式都是存在的，但一般说来，并不唯一。利用一阶逻辑等值式以及三条变换规则（置换规则、换名规则（约束出现）、代替规则（自由出现）就可以求出与公式等值的前束范式，或所谓公式的前束范式。,(1)利用量词转化公式，把否定深入到指导变元的后面。xA(x)xA(x)xA(x)xA(x)(2)利用xA(x)B x(A(x)B)和xA(x)Bx(A(x)B)把量词移到全式的最前面，这样便得到前束范式。,例5.6 求公式的前束范式,（1）xF(x)xG(x)xF(x

15、)yG(y)(换名规则)xF(x)yG(y)(5.2)第二式)x(F(x)yG(y)(5.3)第二式)xy(F(x)G(y)(5.3)第二式)（yx(F(x)G(y)）或者xF(x)xG(x)xF(x)xG(x)(5.2)第二式)x(F(x)G(x)(5.5)第一式),例5.6 求公式的前束范式,（2）xF(x)xG(x)xF(x)xG(x)(5.2)第二式)xF(x)yG(y)(换名规则)x(F(x)yG(y)(5.3)第一式)xy(F(x)G(y)(5.3)第一式),说明,有（1）可知公式的前束范式是不唯一的。,例5.7 求前束范式,(1)xF(x)xG(x)yF(y)xG(x)yx(F(

16、y)G(x)(2)xF(x)xG(x)yF(y)xG(x)yx(F(y)G(x)(3)xF(x)xG(x)yF(y)xG(x)yx(F(y)G(x)(4)xF(x)yG(y)xy(F(x)G(y),例5.8 求公式的前束范式,(1)xF(x,y)yG(x,y)tF(t,y)wG(x,w)(换名规则)tw(F(t,y)G(x,w)(5.3),(5.4)或者xF(x,y)yG(x,y)xF(x,t)yG(w,y)(代替规则)xy(F(x,t)G(w,y)(5.3),(5.4),说明,解本题时一定注意，哪些个体变项是约束出现，哪些是自由出现，特别要注意那些既是约束出现又是自由出现的个体变项。不能混淆

17、。,例5.8 求公式的前束范式,(2)(x1F(x1,x2)x2G(x2)x1H(x1,x2,x3)(x4F(x4,x2)x5G(x5)x1H(x1,x2,x3)x4x5(F(x4,x2)G(x5)x1H(x1,x2,x3)x4(x5(F(x4,x2)G(x5)x1H(x1,x2,x3)x4(x5(F(x4,x2)G(x5)x1H(x1,x2,x3)x4 x5(F(x4,x2)G(x5)x1H(x1,x2,x3)x4x5x1(F(x4,x2)G(x5)H(x1,x2,x3),5.3 一阶逻辑的推理理论,在一阶逻辑中，从前提A1,A2,Ak出发推结论B的推理形式结构，依然采用如下的蕴涵式形式A1

18、,A2,Ak B（5.6）若式（5.6）为永真式，则称推理正确，否则称推理不正确。于是，在一阶逻辑中判断推理是否正确也归结为判断（5.6）式是否为永真式了。在一阶逻辑中称永真式的蕴涵式为推理定律，若一个推理的形式结构正是某条推理定律，则这个推理显然是正确的。在一阶逻辑的推理中，某些前提与结论可能是受量词限制，为了使用命题逻辑中的等值式和推理定律，必须在推理过程中有消去和添加量词的规则，以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。,推理定律的来源,命题逻辑推理定律的代换实例由基本等值式生成的推理定律（消去量词，量词否定，量词辖域收缩与扩张，量词分配等值式）推理规则量词消去和引

19、入规则,命题逻辑推理定律的代换实例,xF(x)yG(y)xF(x)（化简律的代换实例）xF(x)xF(x)yG(y)（附加律的代换实例）,由基本等值式生成的推理定律,xF(x)xF(x)xF(x)xF(x)xF(x)xF(x)xF(x)xF(x),其他推理定律,xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)(P81 ex20)x(A(x)B(x)xA(x)xB(x)（可从定义出发，说明不存在蕴含式的成假解释）,对x(A(x)B(x)xA(x)xB(x)的讨论若x(A(x)B(x)为真，则有一个客体c，使得A(c)B(c)

20、为真，即A(c)和B(c)都为真，所以xA(x)xB(x)也为真。,推理规则,为了构造推理系统，还要给出4条重要的推理规则,即消去量词和引入量词的规则：1全称量词消去规则(简记为UI规则或-)2全称量词引入规则(简记为UG规则或+)3存在量词引入规则(简称EG规则或+)4存在量词消去规则(简记为EI规则或-),全称量词消去规则(UI规则或-),含义：如果个体域的所有元素都具有性质A，则个体域中的任一元素具有性质A。两式成立的条件：(1)在第一式中，取代x的y应为任意的不在A(x)中约束出现的个体变项。(2)在第二式中，c为任意个体常项。(3)用y或c去取代A(x)中自由出现的x时，一定要在x自

21、由出现的一切地方进行取代。,全称量词消去规则(UI规则或-),举例,当A(x)为原子公式时，比如A(x)=F(x)，则当xA(x)为真时，对于个体域中任意的个体变项y，不会出现F(y)为假的情况。当A(x)不是原子公式时，如y已在A(x)中约束出现了，就不能用y取代x，否则会出现xA(x)为真而A(y)为假的情况。考虑个体域为实数集合，公式A(x)=yF(x,y)为xy。当对公式xA(x)=xyF(x,y)使用UI规则时，用y取代x，就会得到A(y)=yF(y,y)，即y(yy)，这显然是假命题。原因是违背了条件(1)。若用z取代x，得A(z)=yF(z,y)=y(zy)就不会产生这种错误。,

22、全称量词引入规则(简记为UG规则或+),该式成立的条件是：(1)无论A(y)中自由出现的个体变项y取何值，A(y)应该均为真。(2)取代自由出现的y的x也不能在A(y)中约束出现。,举例,取个体域为实数集，F(x,y)为xy，A(y)=xF(x,y)。显然A(y)满足条件(1)。对A(y)应用UG规则时，若取已约束出现的x取代y，会得到xA(x)=xx(xx)，这是假命题。产生这种错误的原因是违背了条件(2)。若取z取代y，得zA(z)=zx(xz)为真命题。,存在量词引入规则(简称EG规则或+),该式成立的条件是：(1)c是特定的个体常项。(2)取代c的x不能在A(c)中出现过。,举例,取个

23、体域为实数集，F(x,y)为xy，取A(5)=xF(x,5)。显然A(5)是真命题。在应用EG规则时，若用A(5)中已出现的x取代5，得xxF(x,x)=x(xx)，这是假命题。产生这种错误的原因是违背了条件(2)。若用A(5)中未出现过的个体变项y取代5，得yA(y)=yxF(xy)，这为真命题。,存在量词消去规则(简称EI规则或-),该式成立的条件是：(1)c是使A为真的特定的个体常项。(2)c不在A(x)中出现。(3)若A(x)中除自由出现的x外，还有其它自由出现的个体变项，此规则不能使用（例5.9）,举例,取个体域为自然数集合，F(x)为x是奇数，G(x)为x是偶数。xF(x)与xG(

24、x)都是真命题，则对于某些c和d，可以断定P(c)Q(d)必定为真，但不能断定P(c)Q(c)是真。对xF(x)使用EI规则时，取代x的c一定是特定的个体常项1,3,5等奇数。对xG(x)使用EI规则时，取代x的c一定是特定的个体常项2,4,6等偶数。,定义5.3 自然推理系统定义,1.字母表。同一阶语言的字母表。2.合式公式。同合式公式的定义。3.推理规则：(1)前提引入规则。(2)结论引入规则。(3)置换规则。(4)假言推理规则。(5)附加规则。(6)化简规则。(7)拒取式规则。(8)假言三段论规则。,(9)析取三段论规则。(10)构造性二难推理规则。(11)合取引入规则。(12)UI规则

25、。(13)UG规则。(14)EG规则。(15)EI规则。,例题,例题 在自然推理系统中，构造下面推理的证明所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。解：先将原子命题符号化。设 F(x):x是一个人，G(x):x是要死的，s：苏格拉底。前提：x(F(x)G(x),F(s)结论：G(s)证明：x(F(x)G(x)前提引入 F(s)G(s)UI规则 F(s)前提引入 G(s)假言推理,例5.9,例5.9 设个体域为实数集合，F(x,y)为xy。指出在推理系统F中，以xyF(x，y)(真命题)为前提，推出xF(x,c)(假命题)的下述推理证明中的错误。xyF(x,y)前提引入 yF(z,

26、y)UI规则 F(z,c)EI规则 xF(x,c)UG规则 解 由于c为特定的个体常项，所以xF(x,c)(即为x(xc)为假命题。如果按F中推理规则进行推理，不会从真命题推出假命题。在以上推理证明中，第三步错了，由于F(z,y)中除有自由出现的y，还有自由出现的z，按EI规则应该满足的条件(3)，此处不能用EI规则。用了EI规则，导致了从真命题推出假命题的错误。,例5.10,例5.10 在自然推理系统中，构造下面推理的证明任何自然数都是整数；存在着自然数。所以存在着整数。个体域为实数集合R。解：先将原子命题符号化。设 F(x):x为自然数，G(x):x为整数。前提：x(F(x)G(x),xF

27、(x)结论：xG(x)证明：xF(x)前提引入 F(c)EI规则 x(F(x)G(x)前提引入 F(c)G(c)UI规则 G(c)假言推理 xG(x)EG规则,例5.10说明,以上证明的每一步都是严格按推理规则及应满足的条件进行的。因此，前提的合取为真时，结论必为真。但如果改变命题序列的顺序会产生由真前提推出假结论的错误。如果证明如下进行：x(F(x)G(x)前提引入 F(c)G(c)UI规则 xF(x)前提引入 F(c)EI规则在中取c=,则F()G()为真（前件假）,于是中F()为假，这样从前件真推出了假的中间结果。,例5.11,例5.11 在自然推理系统F中,构造下面推理的证明。前提：x

28、(F(x)G(x),x(F(x)H(x)结论：x(G(x）H(x)提示 在证明序列中先引进带存在量词的前提。,例5.11证明,x(F(x)H(x)前提引入 F(c)H(c)EI规则 x(F(x)G(x)前提引入 F(c)G(c)UI规则 F(c)化简 G(c)假言推理 H(c)化简 G(c)H(c)合取(G(x）H(x)）EG规则,例5.12,例5.12 在自然推理系统F中，构造下面推理的证明：不存在能表示成分数的无理数，有理数都能表示成分数。因此，有理数都不是无理数。个体域为实数集合。,设 F(x):x为无理数，G(x):x为有理数，H(x):x能表示成分数。前提：x(F(x)H(x)，x(

29、G(x)H(x)结论：x(G(x)F(x),解答,例5.12证明,x(F(x)H(x)前提引入 x(F(x)H(x)置换 x(H(x)F(x)置换 H(y)F(y)UI规则 x(G(x)H(x)前提引入 G(y)H(y)UI规则 G(y)F(y)假言三段论 x(G(x)F(x)UG规则,注意x(F(x)H(x)不是前束范式，因而不能对它使用EI规则。因为结论中的量词是全称量词，因而在使用UI规则时用第一式，而不能用第二式。,说明,本章主要内容,等值式与基本的等值式在有限个体域中消去量词等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式基本规则：置换规则、换名规则、代替规则前束范式推理理

30、论：推理的形式结构、推理正确、构造证明新的推理规则：UI、UG、EI、EG,学习要求,深刻理解重要的等值式，并能熟练地使用它们。熟练地使用置换规则、换名规则和代替规则。准确地求出给定公式的前束范式（形式可以不唯一）。正确地使用UI、UG、EI、EG规则，特别地要注意它们之间的关系。一定对前束范式才能使用UI、UG、EI、EG规则，对不是前束范式的公式要使用它们，一定先求出公式的前束范式。记住UI、UG、EI、EG规则的各自使用条件。在同一推理的证明中，如果既要使用UI规则，又要使用EI规则，一定要先使用EI规则，后使用UI规则，而且UI规则使用的个体常项一定是EI规则中使用过的。对于给定的推理

31、，正确地构造出它的证明。,在自然推理系统F中构造推理的证明,前提：xF(x)xG(x)结论：x(F(x)G(x)证明 xF(x)xG(x)前提引入 yF(y)xG(x)置换（换名规则）yx(F(y)G(x)置换 x(F(z)G(x)UI规则 F(z)G(z)UI规则 x(F(x)G(x)UG规则,在自然推理系统F中构造推理的证明,前提：x(F(x)G(x)结论：xF(x)xG(x)证明 xF(x)附加前提引入 F(y)UI规则 x(F(x)G(x)前提引入 F(y)G(y)UI规则 G(y)假言推理 xG(x)UG规则,例题选讲,例题 在自然推理系统F中，构造下面推理的证明：实数不是有理数就是无理数，无理数都不是分数，所以，若有分数，则必有有理数（个体域为实数集合）,设 F(x):x是有理数，G(x):x是无理数，H(x):x是分数。前提：x(F(x)G(x)，x(G(x)H(x)结论：xH(x)xF(x),解答,例题的证明,xH(x)附加前提引入 x(F(x)G(x)前提引入 H(c)EI规则 F(c)G(c)UI规则 x(G(x)H(x)前提引入 G(c)H(c)UI规则 G(c)拒取式 F(c)析取三段论(x)F(x)EG规则,作业,习题五 第一次 2(1)(2)、5(1）第二次 12、15、24、25,