【精】第2章逻辑代数.doc

【精】第2章逻辑代数(下)谓词演算(论文资料)
《离散数学教程》教案与****题解析 理工学院 段景辉
第2章逻辑代数(下):谓词演算
谓词演算基本概念
个体
谓词演算中把一切讨论对象都称为个体(individuals)，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。确定的个体常用a，b，c等小写字母或字母串表示。a，b，c等小写字母或字母串称为个体常元(constants)。不确定的个体常用字母x，y，z，u，v，w等来表示。它们被称为个体变元，或变元(variables)。
谓词演算中把讨论对象——个体的全体称为个体域(domain of individuals)，常用字母D表示，并约定个体域都是非空的集合。当讨论对象未作具体指定，而是泛指一切客体时，个体域特称为全总域(universe)，用字母U表示。
当给定个体域时，常元表示该域中的一个确定的成员，而变元则可以取该域中的任何一个成员为其值。表示D上运算的运算符与常元、变元可组成所谓个体项(terms)。例如，数
22c学中的代数式a+b，x等。
由于在我们讨论的谓词演算中，其变元只能取值个体对象，不能取值函数、命题或谓词，因此，它又常被叫做一阶谓词演算。
谓词
量词
谓词演算中的量词(quantifiers)指数学中常用的数量词“所有的”(或“每一个”)和“有”(或“存在”)，用符号 , 和 ， 来表示，分别称为全称量词和存在量词。为了用全称量词,表示个体域中所有(每一个)个体满足一元谓词P，用存在量词，表示有(存在)个体满足一元谓词P，还需使用变元:
,xP(x) 读作“所有(任意，每一个)x满足P(x)”，表示个体域中所有的个体满足谓词P(x)。
，x P(x) 读作“有(存在，至少有一个)x满足P(x)”，表示个体域中至少有一个体满足谓词P(x)。
当量词用于一谓词填式或复合的谓词表达式时，该谓词或复合的谓词表达式称为量词的辖域(domains of quantifiers)。因此，量词的辖域或者是紧邻其右侧的那个谓词;或者是其右侧第一对括号内的表达式。
1
《离散数学教程》教案与****题解析 理工学院 段景辉
量词的指导变元和量词辖域内的同名变元与通常谓词填式中的个体变元不同，因为它可以改名却不能取值作代入。因此，我们把 ,xP(x) 和 ，xP(x) 中变元x称为约束变元(bound variables)，而那些可以取值作代入的变元则称为自由变元(free variables)。
对于一元谓词P(x)，,xP(x)，，xP(x)均为命题，它们所断言的“所有个体满足性质P(x)”与“存在个体满足性质P(x)”，其真值已经被给定的个体域所确定。特别是,当个体域中个
,„,a,，,xP(x) 的意义与命题 P(a)?„?P(a) 相一致，而 ，xP(x) 体有穷时，例如D = ,a1n1n
的意义与命题P(a)?„?P(a) 相一致。 1n
谓词公式及语句形式化
归纳定义谓词公式(predicate formula)集合，谓词公式又称合式公式，简称公式:
(1)谓词填式是公式，命题常元是公式(看作零元谓词)，常称原子公式。
(2)如果A，B是公式，x为任一个体变元，那么(，A)，(A?B)，(,xA)，(，x A)(当使用五个联结词时还有(A?B)，(A?B)，(A,B))都是公式。
(3)(终极条款，略)。
括号省略原则同命题公式，并约定，(,xA)，(，x A)中最外层括号也可省略。
语句形式化过程的四个关键步骤是:
, 准确地从语句中提取谓词。一般说来，表示性质的谓语用一元谓词表示，表示关系 的谓语用二元或更多元数的谓词来表示。
, 准确使用量词和确定量词的辖域，当辖域中多于一个谓词时必须注意括号的使用。
, 准确地使用谓词之间的真值联结词，正确地反映谓词之间的逻辑关系。
, 准确地使用多个重叠的量词以及与它们配套的指导变元，量词的排列次序应与原语 句的表述相一致。
自然语言语句中，常常涉及全总个体域的某个局部的所有个体或某些个体，这时需要使用所谓“限定谓词”把量词限于那个局部。一般地说，当限定谓词用于限定全称量词时，它必须作为蕴涵词的前件加入;当限定谓词用于限定存在量词时，它必须作为合取词的合取项加入，即用
,x(限定谓词A(x)?„) 和 ，x(限定谓词A(x)?„) 表示“所有满足A(x)的东西都 „”和“在满足A(x)的东西中有满足 „ 的个体”。这里A(x)是限定谓词，将个体域暂时限定在满足A(x)的那些个体上。
2
《离散