谓词逻辑的基本概念.ppt

《谓词逻辑的基本概念.ppt》由会员分享，可在线阅读，更多相关《谓词逻辑的基本概念.ppt（37页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 第二章 谓词逻辑第一讲第一讲 原因是三个原子命题不能把第原因是三个原子命题不能把第1 1个命题和个命题和第第2 2命题的共同属性命题的共同属性“人人”表示出来。苏格拉表示出来。苏格拉底是人，所有底是人，所有“人人”具有的共同属性具有的共同属性“死亡死亡”他也应该有，但在命题逻辑中无法实现。他也应该有，但在命题逻辑中无法实现。这就是命题逻辑的局限性。为了解决这个问这就是命题逻辑的局限性。为了解决这个问题需要引入谓词逻辑的有关概念。题需要引入谓词逻辑的有关概念。21 谓词逻辑的基本概念谓词逻辑的基本概念 211 谓词及其表示谓词及其表示 命题是一个有唯一真值的陈述句。陈述句主命题是一个有唯一真值

2、的陈述句。陈述句主要由主语、谓语、宾语和补语组成。其中主语、要由主语、谓语、宾语和补语组成。其中主语、谓语是句子的主要成份。谓语是句子的主要成份。主语是谓语描述的对象，称为个体或客体。主语是谓语描述的对象，称为个体或客体。谓语用于描述主语的性质和关系，是陈述句谓语用于描述主语的性质和关系，是陈述句的主体部分。的主体部分。定义定义2-1 可以独立存在的人、物、事称为个体或客体。可以独立存在的人、物、事称为个体或客体。定义定义2-2 在谓词逻辑中，刻划个体性质和关系的在谓词逻辑中，刻划个体性质和关系的谓语称为谓词。谓语称为谓词。例例2-1：张三是大学生。张三是大学生。李四是大学生。李四是大学生。我

3、们我们 用大写字母用大写字母S表示表示“是大学生是大学生”，用小写字母用小写字母a、b分别表示分别表示“张三张三”和和“李四李四”。上述两个命题可表示为：上述两个命题可表示为：S（a）：张三是大学生。）：张三是大学生。S（b）：李四是大学生。）：李四是大学生。谓词可分为一元谓词和多元谓词谓词可分为一元谓词和多元谓词。在命题中若在命题中若谓词只联系一个客体，则称之为一元谓词谓词只联系一个客体，则称之为一元谓词。一元谓一元谓词表示客体的属性词表示客体的属性。若谓词联系着若谓词联系着n个客体，则称个客体，则称之为之为n元谓词元谓词。多元谓词表示客体之间的联系多元谓词表示客体之间的联系。例例2-2 冰

4、比水密度小。冰比水密度小。4大于大于3 解：解：用用D表示比密度小，表示比密度小，G表示大于，表示大于，则上述谓词命题可以表示为：则上述谓词命题可以表示为：D（冰（冰,水）和水）和G（4,3）。）。不难发现，在多元谓词中，个体在谓词中出现的次序不不难发现，在多元谓词中，个体在谓词中出现的次序不是任意的，它将直接影响谓词命题的真值。在多元谓词公式是任意的，它将直接影响谓词命题的真值。在多元谓词公式中，个体在谓词公式出现的次序一旦约定就不能更改。中，个体在谓词公式出现的次序一旦约定就不能更改。如果更改便变成不同的命题，其真值也发生变化。如上如果更改便变成不同的命题，其真值也发生变化。如上例中改为例

5、中改为D（水，冰）和（水，冰）和G（3，4），变成命题），变成命题“水比冰密水比冰密度小度小”和和“3大于大于4”，其真值都为假。，其真值都为假。21 常元与变元常元与变元 在谓词逻辑中，表示特定个体的词称为个在谓词逻辑中，表示特定个体的词称为个体常元。个体常元可以是代表个体的标识符，体常元。个体常元可以是代表个体的标识符，也可以直接引用个体的名称。如上述例也可以直接引用个体的名称。如上述例2-1中中a代表代表“张三张三”，b代表代表“李四李四”；在例；在例2-中中直接使用个体的名称，如直接使用个体的名称，如“水水”、“冰冰”、“”、“”等。等。在谓词逻辑中，用来表示未知或泛指的个在谓词逻辑中

