谓词逻辑教学学习课件

第三章谓词逻辑第三章谓词逻辑§3.1 谓词逻辑的基本概念§3.2 谓词公式§3.3 谓词公式的等价关系和蕴含关系

§3.4 范式 §3.5 例 §3.6 谓词逻辑的应用§3.1谓词逻辑的基本概念§3.1.1谓词和量词例如，逻辑学中著名的三段论：

凡人必死

张三是人

张三必死

在命题逻辑中就无法表示这种推理过程。§3.1.1谓词和量词因为，如果用P代表“凡人必死”这个命题，Q代表“张三是人”这个命题，R代表“张三必死”这个命题，则按照三段论，R应该是P和Q的逻辑结果。但是，在命题逻辑中，R却不是P和Q的逻辑结果，因为公式

PQR

显然不是恒真的，解释{P，Q，R}就能弄假上面的公式。

§3.1.1谓词和量词定义3.1.1

可以独立存在的物体称为个体。（它可以是抽象的，也可以是具体的。）如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常在一个命题里表示思维对象。§3.1.1谓词和量词定义3.1.2设D是非空个体名称集合，定义在Dn上取值于{1，0}上的n元函数，称为n元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。§3.1.1谓词和量词下面我们举一个谓词的例子：

令G(x，y)：“x高于y”，于是，G(x，y)是一个二元谓词。将x代以个体“张三”，y代以个体“李四”，则G(张三，李四)就是命题：“张三高于李四”。随便将x，y代以确定的个体，由G(x，y)都能得到一个命题。但是，G(x，y)不是命题，而是一个命题函数即谓词。§3.1.1谓词和量词于是，用谓词的概念可将三段论做如下的符号化：令

H(x)表示“x是人”，

M(x)表示“x必死”。则三段论的三个命题表示如下：

P：H(x)M(x)

Q：H(张三)

R：M(张三)§3.1.1谓词和量词例如我们想得到“命题”P的否定“命题”，应该就是“命题”P。但是， P=(H(x)M(x))

=(H(x)M(x))

=H(x)M(x)亦即，“命题”P的否定“命题”是“所有人都不死”。这和人们日常对命题“所有人都必死”的否定的理解，相差得实在太远了。

§3.1.1谓词和量词其原因在于，命题P的确切意思应该是：“对任意x，如果x是人，则x必死”。但是

H(x)M(x)

中并没有确切的表示出“对任意x”这个意思，亦即H(x)M(x)不是一个命题。因此，在谓词逻辑中除引进谓词外，还需要引进“对任意x”这个语句，及其对偶的语句“存在一个x”。

§3.1.1谓词和量词定义3.1.3

语句“对任意x”称为全称量词，记以x；语句“存在一个x”称为存在量词，记以x。这时，命题P就可确切地符号化如下： x(H(x)M(x))

命题P的否定命题为： P=(x(H(x)M(x)))

=x(H(x)M(x))

亦即“有一个人是不死的”。这个命题确实是“所有人都要死”的否定。

§3.1.1谓词和量词三段论的三个命题，在谓词逻辑中是如下这样表示的：

P：x(H(x)M(x))

Q：H(张三)

R：M(张三)以后可以证明：在谓词逻辑中，R是P和Q的逻辑结果。

§3.1.1谓词和量词设G(x)是一元谓词，任取x0D，则G(x0)是一个命题。于是xG(x)是这样一个命题“对任意xD，都有G(x)”。故对命题xG(x)的真值做如下规定：xG(x)取1值对任意xD，G(x)都取1值；

xG(x)取0值有一个x0D，使G(x0)取0值。§3.1.1谓词和量词xG(x)是命题“存在一个x0D，使得G(x0)成立”。对命题xG(x)的真值规定如下：

xG(x)取1值有一个x0D，使G(x0)取1值；

xG(x)取0值对所有xD，G(x)都取0值。

§3.1.1谓词和量词当D={x0

，x1，…}是可数集合时，

xG(x)等价于G(x1)G(x2)…

xG(x)等价于G(x1)G(x2)…

§3.1.1谓词和量词对于一个谓词，如果其中每一个变量都在一个量词作用之下。则它就不再是命题函数，而是一个命题了。但是，这种命题和命题逻辑中的命题毕竟有所不同。因为终归这种命题里还有变量，当然这种变量和命题函数中的变量还有区别。使用量词时应注意以下几个问题：

