第九章 谓词逻辑基础

第九章

谓词逻辑基础

上一章我们研究了命题逻辑，运用建立起的符号体 系确实能表示命题及其间的逻辑关系，并能进行演 算和推理。命题逻辑以原子命题为最小研究单位， 现在我们来考察这样两个命题： “张天是大学生” “王夜是大学生”。 它们是两个原子命题，因此只能用两个不同字母如 P,Q来表示它们。可是很显然这两个自然语言的谓 语即谈论的问题是一样的，但这一点在命题逻辑符 号化时不能体现。 另外就是著名的苏格拉底推理： 所有的人都是要死的，苏格拉底是人，所以苏格拉 底是要死的。

这是一个很明显成立的推理，但用命题逻辑来解释 时是行不通的。因为我们在形式化时只能将三个语 句用三个字母如A,B,C来表示，这样推理就成为 A∧B C,而A∧B C不是永真式。我们来分析一 下这其中的原因，实际上A,B,C在内部结构上是 有联系的，即C的主语和谓语分别是B的主语和A的 谓语。 要解决以上两个问题都需要将原子命题结构细分， 一般主要划分为主语和谓语，这就是本章要讲的谓 词逻辑。当然谓词逻辑还有一点更重要的区别与命 题逻辑的，那就是要讨论量词。

§9.1谓词逻辑的基本概念9.1.1 个体 谓词与谓词表达式

一个原子命题主要是由主语和谓语组成。主

语就是论述的对象称为个体(individuals), 个体可以是具体的，也可以是抽象的，常用a, b,c等小写字母表示，它可以是一个也可以 是多个。当个体是一个对象时，谓语表示它 的性质，当个体是多个对象时，谓语表示它 们之间的关系，谓语称为谓词(predicate)。 谓词常用P,Q,R,A,B等大写字母来表示， 也常常用英文单词来表示，如GREAT:大于； BETWEEN:位于…之间，尤其在程序设计 和人工智能中。

当一个个体a具有性质P时，就表示为P(a)。

这时称P为一元谓词。如本节开始提到的两个 原子命题，设P:是大学生，a: 张天, b: 王夜， 则两个命题可分别表示为：P(a),P(b), 这说明两个不同的个体具有同一个性质。 又如：2大于3,设R:大于，则命题可表示 为R(2,3),说明2,3具有关系R。这时称 R为二元谓词。

再看命题：武汉位于北京和广州之间。设W:…位 于…和…之间，w: 武汉,b: 北京,g: 广州, 则命题可 表示为W(w,b,g). 这时称W为三元谓词。 值得注意的是，当谓词涉及多个个体时，千万不 能随意交换个体顺序。因为如上述R(3,2)表示3 大于2,显然R(2,3)为假，而R(3,2)为真。 又如上述W(b, w ,g):表示北京位于武汉和广州 之间，显然W(b, w ,g)为假，而W(w,b,g)为真。 把语句写成如

上形式P(a),R(2,3),W (w,b,g)等就称为是谓词表达式。

例9.1 将下列语句写成谓词表达式形式： (1)苏格拉底是要死的。 (2)- 5的平方非负。 (3)董旎生于青岛。 (4)3+ 5 = 8 解：(1)设D表示“…是要死的”,s: 苏格拉底，语 句写成谓词表达式为：D(s)或D(socrates)。 (2)设NN表示“…是非负的”,语句写成谓词 表达式为：NN((-5)2)。 (3)设B表示“…生于…”,a:董旎，b:青岛， 语句写成谓词表达式为：B(a,b)或B(Dongni, qingdao)。 (4)设ADD表示“…+…=…”,语句写成谓词表 达式为：ADD(3,5,8)。

如上述的socrates,-5,a,b,3,5等代表一个确 切的个体，我们称为个体常元(constants)。下面 进一步考察上例中的D(s),容易知道其真值为真， 但若s代表某块石头的话，则D(s)真值为假；同 样如果考察ADD谓词，ADD(3,5,8)为真，而 ADD(5,5,8)为假，ADD(5,7,12)又为真。 可见对同一个谓词一般要依所谈个体对象不同会得 到不同的真值，即假设x,y,z代表任意个体----称 为个体变元(variables),则D(x),ADD(x,y, z)往往要随个体变元的取值不同而真值也不同，当 然这时象D(x),ADD(x,y,z)等不再是命题， 我们称它们为命题函数。

9.1.2 命题函数与个体域

定义9.1

由一个特定谓词P和n个个体变元 x1,x2, …, xn组成的形如P(x1,x2, …, xn) 的表达式称为简单命题函数(propositional function)。简单命题函数可用所有的命题联 接词联接组成复合命题函数。

如： A(x):x 学习好 B(x): x 工作好 则A(x)∧ B(x):表示x 学习好并且工作好。 A(x)→ B(x):表示若x 学习好则x工作好。 对于一个个体变元其变化的范围即—个体的全体称 为个体域(domain of individuals),当讨论对象遍 及一切客体时，个体域特称为全总域(universe)。 那么一些复杂的性质和关系，可以用谓词和联结 词复合的形式来描述。

