CH02谓词逻辑.ppt

《CH02谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《CH02谓词逻辑.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2 2章章 谓词逻辑谓词逻辑 在命题逻辑中，我们把命题分解到在命题逻辑中，我们把命题分解到原子命题为止，认为原子命题是不能再原子命题为止，认为原子命题是不能再分解的，仅仅研究以原子命题为基本单分解的，仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。位的复合命题之间的逻辑关系和推理。实际上，简单命题还可以进行分解，实际上，简单命题还可以进行分解，例如，例如，“王平是大学生王平是大学生”这一简单命题这一简单命题可以分解为主语可以分解为主语(王平王平)和谓语和谓语(是大学是大学生生)，命题逻辑反映不出这一特点。，命题逻辑反映不出这一特点。其次，如下两个简单命题其次，如下两个简单命题“

2、王平是王平是大学生大学生”和和“李明是大学生李明是大学生”，有一个，有一个共同特点共同特点是大学生，这一共性在命是大学生，这一共性在命题逻辑中也表示不出来。因此，有必要题逻辑中也表示不出来。因此，有必要推广命题逻辑。推广命题逻辑。第第2 2章章谓谓词词逻逻辑辑 第三，有些简单而正确的推理过程第三，有些简单而正确的推理过程在命题演算里不能得到证明。例如著名在命题演算里不能得到证明。例如著名的苏格拉底三段论：的苏格拉底三段论：“人都是要死的，苏格拉底是人，人都是要死的，苏格拉底是人，所以苏格拉底是要死的。所以苏格拉底是要死的。”在命题逻辑中，三个原子命题分别在命题逻辑中，三个原子命题分别用用P P

3、，Q Q，R R表示，现在要证明表示，现在要证明P P Q QR R，即证明即证明P P Q QR R是重言式，但这在命题是重言式，但这在命题逻辑中是不可能的。因此从推理的角度逻辑中是不可能的。因此从推理的角度看，也有必要推广命题逻辑。看，也有必要推广命题逻辑。谓词逻辑就是命题逻辑的自然推广。谓词逻辑就是命题逻辑的自然推广。本章介绍的谓词逻辑内容仅限于一阶谓本章介绍的谓词逻辑内容仅限于一阶谓词逻辑或狭义谓词逻辑，即谓词中的变词逻辑或狭义谓词逻辑，即谓词中的变元不再是谓词变元。元不再是谓词变元。第第2 2章章谓谓词词逻逻辑辑本章内容提要：本章内容提要：1.1.个体、谓词和量词的概念个体、谓词和量

4、词的概念 2.2.谓词演算公式谓词演算公式 3.3.谓词演算的等值公式谓词演算的等值公式 4.4.前束范式前束范式 5.5.推理理论推理理论 6.6.谓词逻辑在计算机科学中的应用谓词逻辑在计算机科学中的应用第第2 2章章谓谓词词逻逻辑辑 定定义义2.12.1 可可以以独独立立存存在在的的物物体体称称为为个个体体，它它可可以以是是一一个个具具体体的的事事物物，也也可可以以是一个抽象的概念。是一个抽象的概念。如王平，李明，计算机，离散数学，如王平，李明，计算机，离散数学，精神等都可以作为个体。精神等都可以作为个体。定义定义2.22.2 将表示具体的或确定的个体称将表示具体的或确定的个体称为为个体常

5、元个体常元，而将表示抽象的或泛指的，而将表示抽象的或泛指的（或者说取值不确定的）个体称为（或者说取值不确定的）个体称为个体个体变元变元。个体常元一般用小写英文字母个体常元一般用小写英文字母a,b,ca,b,c或带下标的或带下标的a ai i,b,bi i,c,ci i表示，个表示，个体变元一般用小写英文字母体变元一般用小写英文字母x,y,zx,y,z或或带下标的带下标的x xi i,y,yi i,z,zi i表示。表示。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.1 个体个体 定定义义2.32.3 个个体体变变元元的的取取值值范范围围称称为为个个体体域域或或论论域域，把把宇宇宙宙间

6、间一一切切事事物物组组成成的的个体域称为个体域称为全总个体域全总个体域。个体域可以是有穷集合，例如个体域可以是有穷集合，例如1,2,3,4,51,2,3,4,5，a,b,ca,b,c 等，也可以是无等，也可以是无穷集合，例如自然数集，实数集等。同穷集合，例如自然数集，实数集等。同时约定，本书在论述或推理中如无指明时约定，本书在论述或推理中如无指明所采用的个体域，则都是使用全总个体所采用的个体域，则都是使用全总个体域。域。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.1 个体个体 定义定义2.42.4 表示单个表示单个个体的性质或两个个体的性质或两个以上个体关系的词叫以上个体关系的词叫