1.量词的论域，即D中都有那些元素；

2.在多重量词时，应注意量词的顺序；

3.量词的作用域。

§3.1.2改名规则

定义3.1.4

在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串(实际是指下一节将严格定义的公式)中，变量的出现说是约束的，当且仅当它出现在使用这个变量的量词范围之内；变量的出现说是自由的，当且仅当这个出现不是约束的。例如，x(P(x，y)Q(x，z))R(x)。从左向右算起，变量x的第一，第二次出现是约束的，第三次出现是自由的；变量y，z的出现是自由的。

§3.1.2改名规则

定义3.1.5

变量说是约束的，如果至少一个它的出现是约束的；变量说是自由的，如果至少一个它的出现是自由的。由定义可以看出一个变量可以既是约束变量又是自由变量。例如，上例中的x既是约束变量，又是自由变量；y，z只是自由变量。

§3.1.2改名规则

显然，xG(x)与yG(y)的真值一样，xG(x)与yG(y)的真值一样，亦即，谓词逻辑中的命题的真值，与命题中的约束变量的记法无关。这就引出了谓词逻辑中的改名规则。

§3.1.2改名规则

在由谓词，量词，逻辑联结词，括号组成的有意义的符号串(实际是下节定义的公式)中，我们可将其中出现的约束变量改为另一个约束变量，这种改名必须在量词作用区域内各处以及该量词符号中实行，并且改成的新约束变量要有别于改名区域中的所有其它变量。显然改名规则不改变原符号串的真值。

例:对于x(P(x，y)Q(x，z))，可改名为u(P(u，y)Q(u，z))。但下面的改名都是不对的：

a.

u(P(u，y)Q(x，z))

b.

x(P(u，y)Q(u，z))

c.

u(P(x，y)Q(x，z))

d.

y(P(y，y)Q(y，z))

e.

z(P(z，y)Q(z，z))§3.2谓词公式

§3.2.1公式

在形式化中，我们将使用如下四种符号：1.

常量符号：用小写英文字母a，b，c，…表示，当个体名称集合D给出时，它可以是D中某个元素。2.

变量符号：用小写英文字母x，y，z，…表示，当个体名称集合D给出时，D中任意元素可代入变量符号。§3.2.1公式

3.

函数符号：用小写英文字母f，g，…表示，当个体名称集合D给出时，n元函数符号f(x1，…，xn)可以是Dn到D的任意一个映射。4.

谓词符号：用大写英文字母P，Q，R，…表示，当个体名称集合D给出时，n元谓词符号P(x1，…，xn)可以是Dn上的任意一个谓词。

定义3.2.1项谓词逻辑中的项，被递归定义为：1)

常量符号是项；2)

变量符号是项；3)

若f(x1,…,xn)是n元函数符号，t1,…,tn

是项，则f(t1,…,tn)是项；4)

所有项都是有限次使用1)，2)，3)生成

的符号串。

定义3.2.2若P(x1,…,xn)是n元谓词符号，t1,…,tn是项，则P(t1,…,tn)是原子。

定义3.2.3公式

谓词逻辑中的公式，被递归定义如下：1)

原子是公式；2)

若G，H是公式，则(G)，(GH)，(GH)，

(GH)，(GH)是公式；3)

若G是公式，x是G中的自由变量，则xG，

xG是公式；4)

所有公式都是有限次使用1)～3)生成的符号

串。

§3.2.2解释

定义3.2.4

谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成：1.

对每个常量符号，指定D中一个元素；2.

对每个n元函数符号，指定一个函数，即指

定Dn到D的一个映射；3.

对每个n元谓词符号，指定一个谓词，即指

定Dn到{0，1}的一个映射。

§3.2.2解释

今后我们对讨论的公式做如下规定：公式中无自由变量，或将自由变量看做常量。

例:给出如下两个公式：

1)G=x(P(f(x))Q(x，f(a)))

2)H=x(P(x)Q(x，a))给出如下的解释I：

D={2，3}

a

2

f(2)f(3)

32

P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)

011101例:TI(G) =TI((P(f(2))Q(2，f(2))) (P(f(3))Q(3，f(2))))

=TI((P(3)Q(2，3))(P(2)Q(3，3)))

=(11)(00)

=1TI(H) =TI(P(2)Q(2，2)P(3)Q(3，2))

=0110

=0定义3.2.5