6、，用来表示未知或泛指的个体的词称为个体变元。其标识符常用小写字母体的词称为个体变元。其标识符常用小写字母x，y，z表示。例如用表示。例如用(x)表示表示x是素是素数，数，Q(x)表示表示x是有理数。是有理数。(x)和和Q(x)不是命不是命题，只有用具体的个体取代其中的个体变元后题，只有用具体的个体取代其中的个体变元后才是命题，才有真值。才是命题，才有真值。22 命题命题 函数及量化函数及量化 221 命题命题 函数函数 单独的谓词不是命题，在谓词后面单独的谓词不是命题，在谓词后面的括号中填上代表个体的标识符所得的的括号中填上代表个体的标识符所得的式式 子子 称为谓词填式称为谓词填式 。如果在谓

7、词填式如果在谓词填式 的括号中填入的是的括号中填入的是个体常元，则该谓词填式个体常元，则该谓词填式 是一个命题。是一个命题。在谓词填在谓词填 式式 的括号中填入的是个体变元，的括号中填入的是个体变元，则称该谓词则称该谓词 填式为命题函数。填式为命题函数。定义定义2-3 由一个谓词和一些个体变元组由一个谓词和一些个体变元组成的表达式成的表达式 称为原子命题函数。用逻辑称为原子命题函数。用逻辑联结词把一个或多个原子命题函数连接联结词把一个或多个原子命题函数连接而成的表达式而成的表达式 称为复合命题函数。称为复合命题函数。如上述所举例子中如上述所举例子中S（x）、）、D（x,y）、）、G（x,y）都

8、是简单命题函数，其中都是简单命题函数，其中x、y为个体变元。为个体变元。把不含个体变元的命题函数称为把不含个体变元的命题函数称为0元谓词。元谓词。例如，上述的例如，上述的D（冰（冰,水）和水）和G（4，3）等都是）等都是0元谓词，元谓词，0元谓词本身就是命题。元谓词本身就是命题。命题逻辑中的原子命题都可以用命题逻辑中的原子命题都可以用0元谓词元谓词表示，因此，可以将命题逻辑看成是谓词逻辑表示，因此，可以将命题逻辑看成是谓词逻辑的特殊情况。的特殊情况。值得注意的是，在谓词演算中逻辑联结词值得注意的是，在谓词演算中逻辑联结词的含义与命题演算中完全相同，且命题演算中的含义与命题演算中完全相同，且命题

9、演算中的公式在谓词演算中完全适用。的公式在谓词演算中完全适用。例例2-3 将下列命题将下列命题 符号化：符号化：（1）存在既是素数又是偶数的数。）存在既是素数又是偶数的数。解：令：解：令：F(x):x是素数；是素数；G(x):x是偶数；是偶数；则命题则命题 符号化为：符号化为：F(x)G(x)。（2）只有努力学习才能取得好成绩。）只有努力学习才能取得好成绩。解：解：令：令：G(x):x想取得好成绩；想取得好成绩；H(x):x 努力学习；努力学习；则命题则命题 符号化为：符号化为：（3）在实数域中，若）在实数域中，若x比比y大，大，y比大比大z，则，则x比比z大。大。解：设解：设x、y、z是实数

10、。是实数。令：令：P(x,y):x比比y大。大。则命题则命题 符号化为：符号化为：P(x,y)P(y,z)P(x,z)定义定义2-4 个体变元的论述范围称为个体域个体变元的论述范围称为个体域（或论域）。（或论域）。各种个体域综合在一起作为论述范围称各种个体域综合在一起作为论述范围称为全总个体域。为全总个体域。个体域和全总个体域是相对的，它根据个体域和全总个体域是相对的，它根据你讨论的问题而定，同时它可以是有限的，你讨论的问题而定，同时它可以是有限的，也可以是无限的。也可以是无限的。222 个体域个体域223 量量 化化 用具体个体的名称取代个体变元，使命题函数成用具体个体的名称取代个体变元，使

