前束范式

1

第2章谓词逻辑

本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明.

一、重点内容

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＝{a

1

,a

2

,…,a

n

}，则

)(...)()()()(...)()()(

2121nn

aAaAaAxxAaAaAaAxxA

谓词公式分类，在任何解释下，谓词公式A取真值1，公式A为逻辑有效式(永真式)；

在任何解释下谓词公式A取真值0，公式A为永假式；至少有一个解释使公式A取真值1，

公式A称为可满足式.

3.前束范式一个谓词公式的前束范式仍是谓词公式.若谓词公式F等值地转化成

BxQxQxQ

kk

...

2211

2

那么BxQxQxQ

kk

...

2211

就是F的前束范式，其中Q

1

，Q

2

，…，Q

k

只能是或，x

1

,x

2

,…,x

k

是个体变元，B是不含量词的谓词公式.

每个谓词公式F都可以变换成与它等值的前束范式.其步骤如下：

①消去联结词，，；

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

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

号也不同；

④将x,x移至整个公式最左边；

⑤得到公式的前束范式.

4.谓词逻辑的推理理论

谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等值公式，重言蕴含

式以及P，T，CP规则在谓词演算中仍然使用.在谓词演算推理中，某些前提和结论可能受

到量词的限制，为了使用这些推理，引入消去和附加量词的规则，有US规则(全称量词消

去规则)，UG规则(全称量词附加规则)，ES规则(存在量词消去规则)，EG规则(存在量词附

加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行.

二、实例

例2.1将下列命题符号化：

(1)有某些实数是有理数；

(2)所有的人都呼吸；

(3)每个母亲都爱自己的孩子.

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

联结词“”.

解(1)设R(x)：x是实数，Q(x)：x是有理数。

该命题符号化x(R(x)Q(x)).

(2)设全总个体域，设M(x)：x是人.，H(x)：x要呼吸，

该命题符号化为：x(M(x)H(x))

该命题等价说法：“不存在不需要呼吸的人”，符号化为：x(M(x)H(x)).

其实它们是等值的，

x(M(x)H(x))x(M(x)H(x))(x(M(x)H(x)))x(M(x)H(x))

若个体域D为人的集合。H(x)：x要呼吸.则该命题符号化为xH(x).

(3)在全总个体域，设M(x)：x是母亲，L(x,y)：x爱y，A(y)：y是孩子,H(x,y)：x属于

y．命题符号化为：

))),(),()(()((yxLxyHyAyxMx

或

))),(),()()((yxLxyHyAxMyx

若个体域D是所有母亲的集合.

M(x)：x爱自己的孩子，该命题符号化为xM(x).

例2.2指出公式

),()),(),((yxxHzyLyxRyx

中量词的每次出现的辖域，并指出变元的每次出现是约束出现，还是自由出现，以及公式的

约束变元，自由变元.

解在公式),()),(),((yxxHzyLyxRyx中，x只有一次出现，辖域是

)),(),((zyLyxRy；y只有一次出现，辖域是),(),(zyLyxR；x只有一次出现，

辖域是H(x,y).变元x在该公式中有四次出现，其中第1次、第2次出现是在x及其辖域中，

故是约束出现；第3次，第4次出现是在x及其辖域中，也是约束出现。这四次出现都是

约束出现，所以x是该公式的约束变元.变元y在该公式中也有四次出现.其中第1次是在

3

y中，第2次和第3次出现是在y的辖域中，是约束出现，第4次出现是自由出现，故y

在该公式中有3次约束出现，1次自由出现，因此变元y既是该公式的约束变元，也是自由

变元.变元z在该公式中只有一次自由出现，所以z是该公式的自由变元.

注意，由例2.2看到，同一个个体变项，在同一个公式中，既可以是约束出现，也可以

是自由出现，这种情况有时会造成一些混淆，带来不便.要改变这种情况，使一个个体变项

在同一个公式中，不同时既是约束出现，又是自由出现，采取换名规则或代入规则.在求前

束范式时，尤其需要.

例2.3给定解释I如下：

①D＝{2,3};②D中特定元素a=2；③函数为2)3(,3)2(ff；

④谓词F(x)为F(2)=0,F(3)=1，

G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1

L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0

求在解释I下各公式的真值.

(1)),()(axGxxF;(2)),(yxyLx；(3))))(,())(((xfxGxfFx.

解(1)),()(axGxxF))2,3()3(())2,2()2((GFGF

000)01()00(

(2)),(yxyLx),3(),2(yyLyyL

1)10()01()}3,3()2,3({))3,2()2,2({LLLL

(3))))3(,3())3((()))2(,2())2((()))(,())(((fGfFfGfFxfxGxfFx

0)00()01(

这是给定解释下，求谓词公式的真值，个体域有限，比较好求。只需将量词消去，函数

值代入谓词，根据谓词的真值，即可求出谓词公式的真值.

要判断一个谓词公式的真、假是较为难的.在谓词逻辑中，在任何解释下都真的公式，

才是永真式；在任何解释下公式A为假，才是永假式；公式A不总是假，或者至少有一个

解释使得公式A为真，才是可满足式.困难之点是在全总个体域中所有的解释如何说清楚.

因此只能要求会作简单问题.

例2.4讨论公式),(),(yxxFyyxyFx的类型.

解用A表示该公式.

对任意解释I，A的前件为假，无论后件真假，公式A为真.这说明A不是永假式；

取解释I如下：个体域为整数集，F(x,y)：xy，在I下，xyF(x,y)，即在整数中，任

给整数x，存在y使得xy，显然为真，即A的前件为真.但后件yxF(x,y)，即存在y对任

给x使得xy，显然这是不成立的，亦即后件为假.由蕴含联结词的真值表10的真值为0，

故A为假。这说明A不是永真式.

综上所述，A是可满足式.

由例2.4可知，量词的次序不能随便颠倒.

例2.5将公式

)),()(()),()((zyzDyCyyxBxAxF

化为前束范式.

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

)),()(()),()(((zyzDyyCyxBxAxF

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

)),()(()),()((

)),()(()),()((

zyzDyCyyxBxAx

zyzDyCyyxBxAxF





③换名.

)),()(()),()((zyzDtCtyxBxAxF

(自由变元的y未改)

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

4

)),()()),()(((zyDtCyxBxAztxF(前束范式)

))),()(()),()(((zyDtCyxBxAztx(前束范式)

为所求前束范式.

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

)),()(()),()(((zyzDyyCyxBxAxF

)),()(()),()((

)),()(()),()((

zyzDyCyyxBxAx

zyzDyCyyxBxAx





)),()(()),()((zyzDtCtyxBxAx(自由变元的y未改)

)),()()),()(((zyDtCyxBxAztx

))),()(()),()(((zyDtCyxBxAztx

注：重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换

名规则，把一个谓词公式化为量词在最前面，后面不含量词的公式，即前束范式.虽然前束

范式是谓词公式的一种标准形式，但是一般一个谓词公式的前束范式并不是唯一的.

例2.6构造推理证明

前提：xF(x),x(F(x)G(x)H(x))结论：x(F(x)H(x))

证明：①xF(x)[前提引入]

②F(c)[T①ES]

③x(F(x)G(x)H(x))[前提引入]

④F(c)G(c)H(c)[T③US]

⑤G(c)H(c)[T②,④假言推理]

⑥H(c)G(c)[T⑤置换]

⑦H(c)[T⑥化简]

⑧F(c)H(c)[T②,⑦合取]

⑨x(F(x)H(x))[EG]

例2.7单项选择题

1.谓词公式)())()((xQyyRxPx中量词x的辖域是()

(A)))()((yyRxPx(B)P(x)(C))()(yyRxP(D))(xQ

答案：(C)

解答：x后面的公式是))(()(yyRxP.故应选择(C).

2.谓词公式xA(x)xA(x)的类型是（）

(A)永真式(B)矛盾式

(C)非永真式的可满足式(D)不属于(A),(B),(C)任何类型

答案：(B)

解答：对于任意解释I，xA(x)xA(x)0

所以xA(x)xA(x)是永假式.选择(B).

3设个体域为整数集，下列公式中其真值为1的是()

(A))0(yxyx(B))0(yxxy

(C))0(yxyx(D))0(yxyx

答案：(A)

解答：任意一个整数x，都能找到y＝－x，使x+y=0,故(A)式是永真式.

4设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y.那么命题“所有演员都佩服某

些老师”符号化为()

(A)),()(yxAxxL(B))),()(()((yxAyJyxLx

(C))),()()((yxAyJxLyx(D))),()()((yxAyJxLyx

5

答案：(B)

解答：将命题符号化为)),()(()((yxAyJyxLx，故应选择(B).

5在谓词演算中，P(a)是)(xxP的有效结论，根据是()

(A)US规则(B)UG规则(C)ES规则(D)EG规则

答案：(A)

解答：全称量词消去规则的定义为

)(

)(

cA

xxA





,即A(c)是)(xxA的有效结论.应选择(A).

例2.8填空题

1.公式))(),()),()((xSzyzRyxQxPx的自由变元是,约束

变元是.

答案：y,x;x,z

解答：x的辖域是),,()(yxQxP故x是约束出现，y是自由出现，z的辖域是

),(zyR，故z是约束出现，y是自由出现，而S(x)中的x是自由出现.总之y,x是自由变元，

x,z是约束变元.

2.谓词逻辑公式)()(xxQxxP的前束范式是.

答案：))()((xQxPx或))()((xQxPx

解答：求前束范式

)())(()()(xxQxxPxxQxxP)()(xxQxPx

))()((xQxPx))()((xQxPx

3.设个体域D＝{a,b},消去公式中的量词，则)()(xxQxxP

答案：))()(()()(bQaQbPaP

解答：由x和x真值的定义，

))()(()()()()(bQaQbPaPxxQxxP

4.换名规则施于变元，代入规则施于变元

答案：约束；自由.

解答：见换名规则和代入规则的定义.

三、练习题

1.将下列命题符号化：

(1)丘华和李兵都是学生；(2)存在偶素数；

2.指出谓词公式)()())()((xQxxPxQxPx中量词的辖域，并指出变元的每

次出现是约束出现，还是自由出现，以及公式的约束变元，自由变元.

3.设个体域D＝{岳飞，文天祥，秦荟}，谓词F(x)：x是民族英雄。求xF(x)的真值。

4.设P是二元谓词，给定解释I如下：D＝{a,b},P(a,a)=P(b,a)=1，P(b,a)=P(b,b)=0

求下列公式的真值：(1)

),(xxxP

；(2)

),(yxyPx

;(3)

),(yxyPx

5.讨论公式)()(xxFxxF的类型.

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

)()(xxBxxA))()((xBxAx

四、练习题答案

1.(1)设P(x)：:x是学生。.a：丘华，b：李兵

该命题符号化为：P(a)P(b)

(2)设N(x):x是自然数，F(x)：x是偶数，Q(x)：x是素数

该命题符号化为x(N(x)F(x)Q(x))

2.在公式)()())()((xQxxPxQxPx中,x有二次出现，第一次出现的辖域

是)()(xQxP)(xQ

中;第二次出现的辖域是)(xP.变元x在该公式中有六次出现，其

6

中第1，4次出现和第2，3，5次出现均是约束出现；第6次是自由出现.变元x在该公式

中5次约束出现，1次自由出现.因此变元x既是该公式的约束变元，也是自由变元.

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

4.(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

5.设I为任意一个解释，D为个体域.)(xxF为假，则xF(x)xF(x)为真.

xF(x)为真，即x,F(x)为真,显然x

0

D,F(x

0

)为真，即xF(x)为真则

xF(x)xF(x)为真.

故在任何解释I下xF(x)xF(x)为真.xF(x)xF(x)是永真式.

6.前提：)()(xxBxxA结论：))()((xBxAx

证明：①)))()(((xBxAx[否定结论引入]

②)))()(((xBxAx[T①E]

③))()((cBcA[T①②ES]

④A(c)B(c)[T③E]

⑤A(c)[T④化简]

⑥B(c)A(c)[T④.E]

⑦(7)B(c)[T⑥化简]

⑧)()(xxBxxA[P]

⑨x(A(x)B(x))[T⑧化简]

⑩A(c)B(c)[T⑨US]

11A(c)[T⑩,⑦I

10

]

12)()(cAcA[T11,⑤合取]

可见，推理成立。