谓词逻辑复习

一、重点内容

1．谓词与量词 谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念．谓词是用来刻划个体词的性质或事物之间关系的词. 个体词分个体常项(用a, b, c,…表示)和个体变项(用x, y, z,…表示)；谓词分谓词常项(表示具体性质和关系)和谓词变项(表示抽象的或泛指的谓词)，用F, G, P,…表示. 注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题. 量词，是在命题中表示数量的词，量词有两类：全称量词，表示“所有的”或“每一个”；存在量词，表示“存在某个”或“至少有一个”. 在谓词逻辑中，使用量词应注意以下几点：

(1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变. (2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域. (3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义. 谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题. 所谓解释就是使公式中的每一个变项都有个体域中的元素相对应.

在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域．一般地，使用全称量词，特性谓词后用；使用存在量词，特性谓词后用.

2．公式与解释 谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材). 命题的符号化结果都是谓词公式.

例如x(F(x)G(x))，x(F(x)G(x))，xy(F(x)F(y)L(x,y)H(x,y))等都是谓词公式. 变元与辖域，在谓词公式xA和xA中，x是指导变元，A是相应量词的辖域. 在x和x的辖域A中，x的所有出现都是约束出现，即x是约束变元，不是约束出现的变元，就是自由变元. 也就是说，量词后面的式子是辖域. 量词只对辖域内的同一变元有效. 换名规则，就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变.

代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号. 解释(赋值)，谓词公式A的个体域D是非空集合，则 (1) 每一个常项指定D中一个元素； (2) 每一个n元函数指定Dn到D的一个函数； (3) 每一个n元谓词指定Dn到{0,1}的一个谓词； 按这个规则做的一组指派，称为A的一个解释或赋值.

在有限个体域下，消除量词的规则为：如D＝{a1,a2,…,an}，则 xA(x)A(a1)A(a2)...A(an)xA(x)A(a1)A(a2)...A(an) 谓词公式分类，在任何解释下，谓词公式A取真值1，公式A为逻辑有效式(永真式)；在任何解释下谓词公式A取真值0，公式A为永假式；至少有一个解释使公式A取真值1，公式A称为可满足式. 3．前束范式 一个谓词公式的前束范式仍是谓词公式. 若谓词公式F等值地转化成 Q1x1Q2x2...QkxkB 那么Q1x1Q2x2...QkxkB就是F的前束范式，其中Q1，Q2，…，Qk只能是或，x1,x2,…,xk是个体变元，B是不含量词的谓词公式.

1

每个谓词公式F都可以变换成与它等值的前束范式. 其步骤如下： ① 消去联结词，；

② 将联结词移至原子谓词公式之前；

③ 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；

④将x,x移至整个公式最左边； ⑤ 得到公式的前束范式.

二、实例

例1 将下列命题符号化：

(1) 每个自然数都是整数，而有些整数不是自然数． (2) 不是所有的素数都不是偶数 (3) 鸟会飞．

注意：一般地，全称量词“”后，跟条件联结词“”；存在量词“”后，跟合取联结词“”.

解 (1) 设N(x)：x是自然数，Z(y)；y是整数，则命题符号化为：

x(N(x)Z(x))x(Z(x)N(x))．

(2) 设F(x)：x是素数，E(x)：x是偶数，命题符号化为： x(F(x)E(x))或x（F（x）E（x））

(3) 设F(x)：x是鸟，G(x)：x会飞翔．则命题符号化为：x(F(x)G(x)) ． 例2 设谓词公式x(P(x,y)zQ(y,x,z))yR(y,z)F(y)，试写出量词的辖域，并指出该公式的自由变元和约束变元．

解 x的辖域是：P(x, y)zQ(y, x, z)；

z的辖域是：Q(y, x, z)； y的辖域是：R(y, x)

公式的自由变元是：y, z；约束变元是：x, y, z． 例3 求谓词公式x(PQ(x))R(f(a))的真值．

其中P：43，Q（x）：x1，R（x）：x2．

f（3）=1，f（1）=5，f（5）= 3．a：5．

个体域D=（3，1，5）．

解 x(PQ(x))R(f(a))

=(PQ(3))(PQ(1))(PQ(5))R(f(5)) =(10)(10)(11)R(3)

00110

注：这是给定解释下，求谓词公式的真值，个体域有限，比较好求．只需将量词消去，函数值代入谓词，根据谓词的真值，即可求出谓词公式的真值.

要判断一个谓词公式的真、假是较为难的. 在谓词逻辑中，在任何解释下都真的公式，才是永真式；在任何解释下公式A为假，才是永假式；公式A不总是假，或者至少有一个解释使得公式A为真，才是可满足式. 困难之点是在全总个体域中所有的解释如何说清楚. 因此只能要求会作简单问题. 例4 将谓词公式x(P(x)R(x)Q(x,z))xR(x)zS(x,z)中的约束变元换名．

解 x(P(x)R(x)Q(x,z))xR(x)zS(x,z)

=u(P(u)R(u)Q(u,z))vR(v)wS(x,w) 例5 求谓词公式x(F(x)yG(x,y,z))zH(x,y,z)的前束范式．

2

. 解 ①消去联结词(若有也要消去).

x(F(x)yG(x,y,z))zH(x,y,z)

x(F(x)yG(x,y,z))zG(x,y,z) ② 将联结词移至原子公式之前.

x(F(x)yG(x,y,z))zH(x,y,z)

③ 换名.

u(F(u)vG(u,v,z))wH(x,y,w)

(自由变元的x, y, z未改)

④ 把量词提到整个公式的前面.

uvw(F(u)G(u,v,z)H(x,y,w)) (前束范式) (或)uvw(F(u)G(u,v,z)H(x,y,w))

为所求前束范式. 注：变元字母表示不惟一．

写在一起，所求前束范式是

x(F(x)yG(x,y,z))zH(x,y,z)

x(F(x)yG(x,y,z))zG(x,y,z) x(F(x)yG(x,y,z))zH(x,y,z)

u(F(u)vG(u,v,z))wH(x,y,w)

uvw(F(u)G(u,v,z)H(x,y,w)) (前束范式) (或)uvw(F(u)G(u,v,z)H(x,y,w))

为所求前束范式.

注：重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换名规则，把一个谓词公式化为量词在最前面，后面不含量词的公式，即前束范式. 虽然前束范式是谓词公式的一种标准形式，但是一般一个谓词公式的前束范式并不是唯一的.

三、练习题

1. 选择填空题：

(1) 谓词公式x(P(x)yR(y))Q(x)中量词x的辖域是( C )

(A) x(P(x)yR(y)) (B) P(x) (C) P(x)yR(y) (D) Q(x) (2) 谓词公式xA(x)xA(x)的类型是（ B ） (A) 永真式 (B) 矛盾式

(C) 非永真式的可满足式 (D) 不属于(A),(B),(C)任何类型 (3) 设个体域为整数集，下列公式中其真值为1的是( A ) (A) xy(xy0) (B) yx(xy0)

(4) 公式x(P(x)Q(x,y))zR(y,z)S(x))的自由变元是 , 约

(C)xy(xy0) (D) xy(xy0)

束变元是：y,x ; x,z (5) 换名规则施于 变元，代入规则施于 变元

(6) 谓词公式xP(x)(xQ(x)xQ(x))的类型是(A )

(A) 永真式 (B) 永假式 (C) 非永真的可满足式 (D) 蕴涵式

(7) 设个体域是整数集合，P代表xy((xy)(xy)x)，下面4个命题中为真的是( C ) (A)P是真命题 (B) P是假命题 (C) P是谓词公式，但不是命题 (D) P不是谓词公式

3

(8) 设个体域D＝{a,b},公式x(G(x)yH(x,y))消去量词化为7. (G(a)(H(a,a)H(a,b))) (G(b)(H(b,a)H(b,b))) ．

2. 设个体域D＝{岳飞，文天祥，秦荟}，谓词F(x)：x是民族英雄．求xF(x)的真值． 3. 设P是二元谓词，给定解释I如下：D＝{a,b},P(a,a)=P(b,a)=1，P(b,a)=P(b,b)=0 求下列公式的真值：(1) xP(x,x)； (2) xyP(x,y); (3) xyP(x,y)

4. 用归谬法，构造下面的推理证明.

xA(x)xB(x)x(A(x)B(x))

四、练习题答案

1. (1) C (2) B (3) A (4) y,x ; x , z (5) 约束，自由 (6) A (7) C (8) (G(a)(H(a, a)H(a, b))) (G(b)(H(b, a)H(b, b))) ．

2. 设a, b, c分别为岳飞，文天祥和秦桧，xF(x)F(a)F(b)F(c)0

3. (1)0；

(2)xy(P(y, x)yP(y, a)yP(y, b)(P(a, a)P(b, a))(P(a, b) P(b, b))100 (3) xy(P(x, y)yP(a, y)xP(b, y)=P(a, a)P(a, b)P(b, a)P(b. b)1 4. 前提：xA(x)xB(x) 结论：x(A(x)B(x))

证明：① (x(A(x)B(x))) 附加前提

② x((A(x)B(x))) T①E

③ (A(c)B(c)) T①②ES ④ A(c)B(c) T③ E

⑤ A(c) T④ I ⑥ B(c)A(c) T④ .E

⑦ B(c) T⑥ I ⑧ xA(x)xB(x) P

⑨ x(A(x)B(x)) T⑧ E

⑩ A(c)B(c) T⑨ US 11 A(c) T⑩ ,⑦ I 12 A(c)A(c) T 11 , ⑤I 可见，推理成立．

4