11、命题函数成为命题的过程称为代换，通过代换而得到的命题称为为命题的过程称为代换，通过代换而得到的命题称为命题函数的代换实例。由代换实例得到的命题是个别命题函数的代换实例。由代换实例得到的命题是个别命题。命题。除代换外，我们还可以采用量化的办法来确定命除代换外，我们还可以采用量化的办法来确定命题，采用量化确定的命题是一个命题集合。题，采用量化确定的命题是一个命题集合。所谓量化是指出个体变元在个体域中的取所谓量化是指出个体变元在个体域中的取值方式。值方式。在谓词逻辑中，个体域中个体变元的取值方式常在谓词逻辑中，个体域中个体变元的取值方式常用的有以下两种：用的有以下两种：1.全称量词全称量词 如果命题

12、函数个体变元在个体域中的取值如果命题函数个体变元在个体域中的取值方式是考虑论域中的所有个体，则这种量化称方式是考虑论域中的所有个体，则这种量化称为全称量化。为全称量化。如日常语言中的如日常语言中的“所有的所有的”、“任意的任意的”、“每一个每一个”等词。等词。我们把我们把“所有的所有的”的英语短语的英语短语“For All”中中的的“All”的第一个字母的第一个字母“A”倒写为倒写为“”作作为全称量词符号。为全称量词符号。“x”表示个体域中的所表示个体域中的所有个体，其中的有个体，其中的“x”称为指导变元。例如，称为指导变元。例如，“xP(x)”就表示个体域中的所有个体都具就表示个体域中的所有

13、个体都具有性质有性质P。例如：设论域为人类例如：设论域为人类 H(x)：表示：表示x是要呼吸的。是要呼吸的。则则xH(x)表示：表示：所有人都是要呼吸的。所有人都是要呼吸的。例如：所有的自然数都是实数。例如：所有的自然数都是实数。N(x)：x是自然数。是自然数。R(x)：x是实数。是实数。则原命题可以表示为：则原命题可以表示为：2.存在量词存在量词 如果命题函数个体变元在个体域中的取值方如果命题函数个体变元在个体域中的取值方式是考虑个体域中的部分个体，则称为存在量化。式是考虑个体域中的部分个体，则称为存在量化。它对应日常语言中的它对应日常语言中的“存在着存在着”、“有的有的”、“至少有一个至少

14、有一个”、“有一些有一些”等词。英语短等词。英语短语表示为语表示为“There Exist”，我们用，我们用“Exist”的第的第一个字母一个字母E的反写为的反写为“”作为存在量词符号。作为存在量词符号。“x”表示论域中存在某些个体，其中的表示论域中存在某些个体，其中的“x”称为指导变元。例如，称为指导变元。例如，“xP(x)”表示论域中表示论域中存在个体具有性质存在个体具有性质P。例如：设论域为人类例如：设论域为人类 S(x)：表示：表示x吸烟。吸烟。则则x S(x)表示有人表示有人 吸烟。吸烟。例如：有的学生在看书。例如：有的学生在看书。S(x)：表示：表示x是学生。是学生。B(y)：表示

15、：表示y是书籍。是书籍。R(x,y)：表示：表示x正在看正在看y。则原命题表示为：则原命题表示为：P P(x x)是不能确定真值的命题函数，其中的是不能确定真值的命题函数，其中的 x x 是个体变元；是个体变元；而而 xP(x)和和xP(x)都是可以确定真值的命都是可以确定真值的命题，其中的题，其中的x x再不起变元的作用，已经受到量词再不起变元的作用，已经受到量词x、x 的限制。个体变元受到量词限制的过程的限制。个体变元受到量词限制的过程 称之为量化。称之为量化。【说明说明】xP(x)和和xP(x)与与P(x)有着本质的区别。有着本质的区别。2 22 24 4 特性谓词特性谓词 命题函数的量

