第五章谓词逻辑文档

第五章谓词逻辑

?在命题逻辑中，命题被当作一个基本的，不可分割的单位，只研究由原子命题和联接词所组成的复合命题；因而无法研究命题的内部结构及命题之间内在的联系。

·词项逻辑虽然能处理命题内部主谓项之间的推理关系，但其推理形式都局限于一些特定的形式。面对很多明显有效且司空见惯的推理，词项逻辑也无能为力。

传统逻辑的不足

——谓词逻辑的必要性

例1：有人喜欢所有的展品；（1）

所以，所以展品都有人喜欢。（2）

由（1）显然可以推出（2），但传统逻辑对此推理无法

处理。

例2：所有犯罪或者是故意犯罪，或者是过失犯罪；（3）

有些犯罪不是故意犯罪；（4）

所以，有些犯罪是过失犯罪。（5）

由（3）、（4）推出（5），显然也是有效的。但此推

理既不是三段论，又不是命题推理，当然也不是关系推理，

说明传统逻辑对此推理也是心有余而力不足。

主要内容

?本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间推导关系，对命题逻辑中的推理规则进行扩充，从而可以使我们可以进行量化自然推理。

第一节命题的内部结构

一、个体词和谓词

在谓词演算中，可将原子命题分解为谓词与个体词两部分。

定义5-1 个体是指可以独立存在的客体，个体词是指表示个体的词项。

注个体通常在一个命题里表示思维对象。因此个体词代表命题中的主项。

个体词有个体变项和个体常项之分。个体变项表示某个不确定的个体，而个体常项表示某个确定的个体。

定义5-2 用来刻划个体的性质或个体之间关系的词称为谓词。刻划个体性质的词称为一元谓词；刻划n个个体之间关系的词称为n元谓词。

例3

（1）李明是学生；

（2）李明比陈华高；

（3）x坐在陈华和李明之间。

在这三个命题中，李明、陈华都是个体常项，x是个体变项；“…是学生”是一元谓词，“…比…高”是二元谓词，“…坐…与…之间”是三元谓词。通常，我们用大写字母F、G、H 等表示谓词，小写字母a、b、c等表示个体常项，小写字母x、y、z等表示个体变项。

上述命题可分别表示为F（a）, G（a,b），

H（x,b,a）。

一般地，一个由n个个体词和一个n元谓词所组成的命题可表示为F（a1,a2, … ,an）,其中F表示n元谓词, a1,a2, … ,an 分别表示n个个体。

注意：a1,a2, … ,an的排列次序是重要的。

二、个体函项和个体域

在上例3中，主词是个体常项或者变项。但在有些句子中，主词既不是常项也不是变项，而是个体函项。

例4 张三的父亲病了。

主词“张三的父亲”不是以个体的名字，而是由另一个体张三确定或者说生成的。换句话说，“…的父亲”是以个体为自变量的函数。我们把这种以个体域为定义域，以个体为值域的函数称为个体函数。由于这种个体函数在原子命题中也可以作为主项，因而我们也把个体函数称为个体函项。

一般情况下，我们用f（x）表示个体函项。

例5 令F（x）表示“x病了”，f（x）表示“x的父亲”，a表示“张三”，则张三病了可以表示为F（a），而张三的父亲病了可以表示为F（f（a））。

在命题函数中，个体变元的取值范围称为个体域。

例4 P（x,y）表示“2 x+y=1”，若x,y的个体域为正整数集，则总是假；

若x,y的个体域为有理数集，则y=1―2x，对任意的有理数k ，在x= k，y =1―2k 时，P（k，1―2k）为真。

三、量词和全总个体域

1.量词

使用前面介绍的概念，还不足以表达日常生活中的各种命题。

例如：对于命题“ 所有的正整数都是素数” 和

“ 有些正整数是素数”

仅用个体词和谓词是很难表达的。

量词在命题里表示数量的词。

（1）全称量词“ x”

如“所有人都是要死的。”可表示为x D（x），

x的个体域为全体人的集合。

（2）存在量词“x ”

如“有些有理数是整数。”

