《一阶逻辑等值演算与推理资料》由会员分享，可在线阅读，更多相关《一阶逻辑等值演算与推理资料（75页珍藏版）》请在金锄头文库上搜索。
1、第5章 一阶逻辑等值演算与推理,离 散 数 学,本章说明,本章的主要内容 一阶逻辑等值式与基本等值式 置换规则、换名规则、代替规则 前束范式 一阶逻辑推理理论 本章与其他各章的关系 本章先行基础是前四章 本章是集合论各章的先行基础,本章主要内容,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是等值的。 记做AB，称 AB 是等值式。,例如：,判断公式A与B是否等值，等价于判断公式 AB是否为永真式。 谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。,说明,一阶逻辑中的一些基本而重要等值式,代换实例 消去量词等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式,代换实例,由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式模式给出的代换实例都是一阶逻辑的等值式的模式。 例如： (1)xF(x) xF(x) （双重否定律）
3、(2)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）,在谓词逻辑中，需时
4、刻注意量词的辖域，不得随意扩张或收缩量词的辖域。 例. 设个体域为D，aD，P(x)为D上任意一个谓词。 (1)判断x(P(x)P(a)和xP(x)P(a)是否等值。 (2)判断x(P(x)P(a)和xP(x)P(a)是否等值。 解：(1) 任取解释I， 若P(a) 在I下为真,则xP(x)P(a)在I下为真; 若P(a) 在I下为假,则xP(x)在I下为假,故 xP(x)P(a)在I下为真 因此,xP(x)P(a) 是恒真公式.,量词的辖域（即作用範圍）,而x(P(x) P(a)不是恒真公式。设 解释I为： D=1，2 a 1 P(1) P(2) 0 1 则 TI(x(P(x) P(a) =
5、 TI (P(1) P(1) (P(2) P(1) = 1 0 = 0,(2) 任取解释I，由P(a) P(a)为真，知， 存在xD，使得P(x) P(a)为真，即 x（P(x) P(a)）为真。 因此，x（P(x) P(a)）为恒真公式。 而xP(x) P(a)不是恒真公式。对于解释I， 若xP(x)在I下为0，则xP(x) P(a)在I下为1。 若xP(x)在I下为1，则如果P(a)在I下为1，则xP(x) P(a)在I下 为1，否则如果P(a)在I下为0，则xP(x) P(a)在I下为0。 比如，对于（1）中给出的解释I， TI(xP(x) P(a) = (P(1)P(2) P(1) =
6、 (01) 0 = 0 因此，x(P(x) P(a)和xP(x) P(a)不等价。,判断x(P(x)P(a)和xP(x)P(a)是否等值,量词辖域收缩与扩张等值式,设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则 （1） x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) BxA(x) （2） x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) BxA(x),（5.3）,（5.4）,证明：设G= xA(x)B，H= x(A(x)B) 任取解释I， 若TI(G
7、)=1，则 若TI(B)=1，则对于所有的x，无论A(x)取何真值，A(x)B = 1，即TI(H)= TI(x(A(x)B) = 1。 若TI(B)=0，则TI(xA(x)=0，即对于所有的x， TI(A(x)=0，所以，对于所有的x，TI(A(x)B)=1，即TI(x(A(x)B)=1，亦即TI(H)=1。 若TI(G)=0，则必有TI(xA(x)=1，且TI(B)=0，于是存在x0D， 使得TI(A(x0) )=1，即TI(A(x0)B)=0，从而TI(x(A(x)B)=0，亦即TI(H)=0。 因此，(xA(x)B) x(A(x)B)。,证明 x(A(x)B) xA(x)B,例. 设G
8、= x(A(x)B(x)，H= x A(x) x B(x) G，H不等价。 举反例即可 I: D=2，3 A(2) A(3) B(2) B(3) 1 0 0 0 TI(G)=0 TI(H)=1,证明: x(A(x)B) xA(x)B,xA(x)B xA(x)B xA(x)B x(A(x)B) x(A(x)B),xA(x)B xA(x)B x A(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）,例如，“联欢会上所
9、有人既唱歌又跳舞”和“联欢会上所有人唱歌且所有人跳舞” ，这两个语句意义相同。故有(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),5.5 的對偶式成立嗎？,一阶逻辑等值演算的三条原则,置换规则：设(A)是含公式A的公式，(B)是用公式B取代(A)中所有的A之后的公式，若AB，则(A)(B)。 换名规则：设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余
10、部分不变，设所得公式为A，则AA。 代替规则：设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A，则AA。,说明,一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B是一阶逻辑公式。,例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)G(y)L(x，y) xy(F(x)G(y)L(x,y),例5.5的证明,（1） x(M
11、(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)L(x，y) xy(F(x)G(y)L(x,y
12、) 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),在命题逻辑中，引进过公式的标准形式，即范式。因为一个公式，在等价意义下，可以有各种不同的表示，因此，公式的标准表示形式就是一个有意义的问题。 在命题逻辑中，已经使用过范式来解决公式的判定问题，范式在谓词逻辑中有同样重要的作用。 本节讨论谓词逻辑中公式的两种标准形式: 前束范式 斯科伦（Skolem） 范式（简要介绍，不作要求）,5.2 一阶逻辑的范式,定义5.2 设A为一个一阶逻辑公式，若A具有如下形式 Q1
13、x1Q2x2 QkxkB 则称A为前束范式，其中Qi(1ik)为或，B为不含量词的公式。 亦即：A中的一切量词都位于该公式的最前端(不含否定词)且这些量词的辖域都延伸到公式的末端。 前束范式的例子： 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),前束范式,前束范式存在定理,定理5.1 一阶逻辑中的任何公式都存在与之等值的前束范式。,证明：通过如下算法，可将公式化成等价的前束范式。 1.利用量词转化公式，把否定符号深入到指导变元的后面。 xA(x) xA(x)
14、 xA(x) xA(x) 2.如果必要的话，将约束变量改名。 3.利用量词辖域收缩、扩张等值式把量词移到全式的最前面，这样便得到与公式等价的前束范式。,说明,求前束范式的过程，就是制造量词辖域可以扩大的条件，进行量词辖域扩大。 任何公式的前束范式都是存在的，但一般说来，并不唯一。 利用一阶逻辑等值式以及三条变换规则（置换规则、换名规则、代替规则）就可以求出与公式等值的前束范式，或所谓公式的前束范式。,例5.6 求公式的前束范式,（1） xF(x)xG(x) xF(x)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 求公
