谓词逻辑的基本概念.ppt

,第二章 谓词逻辑,第一讲,原因是三个原子命题不能把第1个命题和第2命题的共同属性“人”表示出来。苏格拉底是人，所有“人”具有的共同属性“死亡”他也应该有，但在命题逻辑中无法实现。这就是命题逻辑的局限性。为了解决这个问题需要引入谓词逻辑的有关概念。,21 谓词逻辑的基本概念 211 谓词及其表示 命题是一个有唯一真值的陈述句。陈述句主要由主语、谓语、宾语和补语组成。其中主语、谓语是句子的主要成份。 主语是谓语描述的对象，称为个体或客体。 谓语用于描述主语的性质和关系，是陈述句的主体部分。,定义2-1 可以独立存在的人、物、事称为个体或客体。,定义2-2 在谓词逻辑中，刻划个体性质和关系的 谓语称为谓词。,例2-1： 张三是大学生。 李四是大学生。 我们 用大写字母S表示“是大学生”， 用小写字母a、b分别表示“张三”和“李四”。 上述两个命题可表示为： S（a）：张三是大学生。 S（b）：李四是大学生。,谓词可分为一元谓词和多元谓词。在命题中若谓词只联系一个客体，则称之为一元谓词。一元谓词表示客体的属性。若谓词联系着n个客体，则称之为n元谓词。多元谓词表示客体之间的联系。,例2-2 冰比水密度小。 4大于3 解： 用D表示 比密度小， G表示大于， 则上述谓词命题可以表示为： D（冰,水）和G（4,3）。 不难发现，在多元谓词中，个体在谓词中出现的次序不是任意的，它将直接影响谓词命题的真值。在多元谓词公式中，个体在谓词公式出现的次序一旦约定就不能更改。 如果更改便变成不同的命题，其真值也发生变化。如上例中改为D（水，冰）和G（3，4），变成命题“水比冰密度小”和“3大于4”，其真值都为假。,21 常元与变元 在谓词逻辑中，表示特定个体的词称为个体常元。个体常元可以是代表个体的标识符，也可以直接引用个体的名称。如上述例2-1中a代表“张三”，b代表“李四”；在例2-中直接使用个体的名称，如“水”、“冰”、“”、“”等。 在谓词逻辑中，用来表示未知或泛指的个体的词称为个体变元。其标识符常用小写字母x，y，z表示。例如用(x)表示x是素数，Q(x)表示x是有理数。(x) 和Q(x)不是命题，只有用具体的个体取代其中的个体变元后才是命题，才有真值。,22 命题 函数及量化 221 命题 函数 单独的谓词不是命题，在谓词后面的括号中填上代表个体的标识符所得的式 子 称为谓词填式 。 如果在谓词填式 的括号中填入的是个体常元，则该谓词填式 是一个命题。在谓词填 式 的括号中填入的是个体变元，则称该谓词 填式为命题函数。,定义2-3 由一个谓词和一些个体变元组成的表达式 称为原子命题函数。用逻辑联结词把一个或多个原子命题函数连接而成的表达式 称为复合命题函数。,如上述所举例子中S（x）、D（x,y）、G（x,y）都是简单命题函数，其中x、y为个体变元。,把不含个体变元的命题函数称为0元谓词。例如，上述的D（冰,水）和G（4，3）等都是0元谓词， 0元谓词本身就是命题。 命题逻辑中的原子命题都可以用0元谓词表示，因此，可以将命题逻辑看成是谓词逻辑的特殊情况。 值得注意的是，在谓词演算中逻辑联结词的含义与命题演算中完全相同，且命题演算中的公式在谓词演算中完全适用。,例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是实数。 令：P(x,y): x比y大。 则命题 符号化为： P(x,y)P(y,z)P(x,z),定义2-4 个体变元的论述范围称为个体域（或论域）。 各种个体域综合在一起作为论述范围称为全总个体域。 个体域和全总个体域是相对的，它根据你讨论的问题而定，同时它可以是有限的，也可以是无限的。,222 个体域,223 量 化 用具体个体的名称取代个体变元，使命题函数成为命题的过程称为代换，通过代换而得到的命题称为命题函数的代换实例。由代换实例得到的命题是个别命题。 除代换外，我们还可以采用量化的办法来确定命题，采用量化确定的命题是一个命题集合。 所谓量化是指出个体变元在个体域中的取值方式。 在谓词逻辑中，个体域中个体变元的取值方式常用的有以下两种：,1.全称量词 如果命题函数个体变元在个体域中的取值方式是考虑论域中的所有个体，则这种量化称为全称量化。 如日常语言中的“所有的”、“任意的”、“每一个”等词。 我们把“所有的”的英语短语“For All”中的“All”的第一个字母“A”倒写为“” 作为全称量词符号。“x ”表示个体域中的所有个体，其中的“x”称为指导变元。例如，“xP(x) ”就表示个体域中的所有个体都具有性质P 。,例如：设论域为人类 H(x)：表示x是要呼吸的。 则xH(x)表示： 所有人都是要呼吸的。 例如：所有的自然数都是实数。 N(x) ：x是自然数。 R(x) ：x是实数。 则原命题可以表示为：,2.存在量词 如果命题函数个体变元在个体域中的取值方式是考虑个体域中的部分个体，则称为存在量化。 它对应日常语言中的“存在着”、“有的”、“至少有一个”、“有一些”等词。英语短语表示为“There Exist”，我们用“Exist”的第一个字母E的反写为“”作为存在量词符号。“x ”表示论域中存在某些个体，其中的“x”称为指导变元。例如，“xP(x) ”表示论域中存在个体具有性质P 。,例如：设论域为人类 S(x) ：表示x吸烟。 则x S(x) 表示有人 吸烟。 例如：有的学生在看书。 S(x) ：表示x是学生。 B(y) ：表示y是书籍。 R(x,y) ：表示x正在看y。 则原命题表示为：,P(x) 是不能确定真值的命题函数，其中的 x 是个体变元； 而 xP(x) 和xP(x) 都是可以确定真值的命题，其中的x再不起变元的作用，已经受到量词x、x 的限制。个体变元受到量词限制的过程 称之为量化。,【说明】xP(x)和xP(x)与P(x)有着本质的区别。,224 特性谓词 命题函数的量化与个体域有关，个体域的指定不但影响命题的表达形式，而且影响命题的真值。 为了描述方便，将所讨论的命题函数的个体域统一使用全总个体域。使用全总个体域后，对于每个个体变元的取值范围必须用刻划个体特性的谓词加以限制。 定义2-5 在全总个体域中, 表示具体个体域的谓词称为特性谓词。 例如：所有人是要死的。 （1） 论域为人类。 D(x) ：表示x是要死的。 符号化为：x D(x),（2）论域是全总个体域。 使用全总个体域，就必须使用特性谓词来限制个体的取值范围。 H(x) ：表示x是人类（特性谓词）。 符号化为： 值得注意的是：在全称量化中，特性谓词常作为条件命题的前件。 例如：有人吸烟 （1）论域为人类。 S(x) ：表示x吸烟。 符号化为： （2）论域为全总个体域。 此时就必须使用特性谓词来限制个体的取值范围。 H(x) ：表示x是人类 符号化为：,例如：存在既是偶数又是素数的有理数。 论域为全总个体域。 Q(x) ：表示x是有理数。 E(x) ：表示x是偶数。 P(x) ：表示x是素数。 原命题符号化为： 值得注意的是： 在存在量化中，特性谓词常作为合取项。,225量化与代换实例 当个体域为有限集合时，例如个体域为有限集a1,a2,a3,an ，由量词的定义可以知道，对于任意谓词都有： （2-1） （2-2） 这就是量词的消去规则，它可以将带量词的谓词公式转化成谓词公式的代换实例。这一点非常重要，在谓词逻辑的等价公式证明中常采用这个规则。,23谓词合适公式与翻译 231谓词合适公式 在命题逻辑中引入了命题公式的概念，它是由命题常元、命题变元、命题联结词和圆括号按照一定的规律所组成的符号串。谓词逻辑是命题逻辑的进一步拓展，在谓词逻辑中，也需要引入原子谓词公式和谓词合适公式(Well form formula简称谓词公式)的概念。,定义2-7 原子谓词公式定义如下： (1) 一个命题是原子谓词公式。 (2) 一个命题变元是原子谓词公式。 (3) 由n 个个体变元 及n 元谓词所组成的命题函数也是一个原子谓词公式。 原子谓词公式简称为原子公式。,定义2-8 谓词公式定义如下： (1)一个原子公式是一个谓词公式。 (2)若A是谓词公式，则A 也是谓词公式。 (3)若A、B是谓词公式，则(AB) 、(AB) 、(AB) 、(AB) 也是谓词公式。 (4)若A是谓词公式，x是A中的个体变元，则xA(x) 、xA(x) 也是谓词公式。 只有有限次地运用规则(1)、(2)、(3)、(4)所得到的符号串才是谓词公式。,注意: 谓词公式中的某些圆括号也可以省 略,其规定与命题公式相同，但量词后的圆括号不能省略，因为它关系到量词的作用范围。,232谓词公式的翻译 与命题公式的翻译类似，谓词公式的翻译同样有两个方 面，一是将自然语言描述的命题符号化，也称形式化；二是将形式化的谓词公式翻译成自然语言描述的命题。在公式翻译过程中，除注意联结词的选择外，还必须注意量词的选择。 一、将自然语言描述的谓词公式形式化 例2-4 每个人都会犯错误 解：该命题可以说成“对于所有的x，如果x是人，则x会犯错误”。 设H(x)：x 是人。 M(x)：x会犯错误。 则命题可表示为：,例2-5 并非所有实数都是有理数 解：该命题可以说成“所有实数都是有理数是不对的”。 设 R(x)：x是实数。 Q(x)：x是有理数。 则命题可表示为： 例2-6 尽管有的人聪明，但不是所有的人都聪明 解：该命题是由两个并列的句子组成，即由两个合取项组成。第一个合取项为“存在聪明的人”，第二个合取项是“不是所有的人都是聪明人”。 设 H(x) ：x是人。 C(x)：x聪明。 则命题可表示为：,例2-7李涛无书不读。 解：该命题即是说“李涛所有的书都读”。 设 P(x) ：x是书。 Q(y,x)：y读x。 a: 李涛。 则命题可表示为： 例2-8有人无书不读。 解：该命题可解释为存在这样的人，这种人所有书都读。 H(y)：