本节对应原书 PDF 第 81–90 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
3.1.1 命题逻辑的局限性
命题逻辑把命题当作不可再分的最小单位，既不剖析简单命题的内部结构，也不考察命题之间的内在联系与数量关系，因此它有明显的局限，连一些很简单、很常见的推理都判断不了。看下面这个推理：
凡偶数都能被 2 整除.
6 是偶数.
所以,6 能被 2 整除.
这是数学中显然正确的推理，但在命题逻辑里却证不出它的正确性。原因在于命题逻辑只能把这 3 句话当成 3 个简单命题，依次符号化为 p,q,r，推理的形式结构就写成
它又不是重言式，于是命题逻辑判定这个推理是错的。要突破这个局限，就得引入个体词、谓词和量词，把个体与总体的内在联系和数量关系表达出来，这就是一阶逻辑所研究的内容。一阶逻辑也称一阶谓词逻辑或谓词逻辑。
解读：说 (p\wedge q)\rightarrow r 不是重言式，等于说 p,q 都为真时 r 未必为真——命题逻辑"看不见" p 与 r 内部共享的那个概念"偶数"，所以搭不起两句话之间的桥。
3.1.2 个体词、谓词与量词
在一阶逻辑中，要求把简单陈述句（可能是命题，也可能不是命题）细分成主语与谓语，用 P(x) 表示 x 具有性质 P，讨论 P(x) 在什么情况下为真、在什么情况下为假，并且讨论在 x 的指定取值范围内是否对所有的 x 均为真、或存在 x 使其为真等。这些讨论中有 3 个要素必不可少，就是个体词、谓词与量词。
1. 个体词
个体词是指所研究对象中可以独立存在的具体的或抽象的客体。例如,小王,小李,中国,\sqrt{2},3 等都可作为个体词。将表示具体或特定的客体的个体词称作个体常项,一般用小写英文字母 a,b,c,\cdots 表示,而将表示抽象或泛指的个体词称为个体变项,常用 x,y,z,\cdots 表示。并称个体变项的取值范围为个体域(或称论域)。个体域可以是有穷集合,例如,\{1,2,3\},\{a,b,c,d\},\{a,b,c,\cdots,x,y,z\},\cdots,也可以是无穷集合。例如,自然数集合 \mathbf{N}=\{0,1,2,\cdots\},实数集合 \mathbf{R}=\{x\,|\,x 是实数\},\cdots。有一个特殊的个体域,它是由宇宙间一切事物组成的,称为全总个体域。本书在论述或推理中如无指明所采用的个体域,都是使用的全总个体域。
例如,在"5 是素数","x>y"中,5,素数,x,y 都是个体词,其中,5,素数是个体常项,x,y 均为个体变项。
2. 谓词
谓词是用来刻画个体词性质及个体词之间相互关系的词。考虑下面 4 个命题(或命题变项):
(1) \sqrt{2} 是无理数.
(2) x 是有理数.
(3) 小王与小李同岁.
(4) x 与 y 具有关系 L.
在(1)中,\sqrt{2} 是个体常项,"\cdots\cdots 是无理数"是谓词,记为 F,并用 F(\sqrt{2}) 表示(1)中命题。在(2)中,x 是个体变项,"\cdots\cdots 是有理数"是谓词,记为 G,用 G(x) 表示(2)中命题。在(3)中,小王,小李都是个体常项,"\cdots\cdots 与 \cdots\cdots 同岁"是谓词,记为 H,则(3)中命题符号化形式为 H(a,b),其中,a:小王,b:小李。在(4)中,x,y 为两个个体变项,"\cdots\cdots 与 \cdots\cdots 有关系 L"是谓词,符号化为 L(x,y)。
同个体词一样,谓词也有常项与变项之分。表示具体性质或关系的谓词称为谓词常项,表示抽象的或泛指的性质或关系的谓词称为谓词变项。无论是谓词常项或变项都用大写英文字母 F,G,H,\cdots 表示,要根据上下文区分。在上面 4 个命题中,(1),(2),(3)中谓词 F,G,H 是常项,而(4)中谓词 L 是变项。一般地,用 F(a) 表示个体常项 a 具有性质 F(F 是谓词常项或谓词变项),用 F(x) 表示个体变项 x 具有性质 F。而用 F(a,b) 表示个体常项 a,b 具有关系 F,用 F(x,y) 表示个体变项 x,y 具有关系 F。更一般地,用 P(x_1,x_2,\cdots,x_n) 表示含 n(n\geqslant 1) 个命题变项 x_1,x_2,\cdots,x_n 的 n 元谓词,n=1 时,P(x_1) 表示 x_1 具有性质 P,n\geqslant 2 时,P(x_1,x_2,\cdots,x_n) 表示 x_1,x_2,\cdots,x_n 具有关系 P。实质上,n 元谓词 P(x_1,x_2,\cdots,x_n) 可以看成以个体域为定义域,以 \{0,1\} 为值域的 n 元函数或关系。它不是命题。要想使它成为命题,必须用谓词常项取代 F,用个体常项 a_1,a_2,\cdots,a_n 取代 x_1,x_2,\cdots,x_n,得 F(a_1,a_2,\cdots,a_n) 是命题,或加量词(见下文)。
有时将不带个体变项的谓词称为 0 元谓词,例如,F(a),G(a,b),P(a_1,a_2,\cdots,a_n) 等都是 0 元谓词,当 F,G,P 为谓词常项时,0 元谓词为命题。这样一来,命题逻辑中的命题均可表示成 0 元谓词,因而可将命题看成特殊的谓词。
解读：n 元谓词本身不是命题，因为它带着自由变项，真值还没定；把变项全部换成常项（0 元谓词）或加量词约束住，才得到一个有真值的命题。
例 3.1 将下列命题在一阶逻辑中用 0 元谓词符号化,并讨论它们的真值.
(1) 只有 2 是素数,4 才是素数.
(2) 如果 5 大于 4,则 4 大于 6.
解 (1) 设 1 元谓词 F(x):x 是素数. a:2, b:4. (1)中命题符号化为 0 元谓词的蕴涵式
由于此蕴涵前件为假,所以(1)中命题为真.
(2) 设 2 元谓词 G(x,y):x 大于 y. a:4, b:5, c:6. G(b,a),G(a,c) 是两个 0 元谓词,把(2)中命题符号化为
由于 G(b,a) 为真,而 G(a,c) 为假,所以(2)中命题为假.
3. 量词
有了个体词和谓词的概念之后，对有些命题来说还是不能准确地符号化，原因是还缺少表示个体常项或变项之间数量关系的词。表示个体常项或变项之间数量关系的词称为量词。量词有两个。
(1) 全称量词 日常生活和数学中常用的"一切的"、"所有的"、"每一个"、"任意的"、"凡"、"都"等词可统称为全称量词,将它们符号化为"\forall"。并用 \forall x,\forall y 等表示个体域里的所有个体,而用 \forall xF(x),\forall yG(y) 等分别表示个体域里所有个体都有性质 F 和都有性质 G。
(2) 存在量词 日常生活和数学中常用的"存在"、"有一个"、"有的"、"至少有一个"等词统称为存在量词,将它们都符号化为"\exists"。并用 \exists x,\exists y 等表示个体域里有的个体,而用 \exists xF(x),\exists yG(y) 等分别表示在个体域里存在个体具有性质 F 和存在个体具有性质 G 等。
解读：量词的作用就是把谓词里的自由变项"绑住"。F(x) 的真值随 x 变，而 \forall xF(x) 与 \exists xF(x) 已经是命题，真值不再随 x 变。
3.1.3 一阶逻辑命题符号化
例 3.2 在个体域分别限制为(a)和(b)条件时,将下面两个命题符号化.
(1) 凡是人都呼吸.
(2) 有的人用左手写字.
其中,
(a) 个体域 D_1 为人类集合;
(b) 个体域 D_2 为全总个体域.
解 (a) 令 F(x):x 呼吸. G(x):x 用左手写字.
(1) 在 D_1 中除人外,再别无的东西,因而"凡是人都呼吸"应符号化为
(2) 在 D_1 中的有些个体(人)用左手写字,因而"有的人用左手写字"符号化为
(b) D_2 中除有人外,还有万物,因而在(1)和(2)符号化时,必须考虑将人先分离出来. 令 M(x):x 是人. 在 D_2 中,(1)和(2)可分别重述如下:
(1) 对于宇宙间一切事物而言,如果事物是人,则他要呼吸.
(2) 在宇宙间存在着用左手写字的人.
于是(1)和(2)的符号化形式应分别为
和
其中,F(x) 与 G(x) 的含义同(a)中.
由例 3.2 可知，命题(1)和(2)在不同的个体域 D_1 和 D_2 中符号化的形式不一样，主要区别在于：使用个体域 D_2 时，要把人与其他事物区别开来，为此引进了谓词 M(x)，像这样的谓词称为特性谓词。在命题符号化时一定要正确使用特性谓词。
在个体域 D_1 与 D_2 中，命题(1)与(2)都是真命题（这里讨论的人是活着的人）。在 D_1 中，式(3.1)与式(3.2)正确地给出了(1)与(2)的符号化形式。在 D_2 中，式(3.3)与式(3.4)的正确性可以这样说明：式(3.3)中，对任意的 x\in D_2，若 x 代表某个人 a，则 M(a) 与 F(a) 均为真，蕴涵式 M(a)\rightarrow F(a) 为真；而当 x 代表人以外的物，如果棵树 b，则 M(b) 为假，M(b)\rightarrow F(b) 也为真。所以式(3.3)中的蕴涵式不会出现前件真后件假的情况，它正确给出了(1)的符号化形式。有些初学者在 D_2 中常将(1)符号化为下面形式:
式(3.5)不是(1)的符号化形式。将它翻译成自然语言，应该是"宇宙间的任何事物都是人并且都呼吸"，这显然不是(1)的意思；任何非人的个体 c 代入后 M(c) 为假，所以式(3.5)为假。因而命题(1)不能符号化为式(3.5)的形式。对于式(3.4)，由于存在用左手写字的人，比如前任美国总统克林顿就用左手写字，当用 a 代表克林顿时，M(a)\wedge G(a) 为真，所以式(3.4)为真。有些人将(2)符号化为下面形式:
式(3.6)已不是(2)的符号化形式。将它翻译成自然语言应该为"在宇宙间存在个体，如果此个体为人，则他用左手写字"，这显然改变了原命题的含义，因而式(3.6)不能代替式(3.4)。
解读：特性谓词 M(x) 与全称量词搭配时用 \rightarrow、与存在量词搭配时用 \wedge，这个搭配不能颠倒；颠倒后含义就从"所有人…"变成"所有事物都是人且…"或"存在一个若为人则…的个体"。
例 3.3 在个体域限制为(a)和(b)条件时,将下列命题符号化.
(1) 对于任意的 x,均有 x^2-3x+2=(x-1)(x-2).
(2) 存在 x,使得 x+5=3.
其中,
(a) 个体域 D_1=\mathbf{N}(\mathbf{N} 为自然数集).
(b) 个体域 D_2=\mathbf{R}(\mathbf{R} 为实数集).
解 (a) 令 F(x):x^2-3x+2=(x-1)(x-2),G(x):x+5=3. 命题(1)的符号化形式为
命题(2)的符号化形式为
显然(1)为真命题,而(2)为假命题.
(b) 在 D_2 内,(1)与(2)的符号化形式还是式(3.7)和式(3.8),(1)仍然是真命题,而此时(2)也为真命题.
从例 3.2 和例 3.3 可以看出以下两点:
(1) 在不同个体域内,同一个命题的符号化形式可能不同,也可能相同.
(2) 同一个命题,在不同个体域中的真值也可能不同.
另外,作为一种规定,在本书中,讨论命题符号化时,若没有指明个体域,就采用全总个体域,见下例.
例 3.4 将下列命题符号化,并讨论真值.
(1) 所有的人都是长着黑头发.
(2) 有的人登上过月球.
(3) 没有人登上过木星.
(4) 在美国留学的学生未必都是亚洲人.
解 由于本题没提出个体域,因而应采用全总个体域,并令 M(x):x 为人.
(1) 令 F(x):x 长着黑头发. 命题(1)符号化为
设 a 为某金发姑娘,则 M(a) 为真,而 F(a) 为假,所以 M(a)\rightarrow F(a) 为假,故式(3.9)所表示的命题为假.
(2) 令 G(x):x 登上过月球. 命题(2)的符号化形式为
设 a 是 1969 年登上月球完成阿波罗计划的阿姆斯特朗,则 M(a)\wedge G(a) 为真,所以式(3.10)表示的命题为真.
(3) 令 H(x):x 登上过木星. 命题(3)符号化形式为
到目前为止,对于任何一个人(含已经去世的人)都还没有登上过木星,所以对任何人 a,M(a)\wedge H(a) 均假,因而 \exists x(M(x)\wedge H(x)) 为假,故式(3.11)表示的命题为真.
(4) 令 F(x):x 是在美国留学的学生, G(x):x 是亚洲人. 命题(4)符号化形式为
容易讨论,(4)中命题为真.
例 3.5 将下列命题符号化.
(1) 兔子比乌龟跑得快.
(2) 有的兔子比所有的乌龟跑得快.
(3) 并不是所有的兔子都比乌龟跑得快.
(4) 不存在跑得同样快的两只兔子.
解 因为本题没有指明个体域,因而采用全总个体域. 因为本例中出现 2 元谓词,因而引入两个个体变项 x 与 y. 令 F(x):x 是兔子, G(y):y 是乌龟, N(x,y):x\neq y, H(x,y):x 比 y 跑得快, L(x,y):x 与 y 跑得同样快. 这 4 个命题分别符号化为
对于存在 n 元谓词的命题,在符号化时应该注意以下几点:
(1) 分析命题中表示性质和关系的谓词,分别符号化为 1 元和 n(n\geqslant 2) 元谓词.
(2) 根据命题的实际意义选用全称量词或存在量词.
(3) 一般说来,多个量词出现时,它们的顺序不能随意调换. 例如,考虑个体域为实数集,H(x,y) 表示 x+y=10,则命题"对于任意的 x,都存在 y,使得 x+y=10"的符号化形式为
所给命题显然为真命题. 但如果改变两个量词的顺序,得
它的含义是"存在 y,使得所有的 x,有 x+y=10",这显然是假命题.
(4) 有些命题的符号化形式可不仅一种. 例如,在例 3.5 中,(3)还可以说成"有的兔子不比有的乌龟跑得快",从而又可以符号化为
(4)还可以说成"任何两只兔子都跑得不一样快",因而又可以符号化为
这样,式(3.15)和式(3.19)都是(3)的符号化形式,式(3.16)与式(3.20)都是(4)的符号化形式,它们都是正确的(3.2.1 小节可以证明式(3.15)和式(3.19)是等值的,式(3.16)和式(3.20)是等值的).
由于引进个体词、谓词和量词的概念,现在可以将本章开始时讨论的推理在一阶逻辑中符号化为如下形式:
其中,F(x):x 是偶数, G(x):x 能被 2 整除, a:6. 由于 \forall x(F(x)\rightarrow G(x)) 为真,F(a)\rightarrow G(a) 为真. 又由于 F(a)\rightarrow G(a) 和 F(a) 为真,根据假言推理,得到 G(a) 为真. 这就解决了本章开头提出的推理问题.
解读：量词顺序不可随意调换，\forall x\exists y 与 \exists y\forall x 含义不同；同一命题也可以有多个等值的符号化形式，只要含义不变都算正确。
3.1.4 一阶逻辑公式与分类
同在命题逻辑中一样，要在一阶逻辑中进行演算和推理，还必须给出一阶逻辑中公式的抽象定义，以及它们的解释和分类。为此先给出一阶语言的概念：一阶语言是用于一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系。一阶语言本身不具备任何含义，但可以根据需要被解释成具有某种含义。一阶语言的形式是多种多样的，本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记它为 \mathscr{L}。
定义 3.1 一阶语言 \mathscr{L} 的字母表定义如下:
(1) 个体常项: a,b,c,\cdots,a_i,b_i,c_i,\cdots,i\geqslant 1.
(2) 个体变项: x,y,z,\cdots,x_i,y_i,z_i,\cdots,i\geqslant 1.
(3) 函数符号: f,g,h,\cdots,f_i,g_i,h_i,\cdots,i\geqslant 1.
(4) 谓词符号: F,G,H,\cdots,F_i,G_i,H_i,\cdots,i\geqslant 1.
(5) 量词符号: \forall,\exists.
(6) 联结词符号: \neg,\wedge,\vee,\rightarrow,\leftrightarrow.
(7) 括号与逗号: (,),,.
3.1.3 小节式(3.1)\sim式(3.21)所用符号均为 \mathscr{L} 字母表中的符号.
为方便起见,再给出 \mathscr{L} 的项的概念.
定义 3.2 \mathscr{L} 的项的定义如下:
(1) 个体常项和个体变项是项.
(2) 若 \varphi(x_1,x_2,\cdots,x_n) 是任意的 n 元函数, t_1,t_2,\cdots,t_n 是任意的 n 个项,则 \varphi(t_1,t_2,\cdots,t_n) 是项.
(3) 所有的项都是有限次使用(1),(2)得到的.
定义 3.3 设 R(x_1,x_2,\cdots,x_n) 是 \mathscr{L} 的任意 n 元谓词, t_1,t_2,\cdots,t_n 是 \mathscr{L} 的任意的 n 个项,则称 R(t_1,t_2,\cdots,t_n) 是 \mathscr{L} 的原子公式.
例 3.5 中的 1 元谓词 F(x),G(y),2 元谓词 H(x,y),L(x,y) 等都是原子公式.
定义 3.4 \mathscr{L} 的合式公式定义如下:
(1) 原子公式是合式公式.
(2) 若 A 是合式公式,则 (\neg A) 也是合式公式.
(3) 若 A,B 是合式公式,则 (A\wedge B),(A\vee B),(A\rightarrow B),(A\leftrightarrow B) 也是合式公式.
(4) 若 A 是合式公式,则 \forall xA,\exists xA 也是合式公式.
(5) 只有有限次地应用(1)\sim(4)构成的符号串才是合式公式.
合式公式也称为谓词公式,简称公式.
在定义 3.4 中出现的字母 A,B 是代表任意公式的元语言符号. 为方便起见,公式 (\neg A),(A\wedge B),\cdots 的最外层括号可以省去,使其变成 \neg A,A\wedge B,\cdots. 式(3.1)\sim式(3.21)都是 \mathscr{L} 中的公式.
因为本书只引进一种一阶语言 \mathscr{L},下文的讨论中都是在 \mathscr{L} 中,因而一般不再提及 \mathscr{L}. 另外,下文中出现的 A,B 等符号均指任意的合式公式,简称为公式. 例如,A 可以是 F(x),G(x) 等原子公式,也可以不是原子公式,如 F(x)\rightarrow \forall yG(y),\forall x(F(x,y)\wedge G(x,z)) 等按合式公式形成规则形成的各种公式.
定义 3.5 在公式 \forall xA 和 \exists xA 中,称 x 为指导变元,A 为相应量词的辖域. 在 \forall x 和 \exists x 的辖域中,x 的所有出现都称为约束出现,A 中不是约束出现的其他变项均称为是自由出现的.
例 3.6 指出下列各公式中的指导变元,各量词的辖域,自由出现以及约束出现的个体变项.
(1) \forall x(F(x,y)\rightarrow G(x,z)) (3.22)
(2) \forall x(F(x)\rightarrow G(y))\rightarrow \exists y(H(x)\wedge L(x,y,z)) (3.23)
解 (1) x 是指导变元. 量词 \forall 的辖域 A=(F(x,y)\rightarrow G(x,z)),在 A 中,x 是约束出现的,而且约束出现两次,y 和 z 均为自由出现的,而且各自自由出现一次.
(2) 公式中含两个量词,前件中的量词的指导变元为 x,\forall x 的辖域 A=(F(x)\rightarrow G(y)),其中 x 是约束出现的,y 是自由出现的. 后件中的量词的指导变元为 y,\exists y 的辖域为 (H(x)\wedge L(x,y,z)),其中 y 是约束出现的,x,z 均为自由出现的. 在整个公式中,x 约束出现一次,自由出现两次,y 自由出现一次,约束出现一次,z 只自由出现一次. 注意,在这里前件中的 x 和后件中的 x 是两个不同的变元,如同两个人取同一个名字一样. 同样地,前件中的 y 和后件中的 y 也是两个不同的变元. 也就是说,在不同的辖域内出现的同一个字母代表不同的变元.
本书用 A(x_1,x_2,\cdots,x_n) 表示含 x_1,x_2,\cdots,x_n 为自由出现的公式. 用 \Delta 表示量词(\forall 或 \exists). 在 \Delta x_iA(x_1,x_2,\cdots,x_{i-1},x_i,x_{i+1},\cdots,x_n) 中,x_i 是约束出现的,其余的个体变项都是自由出现的. 而在 \Delta x_1\Delta x_2\cdots\Delta x_nA(x_1,x_2,\cdots,x_n) 中,无自由出现的个体变项.
可将例 3.6(1)中公式简记为 A(y,z),这表明(1)中公式含自由出现的个体变项 y,z. 而 \forall yA(y,z) 中只含 z 为自由出现的公式,\exists z\forall yA(y,z) 中已无自由出现的个体变项了,此时的公式为
定义 3.6 设 A 是任意的公式,若 A 中不含自由出现的个体变项,则称 A 为封闭的公式,简称闭式.
易知式(3.1)\sim式(3.21)以及式(3.24)都是闭式,而式(3.22)和式(3.23)则不是闭式. 要想使含 r(r\geqslant 1) 个自由出现个体变项的公式变成闭式至少要加上 r 个量词,将式(3.22)加了两个量词就变成了闭式(3.24)了. 类似地,也可以用加量词的方法将式(3.23)变成闭式.
按定义 3.4 定义的合式公式，一般说来没有确定的涵义；一旦将其中的变项（个体变项、项的变项、谓词变项等）用指定的常项代替，所得公式可能具备一定的涵义，有时可以变成命题了。
例 3.7 将下面公式
中的变项指定成常项,使其成为命题.
解 指定个体变项的变化范围,并指定谓词 F,G 的涵义,下面给出两种指定法.
(a) 令个体域 D_1 为全总个体域,F(x) 为 x 是人,G(x) 为 x 是黄种人,则式(3.25)表达的命题为"所有的人都是黄种人",这是假命题.
(b) 令个体域 D_2 为实数集合 \mathbf{R},F(x) 为 x 是自然数,G(x) 为 x 是整数,则式(3.25)表达的命题为"自然数都是整数",这是真命题.
还可以给出其他各种不同指定,使式(3.25)表达各种不同形式的命题.
上面指定公式中的个体域以及个体变项、谓词变项等的具体涵义称作对它的解释。一般地，给定一阶语言的解释，在这个解释下解释公式。定义 3.1 给出了一般性的一阶语言的定义，定义中的个体常项、函数符号和谓词符号称作非逻辑符号，其余的符号称作逻辑符号。就一个具体的应用而言，一阶语言 \mathscr{L} 只涉及某些非逻辑符号，记它所使用的非逻辑符号集为 L，称 \mathscr{L} 是非逻辑符号集 L 生成的一阶语言。不同的非逻辑符号集生成各种不同的具体的一阶语言，但它们使用相同的逻辑符号和相同的生成规则。解释是对这种具体的一阶语言而言的，定义如下。
定义 3.7 设 L 是非逻辑符号集,\mathscr{L} 是由 L 生成的一阶语言,\mathscr{L} 的解释 I 由下面 4 部分组成:
(a) 非空的个体域 D.
(b) 对每一个个体常项 a\in L,有一个 \bar{a}\in D,\bar{a} 称作 a 的解释.
(c) 对每一个 n 元函数符号 f,有一个 D 上的 n 元函数 \bar{f},\bar{f} 称作 f 的解释.
(d) 对每一个 n 元谓词符号 F,有一个 D 上的 n 元谓词 \bar{F},\bar{F} 称作 F 的解释.
设 A 是 \mathscr{L} 中的一个公式,把 A 中的每一个个体常项、函数符号和谓词符号替换成它的解释,得到公式 \bar{A},在解释 I 下,称 \bar{A} 是 A 的解释,或称在解释 I 下,A 被解释成 \bar{A}.
例 3.8 给定解释 I 如下:
(a) 个体域 D=\mathbf{N}(\mathbf{N} 为自然数集合,即 \mathbf{N}=\{0,1,2,\cdots\}).
(b) \bar{a}=0.
(c) \bar{f}(x,y)=x+y,\bar{g}(x,y)=x\cdot y.
(d) \bar{F}(x,y) 为 x=y.
在 I 下,下列哪些公式为真? 哪些为假? 哪些的真值还不能确定?
(1) F(f(x,y),g(x,y)).
(2) F(f(x,a),y)\rightarrow F(g(x,y),z).
(3) \neg F(g(x,y),g(y,z)).
(4) \forall xF(g(x,y),z).
(5) \forall xF(g(x,a),x)\rightarrow F(x,y).
(6) \forall xF(g(x,a),x).
(7) \forall x\forall y(F(f(x,a),y)\rightarrow F(f(y,a),x)).
(8) \forall x\forall y\exists zF(f(x,y),z).
(9) \exists xF(f(x,x),g(x,x)).
解 (1) 在 I 下,公式被解释成"x+y=x\cdot y",这不是命题.
(2) 公式被解释成"(x+0=y)\rightarrow(x\cdot y=z)",这也不是命题.
(3) 公式被解释成"x\cdot y\neq y\cdot z",同样不是命题.
(4) 公式被解释成"\forall x(x\cdot y=z)",不是命题.
(5) 公式被解释成"\forall x(x\cdot 0=x)\rightarrow(x=y)",由于蕴涵式的前件为假,所以被解释成的公式为真.
(6) 公式被解释成"\forall x(x\cdot 0=x)",为假命题.
(7) 公式被解释成"\forall x\forall y((x+0=y)\rightarrow(y+0=x))",为真命题.
(8) 公式被解释成"\forall x\forall y\exists z(x+y=z)",这也为真命题.
(9) 公式被解释成"\exists x(x+x=x\cdot x)",为真命题.
从例 3.8 可以看出,闭式在给定的解释中都变成了命题(见公式(6)\sim公式(9)),其实闭式在任何解释下都变成命题.
定理 3.1 封闭的公式在任何解释下都变成命题.
本定理的证明略.
在给定解释 I 后，如果进一步给公式中的每一个自由出现的个体变项指定个体域中的一个元素，则非封闭的公式也变为命题了。给公式中的每一个自由出现的个体变项指定个体域中的一个元素称作在解释 I 下的赋值。给定解释及赋值，任何公式都变为命题。
例 3.8(续) 给定解释 I 下的赋值 \sigma: \sigma(x)=1,\sigma(y)=2,\sigma(z)=3. 求(1)\sim(5)中公式的真值.
解 在解释 I 和赋值 \sigma 下,其结果分别如下:
(1) 1+2=1\times 2,这是假命题.
(2) (1+0=2)\rightarrow(1\times 2=3),这是真命题.
(3) 1\times 2\neq 2\times 3,这是真命题.
(4) \forall x(2x=3),这是假命题.
(5) \forall x(x\cdot 0=x)\rightarrow(1=2),这是真命题.
这里需注意,在(4)中 x 是约束出现,对 x 不使用赋值. 在(5)的前件中 x 是约束出现,也不对其使用赋值. 而在后件中,x 是自由出现,应对其使用赋值,把它换成 1. 对于(6)\sim(9),由于都是闭式,与赋值无关.
在一阶逻辑中同在命题逻辑中一样，有的公式在任何解释和任何赋值下均为真，有些公式在任何解释和任何赋值下均为假，而又有些公式既存在成真的解释和赋值，又存在成假的解释和赋值。下面给出公式类型的定义。
定义 3.8 设 A 为一公式,若 A 在任何解释和任何赋值下均为真,则称 A 为永真式(或称逻辑有效式). 若 A 在任何解释和任何赋值下均为假,则称 A 为矛盾式(或称永假式). 若至少存在一个解释和一个赋值使 A 为真,则称 A 是可满足式.
从定义可知，永真式一定是可满足式，但可满足式不一定是永真式。在例 3.8 中，公式(2),(3),(5),(7),(8),(9)都是可满足的，因为它们已存在使其成真的解释和赋值；而公式(1),(4),(6)绝不是永真式，因为它已存在使其成假的解释和赋值。
在一阶逻辑中，由于公式的复杂性和解释的多样性，公式的可满足性是不可判定的，即不存在一个算法能在有限步内判断任意一个公式是否是可满足的，这与命题逻辑的情况是完全不同的。下面考虑某些特殊情况。
定义 3.9 设 A_0 是含命题变项 p_1,p_2,\cdots,p_n 的命题公式,A_1,A_2,\cdots,A_n 是 n 个谓词公式,用 A_i 处处代替 A_0 中的 p_i(1\leqslant i\leqslant n),所得公式 A 称为 A_0 的代换实例.
例如,F(x)\rightarrow G(x),\forall xF(x)\rightarrow \exists yG(y) 是 p\rightarrow q 的代换实例,而 \forall x(F(x)\rightarrow G(x)) 不是 p\rightarrow q 的代换实例.
定理 3.2 重言式的代换实例都是永真式,矛盾式的代换实例都是矛盾式.
证明略.
例 3.9 判断下列公式中哪些是永真式,哪些是矛盾式.
(1) \forall x(F(x)\rightarrow G(x)).
(2) \exists x(F(x)\wedge G(x)).
(3) \forall xF(x)\rightarrow(\exists x\exists yG(x,y)\rightarrow \forall xF(x)).
(4) \neg(\forall xF(x)\rightarrow \exists yG(y))\wedge \exists yG(y).
(5) \forall xF(x,y).
解 为方便起见,用 A,B,C,D,E 分别记(1),(2),(3),(4),(5)中的公式.
(1) 取解释 I_1: 个体域为实数集合 \mathbf{R},\bar{F}(x):x 是整数,\bar{G}(x):x 是有理数. 在 I_1 下 A 为真,因而 A 不是矛盾式. 取解释 I_2: 个体域仍为 \mathbf{R},\bar{F}(x):x 是无理数,\bar{G}(x):x 能表示成分数. 在 I_2 下 A 为假,所以 A 不是永真式,即 A 是非永真式的可满足式.
(2) 请读者给出 B 的一个成真解释,一个成假解释,从而说明 B 不是永真式,也不是矛盾式,B 是非永真式的可满足式.
(3) 易知 C 是命题公式 p\rightarrow(q\rightarrow p) 的代换实例,而该命题公式是重言式,所以 C 是永真式.
(4) D 是命题公式 \neg(p\rightarrow q)\wedge q 的代换实例,而该命题公式是矛盾式,所以 D 是矛盾式.
(5) 取解释 I: 个体域为自然数集 \mathbf{N},\bar{F}(x,y): x\geqslant y. 取赋值 \sigma_1(y)=0. 在解释 I 和赋值 \sigma_1 下,E 为 \forall x(x\geqslant 0),这是真命题. 在解释 I 下取赋值 \sigma_2(y)=1,在解释 I 和赋值 \sigma_2 下,E 为 \forall x(x\geqslant 1),这是假命题. 故 E 是非永真式的可满足式.
解读：判断一个公式不是永真式，只要给出一个成假解释；判断它不是矛盾式，只要给出一个成真解释。含自由变项的公式还要挑赋值，所以 \forall xF(x,y) 属于第三类（非永真式的可满足式）。