谓 词 逻 辑原子命题是命题逻辑中最基本的组成单元，不能对它再作进一步的分解，但同时也无法反映出某些原子命题的共同特征和相互关系。

例如，用p表示命题“小李是大学生”，用q表示命题“小王是大学生”，在命题逻辑的范畴中它们是两个独立的原子命题，p和q之间没有任何关系。

但是，命题“小李是大学生”和“小王是大学生”之间有着相同的结构和内在的联系，它们都具有相同的谓语（及宾语）“是大学生”，不同的只是主语，它们都描述了“是大学生”这样一个共同的特性；而使用原子命题表示时并没有能将这一共性刻画出来。

再如著名的苏格拉底三段论：凡是人都是要死的。

苏格拉底是人。

所以苏格拉底是要死的。

这个推理显然是正确的。

但是，如用p、q、r分别表示上面3个命题，由于p∧q⇒r不是永真式，因此它不是正确的推理；也就是说，当p和q都为真时，得不出r一定为真。

其根本原因在于命题逻辑不能将命题p、q、r间的内在的联系反映出来。

为了克服命题逻辑的局限性，引入了谓词和量词对原子命题和命题间的相互关系做进一步的剖析，从而产生了谓词逻辑。

谓词逻辑亦称一阶逻辑，它同命题逻辑一样，是数理逻辑中最基础的内容。

§3.1谓词、量词与自然语句形式化§3.1.1 谓词在谓词逻辑中，一般将原子命题分解为个体词和谓词两个部分。

定义3.1个体词（individual）是一个命题里表示思维对象的词，表示独立存在的具体或抽象的客体。

简单地讲，个体词就表示各种事物，相当于汉语中的名词。

具体的、确定的个体词称为个体常项，一般用a、b、c表示；抽象的、不确定的个体词称为个体变项，一般用x、y、z表示。

个体变项的取值范围称做个体域或论域（domain of the discourse），宇宙间一切事物组成的个体域称做全总个体域（universal domain of individuals）。

注：本书在提及论域时，如未特别说明，指的都是全总个体域。

定义3.2在命题中，表示个体词性质或相互之间关系的词称做谓词（predicate）。

第3章 谓词逻辑 可以这样来理解谓词：如果命题里只有一个个体词，这时表示该个体词性质或属性的词便称为谓词。

这是一元（目）谓词，以P(x)、Q(x)、R(x)表示。

如果在命题里的个体词多于一个，那么表示这几个个体词间的关系的词称做谓词。

这是多元（目）谓词，有n个个体的谓词P(x1, x2, …, x n)称n元（目）谓词，以P(x, y)、Q(x, y)、R(x, y, z)等表示。

用谓词表示命题，必须包括个体词和谓词两个部分。

例如，在“小李是大学生”中，“小李”、“大学生”都是个体词，“是大学生”是谓词。

在“9大于4”中，“9”和“4”都是个体词，“大于”是谓词。

准确地讲，谓词P(x)、Q(x, y)是命题形式而不是命题。

因为既没有指定谓词符号P、Q的含义，而且个体词x、y也是个体变项而不代表某个具体的事物，从而无法确定P(x)、Q(x, y)的真值。

仅当赋予谓词确定的含义，并且个体词取定为个体常项时，命题形式才化为命题。

如P(x)表示“x是素数”，那么P(7)是命题，真值为T；Q(x, y)表示“x等于y”，那么Q(4, 5)是命题，取值为F。

有时将P(3)、Q(2, 3)这样不包含个体变项的谓词称做零元谓词，当赋予谓词确定含义时零元谓词为命题。

因而可将命题看成是特殊的谓词。

【例3.1】将下列命题在一阶逻辑中用零元谓词符号化，并讨论其真值。

（a）8是素数；（b）如果3大于4，则2大于6。

解：（a）设一元谓词P(x)为“x是素数”，则“8是素数”可符号化为零元谓词P(8)，真值为假。

