也为真。故在解释I下A为真。由于I的任意性，所以A是永真式。
(2) (2) 取解释I如下：个体域仍为自然数集，F(x,y)：x ? y。 在I下，B的前、后件
均为真。所以B为真，这说明B不是是矛盾式；
再取解释I?：个体域认为N。F(x,y)：x=y。在解释I?下，B的前件为真，后件为假。故B为假，这又说明B不是永真式。 综上所述，B是非永真式的可满足式。 3. 前束范式 一个谓词公式的前束范式，仍然是谓词公式，只是把谓词公式的所有量词均提到公式的开头，而且它的辖域一直延伸到公式的末尾。如若一个谓词公式F等值地转化成
Q1x1Q2x2...QkxkB
那么Q1x1Q2x2...QkxkB就是谓词公式F的前束范式，其中Q1，Q2，…，Qk只能是?或?，而x1,x2,…,xk是个体变元，B是不含量词的谓词公式。如
?x?y(F(x)?(G(y)?H(x,y))),?x?y?z(F(x)?F(y)?G(x,y,z),
?x(F(x)??y(G(y)?H(x,y))),?x(F(x)??y(G(y)?H(x,y,z)))
等是前束范式，而
等不是前束范式，因为没有把所有量词放到公式的开头。 每个谓词公式F都可以变换成与它等值的前束范式。其步骤如下： ① 消去联结词?，?，??；
② 将联结词?向内深入，使之只作用于原子谓词公式；
③ 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；
④ 利用量词辖域的扩张和收缩律，扩大量词的辖域至整个公式； ⑤ 利用分配律将公式化为前束范式。
例2.6 将公式F
?x(A(x)?B(x,y))?(?yC(y)??zD(y,z))
化为前束范式。 解 ①消去联结词?，?，??；
F??(?x(?A(x)?B(x,y))?(??yC(y)??zD(y,z))
② 将联结词?深入至原子公式
F??x?(?A(x)?B(x,y))?(?y?C(y)??zD(y,z)) ??x(A(x)??B(x,y))?(?y?C(y)??zD(y,z))
③ 换名
F??x(A(x)??B(x,y))?(?t?C(t)??zD(y,z))
④ 把量词提到整个公式的前面
F??x?t?z(A(x)??B(x,y))??C(t)?D(y,z))
为所求前束范式。
重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换名规则，把一个谓词公式化为前束范式，虽然前束范式是谓词公式的一种标准形式，但是一般一个谓词公式的前束范式并不是唯一的。
4.谓词逻辑的推理理论 谓词演算的推理是命题演算推理的推广和扩充，命题演算中的一些规则，如基本等值公式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用。但是在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，必须在推理过程中，有消去和附加量词的规则，即US规则(全称量词消去规则)，UG规则(全称量词附加规则)，ES规则(存在量词消去规则)，EG规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行。
例2.7 试证(P?Q)?R?(R?P)?(S?P) 证明 [方法1] 等值演算法。
要证明(P?Q)?R?(R?P)?(S?P)，只需证明
((P?Q)?R)?((R?P)?(S?P))
的真值是1。
证((P?Q)?R)?((R?P)?(S?P))
??(?(?P?Q)?R)?(?(?R?P)?(?S?P))?((?P?Q)??R)?(R??P)?(?S?P)
(E16)(E1,E8,E9)?[((?P?Q)?(R??P))?(?R?(R??P))]?(?S?P)(E7,E7)?[(Q?(?P?(R??P)))?(R??R)?(?R??P)]?(?S?P)(E2,E4,E6) ?[(Q??P)?(?R??P)]?(?S?P)?(Q??R)??P?(?S?P)?(Q??R)?(?P?P)??S?1(E14,E15)(E6)(E2,E4)
(E10,E12,E14) [方法2]形式证明。
① (P?Q)?R P ② R?P CP
③ (P?Q)?P ①,②,I13假言三段式 ④ ?(?P?Q)?P ③,E16
⑤ (P??Q)?P ④,E8,E9,E1 ⑥ P ⑤,E14 ⑦S?P ⑥,I6 ⑧(R?P)?(S?P) ②,⑦,CP
例2.8 证明：?xA(x)??xB(x)??x(A(x)?B(x)) 证明
前提：?xA(x)??xB(x)
结论：?x(A(x)?B(x))
(1) ?(?x(A(x)?B(x))) 附加前提 (2) ?x(?(A(x)?B(x))) (1) ,T,E (3) ?(A(c)?B(c)) (2),ES
(4) A(c) (3),T,E (5) ?B(c) (3),T,E
(6) ?xA(x) (4),EG
(7) ?xA(x)??xB(x) P
(8) ?xB(x) (6),(7),T,E (9) B(c) (8),US (10) ?B(c)?B(c)
(5),(9)矛盾式
三、举例
例1谓词公式?x(P(x)??yR(y))?Q(x)中量词?x的辖域是( )
(A) ?x(P(x)??yR(y)) (B) P(x) (C) P(x)?(?yR(y)) (D) P(x),Q(x) 答案：(C)
解答：?x后面的公式是P(x)?(?yR(y))。故应选择(C)。
例2 设个体域为整数集，下列公式中其值为1的是( )
(A) ?x?y(x?y?0) (B) ?y?x(x?y?0)
(C)?x?y(x?y?0) (D) ??x?y(x?y?0)
答案：(A)
解答：任意一个整数x，都能找到y＝－x，有x+y=0,故(A)式是永真式。
例3 设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y。那么命题“所有演员都佩服某些老师”符号化为( )
(A) ?xL(x)?A(x,y) (B) ?x(L(x)??y(J(y)?A(x,y)) (C) ?x?y(L(x)?J(y)?A(x,y)) (D) ?x?y(L(x)?J(y)?A(x,y)) 答案：(D)
解答：将命题符号化为“?x?y(L(x)?J(y)?A(x,y))”，故应选择(D)。注意：符号
化为“?xL(x)??yJ(y)?A(x,y)”是不对的，它的意义是所有演员和某些老师，x佩服y。
例4 在谓词演算中，P(a)是?xP(x)的有效结论，根据是 ( ) (A)US规则 (B) UG规则 答案：(A)
(C)ES规则 (D)EG规则
?xA(x)解答：全称量词消去规则的定义为?A(c)，即A(c)是?xA(x)的有效结论。故应选择
(A)。
例5 公式?x(P(x)?Q(x,y))??zR(y,z)?S(x))的自由变元是 , 约
束变元是 。 答案：y,x ; x,z
解答：?x的辖域是P(x)?Q(x,y),故x是约束出现，y是自由出现，?z的辖域是
R(y,z)，故z是约束出现，y是自由出现，而S(x)中的x是自由出现。总之y,x是自由变元，
x,z是约束变元。
例6 谓词逻辑公式?xP(x)??xQ(x)的前束范式是 。 答案：?x(?P(x)?Q(x)) 解答：求前束范式
?xP(x)??xQ(x)??(?xP(x))??xQ(x)??x?P(x)??xQ(x)??x(?P(x)?Q(x))
例7 设个体域D＝{a,b},消去公式中的量词，则?xP(x)??xQ(x)? 答案：P(a)?P(b)?(Q(a)?Q(b))
解答：由?x和?x真值的定义，
?xP(x)??xQ(x)?P(a)?P(b)?(Q(a)?Q(b))
例8 换名规则施于 变元，代入规则施于 变元 答案：约束；自由
解答：见换名规则和代入规则的定义。