令Ｉ(x）：x是整数；

于是命题可表示为xＩ(x）

其中x的个体域为有理数集合。

（3）存在唯一量词“!x ”

如“方程x+1=0存在唯一的整数解。”

令P（x）：x是x+1=0的整数解。

则命题可表示为!x P（x），

其中x的个体域为整数集。

2．全总个体域

含有量词的命题的表达式的形式，与个体域有关。

因此，为了方便，我们引入全总个体域的概念。

定义5―3 宇宙间所有的个体聚集在一起所构成的集合称为全总个体域。

后面的讨论中，除特殊说明外，均使用全总个体域。而对个体变化的真正取值范围，用特性谓词加以限制。

一般地，对全称量词，此特性谓词作蕴含的前件；对存在量词，此特性谓词常作合取项。例5 (1) “所有的人都是要死的。”

(2) “有的人活百岁以上。”

当x的个体域E为全体人组成的集合时，符号化上述命题。

令D（x）：x是要死的。则（1）可表示为x D（x）。

令G（x）：x活百岁以上。则（2）可表示为x G（x）。

当取x的个体域为全总个体域时，必须引入一个特性谓词将人从全宇宙的一切事物中分离出来。

（1）对所有个体而言，如果它是人，则它是要死的。

( 2）存在着个体，它是人并且它活百岁以上。

于是令M（x）：x是人。

（1）x（M（x）D（x））

（2）x（M（x）∧G（x））

六个基本的谓词表达式

?x Fx 表示“任一对象都具有F这种性质”。

? x Fx 表示“存在对象具有F这种性质”。

?x?y Gxy 表示“任一对象x与任一对象y，都具有G这种关系”。

?x?y Gxy 表示“对于任一对象x, 存在对象y，x与y具有G这种关”。

?x?y Gxy 表示“存在对象x, 对任一对象y，x与y具有G这种关系”。

?x?y Gxy 表示“存在对象x和y，x与y具有G这种关系”。

几个重要概念

个体域：个体变项取值的范围，也称论域。

辖域：量词约束的范围。

约束个体变项：被量词约束的个体变项。

自由个体变项：不被量词约束的个体变项。

第二节自然语言的谓词表达式

一、直言命题的符号化

例6 将下列命题符号化(使用全总个体域)。

(1) 发光的不都是金子

解: 令P（x）：x发光；G（x）：x是金子。

则该命题可表示为：

?x(P(x) ∧?G(x))

或??x(P(x) →G(x))

（2）所有运动员都钦佩某些教练。

解：令P（x）：x是运动员；T（x）：x是教练；Q（x，y）：x钦佩y。

则该命题可表示为：?x(P(x) →?y(T(y) ∧Q(x, y)))

（3）凡是实数均能比较大小。

解令R（x）：x是实数；G（x,y)：x与y可比较大小.

则该命题可表示为

例7 将下列命题符号化

（1）会叫的狗未必咬人。

解令D（x）：x是狗；P（x）：x会叫；Q（x）：x咬人。则可表示为（课件上了）y))