“x是小于100的质数”可表示为 L(x,100)∧P(x)(其中L(x,100):x小于 100, P(x):x是质数) “y小于等于3”可表示为 L(y,3)∨E(y,3) (其中E(y,3):y等于3),或 y≤ 3 “如果一个人生于北京，那么他不生于上海” 可表示为 B(x,beijing)→┐B(x,shanghai) ( B(x,beijing):x生于beijing) “y是非负实数当且仅当y大于等于零” 可表 示为 NN(y) 0 ≤ y(NN(y):y是非负的) 例9.2

9.1.3 量词与辖域

我们曾经谈过，谓词逻辑区别于命题逻辑还有一点 更重要的是要讨论量词(quantifiers),即指 “所 有”“一切”“任一个”和“有”“某些”“存 在”,分别用符号

和 来表示，并分别称为全称 量词和存在量词。那么 xP(x)表示个体域中所有的 个体都满足谓词P; x P(x) 表示个体域中有个体满 足谓词P; x (M(x)∧B(x)) 表示个体域中有个体既 满足谓词M,又满足谓词B。如，M(x):x是人， B(x):x是勇敢的， x (M(x)∧B(x)) 表示“有的个体 是人且是勇敢的”,或说“有人勇敢”;若D(x):x 是要死的，则 x(M(x)→D(x)) 表示 “所有人都是要 死的”; 设L(x,2):x小于2,则 x(L(x,2)∨┐L(x,2)) 表示“所有的个体或者小于2 或者不小于2”。

由上，每个量词会有一个量化范围，即对哪个谓词中的个体 变元是全称的，哪个又是存在的，这就是所谓的量词的辖域 (domains of quantifiers)。如 xP(x),量词 x的辖域是 P(x), x (M(x)∧B(x))中量词 x的辖域是M(x)∧B(x) ,而 xM(x)→D(x)中量词 x的辖域是M(x)。量词中的变元以及 量词辖域中的相应变元称为约束变元(bound variables), 不是约束变元的则称为自由变元(free variables)。如 x (M(x)∧B(x))中的x都是约束的，而对于 xM(x)→D(x),由于 x的辖域只是M(x),因此 xM(x)中的x是约束的，D(x) 中的 x是自由的，这样一个变元x在一个公式中既是约束的又是自 由的。为了避免这种混淆，我们可以对约束变元和自由变元 作更改。自然地如 xM(x)→D(x)对约束变元x作更改为 yM(y)→D(x),而对自由变元x作更改为 xM(x)→D(t)。

例9.3 确定下列量词的辖域，约束变元与自由变元，并对约 束变元或自由变元作适当的更改。 (1) xP(x)→P(y) (2) x(P(x)→ y R(x,y))∨Q(x,z) (3) x(P(x) ∧ x B(x)) 解： (1) x的辖域是P(x), x是约束变元，y是自由变元，变元不 需作更改。 (2) x的辖域是P(x)→ y R(x,y), y的辖域是R(x,y),x既是 约束变元也是自由变元，y是约束变元，z是自由变元。若对 约束变元x作更改为 u(P(u)→ y R(u,y))∨Q(x,z)(注意不 能更改为y 和 z),若对自由变元x作更改为 x(P(x)→ y R(x,y))∨Q(t,z) (也不能更改为y 和 z)。 (3) x的辖域是P(x) ∧ x B(x), x的辖域是B(x),x是约束变 元，若对约束变元x作更改分别为 z(P(z) ∧ x B(x)), x (P(x) ∧ z B(z))。

A.

最后再提两点： 全部被量化(即每个谓词都带有量词，不再有自由 变元)的命题函数，在给定的个体域中有确定的真 值，因而是命题。如 xP(x), x (M(x)∧B(x)), x(P(x) ∧ z B(z)), x(P(x)→ y R(x,y))。 对于被量化的命题函数，在有限的个体域中可将量 词消去，用枚举的方法有如下等价式： 设个体域D= D = a1, …,an , xP(x) P(a1)∧…∧P(an), xP(x) P(a1)∨…∨P(an), 其中“ ”的含义同上一章

,在本章下一节还会 讲到。

B.

9. 1. 4 谓词公式及语句的形式化

与命题公式相同，在谓词逻辑中一个合法的符号串 即为一个谓词公式。 定义9.2 归纳定义谓词公式(predicate forrmula), 谓词公式又称合式公式，简称公式。 (1)谓词填式是公式，命题常元是公式(看作零 元谓词),常称原子公式。 (2)如果A,B是公式，x为任一变元，那么(┐A), (A→B),( xA),( x A)(当使用五个联结词时还有 (A∧B),(A∨B),(A B))都是公式。 (3)只有有限步使用(1),(2)条款所形成的 符号串是公式。 我们已经把谓词、个体、个体变元和量词都符号化 了，那么现在可以用谓词公式将语句谓词形式了。

例9.4 设个体域是人类，试将下列语句译为谓词公 式。 (1)有人勇敢，但不是所有的人都勇敢。 用B(x)表示“x勇敢”,它译为 xB(x) ∧┐ x B(x) (2)我为人人，人人为我。 用i表示“我”,S(x,y)表示“x为y服务”,它可译 为 xS(i,x) ∧ xS(x,i) (3)勇敢者未必都是成功者。 用B(x)表示“x是勇敢者”,W(x)表示“x是成功者”, 它可译为 ┐ x(B(x)→W(x)) 或 x(B(x)∧┐W(x))(下一节 我们会知道它们是等价的)

本文来源：https://www.bwwdw.com/article/lw04.html