（b）设二元谓词G(x, y)为“x大于y”，则“如果3大于4，则2大于6”符号化为零元谓词G(3, 4)⇒G(2, 6)，由于G(3, 4)为假，所以该命题为真。

§3.1.2 量词用来表示个体数量的词是量词（quantification），给谓词加上量词称做谓词的量化，可看作是对个体词所加的限制、约束的词，但不是对数量一个、二个、三个、…的具体描述，而是讨论以下两个最通用的数量限制词。

定义3.3符号“∀”称做全称量词（universal quantification），读作“所有的x”、“任意x”或“一切x”，含义相当于自然语言中的“任意的”、“所有的”、“一切的”、“每一个”、“凡”等。

(∀x)P(x)意指对论域D中的所有个体都具有性质P。

命题(∀x)P(x)当且仅当对论域中的所有x来说P(x)均为真时方为真。

定义3.4符号“∃”称做存在量词（existential quantification），读作“存在x”，含义相当于自然语言中的“某个”、“存在”、“有的”、“至少有一个”、“有些”等。

(∃x)P(x)意指对论域D中至少有一个个体具有性质P。

【例3.2】假设个体x的论域是全总个体域，“一切事物都是运动的”可以形式描述为(∀x)(x是运动的)。

若以P(x)表示x是运动的，则可写作(∀x)(P(x))，或简写成(∀x)P(x)离散数学及应用或∀xP(x)。

【例3.3】假设个体x的论域是全总个体域，“有的事物是水果”可以形式描述为(∃x)(x 是水果)。

若以Q(x)表示x是水果，那么这句话就可写成(∃x)Q(x)，或简写成(∃x)Q(x)或∃xQ(x)。

§3.1.3 自然语句形式化命题逻辑表达问题的能力仅限于联结词的使用；而谓词逻辑由于变项、谓词和量词的引入而具有强得多的表达问题的能力，已成为描述计算机所处理的知识的有力工具。

其中首要的工作就是问题本身的形式描述。

类似命题逻辑，将一个用自然语言描述的命题表示成谓词公式的形式，称为谓词逻辑中的自然语言形式化。

基本方法如下：（1）首先要将问题分解成一些原子命题和逻辑联结符；（2）之后分解出各个原子命题的个体词、谓词和量词；（3）按照合式公式的表示规则翻译出自然语句。

【例3.4】将下述语句翻译为谓词公式，使用全总个体域。

（a）所有的素数都是整数。

（b）有的素数是奇数。

（c）并非所有整数都是素数。

（d）没有奇数是偶数。

（e）所有的素数或者是奇数，或者等于2。

（f）存在一个奇数，比所有整数都大。

（g）存在唯一的偶素数。

（h）至多有一个偶素数。

（i）哥德巴赫（Goldbach）猜想：每一个大于2的偶数都可以表示为两个素数的和。

解：令谓词P(x)表示“x是整数”，Q(x)表示“x是奇数”，R(x)表示“x是偶数”，S(x)表示“x是素数”，E(x, y)表示“x=y”，G(x, y)表示“x>y”。

（a）这句话可以形式化为(∀x)(S(x)⇒P(x))。

需注意的是这句话不能形式化为(∀x)(S(x)∧P(x))，这个公式的意思是说，对宇宙间所有的事物x而言，x既是素数又是整数。

一般地讲，“所有的A是B”、“是A的都是B”、“一切A都是B的”这类语句的形式描述只能使用⇒而不能使用∧。

（b）这句话的形式描述应为(∃x)(S(x)∧Q(x))。

需注意的是不能使用(∃x)(S(x)⇒Q(x))，一般地讲，“有的A是B”这类语句的形式描述只能使用∧而不能使用⇒。

（c）这句话可以形式化为~(∀x)(P(x)⇒S(x))；也可以把这句话理解为“有的整数不是素数”，这时应形式化为(∃x)(P(x)∧~S(x))。

它们都是正确的，其理由将在3.3节中阐述。