公式G称为可满足的，如果存在解释I，使G在I下取1值，简称I满足G。若I不满足G，则简称I弄假G。

定义3.2.6

公式G称为是恒假的(或不可满足的)，如果不存在解释I满足G；公式G称为恒真的，如果G的所有解释I都满足G。

§3.3谓词公式的等价关系和蕴含关系

§3.3.1公式的等价和蕴涵

定义3.3.1

公式G，H称为等价，记以G=H，如果公式GH是恒真的。由定义显然可以看出：公式G，H等价的充要条件是：对G，H的任意解释I，G，H在I下的真值相同。因为对任意公式G，H，在解释I下，G，H就是两个命题，所以命题逻辑中给出的基本等价式，在谓词逻辑中仍然成立。

§3.3.1公式的等价和蕴涵

定义3.3.2

设G，H是公式，称G蕴涵H，或H是G的逻辑结果，如果公式GH是恒真的，并记以GH。显然，对任意两个公式G，H，G蕴涵H的充要条件是：对任意解释I，若I满足G，则I必满足H。同样，命题逻辑中的基本蕴涵式仍成立。

§3.3.1公式的等价和蕴涵

令G1=x(H(x)M(x))，G2=H(a)，H=M(a)

证明：H是G1G2的逻辑结果。因为，设I是G1，G2，H的一个解释(I指定a为张三)，且I满足G1G2，即I满足

x(H(x)M(x))H(a)

所以，I满足M(a)。否则，令M(a)在I下为假，而H(a)在I下为真，于是H(a)M(a)在I下为假，故x(H(x)M(x))在I下为假，矛盾!

故M(a)在I下为真命题，而I指定a为“张三”，故M(张三)为真命题。§3.3.1公式的等价和蕴涵

由于谓词逻辑中的恒真(恒假)公式，要求所有解释I都满足(弄假)该公式。而解释I依赖于一个非空集合D。由于集合D可以是无穷集合，而集合D的“数目”也可能是无穷多个，因此，所谓公式的“所有”解释，实际上是无法考虑的。这就使得谓词逻辑中公式的恒真，恒假性的判断变得异常困难。1936年Church和Turing分别独立地证明了：对于谓词逻辑，判定问题是不可解的。

设G(x)是一元谓词符号，若公式xG(x)是恒真公式，则这件事实可被叙述为如下的一个真命题：对任意一元谓词G(x)，命题xG(x)都是真的。但是，如果想把这个命题加以否定，则在谓词逻辑中是办不到的。因为：1)这个命题的否定，应该是如下命题：有一个一元谓词G(x)，使得命题xG(x)是假的。2)公式xG(x)的否定是公式(xG(x))。而后一个公式表示的命题是：公式xG(x)是恒假的，亦即，对任意一元谓词G(x)，命题xG(x)都是假的。

1)和2)所表示出的事实相差得太远了。发生这件事的原因是：用“公式xG(x)是恒真的”来表达命题“对任意一元谓词G(x)，命题xG(x)都是真的”是不确切的。确切地，后一个命题，应该用“公式G(xG(x))是恒真的”来表达。

这个公式中，不仅有关于个体变量x的量词，而且有关于谓词变量(即谓词符号，亦即原子)的量词。由这样的公式组成的系统就称为高阶逻辑。高阶逻辑中，不仅判定问题不可解，甚至连一个完备的公理系统都没有。§3.3.2谓词演算的推理理论

前提引入规则：在证明的任何步骤上都可以引用前提。结论引入规则：在证明的任何步骤上所得到的结论都可以在其后的证明中引用。置换规则：在证明的任何步骤上，公式的子公式都可以用与之等价的其他公式置换。代入规则：在证明的任何步骤上，恒真公式中的任一原子都可以用一公式代入，得到的仍是恒真的公式。

全称特定化规则(US)：xA(x)A(y)

这里的A(y)是将A(x)中的x处代以y。要求y在A(x)中不约束出现。这里自由变量y也可以写成个体常量c，这时c为个体域中任意一个确定的个体。

这个规则的意思是说，如果个体域的所有元素都具有性质A，则个体域中的任一个元素具有性质A。

存在特定化规则(ES)：xA(x)A(c)

存在特定化规则(ES)：xA(x)A(c)

这里c是个体域中的某个确定的个体。这个规则是说，如果个体域中存在有性质A的元素，则个体域中必有某一元素c具有性质A。