16、化与个体域有关，个体域的指定不但命题函数的量化与个体域有关，个体域的指定不但影响命题的表达形式，而且影响命题的真值。影响命题的表达形式，而且影响命题的真值。为了描述方便，将所讨论的命题函数的个体域统一为了描述方便，将所讨论的命题函数的个体域统一使用全总个体域。使用全总个体域后，对于每个个体变使用全总个体域。使用全总个体域后，对于每个个体变元的取值范围必须用刻划个体特性的谓词加以限制。元的取值范围必须用刻划个体特性的谓词加以限制。定义定义2-5 2-5 在全总个体域中在全总个体域中,表示具体个体域的谓词称表示具体个体域的谓词称为特性谓词。为特性谓词。例如：所有人是要死的。例如：所有人是要死的。（

17、1 1）论域为人类。论域为人类。D(xD(x)：表示：表示x x是要死的。是要死的。符号化为：符号化为：x x D(xD(x)（2 2）论域是全总个体域。）论域是全总个体域。使用全总个体域，就必须使用特性谓词来限制个体的使用全总个体域，就必须使用特性谓词来限制个体的取值范围。取值范围。H(xH(x)：表示：表示x x是人类（特性谓词）。是人类（特性谓词）。符号化为：符号化为：值得注意的是：值得注意的是：在全称量化中，特性谓词常作为条件命在全称量化中，特性谓词常作为条件命题的前件。题的前件。例如：有人吸烟例如：有人吸烟（1）论域为人类论域为人类。S(x)：表示表示x x吸烟吸烟。符号化为符号化为

18、：（2）论域为全总个体域论域为全总个体域。此时就必须使用特性谓词来限制个体的取值范围此时就必须使用特性谓词来限制个体的取值范围。H(x)：表示：表示x是人类是人类 符号化为：符号化为：例如：存在既是偶数又是素数的有理数。例如：存在既是偶数又是素数的有理数。论域为全总个体域。论域为全总个体域。Q(x)：表示：表示x是有理数。是有理数。E(x)：表示：表示x是偶数。是偶数。P(x)：表示：表示x是素数。是素数。原命题符号化为：原命题符号化为：值得注意的是：值得注意的是：在存在量化中，特性谓词常作为合取项在存在量化中，特性谓词常作为合取项。225量化与代换实例量化与代换实例 当个体域为有限集合时，例

19、如个体域为有限集当个体域为有限集合时，例如个体域为有限集a1,a2,a3,an，由量词的定义可以知道，对，由量词的定义可以知道，对于任意谓词都有：于任意谓词都有：（2-1）（2-2）这就是这就是量词的消去规则量词的消去规则，它可以将带量词，它可以将带量词的谓词公式转化成谓词公式的代换实例。这一的谓词公式转化成谓词公式的代换实例。这一点非常重要，在谓词逻辑的等价公式证明中常点非常重要，在谓词逻辑的等价公式证明中常采用这个规则。采用这个规则。23谓词合适公式与翻译谓词合适公式与翻译 231谓词合适公式谓词合适公式 在命题逻辑中引入了命题公式的概念，在命题逻辑中引入了命题公式的概念，它是由命题常元、

20、命题变元、命题联结词和它是由命题常元、命题变元、命题联结词和圆括号按照一定的规律所组成的符号串。谓圆括号按照一定的规律所组成的符号串。谓词逻辑是命题逻辑的进一步拓展，在谓词逻词逻辑是命题逻辑的进一步拓展，在谓词逻辑中，也需要引入原子谓词公式和谓词合适辑中，也需要引入原子谓词公式和谓词合适公式公式(Well form formula(Well form formula简称谓词公式简称谓词公式)的概的概念念。定义定义2-7 原子谓词公式定义如下：原子谓词公式定义如下：(1)一个命题是原子谓词公式。一个命题是原子谓词公式。(2)一个命题变元是原子谓词公式。一个命题变元是原子谓词公式。(3)由由n 个

21、个体变元个个体变元 及及n 元元谓词所组成的命题函数也是一个原子谓词谓词所组成的命题函数也是一个原子谓词公式。公式。原子谓词公式简称为原子公式。原子谓词公式简称为原子公式。定义定义2-8 谓词公式定义如下：谓词公式定义如下：(1)一个原子公式是一个谓词公式。一个原子公式是一个谓词公式。(2)若若A是谓词公式，则是谓词公式，则A 也是谓词公式。也是谓词公式。(3)若若A、B是谓词公式，则是谓词公式，则(AB)、(AB)、(AB)、(AB)也是谓词公式。也是谓词公式。(4)若若A是谓词公式，是谓词公式，x是是A中的个体变元，则中的个体变元，则xA(x)、xA(x)也是谓词公式。也是谓词公式。只有有

22、限次地运用规则只有有限次地运用规则(1)、(2)、(3)、(4)所得所得到的符号串才是谓词公式。到的符号串才是谓词公式。注意注意:谓词公式中的某些圆括号也可以省谓词公式中的某些圆括号也可以省 略略,其其规定与命题公式相同，但量词后的圆括号不能省略，规定与命题公式相同，但量词后的圆括号不能省略，因为它关系到量词的作用范围。因为它关系到量词的作用范围。232谓词公式的翻译谓词公式的翻译 与命题公式的翻译类似，谓词公式的翻译同样有两个与命题公式的翻译类似，谓词公式的翻译同样有两个方方 面，一是将自然语言描述的命题符号化，也称形式面，一是将自然语言描述的命题符号化，也称形式化；二是将形式化的谓词公式翻

23、译成自然语言描述的化；二是将形式化的谓词公式翻译成自然语言描述的命题。在公式翻译过程中，除注意联结词的选择外，命题。在公式翻译过程中，除注意联结词的选择外，还必须注意量词的选择。还必须注意量词的选择。一、将自然语言描述的谓词公式形式化一、将自然语言描述的谓词公式形式化 例例2-4 每个人都会犯错误每个人都会犯错误 解：该命题可以说成解：该命题可以说成“对于所有的对于所有的x，如果如果x是人，则是人，则x会犯错误会犯错误”。设设H(x)H(x)：x 是人。是人。M(x)M(x)：x会犯错误。会犯错误。则命题可表示为：则命题可表示为：例例2-5 并非所有实数都是有理数并非所有实数都是有理数解：该命

24、题可以说成解：该命题可以说成“所有实数都是有理数是不对的所有实数都是有理数是不对的”。设设 R(x)：x是实数。是实数。Q(x)：x是有理数。是有理数。则命题可表示为：则命题可表示为：例例2-6 尽管有的人聪明，但不是所有的人都聪明尽管有的人聪明，但不是所有的人都聪明解：该命题是由两个并列的句子组成，即由两个合取项组成。解：该命题是由两个并列的句子组成，即由两个合取项组成。第一个合取项为第一个合取项为“存在聪明的人存在聪明的人”，第二个合取项是，第二个合取项是“不不是所有的人都是聪明人是所有的人都是聪明人”。设设 H(x)：x是人。是人。C(x)：x聪明。聪明。则命题可表示为：则命题可表示为：

25、例例2-7李涛无书不读。李涛无书不读。解：该命题即是说解：该命题即是说“李涛所有的书都读李涛所有的书都读”。设设 P(x)：x是书。是书。Q(y,x)：y读读x。a:李涛。李涛。则命题可表示为：则命题可表示为：例例2-8有人无书不读。有人无书不读。解：该命题可解释为存在这样的人，这种人所有解：该命题可解释为存在这样的人，这种人所有书都读。书都读。H(y)：y是人。是人。P(x)：x是书。是书。Q(y,x)：y读读x。则命题可表示为：则命题可表示为：例例2-9 设个体域为全总个体域，令设个体域为全总个体域，令C(x):x是火车；是火车；G(y):y是汽是汽车；车；Q(x,y):x比比y跑得快跑得快;S(x,y):x和和y相同。符号化下列命题：相同。符号化下列命题：(1)有的火车比所有的汽车跑得快。有的火车比所有的汽车跑得快。(2)并不是所有的火车比汽车跑得快。并不是所有的火车比汽车跑得快。(3)不存在两辆完全相同的汽车。不存在两辆完全相同的汽车。符号化谓词公式的步骤：符号化谓词公式的步骤：（1）分解原子谓词，包括谓词、个体和量词。）分解原子谓词，包括谓词、个体和量词。（2）选择正确的量词。）选择正确的量词。（3）选择正确的联接词。）选择正确的联接词。