离散数学与组合数学-数理逻辑-02谓词演算及其形式系统-01个体谓词和量词

第二章 谓词演算及其形式系统

2.1 个体谓词和量词

2.1.1 个体

个体常元(constants):确定的个体用

等小写字母或字符串表示，称为常元(constants) 个体变元(variables):不确定的个体常用字母

等表示，称为变元(variables)

个体域(domain of individuals)：谓词演算中把讨论对象–个体的全体称为个体域，常用字母

表示，并约定任何

中都至少含有一个成员。 全总域(universe)：当讨论对象遍及一切客体时，个体域特称为全总域，用字母

表示。

当给定个体域时，常元表示该域中的一个确定成员，而变元则可以取该域中的任何一个成员为其值。表示

上个体间运算的运算符与常元、变元组成所谓个体项，例如

等。

2.1.2 谓词

谓词(predicate)：我们把语句中表示个体性质和关系的语言成分（通常是谓语）称为谓词(predicate)。谓词携有可以放置个体的空位，当空位上填入个体后，便产生一个关于这些个体的语句，它断言个体具有谓词所表示的性质和关系。空位的写法有一个明显的缺点，可读性差。因此常用变元来代替空位，被称为谓词命名式，简称谓词。

元数：通常把谓词所携空位的数目称为谓词的元数。

2.1.3 量词

量词(quantifiers)：谓词演算中的量词值数量词“所有”和“存在有”，分别用符号

（全称量词）和

（存在量词）来表示。

自由变元(free variables)：可以取值带入的变元则称为自由变元(free variables)。 约束变元：不可以取值代入的变元称为约束变元。

量词的辖域(domains of quantifers)：当量词用于一谓词或复合的谓词表达式时，该谓词或符合的谓词表达式称为量词的辖域(domains of quantifers) 案例：

读作“有（存在）

满足

”。表示个体域中至少有一个体满足

。

中

的辖域是

其中

是约束变元。

不在辖域内，

里的

是自由变元。

谓词演算是数理逻辑最基本的形式系统，其又被称为一阶逻辑。一个可以回答真假的命题，不仅可以分析到简单命题，还可以分析到其中的个体、量词和谓词。个体表示某一个物体或元素，量词表示数量，谓词表示个体的一种属性 。例如用P(x)表示x是一棵树，则P(y)表示y是一棵树，用Q(x)表示x有叶 ，则Q(y)表示y也有叶。这里P、Q是一元谓词，x，y是个体，公式"∀x(P(x)→Q(x))表示每一棵树都有叶子 ，这里"是全称量词表示“每一个” 。公式∃ x(P(x)∧Q(x))表示存在有叶子的树，∃这里是存在量词，表示“至少存在一个”。 谓词演算除了一元谓词，也可以有二元 ，三元 ，甚至多元谓词。事实上，数学中的关系，函数都可以看成谓词。例如x≤y可以看成二元谓词，x+y=z可以看成三元谓词，因此谓词演算的公式可表示数学中的一些命题。

2.1.4 谓词公式及语句的形式化

谓词可以在一定的个体集合中给出解释，谓词公式可以在这样的个体集合中取到真假值。

合式公式，又称谓词公式，是一种形式语言表达式，即形式系统中按一定规则构成的表达式。按照模型论中一种通行习惯，语言F中的合式公式定义如下：

1.原子公式是合式公式； 2.若φ和ψ是合式公式，则(φ∧ψ)及(ᒣφ)是合式公式； 3.若φ是合式公式，而x是变元,则(ᗄx)φ是合式公式； 4.有限次地应用1—3所得到的符号序列是合式公式。 合式公式有时简称公式，如果一个公式φ中的自由变元都属于集合{x₁，x₂，…，xₑ}，则φ也可以记为φ(x₁，x₂，…，xₑ)，不含量词、自由变元的合式公式，分别称为开公式和闭公式，后者又称语句，例如R(x，y)为开公式，ᗄxR(x)是一个语句，由原子公式及联结词∧，∨，ᗄ，∃构成语句 称为正语句。

谓词公式在个体集合中取值的严格定义称为基本语义定义，这个定义是波兰籍数学家A.塔尔斯基在20 世纪 30年代给出的。给定了谓词解释的个体集合称为模型。基本语义定义使谓词公式和模型都可以被当作数学对象加以研究。一个谓词公式在任意一个模型中都取真值，就称之谓恒真式。两个谓词公式A，B在任意模型的任何一种解释下都取相同的值，就称A，B逻辑等价。命题演算中的恒真式和等价式所反映的规律在谓词演算中仍成立。利用有关量词的等价式作等价变换，可以把任何一个谓词公式的量词移到公式的最前面，得到与之等价的前束标准形公式。