但是，如果xA(x)中有其它自由变量出现，且x是随其它自由变量的值而变，那么就不存在唯一的c使得A(c)对自由变量的任意值都是成立的。这时，就不能应用存在特定化规则。

例如，x(x=y)中，x、y的论域是实数集合。若使用ES规则，则得c=y，即在实数集中有一实数c，等于任意实数y。结论显然不成立，这是因为A(x)：x=y中的x依赖于自由变量y，此时不能使用ES规则。另外，要注意的是，如果xP(x)和xQ(x)都真，则对于某个c和某个d，可以断定

P(c)Q(d)必真，但不能断定P(c)Q(c)为真。

全称一般化规则(UG)：A(x)yA(y)

这个规则是说，如果个体域中任意一个个体都具有性质A，则个体域中的全体个体都具有性质A。这里要求x必须为自由变量，并且y不出现在A(x)中。存在一般化规则(EG)：A(c)yA(y)

这个规则是说，如果个体域中某一元素c具有性质A，则个体域中存在着具有性质A的元素。这里要求y不在A(c)中出现。

证明： （1）x(P(x)Q(x))

前提 （2）P(c)Q(c) (1)；US （3）P(c)

前提 （4）Q(c) (2),(3)

例3.3.1

证明:x(P(x)Q(x))P(c)Q(c)证明：用反证法，假设xQ(x)成立。 xP(x)

前提 P(y) (1)；US xQ(x)

假设 xQ(x) (3) Q(y) (4)；US P(y)Q(y) (2)，(5)

例3.3.2证明：

x(P(x)Q(x)),xP(x)xQ(x) (P(y)Q(y)) (6) x(P(x)Q(x))

前提

P(y)Q(y) (8),US (P(y)Q(y))(P(y)Q(y)) (7),(9)

因为(P(y)Q(y))(P(y)Q(y))是恒假公式，所以x(P(x)Q(x))，xP(x)xQ(x)。

（1）x(F(x)G(x))

前提（2）F(c)G(c) （1），ES（3）F(c) （2）（4）y(H(y)I(y))

前提（5）H(c)I(c) （4）（6）H(c) （5）（7）F(c)H(c)

（3）,（6）（8）x(F(x)H(x))

（7），EG。

例3.3.3指出下面推理中的错误。

§3.4范式定义3.4.1

谓词逻辑中公式G称为前束范式，如果G有如下形状：

Q1x1…QnxnM

其中

Qixi或者是xi，或者是xi，i=1，…，n，M是不含量词的公式，Q1x1…Qnxn称为首标，M称为母式。例如， xyz(P(x，y)Q(x，z))

xyzP(x，y，z)§3.4.1前束范式

设G是公式，其中自由变量有且仅有一个x，记以G(x)，H是不含变量x的公式，于是有：1)

x(G(x)H)=xG(x)H1’)

x(G(x)H)=xG(x)H2)

x(G(x)H)=xG(x)H2’)

x(G(x)H)=xG(x)H3)

(xG(x))=x(G(x))4)

(xG(x))=x(G(x))引理1

1)

设I是G(x)和H的一个解释。若x(G(x)H)在I下取1值，则在I下，对任意xD，G(x)H都是真命题。若H是真命题，则xG(x)H是真命题；若H是假命题，则必然是对每个xD，G(x)都是真命题，故xG(x)取1值。所以xG(x)H在I下取1值。若x(G(x)H)在I下取0值，则必有一个x0D，使G(x0)H在I下取0值。故G(x0)为假命题，并且H为假命题。所以xG(x)取0值。从而xG(x)H在I下取0值。

证明：

（1）‘的证明设I是G(x)和H的一个解释。若

x(G(x)H)在I下取1值，则在I下，存在x0

D，G(x0)H是真命题。若H是真命题，则

xG(x)H是真命题；若H是假命题，则必然有G(x0)

是真命题，故

xG(x)取1值。所以

xG(x)H在I下取1值。若

x(G(x)H)在I下取0值，则在I下对任意的xD，使G(x)H在I下取0值。故G(x)和H都为假命题，所以

xG(x)H在I下取0值。（3）的证明若I满足(xG(x))，则I弄假xG(x)。则必有某一个x0