（d）这句话可以形式化为~(∃x)(Q(x)∧R(x))；也可以把这句话理解为“所有的奇数都不是偶数”或者“所有的偶数都不是奇数”，这时应形式化为(∀x)(Q(x)⇒~R(x))或者第3章 谓词逻辑 (∀x)(R(x)⇒~Q(x))。

它们都是正确的。

（e）这句话可以形式化为(∀x)(S(x)⇒(E(x, 2)∨Q(x)))。

（f）这句话的含义是：“存在一个个体x，它是奇数；而且，如果对于任意个体y，如果它是整数，那么一定有y<x。

”因此可以形式化为(∃x)(Q(x)∧(∀y)(P(y)⇒G(x, y)))。

（g）这句话的含义是：“存在一个个体x，它既是偶数又是素数；而且，如果还有个体y也是既是偶数又是素数，那么一定有x=y。

”因此可以形式化为(∃x)(S(x)∧R(x)∧(∀y)(S(y)∧R(y)⇒E(x, y)))。

（h）这句话和（g）的区别在于允许不存在偶素数，因此在形式化后也是不同的，应该表示为(∀x)(S(x)∧R(x)⇒(∀y)(S(y)∧R(y)⇒E(x, y)))。

这句话也可以理解为“不存在不相等的两个个体，它们都既是偶数又是素数”，可形式化为~(∃x)(∃y)(S(x)∧R(x)∧S(y)∧R(y)∧~E(x, y))。

（i）这句话可以形式化为(∀x)(R(x)∧G(x, 2)⇒(∃y)(∃z)(S(y)∧S(z)∧E(x, y+z)))。

【例3.5】假设论域是整数集，将下述语句翻译为谓词公式。

（a）至少存在一个偶数，且至少存在一个奇数。

（b）至少有一个整数既是偶数又是奇数。

（c）对于任一个整数而言，它或者是偶数，或者是奇数。

（d）所有整数都是偶数或者所有整数都是奇数。

（e）对于任一个整数而言，都存在比它小的整数。

（f）存在一个整数，满足任何整数都大于它。

解：令谓词P(x)表示“x是奇数”，Q(x)表示“x是偶数”，E(x, y)表示“x=y”，G(x, y)表示“x>y”。

将以下各式译为汉语，并判断其真值。

（a）这句话可以形式化为(∃x)P(x)∧(∃x)Q(x)，是真命题。

（b）这句话可以形式化为(∃x)(P(x)∧Q(x))，是假命题。

（c）这句话可以形式化为(∀x)(P(x)∨Q(x))，是真命题。

（d）这句话可以形式化为(∀x)P(x)∨(∀x)Q(x)，是假命题。

（e）这句话可以形式化为(∀x)(∃y)G(x, y)，是真命题。

（f）这句话可以形式化为(∃y)(∀x)G(x, y)，是假命题。

上述例子说明(∃x)P(x)∧(∃x)Q(x)和(∃x)(P(x)∧Q(x))、(∀x)(P(x)∨Q(x))和(∀x)P(x)∨(∀x)Q(x)、(∀x)(∃y)G(x, y)与(∃y)(∀x)G(x, y)含义不同。

这些都是容易混淆的，须注意加以区别。

【例3.6】假设论域是全总个体域，将下述语句翻译为谓词公式。

（a）没有人可以永生不死。

（b）天下乌鸦一般黑。

（c）金子一定闪光，但闪光的不一定是金子。

（d）所有的大学生都会说英语，有一些大学生会说法语。

解：∧Q(x))。

（a）设P(x)表示“x是人”，Q(x)表示“x会死”。

原语句可表示成~(∃x)(P(x)~（b）设F(x)表示“x是乌鸦”，G(x,y)表示“x与y一般黑”。

原语句可表示成离散数学及应用∧G(x,y))，即不存在个体x, y (∀x)(∀y)(F(x)∧F(y)⇒G(x,y))；或者~(∃x)(∃y)(F(x)∧F(y)~都是乌鸦但不一般黑。