7、谓词谓词。定义定义2.52.5 表示具体性质或关系的谓词表示具体性质或关系的谓词称为称为谓词常元谓词常元，表示抽象的或泛指的性，表示抽象的或泛指的性质或关系的谓词称为质或关系的谓词称为谓词变元谓词变元。无论是谓词常元或变元都用大写英无论是谓词常元或变元都用大写英文字母文字母P,Q,RP,Q,R或带下标的或带下标的P Pi i,Q,Qi i,R,Ri i表表示，要根据上下文区分。示，要根据上下文区分。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.2 谓词谓词 定义定义2.62.6 由一个谓词由一个谓词(如如P)P)和和n n个个体个个体变元变元(如如x x1 1，x x2 2，x xn

8、 n)组成的组成的P(xP(x1 1，x x2 2，x xn n)，称它为称它为n n元原子谓词元原子谓词或或n n元元命题函数命题函数，简称，简称n n元谓词元谓词。当当n=1n=1时，称一元谓词；当时，称一元谓词；当n=2n=2时，时，称为二元谓词，称为二元谓词，。特别地，当。特别地，当n=0n=0，称为零元谓词，即不带个体变元的谓词称为零元谓词，即不带个体变元的谓词为零元谓词。零元谓词是命题，这样命为零元谓词。零元谓词是命题，这样命题与谓词就得到了统一，因而可将命题题与谓词就得到了统一，因而可将命题看成特殊的谓词。看成特殊的谓词。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.2

9、 谓词谓词 例例2.12.1 分析下列命题的个体与谓分析下列命题的个体与谓词。词。（1 1）5 5是质数。是质数。解解 “5 5”是个体常元，是个体常元，“是质数是质数”是谓词，记为是谓词，记为P P。这里的谓词是。这里的谓词是一元谓词，属于谓词常元。一元谓词，属于谓词常元。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.2 谓词谓词（2 2）张三与李四是同学。）张三与李四是同学。解解 “张三张三”与与“李四李四”是个体常是个体常元，分别记为元，分别记为a a，b b，“与与是同是同学学”是谓词，记为是谓词，记为Q Q。这里的谓词。这里的谓词是二元谓词，属于谓词常元。是二元谓词，属于谓

10、词常元。（3 3）x x与与y y具有关系具有关系R R。解解 “x x”与与“y y”是个体变元，谓是个体变元，谓词为词为R R。这里的谓词是二元谓词，。这里的谓词是二元谓词，属于谓词变元。属于谓词变元。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.2 谓词谓词 例例2.22.2 用个体，谓词表示下列命题。用个体，谓词表示下列命题。（1 1）张华是大学生。）张华是大学生。解解 令令a a：张华；：张华；S(xS(x)：x x是大学生。整是大学生。整个命题可表示为：个命题可表示为：S(aS(a)。说明说明：若若x x的个体域为某大学计算机系的个体域为某大学计算机系的全体学生，则的全体

11、学生，则S(aS(a)为真；为真；若若x x的的个个体体域域为为某某中中学学的的全全体体学学生，则生，则S(aS(a)为假；为假；若若x x的的个个体体域域为为某某电电影影院院中中的的观观众众，则则S(aS(a)真真值值不不确确定定。所所以以个个体体变变元元在在哪哪些些个个体体域域取取特特定定的的值值，对对命命题题的的真真值极有影响。值极有影响。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.2 谓词谓词 （2 2）武汉位于重庆和上海之间。）武汉位于重庆和上海之间。解解 令令a a：武汉；：武汉；b b：重庆；：重庆；c c：上：上海；海；P(x,y,zP(x,y,z)：x x位于位于

12、y y和和z z之间。之间。整个命题可表示为整个命题可表示为P(a,b,cP(a,b,c)。说明说明：显然：显然P(a,b,cP(a,b,c)为真，但为真，但P(b,a,cP(b,a,c)为假。所以个体变元的顺为假。所以个体变元的顺序影响命题真值，不能随意改动。序影响命题真值，不能随意改动。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.2 谓词谓词 定义定义2.72.7 表示个体常元或变元之间数表示个体常元或变元之间数量关系的词叫量词；表示量关系的词叫量词；表示“全部全部”，“所有的所有的”，“一切的一切的”，“每一个每一个”，“任意的任意的”等数量关系的词叫等数量关系的词叫全称量词

13、全称量词，用符号用符号“”表示；表示表示；表示“存在一些存在一些”，“有一些有一些”，“至少有一个至少有一个”等数量等数量关系的词叫关系的词叫存在量词存在量词，用符号，用符号“”表示；表示表示；表示“存在惟一存在惟一”，“恰有一个恰有一个”等数量关系的词叫等数量关系的词叫存在惟一量词存在惟一量词，用，用符号符号“！”表示。表示。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.3 量词量词 注意注意：量词的优先级高于任量词的优先级高于任何联结词，所以何联结词，所以(x)P(xx)P(x1 1,x,x2 2,x,xn n)、(x)P(xx)P(x1 1,x,x2 2,x xn n)、可分别

14、写可分别写成成 xP(xxP(x1 1,x,x2 2,x,xn n)、xP(xxP(x1 1,x,x2 2,x xn n)，但要注意明确但要注意明确量词的辖域（辖域将在下一节讨量词的辖域（辖域将在下一节讨论）。论）。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.3 量词量词 例例2.32.3 符符号号化化下下列列命命题题（设设个个体体域域为为整整数集合）。数集合）。（1 1）所有的整数都是有理数。）所有的整数都是有理数。（2 2）有些整数是奇数。）有些整数是奇数。（3 3）存在着惟一的偶素数。）存在着惟一的偶素数。解解 （1 1）令）令P(xP(x)：x x是有理数，则命题可是有理数

15、，则命题可表示为：表示为：xP(xxP(x)。（2 2）令）令Q(xQ(x)：x x是奇数，则命题可表示为：是奇数，则命题可表示为：xQ(xxQ(x)。（3 3）令）令R(xR(x)：x x是偶数，是偶数，S(xS(x)：x x是素数，是素数，则命题可表示为则命题可表示为！x(R(x)x(R(x)S(xS(x)。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.3 量词量词 定定义义2.82.8 若若一一个个谓谓词词P(xP(x)是是用用来来限限制制个个体体变变元元的的取取值值范范围围，那那么么称称谓词谓词P(xP(x)为为特性谓词特性谓词。在使用全总个体域时，对个在使用全总个体域时，对

16、个体变化的真正取值范围，用特性谓体变化的真正取值范围，用特性谓词加以限制。词加以限制。一般地，对全称量词，一般地，对全称量词，将特性谓词作蕴含的前件；对存在将特性谓词作蕴含的前件；对存在量词，将特性谓词作合取项量词，将特性谓词作合取项。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.3 量词量词 例例2.42.4 用全总个体域对例用全总个体域对例2.32.3中中的所有命题进行符号化。的所有命题进行符号化。解解 在例在例2.32.3的基础上增加一个特的基础上增加一个特性谓词性谓词I(xI(x)：x x是整数。则各命题是整数。则各命题可表示为：可表示为：（1 1）x(I(x)x(I(x)P

17、(xP(x)（2 2）x(I(x)x(I(x)Q(xQ(x)（3 3）！x(I(x)x(I(x)R(x)R(x)S(xS(x)2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.3 量词量词 练习练习 将下列命题符号化。将下列命题符号化。(1)(1)天下乌鸦一般黑。天下乌鸦一般黑。(2)(2)任何金属都可以溶解在某种液任何金属都可以溶解在某种液体中。体中。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.3 量词量词 在谓词前加上量词，称为谓词在谓词前加上量词，称为谓词的量化。若一个谓词中所有个体变的量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命元都量化了，则该谓词就变成

18、了命题。这是因为在谓词被量化后，可题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值以在整个个体域中考虑命题的真值了。这如同数学中的函数了。这如同数学中的函数f(xf(x)，的值是不确定的，但的值是不确定的，但 可确定其值。可确定其值。2.1 2.1 个个体体 、谓谓词词和和量量词词2.1.3 量词量词 定定义义2.92.9 由由n n元元谓谓词词P P和和n n个个个个体体变变元元x x1 1，x x2 2，x xn n所所构构成成的的不不含含命命题题联联结结词词和和量量词词的的谓谓词词表表达达式式P P(x(x1 1，x x2 2，x xn n)称称为为谓谓词词逻逻辑辑中中的的原

19、子谓词公式原子谓词公式，简称，简称原子公式原子公式。由定义可知，一个命题或一由定义可知，一个命题或一个命题变元也称为原子公式，也就个命题变元也称为原子公式，也就是说，当是说，当n=0n=0时，时，P(xP(x1 1，x x2 2，x xn n)为原子命题为原子命题P P。2.2.2 2 谓谓词词公公式式2.2.1 2.2.1 谓词公式与翻译谓词公式与翻译 定义定义2.102.10 谓词公式归纳定义如下：谓词公式归纳定义如下：（1 1）原子公式是谓词公式；）原子公式是谓词公式；（2 2）如如果果是是谓谓词词公公式式，则则 也也是是谓谓词公式；词公式；（3 3）如如果果和和是是谓谓词词公公式式，则

20、则，和和也也都都是是谓谓词词公式；公式；（4 4）如如果果是是谓谓词词公公式式，x x是是个个体体变变元元，则则 x x(x)(x)，x x(x(x)和和！x x(x(x)也也都都是是谓词公式；谓词公式；（5 5）只有有限次地应用（）只有有限次地应用（1 1）（4 4）构）构成的符号串才是谓词公式。成的符号串才是谓词公式。2.2.2 2 谓谓词词公公式式2.2.1 2.2.1 谓词公式与翻译谓词公式与翻译 由定义可知，谓词公式是由由定义可知，谓词公式是由原子公式、命题联结词、量词以及原子公式、命题联结词、量词以及圆括号按照上述规则组成的一个符圆括号按照上述规则组成的一个符号串。因此，命题逻辑中

21、的命题公号串。因此，命题逻辑中的命题公式是谓词公式的一个特例。式是谓词公式的一个特例。为叙述方便，我们下面讨论为叙述方便，我们下面讨论只含只含“x x”和和“x x”的谓词公的谓词公式，事实上，量词式，事实上，量词“！x x”可以可以通过量词通过量词“x x”和和“x x”来表来表示。示。2.2.2 2 谓谓词词公公式式2.2.1 2.2.1 谓词公式与翻译谓词公式与翻译 一一般般来来说说，将将自自然然语语言言翻翻译译成成谓谓词词公公式主要有以下几个式主要有以下几个步骤步骤：（1 1）确定个体域，如无特别说明，一般）确定个体域，如无特别说明，一般使用全总个体域；使用全总个体域；（2 2）根根据

22、据个个体体域域，分分析析命命题题中中的的个个体体、个个体体性性质质以以及及各各个个个个体体间间的的关关系系，确确定定谓词；谓词；（3 3）根据表示数量的词确定量词；）根据表示数量的词确定量词；（4 4）利用联结词将整个命题符号化。）利用联结词将整个命题符号化。2.2.2 2 谓谓词词公公式式2.2.1 2.2.1 谓词公式与翻译谓词公式与翻译 例例2.2.5 5 将下列命题符号化。将下列命题符号化。（1 1）教室里有同学在讲话。教室里有同学在讲话。解解 因为题中没有特别指明个体域，因为题中没有特别指明个体域，所以这里采用全总个体域。所以这里采用全总个体域。令令S(xS(x)：x x是同学，是同

23、学，R(xR(x)：x x在教室里，在教室里，T(xT(x)：x x在讲话，则命在讲话，则命题可符号化为：题可符号化为：x(S(x)x(S(x)R(x)R(x)T(xT(x)。2.2.2 2 谓谓词词公公式式2.2.1 2.2.1 谓词公式与翻译谓词公式与翻译 （2 2）在在我我们们班班中中，并并非非所所有有同同学学都能取得优秀成绩。都能取得优秀成绩。解解 令令S(xS(x)：x x是是同同学学，C(xC(x)：x x在在我我们们班班中中，E(xE(x)：x x能能取取得得优优秀秀成成 绩绩，则则 命命 题题 可可 符符 号号 化化 为为：x(S(x)x(S(x)C(x)C(x)E(xE(x)

24、。或或者者，此此命命题题也也可可以以理理解解为为“在在我我们们班班中中存存在在不不能能取取得得优优秀秀成成绩绩的的同同学学”，则则 该该 命命 题题 也也 可可 符符 号号 化化 为为：x(S(x)x(S(x)C(x)C(x)E(xE(x)。2.2.2 2 谓谓词词公公式式2.2.1 2.2.1 谓词公式与翻译谓词公式与翻译 （3 3）没有最大的自然数。）没有最大的自然数。解解 命题中命题中“没有最大的没有最大的”显然是显然是对所有的自然数而言，所以可理解对所有的自然数而言，所以可理解为为“对任意的自然数对任意的自然数x x，存在着比，存在着比x x更大的自然数更大的自然数”。令。令N(x):

25、xN(x):x是自然是自然数，数，G(x,y):xG(x,y):x大于大于y y，则命题可符，则命题可符号化为：号化为：x(N(x)x(N(x)y(N(y)y(N(y)G(y,xG(y,x)。2.2.2 2 谓谓词词公公式式2.2.1 2.2.1 谓词公式与翻译谓词公式与翻译（4 4）今天有雨雪，有些人会跌跤。）今天有雨雪，有些人会跌跤。解解 令令R R：今天下雨，：今天下雨，S S：今天下雪，：今天下雪，M(xM(x)：x x是人，是人，F(xF(x)：x x会跌跤，则会跌跤，则命题可符号化为：命题可符号化为：(R R S)S)x(M(x)x(M(x)F(xF(x)。2.2.2 2 谓谓词词

26、公公式式2.2.1 2.2.1 谓词公式与翻译谓词公式与翻译 定义定义2.11 设设是谓词公式，是谓词公式，是是中连续的符号串且也是谓词公式，中连续的符号串且也是谓词公式，则称则称是是的的子公式子公式。例如，例如，=x(P(x)x(P(x)y(Q(y)y(Q(y)R(x,y)R(x,y)，=y(Q(y)y(Q(y)R(x,yR(x,y)，则则是是的子公式。而的子公式。而P(x)P(x)y y不不是谓词公式，因而也不是是谓词公式，因而也不是的子公的子公式。式。2.2.2 2 谓谓词词公公式式2.2.1 2.2.1 谓词公式与翻译谓词公式与翻译 定义定义2.112.11 设设是一个谓词公式，是一个

27、谓词公式，xx(x(x)和和 x x(x(x)是是的子公式，的子公式，则称则称 xx(x(x)与与 x x(x(x)是是的约束的约束部分，部分，x x称为是约束出现的。约束称为是约束出现的。约束出现的变元称为出现的变元称为约束变元约束变元，不是约，不是约束出现的变元称为束出现的变元称为自由变元自由变元。(x(x)称为是称为是 x x在在中的中的辖域辖域（或（或作用域作用域），），(x(x)称为是称为是 x x在在中中的辖域。的辖域。2.2.2 2 谓谓词词公公式式2.2.2 2.2.2 自由变元与约束变元自由变元与约束变元 确确定定一一个个量量词词的的辖辖域域即即是是找找出出位位于于该该量量词

28、词之之后后的的相相邻邻接接的的子子公公式式，具具体体地地讲：讲：若若量量词词后后有有括括号号，则则括括号号内内的的子子公公式就是该量词的辖域；式就是该量词的辖域；若量词后无括号，则与量词邻接的若量词后无括号，则与量词邻接的子公式为该量词的辖域。子公式为该量词的辖域。另外，当多个量词连续出现，它们另外，当多个量词连续出现，它们之间无括号之间无括号分隔时，后面的量词在前面分隔时，后面的量词在前面量词的辖域之中，且量词对变元的约束量词的辖域之中，且量词对变元的约束与量词的次序有关，一般不能随意调动。与量词的次序有关，一般不能随意调动。2.2.2 2 谓谓词词公公式式2.2.2 2.2.2 自由变元与

29、约束变元自由变元与约束变元 例例2.62.6 指出下列谓词公式中的自由变指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域。元和约束变元，并指明量词的辖域。（1 1）x(P(x)x(P(x)y(Q(y)y(Q(y)R(x,yR(x,y)（2 2）x(P(x)x(P(x)Q(y)Q(y)yR(x,yyR(x,y)解解 （1 1）量词）量词 x x的辖域是的辖域是P(x)P(x)y(Q(y)y(Q(y)R(x,yR(x,y)，y y的辖域的辖域是是Q(y)Q(y)R(x,yR(x,y)；x x和和y y的所有出现都是的所有出现都是约束出现。约束出现。（2 2）量词）量词 x x的辖域是的辖域

30、是P(x)P(x)Q(yQ(y)，这里，这里的的x x是约束变元，是约束变元，y y是自由变元；是自由变元；y y的辖的辖域是域是R(x,yR(x,y)，这里的，这里的x x是自由变元，是自由变元，y y是是约束变元。约束变元。2.2.2 2 谓谓词词公公式式2.2.2 2.2.2 自由变元与约束变元自由变元与约束变元 从上面的例子中可以看出，一个个从上面的例子中可以看出，一个个体变元在谓词公式中既可以自由出现，体变元在谓词公式中既可以自由出现，又可以约束出现。但是，在一个公式里又可以约束出现。但是，在一个公式里每个变元最好以一种形式出现。这就需每个变元最好以一种形式出现。这就需要对谓词公式进

31、行改名和代入。要对谓词公式进行改名和代入。v所谓所谓改名改名就是把一变元改为另一变元，就是把一变元改为另一变元，并要求改名后的式子与原式同真假。并要求改名后的式子与原式同真假。v所谓所谓代入代入就是把一变元代以公式就是把一变元代以公式(公式公式的值的变域应与变元的变域相同的值的变域应与变元的变域相同)，并，并要求代入后的公式为原式的特例。要求代入后的公式为原式的特例。2.2.2 2 谓谓词词公公式式2.2.2 2.2.2 自由变元与约束变元自由变元与约束变元q改名的规则如下：改名的规则如下：(1)(1)改名只对约束变元进行，不对自由变元进行；改名只对约束变元进行，不对自由变元进行；(2)(2)

32、改名必须处处进行，即对某量词约束的变元改名必须处处进行，即对某量词约束的变元改名时，必须对原式中该变元的一切受该量词改名时，必须对原式中该变元的一切受该量词约束的约束出现改名；约束的约束出现改名；(3)(3)对受某量词约束的变元改名时新名决不能与对受某量词约束的变元改名时新名决不能与该量词的辖域中的其它自由变元同名；该量词的辖域中的其它自由变元同名；(4)(4)改名前与改名后的约束关系保持不变。改名前与改名后的约束关系保持不变。总之，正确的改名结果是每个变元只以一总之，正确的改名结果是每个变元只以一种形式出现，最多只受一个量词约束。种形式出现，最多只受一个量词约束。2.2.2 2 谓谓词词公公

33、式式2.2.2 2.2.2 自由变元与约束变元自由变元与约束变元 例例2.2.7 7 对公式对公式 x(P(x,yx(P(x,y)yQ(yyQ(y)M(x,yM(x,y)(xR(xR(x x)Q(xQ(x)中的约束变元进行改名。中的约束变元进行改名。使使每个变元在公式中只以一种形式出现每个变元在公式中只以一种形式出现（即约束出现或自由出现）。（即约束出现或自由出现）。解解 在该公式中，将在该公式中，将P(x,yP(x,y)和和M(x,yM(x,y)中中的约束变元的约束变元x x改名为改名为z z，R(xR(x)中的中的x x改名改名为为S S，Q(yQ(y)中的中的y y改名为改名为t t，改

34、名后为：，改名后为：z(P(z,y)z(P(z,y)tQ(t)tQ(t)M(z,y)M(z,y)(SR(SSR(S)Q(xQ(x)。2.2.2 2 谓谓词词公公式式2.2.2 2.2.2 自由变元与约束变元自由变元与约束变元q代入的规则如下：代入的规则如下：(1)(1)代入只对自由变元进行；代入只对自由变元进行；(2)(2)代入必须处处进行，即对某自由变元代入必须处处进行，即对某自由变元施行代入时，必须对该自由变元的一切施行代入时，必须对该自由变元的一切自由出现施行代入；自由出现施行代入；(3)(3)代入前后的约束关系保持不变；代入前后的约束关系保持不变；(4)(4)代入前先对原式改名，使原式

35、中所有代入前先对原式改名，使原式中所有约束变元名与代入式中所有变元名互不约束变元名与代入式中所有变元名互不相同，然后施行代入；相同，然后施行代入；(5)(5)对命题变元和谓词变元也可施行代入，对命题变元和谓词变元也可施行代入，但必须保持代入前后约束关系不变。但必须保持代入前后约束关系不变。2.2.2 2 谓谓词词公公式式2.2.2 2.2.2 自由变元与约束变元自由变元与约束变元 例例2.2.8 8 对公式对公式(yA(x,y)yA(x,y)(xB(x,z)xB(x,z)C(x,y,z)C(x,y,z)x x zCzC(x,y,zx,y,z)中的自由变元进中的自由变元进行代入行代入,使每个变元

36、在公式中只以一种使每个变元在公式中只以一种形式出现（即约束出现或自由出现）。形式出现（即约束出现或自由出现）。解解 将该公式中的自由变元将该公式中的自由变元x x用用t t代入，代入，y y用用u u代入，代入，z z用用v v代入，代入后为：代入，代入后为：(yA(t,y)yA(t,y)(xB(x,v)xB(x,v)C(t,u,vC(t,u,v)x x zC(x,u,zzC(x,u,z)。2.2.2 2 谓谓词词公公式式2.2.2 2.2.2 自由变元与约束变元自由变元与约束变元 定义定义2.122.12 设有一谓词公式设有一谓词公式，其自由其自由个体变元为个体变元为x x1 1,x,x2

37、2,x xh h；命题变元为命题变元为P P1 1,P,P2 2,P Pk k，则我们把则我们把表示为：表示为：(x(x1 1,x,x2 2,x,xh h；P P1 1,P,P2 2,P Pk k)如果对个体域指定以如果对个体域指定以D D，对对x x1 1,x,x2 2,x xh h在个体域上分别指派以个体在个体域上分别指派以个体a a1 1,a,a2 2,a,ah h；对对P P1 1,P,P2 2,P Pk k分别指派以分别指派以P P1 1*,P,P2 2*,P Pk k*(其中其中P Pi i*或为或为0,0,或为或为1 1，i=1,2,i=1,2,k),k)，则称对则称对作了一个个

38、体作了一个个体域域D D上的上的指派指派，记为，记为(a(a1 1,a,a2 2,a,ah h；P P1 1*,P,P2 2*,P Pk k*)。如果该值为真，则该指如果该值为真，则该指派为派为的的成真指派成真指派；如果该值为假，则；如果该值为假，则该指派称为该指派称为的的成假指派成假指派。2.2.2 2 谓谓词词公公式式2.2.3 2.2.3 谓词公式的分类谓词公式的分类例例2.2.9 9 求公式求公式=x(P(x)x(P(x)Q(x,y)Q(x,y)R R的成真指派和的成真指派和成假指派，其中成假指派，其中P(xP(x)表示表示“x x是偶数是偶数”，Q(x,yQ(x,y)表示表示“y y

39、能整除能整除x x”,的个体域的个体域D=3,4D=3,4，R R是命题变元。是命题变元。解解 2.2.2 2 谓谓词词公公式式2.2.3 2.2.3 谓词公式的分类谓词公式的分类y Ry R x(P(x)x(P(x)Q(x,yQ(x,y)3 03 03 13 14 04 04 14 10 00 01 11 10 01 11 11 1 定义定义2.132.13 如果公式如果公式对个体域对个体域D D中任何指派均取得真值，则称中任何指派均取得真值，则称为为D D中的中的永真式永真式；如果均取得假值，；如果均取得假值，则称则称为为D D中的中的永假式永假式；如果至少；如果至少有一个指派取得真值，则

40、称有一个指派取得真值，则称为为D D中的中的可满足式可满足式。2.2.2 2 谓谓词词公公式式2.2.3 2.2.3 谓词公式的分类谓词公式的分类 例例2.12.10 0 判断下列公式的类型。判断下列公式的类型。（1 1）x x yG(x-yG(x-y,x+y)y,x+y)(Q(QQ Q)（2 2）G(x-y,x+y)G(x-y,x+y)（3 3）x x y(G(x,y)y(G(x,y)G(x,y)G(x,y)Q Q 其其中中x,yx,y的的个个体体域域为为整整数数集集I I，Q Q为命题变元，为命题变元，G(x,yG(x,y)表示表示x x y y。2.2.2 2 谓谓词词公公式式2.2.3

41、 2.2.3 谓词公式的分类谓词公式的分类 解解 (1)(1)无论对无论对Q Q指派何种命题常指派何种命题常元，元，Q QQ Q的真值总为的真值总为1 1，而在，而在I I中中对任意的对任意的x x，总存在，总存在y=1y=1使使x-1x-1 x+1x+1成立，所以成立，所以 x x yG(x-y,x+yyG(x-y,x+y)在在I I中中总为真，因此总为真，因此 x x yG(x-yG(x-,x+y),x+y)(Q(QQ Q)对任意的指派总对任意的指派总为真，是永真式。为真，是永真式。2.2.2 2 谓谓词词公公式式2.2.3 2.2.3 谓词公式的分类谓词公式的分类 （2 2）因为）因为x

42、-yx-y x+yx+y在在I I中的真值不确定，中的真值不确定，当指派当指派x=1,y=1x=1,y=1时，时，0 0 2 2，即，即x-yx-y x+yx+y取值为真；当指派取值为真；当指派x=1,y=-1x=1,y=-1时，时，2 2 0 0不不成立，即成立，即x-yx-y x+yx+y取值为假，所以，公取值为假，所以，公式式G(x-y,x+yG(x-y,x+y)是可满足式。是可满足式。（3 3）无论在个体域）无论在个体域I I中对中对x x，y y指派什么指派什么个体常元，个体常元，G(x,y)G(x,y)G(x,yG(x,y)总为假，总为假，从而从而 x x y(G(x,y)y(G(

43、x,y)G(x,y)G(x,y)Q Q总为假，总为假，所以该公式是永假式。所以该公式是永假式。2.2.2 2 谓谓词词公公式式2.2.3 2.2.3 谓词公式的分类谓词公式的分类 定义定义2.142.14 设设，为任意两个为任意两个谓词公式，它们有共同的个体域谓词公式，它们有共同的个体域D D，若在若在D D中中为永真式，则称为永真式，则称公式公式和和在在D D上等值，记为上等值，记为，称称为为等值式等值式。2.2.3 3 等等值值演演算算2.3.1 2.3.1 等值式的基本概念等值式的基本概念1.1.由命题公式推广的等值式由命题公式推广的等值式 利用代入定理将命题演算中的等值利用代入定理将命

44、题演算中的等值公式推广而得到谓词演算中的等值公式。公式推广而得到谓词演算中的等值公式。例如，在命题演算中有公式：例如，在命题演算中有公式：P PQ QP P Q Q，可推广而得：可推广而得：P(x)P(x)Q(x)Q(x)P(x)P(x)Q(xQ(x)，xP(x)xP(x)xQ(x)xQ(x)xP(x)xP(x)xQ(xxQ(x)等等等。等。利用以上方法，可得一类公式。利用以上方法，可得一类公式。2.2.3 3 等等值值演演算算2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算2.2.关于量词与联结词的一元谓词等值式关于量词与联结词的一元谓词等值式 1）消去量词等值式消去量词等值

45、式 设个体域为有限集设个体域为有限集D=aD=a1 1,a,a2 2,a,an n，则有则有 （1 1）xA(x)xA(x)A(aA(a1 1)A(aA(a2 2)A(aA(an n)（2 2）xA(x)xA(x)A(aA(a1 1)A(aA(a2 2)A(aA(an n)2 2）量词转换律量词转换律（1 1）xA(x)xA(x)x x A(xA(x)（2 2）xA(x)xA(x)x x A(x)A(x)2.2.3 3 等等值值演演算算2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算3 3）量量词词辖辖域域的的收收缩缩与与扩扩张张律律（下下述述等等值值式中，变元式中，变元x x

46、不在不在B B中出现）中出现）（1 1）x(A(x)x(A(x)B)B)xA(x)xA(x)B B（2 2）x(A(x)x(A(x)B)B)xA(x)xA(x)B B（3 3）x(A(x)x(A(x)B)B)xA(x)xA(x)B B（4 4）x(Bx(BA(x)A(x)B BxA(x)xA(x)（5 5）x(A(x)x(A(x)B)B)xA(x)xA(x)B B（6 6）x(A(x)x(A(x)B)B)xA(x)xA(x)B B（7 7）x(A(x)x(A(x)B)B)xA(x)xA(x)B B（8 8）x(Bx(BA(x)A(x)B BxA(x)xA(x)2.2.3 3 等等值值演演算算2

47、.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算4 4）量词分配律）量词分配律（1 1）x(A(x)x(A(x)B(x)B(x)xA(x)xA(x)xB(xB(x x)（2 2）x(A(x)x(A(x)B(x)B(x)xA(x)xA(x)x xB(x)B(x)要特别注意的是，量词分配律中要特别注意的是，量词分配律中的的“”和和“”联结词不要记错。联结词不要记错。2.2.3 3 等等值值演演算算2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算 例例2.112.11 证明证明 x(A(x)B(x)xA(x)xB(x)证明证明 令个体域为令个体域为D，设在任一指派，设在

48、任一指派 下，左式下，左式T，则在，则在D中存在一个个体中存在一个个体c使得使得A(c)B(c)T，从而，从而A(c)T或或B(c)T，因此，因此有有 xA(x)T或或 xB(x)T，所以，所以 xA(x)xB(x)T。反之，设在任一指派反之，设在任一指派 下，右式下，右式T，则，则 xA(x)T或或 xB(x)T，即在，即在D中存在两个个中存在两个个体体c，d使得使得A(c)T或或B(d)T，从而在，从而在D中存中存在一个个体在一个个体c或或d（不妨设（不妨设c）使得）使得A(c)B(c)T，所以，所以 x(A(x)B(x)T。由以上两方面知等值式成立。由以上两方面知等值式成立。2.2.3

49、3 等等值值演演算算2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算 思考思考 判断以下两个式子是否成立？判断以下两个式子是否成立？(1)(1)xA(xxA(x)xB(xxB(x)x(A(xx(A(x)B B(x(x)(2)(2)xA(xxA(x)xB(xxB(x)x(A(xx(A(x)B(B(x x)2.2.3 3 等等值值演演算算2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算3.3.关于二元谓词的等值式关于二元谓词的等值式 在在上上一一节节我我们们曾曾指指出出，量量词词出出现现的的次次序序直直接接关关系系到到命命题题的的意意义义，但但也也有有例例外外，相相

50、同同量量词词间间的的次次序序是是可可以以任任意意调调动动的的，不不同同量量词词间间的的次次序序则则不不能能随随意意调调动动。因此有下面两个等值式成立。因此有下面两个等值式成立。（1 1）x x y(A(x,y)y(A(x,y)y y x(A(x,yx(A(x,y)（2 2）x x y(A(x,y)y(A(x,y)y y x(A(xx(A(x,y),y)2.2.3 3 等等值值演演算算2.3.2 2.3.2 常用等值式及等值演算常用等值式及等值演算 思考思考 判断式子判断式子 x x yP(x,yyP(x,y)y y xP(x,yxP(x,y)是否成是否成立？立？2.2.3 3 等等值值演演算算