D，G(x0)是假命题，于是G(x0)是真命题，即x(G(x))在I下是真命题，故I满足x(G(x))若I弄假(xG(x))，则I满足xG(x)。即对任意的xD，有G(x)是真命题。也就是对任意的xD，G(x)是假命题，于是x(G(x))是假命题，故I弄假x(G(x))。若I满足(xG(x))，则I弄假xG(x)。故对任意xD，G(x)都是假命题，从而G(x)都是真命题，故I满足x(G(x))若I弄假(xG(x))，则I满足xG(x)。故有x0D，使得G(x0)是真命题。从而G(x0)是假命题，故I弄假x(G(x))。证明：

设G，H是两个公式，其中自由变量有且只有一个x，分别记以G(x)，H(x)，于是有：1)

xG(x)xH(x)=x(G(x)H(x))2)

xG(x)xH(x)=x(G(x)H(x))3) xG(x)xH(x)=xy(G(x)H(y))4) xG(x)xH(x)=xy(G(x)H(y))引理2设I是G(x)和H(x)的一个解释。若xG(x)xH(x)在I下取1值，则在解释I下，对任意xD，G(x)、H(x)都是真命题，所以G(x)H(x)是真命题，即对任意xD，G(x)H(x)是真命题，所以x(G(x)H(x))在I下取1值。若xG(x)xH(x)在I下取0值，则xG(x)为假，或xH(x)为假，若xG(x)为假，必有一个x0D，使G(x0)在I下取0值，所以G(x0)H(x0)为假命题，所以x(G(x)H(x))在I下取0值。若xH(x)为假，同理可证。1)证明：xG(x)xH(x)

=xG(x)yH(y)

改名规则=x(G(x)yH(y))

引理1

=xy(G(x)H(y))

引理13)证明：

对任意公式G，都存在与其等价的前束范式。

证明：通过如下算法，可将公式G化成等价的前束范式。1.使用基本等价

(KH)=(KH)(HK)

(KH)=KH

可将公式G中的和删除。定理3.4.12.使用(H)=H，摩根律，引理1，可将公式中所有否定号放在原子之前。3.如果必要的话，则将约束变量改名。4.使用引理1，2将所有量词都提到公式的最左边。于是，将公式G在等价意义下化成了一个前束范式。

xy(z(P(x,z)P(y,z))uQ(x,y,u))=xy((z(P(x,z)P(y,z)))uQ(x,y,u))=xy(z(P(x,z)P(y,z))uQ(x,y,u))=xyz(P(x,z)P(y,z)uQ(x,y,u))=xyzu(P(x,z)P(y,z)Q(x,y,u))例3.4.1定义3.4.2

设G是一个公式，Q1x1…QnxnM是与G等价的前束范式，其中M为合取范式形式。若Qr是存在量词，并且它左边没有全称量词，则取异于出现在M中所有常量符号的常量符号c，并用c代替M中所有的xr，然后在首标中删除Qrxr。§3.4.2Skolem范式

若Qs1,…,Qsm是所有出现在Qrxr左边的全称量词(m1，1s1<s2<…<sm<r)，则取异于出现在M中所有函数符号的m元函数符号f(xs1,…,xsm)，用f(xs1,…,xsm)代替出现在M中的所有xr，然后在首标中删除Qrxr。对首标中的所有存在量词做上述处理后，得到一个在首标中没有存在量词的前束范式，这个前束范式就称为公式G的Skolem范式。其中用来代替xr的那些常量符号和函数符号称为公式G的Skolem函数。

§3.4.2Skolem范式

G=xyzuvwP(x,y,z,u,v,w)\用a代替x，

用f(y，z)代替u，

用g(y，z，v)代替w，

得公式G的Skolem范式：

yzvP(a,y,z,f(y,z),v,g(y,z,v))例3.4.2证明：设G是前束范式：

G=Q1x1…QnxnM(x1,…,xn)设Qr是从左往右看第一个存在量词。令G1=x1…xr-1Qr+1

xr+1…QnxnM(x1,…,xr-1,f(x1,…,xr-1),xr+1，,…,xn)

其中f(x1,…,xr-1)是代替xr的Skolem函数。下面证明:1)满足G1的解释满足G；

2)满足G的解释，适当扩充后可

满足G1。1.G与S的可满足性是等价的。

设个体域为D，取一个满足G1的解释I，于是，对每一组(x1’,…,xr-1’)Dr-1，都有f(x1’,…,xr-1’)D，使得

Qr+1

xr+1…QnxnM