G(x,

R(y)

y((R(x)

x→

∧

?

?

（2）没有不散的筵席。

解B(x)：x是筵席；D(x):x是要散的;

则句（2）可表示为：(课件上）

（3）蛇是冷血的爬行动物。

解：Sx: x是蛇；Cx: x是冷血动物；Rx:x爬行动物。。

可表示为(课件上)

总结：直言命题的谓词表达式

全称肯定：所有S都是P

?x (Sx →Px)

全称否定：所有S都不是P

?x (Sx →?Px)

特称肯定：有的S是P

?x (Sx ∧Px)

特称否定：有的S不是P

?x (Sx ∧?Px)

例1 苏格拉底三段论可用谓词公式表示。

令M（x）：x是人；D（x）：x是要死的；

a：苏格拉底

则三段论可表示为

( x（M（x）D（x））∧M（a）) D（a）

例2 给出“x+y≥3”的谓词公式的表示形式。

解令P（x,y,z）：x+y≥z

则上述表达式可用谓词公式表示为P（x,y,3）。

二、约束变元和自由变元

个体变元有自由变元和约束变元之分.

例3 “x是整数”可以表示为Q（x），

它是一个命题函数，而不是命题。

例4“ x

例5“凡是有理数都可以表示成分数。”

令Q（x）：x是有理数；F（x）：x可以表示为分数

符号化表示为（课件上）

这是一个真值确定的命题。

例6 “某些人对某些药物过敏”

令H(x)：x是人;M(y):y是药;S(x，y)：x对y过敏。

符号化表示为（课件上）也是一个真值确定的命题。

在谓词公式中，形如。。。或。。。的那一部分称为公式的x约束部分。而A（x）称为量词

x或x的辖域。x在公式的x约束部分的任一出现都称为x的约束出现。

公式中约束出现的变元是约束变元

当x的出现不是约束出现时，称x的出现是自由出现。自由出现的变元是自由变元。例7 指出下列各公式中的量词辖域及自由变元和约束变元。

（课件上）。。。

解。。。是的辖域。

是的辖域.

R(z）是z的辖域。

x,y,z在公式中的所有出现均是约束出现，故它们均是约束变元。

（课件上）

解P（x，y）－> yQ（x，y，z）是x的辖域，在这一部分中，x是约束出现，故x是约束变元，在P（x，y）中的y是自由出现，故y为自由变元。但Q（x，y ，z）是y的辖域，因而在Q（x，y ，z）中y却是约束出现，故此时y是约束变元，z是自由变元。在S（x，z）中x，z是自由变元。

例8对公式。。。进行换名，使各变元只呈一种形式出现。

解需对x，y换名

。。。

2. 代入规则

对于公式中自由变元的更改叫做代入。

（1）对于谓词公式中的自由变元可以代入，代入时须对该自由变元的所有自由出现同时进行代入；

（2）代入时所选用的变元符号与原公式中所有变元的符号不相同。

例如对例8中公式。。。的x,y的自由出现分别用w,t代入得

。。。

8.3 谓词公式的等值和蕴含

一、公式的类型

一个谓词公式一般含有个体变元、命题变元和谓词，只有当公式中的自由变元用某个体域中确定的个体代入，命题变元用确定的命题代入后，原公式才变成为一个命题。

指派一组代入到谓词公式中，并使得谓词公式成为命题的确定的个体和命题称为公式的一组指派。

定义8-7 给定谓词公式A，其个体域为E，如果对于任一组指派，公式A的值总是为真，则称A在E上式永真的。如果对于公式A的任一组指派，公式A的值总是为假，则称A在E上是永假的。如果至少存在着一组指派，使公式A的值为真，则称A在E上是可满足的。

例1 试说明下列各公式的类型（个体域取为全总个体域）

（1）

（2）

（3）F(x) （其中F(x): x+6=5）

（4）

解(1) 永真公式

(2) 可满足公式

(3) 可满足公式

(4) 永假公式

例2 试说明下列各公式的类型。

（1） （2） （3）

（4）P （x ，y ）

其中x ，y 的个体域为R ；谓词P （x ，y ）：x=y ；

Q 是命题变元.

解 （1） 可满足公式。 （2） 永假公式。 （3） 永真公式。 （4） 可满足公式。 二、公式的等值与蕴含

定义8-8 设A 、B 是两个公式，它们有共同的个体域E ，若对于A 和B 的任意一组指派，两公式都具有相同的真值，则称公式A 和B 在E 上等值，记作A 。。。 B 。

定义8-9 对于公式A 和B ，若A B 1，则称公式A 蕴含公式B ，记作A B 。 谓词演算中的等值式和蕴涵式 1.命题公式的推广

在命题演算中，任一等值式或蕴涵式，其中同一命题变元，当用同一命题公式取代时，其结果仍是等值式或蕴涵式。

将此情况推广到谓词公式中，用谓词公式去取代命题演算中等值式或蕴涵式的命题变元时，便得到谓词演算的等值式或蕴涵式。 。。。

2. 全称量词和存在量词间转化的等值式

其中A （x ）是任意的公式 对个体域是有限时，给出其证明。

证明 设个体域 ,则

3.量词辖域扩展与收缩的等值式

)

()()()(x A x x xA x A x x xA ??????????

（2）①

②

③

④

4. 量词分配等值式与蕴涵式

（1）①

②

证明（1）①

“个体域中每一个体x，使得A(x)与B(x)均为真”与“个体域中每一个体x，使得A(x)为真且每一个体x使得B(x)为真”具有相同的含义.

（2）①

②

证明（2）②

由（2）①得

5.量词与联结词的关系

证明

证明设为假，

则为真，为假。

因此在个体域中必存在某个体a使B(a)为假，但A(a)为真。

于是为假，因此为假。由此永真。

故

8.4 谓词演算的推理理论

在谓词演算中，推理的形式结构仍为

。。。

若是永真式，

则称由前提逻辑的推出结论C，

在此, C均为谓词公式。

一、推理规则

命题演算中的推理规则，可在谓词推理理论中应用。

与量词有关的推理规则

1. US(全称消去规则)

。。。

使用此规则时要注意：

（1）x是A(x)中的自由变元；

（2）y为任意不在A(x)中约束出现的个体变元；

（3）c为任意的个体常元。

关于（2）的反例：

设则, x,y的个体域为R，是一真命题.

若应用US得，则是错误的。

正确的做法是换成

2. ES（存在消去规则）

。。。

使用此规则时应注意：

（1）c 是使A为真的特定个体常元；（2）如果A(x)中有其他自由变元出现，且x是随其他自由变元变化的，那么不能使用此规则。

3. UG（全称添加规则）

。。。

使用此规则时注意:

(1) y在A(y)中自由出现，且y取任何值时A均为真。

(2) x不在A(y)中约束出现

4、EG（存在添加规则）

。。。

使用此规则时注意:

(1) C是个体域中某个确定的个体。

(2) 代替C的x不能已在A(c)中出现。

二、推理规则的应用

例1 证明苏格拉底的三段论。

解令M(x):x是人; D(x):x是要死的; c:苏格拉底。

于是苏格拉底三段论可表示为：。。。

证明（1）M(c) 前提

（2）前提

（3）（1）；US

（4）D(c) (1),(3);

例2 证明

。。。

证明（1）前提（2）前提

（3）C(a) ∧Q(a) （2）；ES

（4）（1）；US

（5）C(a) （3）；I1

（6）W(a) ∧R(a) （4）,（5）；I11

（7）Q(a) （3）；I2

（8）R(a) （6）；I2

（9）Q(a) ∧R(a) （7）,（8）；I9

（10）（9）；EG

例3 证明。。

证明（1）附加前提

（2）（1）；E

（3）（2）；ES

（4）前提

( 5 ) （4）；US （6）Q(c) （3）,（5）；I10

（7）（6）；EG

例4 证明。。。

例5 指出下面推理的错.

证明

（1）前提

（2）（1）；I1

（3）（1）；I2

（4）（2）；ES

（5）（3）；ES

（6）（4）（5）；I9

（7）（6）；EG

因此。。。

例6 指出下面推理的错误.

设D(x,y)表示“x可被y 整除” ,个体域为{ 5,7 ,10 ,11 }.

因为D(5，5)和D(10,5)为真，所以xD(x,5)为真.

因为D(7，5)和D(11,5)为假，所以xD(x,5)为假. 但有下面的推理过程：

(1) xD(x,5) 前提

(2) D(z,5) (1);ES

(3) xD(x,5) (2);UG

因此，xD(x,5) xD(x,5).

例7 对多个量词的使用情况，观察下列推理过程.

证明（1）前提

（2）（1）；US

（3）（2）；ES

（4）（3）；UG

（5）（4）；EG

推出错误结论：与可交换.

习题

1 将下列命题符号化.

（1）在上海高校学习的学生，未必都是上海籍的学生。

解令H(x)：x是在上海高校学习的学生

S(y)：y是上海籍的学生

或者

（2）没有一位女同志既是国家选手又是家庭妇女。

解令W(x):x是一位女同志；

C(x):x是国家选手；

H(x):x是家庭妇女

x(W(x)∧C(x)∧H(x))

（3）对于每一个实数x，存在一个更大的实数y。

解令R(x)：x是实数；G(x,y):x比y大。

x(R(x) y(R(y)∧G(y,x))

（4）某些汽车比所有的火车都慢，但至少有一列火车比每辆汽车快。

解令C(x)：x是汔车；H(x)：x是火车；

S(x,y): x比y慢。

。。。

2 对下列谓词公式中的约束变元进行改名.

。。。

解对x(P(x) (R(x)∨Q(x)))中的x换为y.

xR(x)中的x换名为t得

。。。

3.将下面谓词公式中的自由变元进行代换.

。。。

解对y(P(x,y)中的自由变元x和Q(x,z)中的自由变元x代换为t , 对x(R(x,y) 中的自由变元y代换为s得

。。。

4. 用构造推理过程的方法证明

。。。

5.符号化下述命题,并推证其结论。

“所有有理数是实数，某些有理数是整数，因此某些实数是整数。”

解先将命题符号化

令Q(x):x是有理数；R(x):x是实数;I(x);x是整数.

。。。

证明