1、第 5 章 一阶逻辑等值演算与推理,5.1 一阶逻辑等值式与置换规则定义5.1 设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值的。记做AB，称AB是等值式。 谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。下面主要讨论关于量词的等值式。 一、基本等值式 第一组 代换实例 由于命题逻辑中的重言式的代换实例都,是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。例如 xF(x) xF(x) 与 xy(F(x,y)G(x,y) xy(F(x,y)G(x,y)都是(2.1)式（双重否定律）的代换实例。又如： F(x)G(y) F(x)G(
2、y) 与 x(F(x)G(y)zH(z) x(F(x)G(y)zH(z) 等都是(2.12)式（蕴涵等值式）的代换实例。,第四组 量词辖域收缩与扩张等值式 设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) (5.3)(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.4) 注意：这些等值式的条件,第五组 量词分配等值式 设A(x)，B(x)是任意的含自由出现
3、个体变项x的公式，则 (1) x(A(x)B(x)）xA(x)xB(x)(2) x(A(x)B(x) xA(x)xB(x)(5.5),二、基本规则 1置换规则 设(A)是含公式A的公式，(B)是用公式B取代(A)中所有的A之后的公式，若AB，则(A) (B). 一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B是一阶逻辑公式。 2换名规则 设A为公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A，则AA.,3代替规则 设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现
4、过的个体变项符号代替，A中其余部分不变，设所得公式为A，则AA. 三、等值演算 例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) (换名规则) 原公式中，x，y都是既约束出现又有自由出现的个体变项，只有z仅自由出现。而在最后得到的公式中，x，y，z，t，w中再无既是约束出现又有自由出现个体变项了。还可以如下演算，也可以达到要求。 xF
5、(x,y,z)yG(x,y,z) xF(x,t,z)yG(x,y,z) (代替规则) xF(x,t,z)yG(w,y,z) (代替规则),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 证明 (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自由出现的公式。证 (1)只要证明在某个解释下两边的式子不等 值。,取解释I：个体域为自然数集合N；取F(x)：x是奇数，代替A(x)；取G(x
6、)：x是偶数，代替B(x). 则x(F(x)G(x)为真命题，而xF(x)x G(x)为假命题。两边不等值。 对于(2)可以类似证明。 取解释I：个体域为实数集合R；取F(x)：x是奇数，代替A(x)；取G(x)：x是偶数，代替B(x). 则x(A(x)B(x) 为假命题，而xA(x)xB(x)为真命题。 本例说明，全称量词“”对“”无分配律。同样的，存在量词“”对“”无分配律。但当B(x)换成没有x出现的B时，则有 x(A(x)B) xA(x)B (5.3)x(A(x)B) xA(x)B (5.4),例5.3 设个体域为Da,b,c，将下面各公式的量词消去： (1) x(F(x)G(x) (
7、2) x(F(x)yG(y) (3) xyF(x,y) 解 (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)将量词的辖域缩小，演算过程较长。注意，此时yG(y)是与x无关的公式B. (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) 在演算中先消去存在量词也可以，得到结果是等值的。,
8、例5.4 给定解释I如下： （a）个体域 D2, 3. （b）D中特定元素 =2（c）D上的特定函数 (x)为： (2)=3, (3)=2 . （d）D上的特定谓词 (x,y)为：(2,2)= (2,3)= (3,2)=1, (3,3)=0。 (x,y)为： (2,2)= (3,3)=1, (2,3)= (3,2)=0。 (x)为： (2)=0， (3)=1.,在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)解(1) x(F(x)G(x,a) (F(2)G(2,2) (F(3)G(3,2)
9、(01)(11) 0 (2) x(F(f(x)G(x,f(x) (F(f(2)G(2,f(2)(F(f(3)G(3,f(3) (F(3)G(2,3)(F(2)G(3,2) (11)(01) 1,(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 证明下列等值式。 (1)x(M(x)F(x) x(M(x)F(x) (2)x(F(x)G(x) x(F(x
10、)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) 证 (1)x(M(x)F(x) x(M(x)F(x) (公式(5.2) x(M(x)F(x) (置换规则) x(M(x)F(x) (置换规则),(2) x(F(x)G(x)x(F(x)G(x) (公式(5.2)x(F(x)G(x) (置换规则) x(F(x)G(x) (置换规则) (3) 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
11、(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) xy(F(x)G(y)L(x，y)xy (F(x)G(y)L(x,y),5.2 一阶逻辑的前束范式,一、一阶逻辑公式的标准形前束范式定义5.2 设A为一个一阶逻辑公式，若A具有如下形式 Q1x1Q2x2QkxkB 其中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)
12、H(x，y) 等都不是前束范式。,可证明每个一阶逻辑公式都能找到与之等价的前束范式。 定理5.1 (前束范式存在定理)一阶逻辑中的任何公式都存在与之等值的前束范式。,下面用一阶逻辑的等值演算求前束范式。 例5.6 求下面公式的前束范式： (1) xF(x)xG(x) 解 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)第二式),或者 xF(x)xG(x) xF(x)xG(x) (5.2)第二式) x (F(x)G(x) (5.5)第一式) 由此可知，(1)中公式的前束范式
13、是不唯一的。 另外， yx(F(x)G(y) 也是(1)中公式的前束范式。,(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(x) (5.3)第一式) 例5.8 求下列各公式的前束范式： (1) xF(x,y)yG(x,y) 解 xF(x,y)yG(x,y) tF(t,y)wG(x,w) (换名规则)t(F(t,y)w G(x,w) (5.4) 第三式tw(F(t,y)G(x,w) (5.4) 第四式,或者 xF(x,y)yG(x,y) xF(x,t)yG(w,y) (代替规则
14、) xy(F(x,t)G(w,y) ( (5.4) 第三式、第四式)(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) x4x5x1(F(x4,x2)G(x5)H(x1,x2,x3),5.3 一阶逻辑推理理论,本节讨论推理理论。 一、推理定律 第一组 命题逻辑推理定律的代换实例例如：xF(x)yG(y) xF(x) xF(x) xF(x)yG(y) 分别为命题逻辑中化简律和附加律的代换实例。 第二组 由基本等值式生成的推理定律 上一节给出的两组等值
15、式中的每个等值式可生成两个推理定律。例如：,xF(x) xF(x) xF(x) xF(x) 和 xF(x) xF(x) xF(x) xF(x) 分别由双重否定律和量词否定等值式生成。 第三组 还有下面各重要推理定律例如： (1) xA(x)xB(x) x(A(x)B(x) (2) x(A(x)B(x) xA(x)xB(x) (3) x(A(x)B(x) x A(x)x B(x) (4) x(A(x)B(x) xA(x)xB(x),二、推理规则 1全称量词消去规则(简记为UI规则或UI)两式成立的条件是： （1）在第一式中，取代x的y应为任意的不在A(x)中约束出现的个体变项。 （2）在第二式中
16、，c为任意个体变项。 （3）用y或c去取代A(x)中自由出现的x时，一定要在x自由出现的一切地方进行取代。,2全称量词引入规则(简记为UG规则或UG)该式成立的条件是： （1）无论A(y)中自由出现的个体变项y取何值，A(y)应该均为真。 （2）取代自由出现的y的x也不能在A(y)中约束出现。 3存在量词引入规则(简称EG规则或EG),该式成立的条件是： （1）c是特定的个体常项。（2）取代c的x不能在A(c)中出现过。 4存在量词消去规则(简记为EI规则或EI)该式成立的条件是： （1）c是使A为真的特定的个体常项。 （2）c不在A(x)中出现。 （3）若A(x)中除自由出现的x外，还有其它
17、自由出现的个体变项，此规则不能使用。,三、一阶逻辑自然推理系统F定义5.3 自然推理系统F定义如下： 1 字母表。同一阶语言的字母表 2 合式公式。同合式公式的定义 3 推理规则： （1） 前提引入规则。 （2） 结论引入规则。 （3） 置换规则。 （4） 假言推理规则。 （5） 附加规则。 （6） 化简规则。 （7） 拒取式规则。,（8） 假言三段论规则。 （9） 析取三段论规则。 （10）构造性二难推理规则。 （11）合取引入规则。（12）UI规则。 （13）UG规则。 （14）EI规则。 （15）EG规则。 F中的推理过程类似命题演算自然推理系统P。例5.9 设个体域为实数集合，F(x,
18、y)为xy. 指出在推理系统F中，以x yF(x，y)(真命题)为前提，推出xF(x,c)(假命题)的下述推理证明中的错误。, xyF(x,y) 前提引入 yF(z,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 在自然推理系统F中，构造下面推理的证明：任何自然
19、数都是整数；存在着自然数。所以存在着整数。个体域为实数集合R。 解 先将原子命题符号化。设 F(x):x为自然数，G(x):x为整数。前提：x(F(x)G(x), xF(x)结论：xG(x)证明： xF(x) 前提引入 F(c) EI规则 x(F(x)G(x) 前提引入 F(c)G(c)UI规则, G(c) 假言推理 xG(x)EG规则 以上证明的每一步都是严格按推理规则及应满足的条件进行的。因此，前提的合取为真时，结论必为真。但如果改变命题序列的顺序会产生由真前提推出假结论的错误。如果证明如下进行： x(F(x)G(x) 前提引入 F(c)G(c) UI规则 xF(x) 前提引入 F(c)
20、EI规则,在中取c= ,则F( )G( )为真（前件假）,于是中F( )为假，这样从前件真推出了假的中间结果。例5.11 在自然推理系统F中，构造下面推理的证明。 前提：x(F(x)G(x)，x（F(x)H(x)） 结论：x（G(x)H(x)） 证明：注意，在证明序列中先引入带存在量词的前提。 x(F(x)H(x) 前提引入 F(c)H(c) EI规则 x(F(x)G(x) 前提引入, F(x)G(x) UI规则 F(c) 化简 G(c) 假言推理 H(c) 化简 G(c)H(c) 合取 x(G(x)H(x) EG规则 例5.12 在自然推理系统 F中，构造下面推理的证明：（个体域为实数集合）
21、。 不存在能表示成分数的无理数；有理数都能表示成分数。因此，有理数都不是无理数。 解 设F(x):x为无理数，G(x):x为有理数，H(x):x能表示成分数。,前提：x(F(x)H(x)，x(G(x)H(x) 结论：x(G(x)F(x) 证明： 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(x)F(x) 假言三段论 x(G(x)F(x) UG规则 在本题的证明中，要注意以下两点：,1注意x（F(x)H(x)）不是前束范式，因而不能对它使用EI规则。 2因为结论中的
22、量词是全称量词，因而在使用UI规则时用第一式，而不能用第二式。,主要内容等值式与基本的等值式在有限个体域中消去量词等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式2. 基本规则置换规则换名规则代替规则3. 前束范式,学习要求 深刻理解重要的等值式，并能熟练地使用它们。2. 熟练地使用置换规则、换名规则和代替规则。3. 准确地求出给定公式的前束范式（形式可不唯一）。4. 正确地使用UI、UG、EI、EG规则，特别地要注意它们之间的关系。5. 对于给定的推理，正确地构造出它的证明。,练 习 题,（3）x(F(x)y(F(y)H(x,y)L(x,y) xy(F(x)F(y)H(x,y)L(
23、x,y) 答案 （1）x(F(x)G(x) x(F(x)G(x) （量词否定等值式） x(F(x)G(x) （蕴涵等值式）,1.证明下列等值式（1）x(F(x)G(x)x(F(x)G(x)（2）x(F(x)G(x) x(F(x)G(x),x(F(x)G(x) （德.摩根律） 至此，回答了第四章习题课中题2中（3）的两种符号化形式是等值的。（2）x(F(x)G(x)x(F(x)G(x)（量词否定等值式）x(F(x)G(x) （德.摩根律）x(F(x)G(x) （蕴涵等值式） 这又证明了第四章习题课题2中（4）的两种符号化形式是等值的。,（3）x(F(x)y(F(y)H(x,y)L(x,y) xy
24、(F(x)(F(y)H(x,y)L(x,y) （辖域扩张等值式） xy(F(x)（(F(y)H(x,y)） L(x,y) （蕴涵等值式） xy(F(x)F(y)H(x,y)L(x,y) （德.摩根律）xy(F(x)F(y)H(x,y)L(x,y) （蕴涵等值式）,2.设个体域D=a,b,c，消去下列各公式的量词 （1）xy(F(x)G(y)（2）xy(F(x)G(y) （3）x(F(x,y)yG(y) 分析（1）在有限个体域内消去量词，一般来说，将量词的辖域缩小较为方便。为了说明这点，我们用两种方法做此题。 方法一.量词辖域不缩小，即按此前束范式做 xy(F(x)G(y)x(F(x)G(a)(
25、F(x)G(b)(F(x)G(c)x(F(x)(G(a)G(b)G(c)（幂等律）, (F(a)(G(a)G(b)G(c)(F(b) (G(a)G(b)G(c)(F(c) (G(a)G(b)G(c) (F(a)F(b)F(c)(G(a)G(b)G(c) 在以上的演算中每步都没缩小量词的辖域，只是在第二步用了幂等律，否则将更麻烦。方法二.将量词辖域缩小 xy(F(x)G(y) x(F(x)yG(y) xF(x)yG(y) (F(a)F(b)F(c)(G(a)G(b)G(c),两次使用量词辖域缩小与扩张等值式，演算就简单多了。 （2）xy(F(x)G(y) xF(x)yG(y) (F(a)F(b)
26、F(c)(G(a)G(b)G(c) （3） x(F(x,y)yG(y) xF(x,y)yG(y) (F(a,y)F(b,y)F(c,y)(G(a)G(b)G(c) 在这个演算中，有两点应注意： 在x的辖域中，蕴涵式的后件yG(y)中不含x，故可以缩小x的辖域。, 由于F(x,y）中的y是自由出现的，所以在消去量词后仍有y的自由出现。答案（1）(F(a)F(b)F(c)(G(a)G(b) G(c)（2）(F(a)F(b)F(c)(G(a)G(b)G(c) （3）(F(a,y)F(b,y)F(c,y)(G(a)G(b) G(c),3.求下列公式的前束范式 （1）xF(x)yG(x,y)（2）xF(
27、x,y) xG(x,y) （3）(x1(F(x1,x2)x2G(x2)x2H(x1,x2) 分析 求前束范式的过程，就是制造量词辖域可以扩大的条件，进行量词辖域扩大。（1） xF(x)yG(x,y) xF(x)yG(z,y) （代替规则，将自由出现的x改成z） x(F(x)yG(z,y) xy(F(x)G(z,y),（2） xF(x,y) xG(x,y)(xF(x,y)xG(x,y)(xG(x,y)xF(x,y) (x1F(x1,y)x2G(x2,y)(x3G(x3,y)x4F(x4,y) x1x2(F(x1,y)G(x2,y)x3x4(G(x3,y)F(x4,y)x1x2x3x4(F(x1,
28、y)G(x2,y)(G(x3,y) F(x4,y) 在前束范式中，保证不增加新的约束，并且y还是自由出现。,（3） (x1F(x1,x2)x2G(x2)x2H(x1,x2) (x3F(x3,x2)x4G(x4)x5H(x1,x5) x3x4(F(x3,x2)G(x4)x5H(x1,x5) x3x4x5(F(x3,x2)G(x4)H(x1,x5)答案 答案不唯一，这里给出一组。（1）xy(F(x)G(z,y) （2）x1x2x3x4(F(x1,y)G(x2,y) (G(x3,y)F(x4,y)（3）x3x4x5(F(x3,x2)G(x4)H(x1,x5),4.在自然推理系统F中构造下面推理的证明
29、（1）前提：xF(x)xG(x) 结论：x(F(x)G(x) （2）前提：x(F(x)G(x) 结论：xF(x)xG(x) （3）前提：x(F(x)(G(a)R(x),xF(x) 结论：x(F(x)R(x) 答案 （1）方法一。直接证明。 证明： 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 方法二。归谬法。 x(F(x)G(x) 结论否定的引入 x(F(x)G(x) 置换 (F(c)G(c) EI (F(c)G(c) 置换 F(c)G(c) 置换 xF(x)
30、xG(x) 前提引入 zF(z)xG(x) 置换, zx(F(z)G(x) 置换 F(c)G(c) UI F(c) 化简 G(c) 假言推理 G(c) 化简 G(c)G(c) 合取 为矛盾式，由归谬法可知，推理正确。 注意：本题不能用附加前提证明法,（2）用附加前提证明法 证明： xF(x) 附加前提引入 F(y) UI x(F(x)G(x) 前提引入 F(y)G(y) UI G(y) 假言推理 xG(x) UG 思考：为何（2）能用附加前提证明法，而（1）不能？,（3）证明： xF(x) 前提引入 F(c) EI x(F(x)(G(a)R(x) 前提引入 F(c)(G(a)R(c) UI G
31、(a)R(c) 假言推理 R(c) 化简 F(c)R(c) 合取 x(F(x)R(x) EG 注意：在此证明中，要先消去存在量词。,5.在一阶逻辑自然推理系统F中构造下面推理的证明 （1）所有的人或者是吃素的或者是吃荤的，吃素的常吃豆制品，因而不吃豆制品的人是吃荤的。（个体域为人的集合）。 （2）每个喜欢步行的人都不喜欢骑自行车，每个人或者是喜欢骑自行车或者喜欢乘汽车，有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人的集合）。 答案（1）由于个体域为人类集合，所以不用引入特性谓词，,令F(x)：x是吃素的，G(x)：x是吃荤的， H(x)：x吃豆制品 前提：x(F(x)G(x)，x(F(
32、x)H(x) 结论：x(H(x)G(x) 证明： x(F(x)G(x) 前提引入 F(y)G(y) UI F(y)G(y) 置换 x(F(x)H(x) 前提引入 F(y)H(y) UI F(y)H(y) 置换,H(y)F(y) 置换 H(y)G(y) 假言三段论 x(H(x)G(x) UG（2）令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) 前提引入 H(c) EI x(G(x)H(x) 前提引入,G(c)H(c) UI G(c) 析取三段论x(F(x)G(x) 前提引入F(c)G(c) UIF(c) 拒取式xF(x) EG注意：要先消去存在量词，否则会犯错误。,
