命题不仅可能对单个具体事物的性质或几个具体事物之间的关系做
出判断，也可能对一类事物的性质或几类事物之间的关系做出判断。例如，命题“张三是计算机专业学生”是对单个人“张三”的性质的判断，而命题“计算机专业学生要学习离散数学”是对“计算机专业学生”这一类人的性质的判断。
命题逻辑只研究复合命题与其子命题之间的真值关系，即逻辑运算符的性质，不能分析一类事物与单个具体事物之间的联系。例如，从“计算机专业学生要学习离散数学”和“张三是计算机专业学生”这两个命题，人们很容易得到“张三要学习离散数学”这个结论，但在命题逻辑中，这三个命题都是独立的原子命题，只能分别使用命题变量p,q,r表示，而(p. q) ≡ r 不是命题逻辑的永真式，也即由于无法表达像“张三”这个具体个体与一类个体“计算机专业学生”之间的联系，在命题逻辑中无法分析一些人们广为接受的推理的有效性。
一阶逻辑(first-orderlogic)对原子命题的结构进行细分，以便表达一类事物与单个具体事物之间的联系。本章首先介绍一阶逻辑的一些基本概念，然后定义一阶逻辑公式及其真值的确定，并讨论一阶逻辑的等值演算和推理理论，最后介绍一阶逻辑公式的一些应用。

3.1 一阶逻辑的基本概念
命题是具有真值的陈述句，是对事物是否具有某种性质或事物之间是否具有某种关系的判断。一阶逻辑对原子命题的结构进行细分，将原子命题要判断的事物称为个体(individual)，而原子命题中给出的性质或关系称为谓词(predicate)。例如，命题“张三是计算机专业学生”中的“张三”是个体，而“……是计算机专业学生”是谓词。
谓词总是要作用于个体，例如，“……是计算机专业学生”中的省略号就是代表谓词要作用的个体。我们使用“x是计算机专业学生”这种更数学化的句式给出谓词，其中x代表某个不确定的个体，在一阶逻辑中称为个体变量(individualvariable)。我们使用大写字母P,Q,R等作用在一个或多个个体变量的形式符号化谓词，例如用P(x)表示“x是计算机专业学生”，用Q(x,y)表示“x和y是同学”等。这里P(x)是一元谓词，只作用于一个个体，而Q(x,y)是二元谓词，作用于两个个体，表示这两个个体之间的关系。能作用的个体数目称为谓词的元数(arity)。一元谓词表达个体性质，而二元或更多元谓词表达二个或多个个体之间的关系。
我们使用a,b,c等小写字母表示具体的个体，称为个体常量(individualconstant)。
当原子命题是对单个具体事物的性质或几个具体事物间的关系进行判断时，用个体常量
表示其中的具体事物，用谓词表示其中的性质和关系，从而将这类命题进行符号化。例
如，对原子命题“张三是计算机专业学生”，使用个体常量a表示“张三”，谓词P(x)
表示“x是计算机专业学生”，从而这个命题符号化为P(a)。对原子命题“张三和李四
是同学”，分别使用个体常量a和b表示“张三”和“李四”，谓词Q(x,y)表示“x和
y是同学”，从而这个命题符号化为Q(a,b)。
当原子命题是对一类事物的性质或几类事物间的关系进行判断时，人们通常是对一类事物的所有个体或某些个体的性质或参与的关系进行判断。例如命题“计算机专业学生要学习离散数学”是“所有计算机专业学生要学习离散数学”的省略形式，是对“计算机专业学生”这一类人员中所有个体进行判断，而命题“有的计算机专业学生选修数理逻辑”是对“计算机专业学生”这一类人员中某些个体进行判断。
人们将这种命题称为量化命题(quantificationproposition)，命题中像“所有”“有的”这种修饰事物类的词语称为量词(quantifier)。表达事物类的所有个体都具有某种性质或参与某种关系的量词称为全称量词(universalquantifier)，在符号化命题时用∈ 表示；而表达事物类的某些个体具有某种性质或参与某种关系的量词称为存在量词(existentialquantifier)，用. 表示。用到全称量词的量化命题称为全称命题，而用到存在量词的量化命题称为存在命题。
量化命题的符号化必须用到个体变量，用于表示某一类事物中某个不确定的个体。
个体变量所表示的不确定个体所属的事物类称为该个体变量的论域(domain)。例如，对
于命题“计算机专业学生要学习离散数学”，可用谓词H(x)表示“x要学习离散数学”，
使用个体变量x表示“计算机专业学生”这一类人员中某个不确定的个体，即x的论
域是所有“计算机专业学生”构成的集合，整个命题符号化为∈xH(x)，读作“对所有
x，H(x)”，或更准确地读作“对所有计算机专业学生x，H(x)”，因为x的论域是“计
算机专业学生”。
量化命题的符号化需要先确定其中出现的个体变量的论域，不同的论域可能有不同
的符号化形式。例如，对于命题“计算机专业学生要学习离散数学”，个体变量x的论
域也可以是任意包含所有“计算机专业学生”的集合，例如，所有“学生”的集合。这
时需要为命题中的事物类，即“计算机专业学生”也引入谓词，这种谓词称为特征谓词
(characteristicpredicate)。仍用P(x)表示“x是计算机专业学生”，当x的论域是所
有“学生”的集合时，整个命题应细化理解为“对所有学生x，若x是计算机专业学生，
则x 要学习离散数学”，从而符号化为∈x(P(x)≡ H(x))。
83 
这里给出了一阶逻辑的基本概念，包括个体、谓词、个体常量、个体变量、全称量词、存在量词、论域和特征谓词。后面介绍一阶逻辑应用时，将在定义一阶逻辑公式语法和语义的基础上更深入地讨论自然语言命题在一阶逻辑中的符号化。
最后要指出的是，一阶逻辑是一阶谓词逻辑(first-orderpredicatelogic)的简称。一阶谓词是指只作用于个体变量的谓词。一阶逻辑不引入可以作用于谓词、函数或者公式的高阶谓词，也不使用取值范围为某类谓词、函数或者公式的谓词变量、函数变量或公式变量等，一阶逻辑的量词也只能作用于个体变量，而不能作用于谓词、函数或公式。例如，“说x和y是相同的事物，如果对任意性质P，x具有性质P当且仅当y具有性质P”就是典型的非一阶逻辑的命题，这里“对任意性质P”就是量词作用于谓词，而非作用于个体变量。
3.2 一阶逻辑公式的语法
一阶逻辑公式的语法比命题逻辑公式的语法复杂，首先要将一阶逻辑公式中可以出现的符号分为逻辑符号和非逻辑符号，非逻辑符号由应用一阶逻辑公式的应用领域决定，而逻辑符号与应用领域无关，一阶逻辑本质上是研究逻辑符号，特别是量词的性质。给定非逻辑符号集，先定义一阶逻辑公式中的项，然后再定义一阶逻辑公式。项没有真值，是对个体的符号化，谓词作用于项才是一阶逻辑的原子公式，原子公式通过逻辑运算符和量词按照一定的规则构成一阶逻辑公式。
本节先讨论一阶逻辑公式的符号集，然后定义一阶逻辑公式中的项和一阶逻辑公式，最后讨论一些与一阶逻辑公式语法相关的概念，主要包括量词的辖域、个体变量的约束出现和自由出现、一阶逻辑公式的约束变量和自由变量等。
3.2.1 一阶逻辑公式的符号
命题逻辑公式中允许出现的符号包括命题变量符号、逻辑运算符以及圆括号。一阶逻辑公式中允许出现的符号更为复杂，分为逻辑符号和非逻辑符号。
一阶逻辑公式中出现的逻辑符号包括：.个体变量符号，使用小写字母x,y,z等表示个体变量，记所有个体变量符号构成的集合为V；.逻辑运算符号，包括否定.、逻辑与.、逻辑或.、逻辑蕴涵≡ 和逻辑双蕴涵～；. 量词符号，包括全称量词和存在量词.；.辅助符号，包括圆括号(和)，以及逗号。∈ 
一阶逻辑公式中出现的非逻辑符号包括：.个体常量符号，使用小写字母a,b,c等表示个体常量；.函数符号，使用小写字母f,g,h等表示函数，每个函数都有一个元数信息，表明该函数是几元函数；.谓词符号，使用大写字母F,G,H等表示谓词，每个谓词都有一个元数信息，表明该谓词是几元谓词。
将一阶逻辑公式中可以出现的符号分为逻辑符号和非逻辑符号是因为非逻辑符号与一阶逻辑的具体应用领域相关，例如应用一阶逻辑公式研究整数的性质，可以使用0,1等作为个体常量符号，+,., ×, ÷ 等作为函数符号，.,.,=等作为谓词符号，而研究集合的性质，可以使用空集作为常量符号，集合并、交等运算作为函数符号，而子集关系、集合相等作为谓词符号。非逻辑符号由应用领域抽象而得到，在确定一阶逻辑公式的真值时也必须基于应用领域先给出非逻辑符号的解释。因此，区分一阶逻辑公式中的逻辑符号和非逻辑符号有助于读者更好地应用一阶逻辑。
一阶逻辑本身只研究与逻辑符号，特别是与量词符号有关的性质，因此本章总是假定有一个非逻辑符号集，记为L，其中的个体常量使用小写字母a,b,c等表示，函数符号使用f,g,h等表示，谓词符号使用F,G,H等表示，读者从上下文很容易区别这些符号。一阶逻辑公式在给定的非逻辑符号集L，以及个体变量集V的基础上定义。非逻辑符号集L 可以没有个体常量符号和函数符号，但至少要有一个谓词符号。
3.2.2 一阶逻辑公式的定义
定义3.1给定非逻辑符号集L 和个体变量集V，一阶逻辑公式中的项(term)归纳定义如下。
（1）归纳基：L 的任意个体常量c 都是项；V 的任意个体变量x 也是项。
（2）归纳步：对L 的任意n元函数f，如果t1,t2,··· ,tn是项，则f(t1,t2,··· ,tn)也是项。
直观地说，一阶逻辑公式中的项就是通过函数构造的复杂个体。例如，设0,1是非逻辑符号集L 中的个体常量，+是二元函数，x,y是个体变量，则+(x,y),+(+(x,0),1)等是项，当函数是运算符时我们用更熟悉的中缀方式表示，即写成(x+y),((x+0)+1)这种形式的表达式。由于在应用领域中广泛存在函数与运算，因此一阶逻辑公式引入函数符号，用基于个体常量和个体变量构造项作为对应用领域中函数或运算表达式的符号化。
定义3.2给定非逻辑符号集L 和个体变量集V，一阶逻辑公式(first-orderlogicformula)归纳定义如下。
（1）归纳基：对L 的任意n元谓词F，如果t1,t2,··· ,tn是项，则F(t1,t2,··· ,tn)是公式，并称为一阶逻辑的原子公式。

（2）归纳步：.如果A是一阶逻辑公式，则(.A)是一阶逻辑公式；.如果A,B是一阶逻辑公式，则(A. B),(A. B),(A≡ B)和(A～ B) 是一阶逻辑公式；. 如果A 是一阶逻辑公式，x 是个体变量，则∈xA 和.xA 是一阶逻辑公式。


将(.A),(A. B),(A. B),(A≡ B)和(A～ B) 分别称为否定式、合取式、析取式、蕴涵式和双蕴涵式，而将∈xA 称为全称量词公式，.xA 称为存在量词公式。
后面有时将一阶逻辑公式简称为一阶公式，或者直接称公式，因为在没有特别说明
的情况下，本章说的公式都是指一阶逻辑公式。注意，上述定义要求非逻辑符号集L 至
少有一个谓词符号（否则不能构造出原子公式，更不能构造出其他一阶公式）。
例子3.1设非逻辑符号集L 有一元谓词F和二元谓词符号G,H，个体变量集V有个体变量x,y,z，则下面是一阶逻辑公式的例子。（1）∈x(F(x)≡.yG(x,y))
（2）∈xF(x)..y(F(y).∈zH(y,z))
（3）(∈x(F(x). H(x,y))≡.x(G(x,y)≡ (..yH(x,y))))
（4）.x((G(x,y). ((.yF(y). H(x,y)))).∈z.y(F(z)～ H(z,y)))
.
与命题逻辑公式类似，对于复杂的一阶逻辑公式，根据定义3.2画出公式的抽象语法树更容易看清楚它的语法结构。图3.1是上面（3）给出的一阶公式的抽象语法树，可以看到它是一个逻辑蕴涵式，前件是由全称量词∈x 构造的子公式∈xA，其中A是一个合取式，而后件是由存在量词.x 构造的子公式.xB，其中B是一个逻辑蕴涵式。

图3.1公式(.x(F(x)∧ H(x,y))→.x(G(x,y)→ (..yH(x,y))))的抽象语法树
注意，在给出一阶公式的抽象语法时，叶子节点是原子公式，不再给出原子公式的语法构造（即不再给出原子公式是怎样由谓词作用于项而得到）。我们将量词及其约束的个体变量一起作为一阶公式的一种构造方式，标记抽象语法树的内部节点，例如上面
（3）给出的一阶公式的逻辑蕴涵前件是由∈x 构造的子公式，而后件是由.x 构造的子公式。
图3.2是上面（4）给出的一阶公式的抽象语法树，它最后由存在量词.x 构造，具有.xA的形式，其中A是一个合取式(B. C)，其中B是一个析取式，而C是一个全称量词公式∈zD ，这里D 又是一个存在量词公式等。

图3.2公式.x((G(x,y)∨ (.(.yF(y)∧ H(x,y))))∧.z.y(F(z). H(z,y)))的抽象语法树
我们选了例子3.1的（3）和（4）给出的两个比较复杂的公式说明一阶公式的语法
结构和抽象语法树，（1）和（2）给出的公式语法结构比较简单，读者可自己练习画出
它们的抽象语法树。在实际应用中，下面例子的一阶公式可能更为常见。
例子3.2设非逻辑符号集L 有个体常量符号0,1，有二元函数符号+和.，以及二元谓词符号.,=，个体变量集V有个体变量x,y，则下面是一阶逻辑公式的例子。
（1）∈x((0.x)≡.y(x=y. y))（2）∈x.y(x.y)（3）(.x∈y(x+y=y).∈x.y(x. y=1))（4）.x∈y(x.y)这里将项和原子公式都写成了更为熟悉的中缀表示形式，也即原子公式0.x严格地说应该是.(0,x)，而项y. y 严格地说应该是.(y,y)，等等。基于一阶逻辑公式的抽象语法树，我们可清楚地看到每个公式包含哪些子公式，因为这个公式的抽象语法树的每棵子树都对应它的一个子公式。具体来说，可如下定义一阶逻辑公式的子公式。
定义3.3一阶逻辑公式A的子公式(sub-formula)按如下方式归纳定义。
（1）若公式A是原子公式F(t1,t2,··· ,tn)，则它的子公式只有它自己，即只有F(t1,t2,··· ,tn)。

（2）若公式A是公式(.B)，则它的子公式包含A，以及B的所有子公式。

（3）若公式A是公式(B. C)，这里. 代表., ., ≡ 或～，则它的子公式包括A，以及B和C的所有子公式。

（4）若公式A是公式∈xB 或.xB，则它的子公式包括A，以及B的所有子公式。例子3.3（1）公式∈x.y(x.y)的子公式除它自己外还有：.y(x.y)和x.y。

（2）公式(.x∈y(x+y=y).∈x.y(x.y = 1) 的子公式除它自己外还有.x∈y(x+y=y),∈x.y(x. y = 1), ∈y(x+y=y),.y(x. y=1),x+y=y,x. y =1 。


通过规定优先级和组合性可省略一阶公式中的一些圆括号。通常规定量词的优先
级最高，然后是否定、合取、析取、蕴涵和双蕴涵运算符，因此公式∈xF(x). G(x,y)
不是∈x(F(x). G(x,y))。蕴涵从右至左结合，而合取、析取和双蕴涵都是从左至右结
合。注意，使用量词构造公式时，我们采用简单的形式∈xA 和.xA，而不是(∈xA) 和
(.xA)，也不是∈x(A)和.x(A)，这意味着：.当最后一步是使用量词构造公式时，最
外层总是不再加圆括号；. 对于公式∈xA 或.xA，如果A是原子公式或量词公式时，
量词与A之间也不再使用圆括号。由于一阶公式的语法结构可能比较复杂，因此需要
仔细使用圆括号以清楚展示公式结构，并保证左右圆括号配对使用。
3.2.3 自由变量和约束变量
个体变量在一阶逻辑公式中起着非常重要的作用，并且同样的个体变量符号在一个
一阶逻辑公式中可能以不同的身份出现，从而起不同的作用，所以有必要对个体变量在
一阶逻辑公式中的出现方式做更深入的讨论。
定义3.4设公式A是∈xB 或.xB，称用于构造公式A的量词∈x 或.x中的个体变量x为这个量词（即∈x 或.x）的指示变量，称子公式B为这个量词（即∈x 或
.x）的辖域(scope)，或作用域。
若个体变量x在公式A的一处出现是在A的一个以x为指示变量的量词子公式∈xB 或.xB的辖域B中，则称x在A的这处出现是约束出现。若个体变量x在公式A的一处出现不在A的任意以x为指示变量的量词子公式∈xB 或.xB的辖域B中，则称x在A的这处出现是自由出现。
设个体变量x在公式A中出现，如果x在公式A中有一处出现是自由出现，则称x是公式A的自由变量(freevariable)；如果x在公式A的所有出现都是约束出现，则称x是公式A的约束变量(boundvariable)。没有自由变量的公式称为闭公式(closedformula)，或句子(sentence)。
从抽象语法树的角度看，一个量词的辖域就是以它的儿子节点为根的子树对应的公式。对一个个体变量在公式的一处出现，若从抽象语法树的根节点到该处的唯一路径上存在以该变量为指示变量的量词节点，则是约束出现，否则是自由出现。一个个体变量可以既在一个公式中自由出现，又在这个公式中约束出现，但它要么是这个公式的自由变量，要么是这个公式的约束变量，二者必居其一。
问题3.4给出下面公式中每个量词的辖域，确定个体变量的每处出现是约束出现还是自由出现，并说明出现的每个个体变量是公式的自由变量还是约束变量。
（1）∈x(F(x)≡.yG(x,y))
（2）∈xF(x)..y(F(y).∈zH(y,z))
（3）(∈x(F(x). H(x,y))≡.x(G(x,y)≡ (..yH(x,y))))
（4）.x((G(x,y). ((.yF(y). H(x,y)))).∈z.y(F(z)～ H(z,y)))
.
【解答】我们在这里只给出（2）和（4）的解答，（1）和（3）留作读者自行练习，对于（3）给出的公式，读者可参考图3.1给出的抽象语法树。
（2）公式∈xF(x)..y(F(y).∈zH(y,z))的量词∈x的辖域是F(x)，量词.y的辖域是(F(y).∈zH(y,z))，而量词∈z的辖域是H(y,z)。每个个体变量的出现方式如下：
指示变量约束出现指示变量约束出现指示变量约束出现约束出现
↓↓↓↓↓↓↓ . xF ( x) ∧. y(F(y)∧. zH(y,z))
所有个体变量的出现都是约束出现，因此个体变量x、y和z都是这个公式的约束变量，即这个公式没有自由变量，是闭公式。
（4）对于公式.x((G(x,y). (.(.yF(y). H(x,y)))).∈z.y(F(z)～ H(z,y)))中的
量词辖域情况根据图3.2给出的抽象语法树容易确定以下判断。
. 量词.x的辖域是((G(x,y). (.(.yF(y). H(x,y)))).∈z.y(F(z)～ H(z,y)))。
. 前一个量词.y的辖域是F(y)，而后一个量词.y的辖域是(F(z)～ H(z,y))。
. 量词∈z 的辖域是.y(F(z)～ H(z,y)))。
每个个体变量的出现方式如下：
指示变量约束出现自由出现指示变量约束出现约束出现
↓↓↓↓↓↓ 
. x((G(x,y)∨ (.(. yF ( y) ∧ H( x, 
自由出现指示变量指示变量约束出现约束出现约束出现
↓↓↓↓↓↓ 
y))))∧. z. y(F(z)H(z,y)))
. 
可以看到，个体变量x和z在这个公式中的出现都是约束出现，因此是这个公式的约束变量，但个体变量y在这个公式中既有约束出现又有自由出现，因此是这个公式的自由变量。
【讨论】（1）在一阶逻辑中，量词只能作用于个体变量，因此在说明量词的辖域时，可通过量词及其指示变量一起区分不同的量词。当量词与指示变量都相同时，例如上面
（4）给出的公式有两个.y，可进一步根据量词的位置进行区分。

（2）量词的辖域与计算机程序中变量的作用域类似。一个一阶公式中的量词子公式相当于一个子模块，量词的指示变量相当于声明一个局部变量，它只是在其辖域内起作用，辖域之外同名的个体变量与辖域内的个体变量本质上是两个不同的个体变量。


例如，公式.x((G(x,y). (.(.yF(y). H(x,y)))).∈z.y(F(z)～ H(z,y)))中前一个.yF(y)的个体变量y与后面的.y(F(z)～ H(z,y))中的y是本质上不同的个体变量，这类似于计算机程序中有两个子模块恰巧有相同名字的局部变量，但实际上它们是不同的程序变量。
.yF(y)中的y与合取运算后面的H(x,y)中的y也是不同的个体变量，这两者类似计算机程序中局部变量和全局变量的关系。一个一阶公式中自由出现的个体变量在整个公式中起作用，相当于计算机程序的全局变量。在这个公式中，G(x,y)和H(x,y)中的y都是自由出现，它们是同一个y。
可看到，当个体变量既在公式中自由出现又在公式中约束出现时容易带来混淆。实
际上，人们在使用一阶逻辑公式符号化自然语言命题时，个体变量的选择有一定的随意
性。例如，对命题“所有计算机专业学生都要学离散数学”，用谓词P(x)表示“x是计
算机专业学生”，H(x)表示“x要学离散数学”，可将命题符号化为∈x(P(x)≡ H(x))，
也可符号化为∈y(P(y)≡ H(y))。这正如编写同样的计算机程序，不同程序员也会用不
同的变量名。直观地看，这两个一阶公式没有实质差别。因此，在符号化时最好能小心
选择个体变量符号以尽量避免混淆。
在一阶逻辑中，可利用约束变量改名避免一个个体变量在公式中既自由出现又约束出现。约束变量改名是指将公式∈xA 或.xA的指示变量x及它的辖域A中所有自由出现的x都改为一个不在A中自由出现的个体变量y。例如，公式∈x(F(x)..xH(x,y))使用约束变量改名可得到公式∈z(F(z)..xH(x,y))。这里有两点需要注意。
（1）这个公式的量词∈x的辖域是A=(F(x)..xH(x,y)，其中F(x)中的x对于A这个子公式是自由出现，但H(x,y)中的x即使对于A也是约束出现，因此在对于量词∈x进行约束变量改名时，不能改变H(x,y)中的x。这个公式的量词.x 的辖域

嵌套在量词∈x 的辖域中，从一阶公式的语法上说没有问题，但辖域嵌套更容易带来混淆，所以后面我们将完全避免出现辖域嵌套的情况。

（2）约束变量改名时要选择不在辖域中自由出现的个体变量，所以这里不能选择y而将上述公式错误地约束变量改名为∈y(F(y)..xH(x,y))。原本公式A的F(x)中的个体变量x与H(x,y)中的y就不是同一个个体变量，约束变量改名后成为相同的个体变量，显然是错误的。进一步，为避免辖域嵌套，应该选择在辖域中不出现的个体变量。


通过约束变量改名总可以使得一个一阶逻辑公式中没有个体变量符号既自由出现又约束出现，也可完全避免辖域嵌套，甚至可使得每个量词都有不同的指示变量。后面给出的一阶公式会完全避免出现辖域嵌套，也会尽量避免同一个个体变量符号在公式中既自由出现又约束出现。不过，在容易理解的情况下允许不同的量词有相同的指示变量。
在一阶逻辑中，将公式A中所有自由出现的个体变量x都替换为一个不在A中自由出现的个体变量y称为自由变量替换。只要替换时选择不在A中出现的个体变量，通过自由变量替换也可使得在一个一阶公式中没有个体变量既自由出现又约束出现。后面主要使用约束变量改名，因为这种操作是相对局部的操作，更不容易出错。
3.3 一阶逻辑公式的语义
一阶逻辑公式的语义讨论如何确定一阶逻辑公式的真值。一阶逻辑公式在给定非逻辑符号集L 以及个体变量集V 的基础上构造，因此要确定一阶逻辑公式的真值也需要先给出非逻辑符号的解释，以及对个体变量的指派。本节先定义解释和指派，然后给出一阶逻辑公式的真值定义，最后讨论一阶逻辑公式的语义分类，即永真式、矛盾式和可满足式。
3.3.1 一阶逻辑公式的解释
一阶逻辑公式的非逻辑符号来自对应用领域事物的抽象，个体常量是应用领域特定事物的抽象，谓词是应用领域事物的性质或事物之间关系的抽象，而函数符号是应用领域事物之间的运算或变换的抽象。考察一阶逻辑公式的真值首先要将其中的非逻辑符号与具体的应用领域进行对应，这种对应称为一阶逻辑公式的解释，或说模型。也就是说，一阶逻辑公式是应用领域中事物性质、关系或约束的抽象，而应用领域是一阶逻辑公式的解释或说模型。通过这种抽象与对应，人们可更深入地理解应用领域以及不同应用领域之间的联系。
定义3.5设一阶逻辑公式的非逻辑符号集是L，它的解释(interpretation)或说模型(model)，记为M，包括：
（1）一个非空集合D，称为解释M 的论域(domain)。

（2）对L 的每个个体常量符号c，有论域D的一个元素与之对应，记这个元素为


.c.。
（3）对L 
的每个n元函数符号f，有论域D上的一个n元函数与之对应，记这个n元函数为.f.:Dn≡D，注意，这里Dn 是n个集合D的笛卡儿积，即Dn = D×D×···×D。

（4）对L 的每个n元谓词符号F，有论域D上的一个n元关系与之对应，记这个n元关系为.F.⊕ Dn，注意，第1 章的基础知识已经提到关系是笛卡儿积的子集。


直观地说，论域是应用领域中所有个体（或说事物）构成的集合，它不能是空集，
否则不存在与非逻辑符号集中谓词对应的关系。一阶逻辑公式的非逻辑符号可以没有
个体常量符号和函数符号，但必须至少有一个谓词符号。给定解释的论域之后，个体常
量符号解释为论域中的元素，函数符号解释为论域上的函数，谓词符号解释为论域上的
关系。
例子3.5假定一阶逻辑公式非逻辑符号集包括个体常量符号0,1，二元函数符号
+ 和.，以及二元谓词符号.,=。这里可给出这些非逻辑符号的两个解释。

（1）解释M1的论域是自然数集N，常量符号0,1分别解释为自然数0,1，二元函数符号+和. 分别解释为N上的加法和乘法运算，二元谓词符号.,=分别解释为N上的小于等于和相等关系。

（2）解释M2的论域是实数集R，常量符号0,1分别解释为实数0,1，二元函数符号+和. 分别解释为R上的加法和乘法运算，二元谓词符号.,=分别解释为R上的小于等于和相等关系。

从例子3.5可以看到：

（1）一阶逻辑公式的非逻辑符号集可以有不同的解释，这是人们从具体应用领域中抽象出逻辑公式的意义之一。

（2）由于一阶逻辑公式的非逻辑符号集是应用领域事物的抽象，因此常出现模型中的符号与非逻辑符号集的符号相同的情况，这是因为这个模型是非逻辑符号集最自然的解释，人们为方便起见采用了相同的符号。但严格地说，非逻辑符号集中的符号仅仅是符号，而模型中的符号已经预先赋予了含义。例如，作为一阶逻辑公式中的个体常量符号0，它仅仅是个符号，没有含义，但作为以自然数集为论域的解释M1，0不仅仅是符号，而且是人们熟知的那个自然数0。


在逻辑学研究中，将所研究的逻辑公式，如命题逻辑公式、一阶逻辑公式称为对象语言(objectlanguage)，而研究逻辑时使用的语言，如自然语言称为元语言(meta-language)。人们对命题逻辑公式、一阶逻辑公式的符号集及公式语法的归纳定义给出了对象语言的严格定义，但采用的元语言是自然语言，即汉语，无法严格定义。
逻辑学研究的一个特点就是元语言也不得不采用一些逻辑语言，因此容易混淆元语言和对象语言。例如，在等值演算中，使用. 表示两个公式逻辑等值，它是元语言的符号，而双蕴涵运算符～ 是对象语言的符号。在推理理论中人们使用= → 分隔推理的前提和结论，也带有“蕴涵”“推出”的意味，但它是元语言符号，而蕴涵运算符≡ 是对象语言的符号。有些读者可能会混淆. 和～，以及= → 和≡。同样地，一阶逻辑公式的非逻辑符号集中的符号是对象语言符号，而它的解释中的符号则是元语言符号。
定义3.6给定一阶逻辑公式的非逻辑符号集L 及它的一个解释M。解释M 的一个个体变量指派函数σ是从个体变量集V到解释M 的论域D 的函数，即是一个函数σ : V ≡D。
为确定一阶逻辑公式中量词的真值，需要一点小技巧，使得人们可以对个体变量指派函数进行变换，从而对某个特定的个体变量指派论域中特定的元素。
定义3.7给定一阶逻辑公式的非逻辑符号集L 及它的一个解释M，其论域是D。对于M 的一个个体变量指派函数σ，以及一个个体变量x↓ V，和论域D的一个元素d↓ D，定义一个新的M 的个体变量指派函数，记为σ[x.≡ d]：对任意个体变量yV，
↓ 
=
σ[x.≡ d](y)
.. .

d 若y = x 
σ(y)若y=. x 
例子3.6设一阶逻辑公式的非逻辑符号集L 只包含一个一元谓词符号F，以及两个二元谓词符号G,H，个体变量集V={x,y,z}。
定义L 的一个解释M：论域D = {a,b,c}，谓词符号F的解释是D上的一元关系，即D的子集.F.={a,b}⊕ D，谓词符号G的解释是D上的二元关系.G.={.a,b∧, .b,c∧}，谓词符号H的解释是D上的二元关系.H.={.a,a∧, .c,c∧}。这里解释的论域集、谓词符号的解释，都使用元素枚举法给出了这些集合的元素。
定义M 的一个个体变量指派函数σ : V ≡D，σ(x)=a,σ(y)=b,σ(z)=c。这样，对于个体变量x，以及论域D的元素c，则有σ[x.≡ c](x)=c,σ[x.≡ c](y)=σ(y)=b,σ[x.≡ c](z)=σ(z)=c。同样，这里定义函数也是使用元素枚举法给出定义域（即个体变量集V）的每个元素的函数值。
3.3.2 一阶逻辑公式的真值
一阶逻辑公式在给定的非逻辑符号集和个体变量集的基础上归纳构造，相应地，一阶逻辑公式的真值则在给定非逻辑符号集的解释以及个体变量指派函数的基础上确定。在给出一阶逻辑公式的语法时，先定义了一阶逻辑公式中的项，同样这里也需要先定义项的语义。
定义3.8设一阶逻辑公式的非逻辑符号集是L，个体变量集是V。给定L 的解释M，以及一个个体变量指派函数σ : V ≡D，这里D是解释M 的论域。
在解释M 及个体变量指派函数σ下，一阶逻辑公式的项t的语义解释是论域D的元素，记为.t.σ，根据项t的结构归纳定义如下。
（1）如果项t是个体常量c，则.t.σ=.c.，这里.c.↓ D 是个体常量符号c 在M 的解释。
（2）如果项t是个体变量x，则.x.σ=σ(x)。

（3）如果项t是f(t1,t2,··· ,tn)，则


.t.σ=.f(t1,t2,,tn).σ=.f.(.t1.σ,.t2.σ,.σ)
······,.tn
这里.f.:Dn≡D 是n 元函数符号f 在M 的解释。

例子3.7设一阶逻辑公式非逻辑符号集包括个体常量符号0,1，二元函数符号+和.，以及二元谓词符号.,=。给定解释M1，论域是自然数集N，个体常量符号0,1分别解释为自然数0,1，二元函数符号+和. 分别解释为自然数集上的加法和乘法运算，二元谓词符号.,=分别解释为自然数集上的小于或等于以及相等关系。
设个体变量集V = {x,y}，个体变量指派函数σ : V ≡N定义为：σ(x)=0,σ(y)=1。
我们知道，0,1,x+y,x. y 都是基于这里定义的非逻辑符号集和个体变量集构造的一阶
公式中的项，它们的语义解释如下：
.0.σ=0.1.σ=1.x+y.σ=.x.σ+.y.σ=σ(x)+σ(y)=1.x. y.σ=.x.σ. .y.σ=σ(x). σ(y)=0
注意，这里在对象语言（即一阶逻辑公式）和元语言（公式的解释）中使用了相同的符号，读者注意区别。例如在.0.σ中的0是指一阶逻辑公式中的个体常量，而等号后面的0是自然数0，在.x+y.σ中的+是一阶逻辑公式中的函数符号，而在.x.σ+.y.σ中的+是自然数加法运算。
定义3.9设一阶逻辑公式的非逻辑符号集是L，个体变量集是V。给定L 的解
释M，以及一个个体变量指派函数σ : V ≡D，这里D是解释M 的论域。在解释M 及个体变量指派函数σ下，一阶逻辑公式A的语义解释是2={1, 0}
的元素，即公式A的真值，记为σ(A)，根据公式A的结构归纳定义如下。
（1）如果公式A是原子公式F(t1,t2,··· ,tn)，则
σ(A)=1当且仅当..t1.σ,.t2.σ,··· ,.tn.σ∧↓ .F . 
这里.F.↓ Dn 是n 元谓词符号F 在M 的解释。
（2）如果公式A是(.B)，则σ(A)=1当且仅当σ(B)=0。

（3）如果公式A是(B. C)，则σ(A)=1当且仅当σ(B)=σ(C)=1。

（4）如果公式A是(B. C)，则σ(A)=0当且仅当σ(B)=σ(C)=0。

（5）如果公式A是(B≡ C)，则σ(A)=0当且仅当σ(B)=1且σ(C)=0。

（6）如果公式A是(B～ C)，则σ(A)=1当且仅当σ(B)=σ(C)。


（7）如果公式A是∈xB，则σ(A)=1当且仅当对论域D的任意元素d有σ[x.≡ d](B)=1。

（8）如果公式A是.xB，则σ(A)=1当且仅当存在论域D的元素d使得σ[x.≡ d](B)=1。


当公式的真值是1时人们通俗地称这个公式的真值为真，否则称这个公式的真值为假。简单地说，原子公式的真值取决于谓词作用的项的解释（即D的元素）是否具有谓词对应的关系（即谓词的解释），逻辑运算符构造的公式的真值确定方法与命题逻辑完全相同，量词公式的真值使用定义3.7给出的个体变量指派函数的变换将全称量词公式∈xB定义为对论域的每个元素都使得公式B的真值为真，而存在量词公式.xB 定义为存在论域的元素使得公式B 的真值为真。
问题3.8设一阶逻辑公式的非逻辑符号集L 只包含一个一元谓词符号F，以及两个二元谓词符号G,H，个体变量集V={x,y,z}。
定义L 的一个解释M：论域D = {a,b,c}，谓词符号F的解释.F.={a,b}⊕ D，谓词符号G的解释是.G.={.a,b∧, .b,c∧}，谓词符号H的解释是.H.={.a,a∧, .c,c∧}。
定义M 的一个个体变量指派函数σ : V ≡D，σ(x)=a,σ(y)=b,σ(z)=c。确定下面公式在M 和σ 下的真值。
（1）∈x(F(x)≡.yG(x,y))
（2）∈xF(x)..y(F(y).∈zH(y,z))
（3）F(x). G(x,y).∈zH(y,z)
【解答】（1）记A=∈x(F(x)≡.yG(x,y))，它具有形式∈xB，其中B=F(x)≡ .yG(x,y)，因此σ(A)为真当且仅当对论域D的元素a,b,c有
σ[x.≡ a](B)=1且σ[x.≡ b](B)=1且σ[x.≡ c](B)=1
B是蕴涵式，因此σ[xa](B)=0当且仅当σ[xa](F(x))=1且σ[xa](.yG(x,y))=0。而.≡ .≡.≡ 
σ[x.≡ a](F(x))=1当且仅当.x.σ[x..a] ↓ .F.当且仅当σ[x.≡ a](x)↓ .F . = {a,b} 
注意到σ[x.≡ a](x)=a，因此σ[x.≡ a](F(x))=1。由于F是谓词，为简便起见，当F解释为D的子集{a,b} 时，可理解为F(a),F(b)为真（因为a,b属于这个子集），而F(c)为假（因为c不属于这个子集），这样σ[x.≡ a](F(x))的真值与F(a)相同。
对于σ[x.≡ a](.yG(x,y))，根据存在量词的语义，σ[x.≡ a](.yG(x,y))=1当且仅当对论域D的元素a,b,c有
σ[x.≡ a][y.≡ a](G(x,y))=1或σ[x.≡ a][y.≡ b](G(x,y))=1或σ[x.≡ a][y.≡ c](G(x,y))=1
类似地，当G解释为D×D 的子集{.a,b∧, .b,c∧}，可理解为G(a,b),G(b,c)为真，而对于D×D的其他有序对都为假。注意到σ[x.≡ a][y.≡ a]总是将x指派为a，将y也指派为a，因此可认为σ[x.≡ a][y.≡ a](G(x,y))的真值与G(a,a)相同，σ[x.≡ a][y.≡ b](G(x,y))的真值与G(a,b)相同，σ[x.≡ a][y.≡ c](G(x,y))的真值与G(a,c)相同。
更进一步，可认为σ[x.≡ a](.yG(x,y))的真值与.yG(a,y)的真值相同，而.yG(a,y)的真值与G(a,a). G(a,b). G(a,c)的真值相同，而σ[x.≡ a](B)=σ[x.≡ a](F(x)≡ .yG(x,y))的真值与F(a)≡.yG(a,y)的真值相同，进一步与F(a)≡ (G(a,a). G(a,b). G(a,c))的真值相同。对σ[x.≡ b](B),σ[x.≡ c](B)也做类似地处理，这样在给定的解释和个体变量指派函数下，可使用类似等值演算的方式确定公式A的真值：
∈x(F(x)≡.yG(x,y))
.	
(F(a)≡.yG(a,y)). (F(b)≡.yG(b,y)). (F(c)≡.yG(c,y))

.	
(F(a)≡ (G(a,a). G(a,b). G(a,c))). (F(b)≡ (G(b,a). G(b,b). G(b,c))). (F(c)≡ (G(c,a). G(c,b). G(c,c)))

. 
(1 ≡ (0 . 1 . 0)). (1 ≡ (0 . 0 . 1)). (0 ≡ (0 . 0 . 0)). 1 . 1 . 1 . 1 


综上，有σ(∈x(F(x)≡.yG(x,y)))=1。
（2）直接用类似等值演算的方式确定公式∈xF(x)..y(F(y).∈zH(y,z))的真值：
∈xF(x)..y(F(y).∈zH(y,z))
.	
(F(a). F(b). F(c))..y(F(y).∈zH(y,z))

.	
(1 . 1 . 0) ..y(F(y).∈zH(y,z))


根据合取运算符的特点，到这一步已经能确定这个公式的真值为假。不过为了让大家进一步熟悉这种演算方式，继续计算.y(F(y).∈zH(y,z))的真值：
.y(F(y).∈zH(y,z))
.	
(F(a).∈zH(a,z)). (F(b).∈zH(b,z)). (F(c).∈zH(c,z))

.	
(F(a). (H(a,a). H(a,b). H(a,c))). (F(b). (H(b,a). H(b,b). H(b,c))). (F(c). (H(c,a). H(c,b). H(c,c)))

.	
(1 . (1 . 0 . 0)). (1 . (0 . 0 . 0)). (0 . (0 . 0 . 1)). 0 . 0 . 0 . 0 


综上，有σ(∈xF(x)..y(F(y).∈zH(y,z)))=0。
（3）公式F(x). G(x,y).∈zH(y,z)在M 和σ下的真值为真，当且仅当σ(F(x)),σ(G(x,y))以及σ(∈zH(y,z))的值都为1，注意到σ(x)=a,σ(y)=b，因此σ(F(x))的值等于F(a)的真值，σ(G(x,y))的值等于G(a,b)的真值，它们都为真，因此这个公式的真值等于σ(∈zH(y,z))，即等于H(b,a). H(b,b). H(b,c)的真值，即为假。总之，有σ(F(x). G(x,y).∈zH(y,z))=0。
【讨论】（1）这里给出的解释的论域是有限集D=(a,b,c)，因此对于全称量词公式∈xF(x)，它的真值等于F(a). F(b). F(c)的真值，而对于存在量词公式.xF(x)，它的真值等于F(a). F(b). F(c)的真值。也就是说，全称量词公式在有限论域可展开为合取式，存在量词公式在有限论域可展开为析取式。
95 
注意，严格来说，F(a),F(b),F(c)都不是由给定的非逻辑符号集L 和个体变量集V能构造的公式，因为a,b,c不是L 中的符号。所以上面的演算严格来说不是逻辑公式的等值演算，而是当解释的论域是有限集时，我们确定一阶公式真值的一种简便计算方式。将谓词符号作用于论域的元素或有序对，它的真值为真当且仅当所作用的元素或有序对属于谓词符号的解释所对应的子集或关系，例如，F(a)为真当且仅当a↓ .F.。
（2）上面（1）和（2）给出的公式都是闭公式，不含有自由变量，可以看到它们的真值与个体变量指派函数σ没有关系。简单地说，对于量词公式∈xF(x)或.xF(x)，它们的真值与个体变量指派函数σ对个体变量x的指派无关。上面（3）给出的公式F(x). G(x,y).∈zH(y,z)含有自由变量x和y，这时它的真值与σ(x)和σ(y)的值有关，但z是它的约束变量，所以它的真值与σ(z)无关。
一阶公式的真值与个体变量指派函数对它的约束变量所指派的值无关，这样可得到如下定理。
定理3.1设公式∈xA 通过约束变量改名得到公式∈yA.，即A.是将A中所有自由出现的x改为y得到的公式，这里设y不在A中出现，则在任意的解释M 和任意的个体变量指派函数σ 下，公式∈xA 和∈yA.都有相同的真值。类似地，若公式.xA 通过约束变量改名得到公式.yA.，则.xA 与.yA.在任意解释和个体变量指派函数下也有相同的真值。
下面是使用类似等值演算的方法确定闭公式真值的例子，其中的闭公式都是嵌套量词公式。所谓的嵌套量词公式，是指一个量词的辖域中还包括另外的量词。我们也用这个例子说明一阶公式中含有多个量词时，量词的顺序会影响公式的真值。
例子3.9设非逻辑符号集L 只包含二元谓词F，个体变量集V={x,y}。定义解释M，论域D = {a,b}，二元谓词F的解释是.F.={.a,b∧, .b,b∧}，即F(a,b)和F(b,b)为真，而F(a,a)和F(b,a)为假。
（1）对于公式∈x∈yF(x,y)，有：∈x∈yF(x,y).∈yF(a,y).∈yF(b,y)
. (F(a,a). F(a,b)). (F(b,a). F(b,b))0
. 
（2）对于公式∈y∈xF(x,y)，有：∈y∈xF(x,y).∈xF(x,a).∈xF(x,b)
. (F(a,a). F(b,a)). (F(a,b). F(b,b))0
. 
由（1）和（2）容易看到，∈x∈yF(x,y)和∈y∈xF(x,y)具有相同的真值。类似地，读者可自行验证公式.x.yF(x,y)和.y.xF(x,y)也具有相同的真值，即如果都是存在量词，或者都是全称量词（指示变量不同），则交换量词的顺序不影响公式的真值。
（3）对于公式∈x.yF(x,y)，有：∈x.yF(x,y)..yF(a,y)..yF(b,y)
. (F(a,a). F(a,b)). (F(b,a). F(b,b))1
. 
（4）对于公式.y∈xF(x,y)，有：
.y∈xF(x,y).∈xF(x,a).∈xF(x,b)
. (F(a,a). F(b,a)). (F(a,b). F(b,b))0
. 
由（3）和（4）容易看到，∈x.yF(x,y)和.y∈xF(x,y)具有不同的真值。类似地，读者可自行验证公式.x∈yF(x,y)和∈y.xF(x,y)也具有不同的真值。实际上，这四个公式中的任意两个都可能具有不同的真值。
（5）对于公式.x∈yF(x,y)，有：
.x∈yF(x,y).∈yF(a,y).∈yF(b,y)
. (F(a,a). F(a,b)). (F(b,a). F(b,b))0
. 
可以看到，当F 的解释是关系{.a,b∧, .b,b∧} 时，.y∈xF(x,y)和.x∈yF(x,y)的真值都是0，但不难给出F的另一个解释，例如它的解释是关系{.a,a∧, .a,b∧} 时，这两个公式就具有不同的真值。同样，容易给出F 的解释使得∈x.yF(x,y)与∈y.xF(x,y)
也具有不同的真值。总之，如果公式中的两个量词类型不同（即一个是全称量词一个是存在量词），则交换量词的顺序会影响公式的真值。上面讨论了非逻辑符号的解释的论域是有限集的情况，下面的问题讨论当非逻辑符号解释的论域不是有限集时如何确定一阶公式的真值。问题3.10设一阶逻辑公式非逻辑符号集包括个体常量符号0,1，二元函数符号
+ 和.，以及二元谓词符号.,=。个体变量集V={x,y}。
给定解释M1，论域是自然数集N，个体常量符号0,1分别解释为自然数0,1，二元函数符号+和. 分别解释为自然数集上的加法和乘法运算，二元谓词符号.,=分别解释为自然数集上的小于或等于以及相等关系。确定下面闭公式的真值。
（1）∈x((0.x)≡.y(x=y. y))（2）∈x.y(x.y)（3）(.x∈y(x+y=y).∈x.y(x. y=1))（4）.x∈y(x.y)【解答】（1）公式∈x((0.x)≡.y(x=y. y))的真值为真当且仅当对任意的自然数n，n.0蕴涵存在自然数m使得n=m. m成立，但显然不是所有的自然数n都存在自然数m使得n=m. m 成立，因此这个公式的真值为假。
（2）公式∈x.y(x.y)的真值为真当且仅当对任意的自然数n，存在自然数m使得n.m成立，也即，任意自然数都有大于或等于它的自然数，这显然成立，因此这个公式的真值为真。

（3）公式(.x∈y(x+y=y).∈x.y(x. y = 1)) 为真当且仅当公式.x∈y(x+y=y)为真且公式∈x.y(x. y = 1) 为真。而公式.x∈y(x+y=y)为真，当且仅当存在自然数n，使得对任意自然数m，都有n+m=m成立，这显然成立，因为存在自然数0，对任意的自然数都有0+m=m，所以公式.x∈y(x+y=y)的真值为真；公式∈x.y(x. y=1)为真当且仅当对任意的自然数n，都存在自然数m使得n. m =1 ，这显然不成立，因此公式∈x.y(x. y = 1) 的真值为假，因此整个公式的真值为假。


97 
（4）公式.x∈y(x.y)的真值为真当且仅当存在自然数n，对任意的自然数m，都有n.m，也即存在小于或等于任意自然数的自然数，也即存在最小的自然数，这显然成立，因为0是最小的自然数，因此这个公式的真值为真。
【讨论】（1）当解释的论域不是有限集时，对于全称量词公式∈xA(x)只能直观地说，它的真值为真，当且仅当对论域的每个元素d有A(d)成立，这里A(d)是用论域元素d替换A中自由出现的x后得到的命题，而对于存在量词公式.xA(x)只能直观地说，它的真值为真，当且仅当存在论域的元素d使得A(d)成立。
当存在论域的元素d使得命题A(d)不为真时，∈xA(x)的真值为假，而当存在论域的元素d使得命题A(d)为真时，.xA(x)为真，对于这两种情况，我们都应该具体地指出d到底是论域的哪个元素。
注意，这里说的A(d)严格来说不是一阶逻辑公式，因为d是论域元素而不是非逻辑符号集中的个体常量符号，但可将A(d)看作是使用d替换A中自由出现的x后的命题，这个命题是元语言的命题，而非对象语言（即一阶逻辑）中的公式，然后根据与论域相关的知识判断该命题是否成立，以说明量词公式的真值。
（2）当一阶逻辑公式的解释的论域是有穷集时，可以像例子3.8一样使用类似等值演算的方法将全称量词公式展开为合取式，存在量词公式展开为析取式而确定公式真值。但一般来说，由于一阶逻辑公式的解释可以有无穷多，解释的论域也可能是无穷集，因此不存在通用算法能确定任意一阶逻辑公式的真值。这也是本章没有介绍一阶逻辑公式语法和语义相关算法的主要原因。
3.3.3 一阶逻辑公式的分类
根据构造一阶逻辑公式的最后一步所使用的逻辑运算或量词，一阶逻辑公式从语法上可分为否定式、合取式、析取式、蕴涵式、双蕴涵式，以及全称量词公式和存在量词公式。从语义角度，也即从公式的真值角度，一阶逻辑公式和命题逻辑公式一样也可分为永真式、矛盾式和可满足式。
定义3.10设A是基于非逻辑符号集L 和个体变量集V构造的一个一阶逻辑公式。
（1）如果A在L 的任意解释，以及任意个体变量指派函数下的真值都为真，则称A为永真式(tautology)，也称为普遍有效式。

（2）如果A在L 的任意解释，以及任意个体变量指派函数下的真值都为假，则称A为矛盾式(contradiction)。

（3）如果A不是矛盾式，即存在一个L 的解释，及一个个体变量指派函数使得A的真值为真，则称A是可满足的(satisfiable)。


显然，公式A是永真式当且仅当(.A) 是矛盾式。可根据定义，证明一些一阶逻辑公式是永真式。
例子3.11设F是构造一阶逻辑公式的非逻辑符号集中的一元谓词，x是个体变量。一阶逻辑公式.(∈xF(x))～.x(.F(x))是永真式。
因为，对非逻辑符号集的任意解释，.(∈xF(x))为真当且仅当∈xF(x)为假。∈xF(x)为真当且仅当对解释论域的任意元素d有F(d)为真，因此∈xF(x)为假当且仅当存在论域的元素d使得F(d)为假，也即存在论域的元素d使得.F(d)为真，也即.x(.F(x))为真。因此，在任意解释下，公式.(∈xF(x))和.x(.F(x))都有相同的真值，也即在任意解释下.(∈xF(x))～.x(.F(x))的真值都为真。
类似地，一阶逻辑公式.(.xF(x))～∈x(.F(x))也是永真式。
例子3.12设F是构造一阶逻辑公式的非逻辑符号集中的二元谓词，x,y是个体变量。一阶逻辑公式.x∈yF(x,y)≡∈y.xF(x,y)是永真式。
因为对非逻辑符号集的任意解释，若.x∈yF(x,y)为假，则整个蕴涵式为真，所以只需要考虑.x∈yF(x,y)为真的情况。而.x∈yF(x,y)为真当且仅当存在解释论域的元素d0，使得对论域的任意元素d，都有F(d0,d)为真，从而对论域的任意元素d，都存在论域元素d0使得F(d0,d)为真，也即∈y.xF(x,y)为真，因此在任意解释下蕴涵式.x∈yF(x,y)≡∈y.xF(x,y)总为真。
不存在通用算法确定一个一阶逻辑公式的真值，因此也不存在通用算法判定一个公式是否永真式、矛盾式或可满足式。判断一个逻辑公式是否可满足的，称为逻辑公式的可判定问题。命题逻辑公式的可判定问题可以由计算机自动求解，例如，可以构造命题逻辑公式的真值表。但邱奇(AlonzoChurch,1903—1995)和图灵(AlanTuring,1912—1954)早在1936年就分别独立证明了一阶逻辑公式的判定问题不是计算机可解的。实际上，一阶逻辑公式是半可判定的，即存在通用的算法，对任意的一阶逻辑公式，如果它是可满足的，则该算法会终止并回答说它是可满足的，但如果它不是可满足的，则算法不会终止。
有一类称为命题逻辑公式替换实例的一阶逻辑公式，可利用命题逻辑的永真式判断它们是否一阶逻辑的永真式。
定义3.11设A是命题逻辑公式，其中出现的命题变量是p1,p2,··· ,pn，用任意的一阶逻辑公式A1,A2,··· ,An分别替换A中p1,p2,··· ,pn的所有出现得到的一阶逻辑公式称为命题逻辑公式A的替换实例。
例子3.13（1）一阶逻辑公式∈xF(x)≡ (.xG(x,y)≡∈xF(x))是命题逻辑公式p≡ (q ≡ p) 的替换实例，是用∈xF(x)替换其中的p，而用.xG(x,y)替换其中的q。
（2）一阶逻辑公式∈xF(x)≡∈xF(x)是命题逻辑公式p≡ p 的替换实例，但是∈x(F(x)≡ F(x))不是命题逻辑公式p≡ p 的替换实例。
定理3.2若一阶逻辑公式A是命题逻辑某个永真式的替换实例，则A也是一阶逻辑的永真式。类似地，若一阶逻辑公式A是命题逻辑某个矛盾式的替换实例，则A也是一阶逻辑公式的矛盾式。
证明设公式A是命题逻辑永真式B的替换实例，即是使用某些一阶逻辑公式B1,B2,··· ,Bn分别替换B中出现的命题变量p1,p2,··· ,pn 的所有出现而得到的公式。对构造公式A的非逻辑符号集的任意解释和任意个体变量指派函数，在这个解释和个体变量指派函数下无论B1,B2,··· ,Bn的真值如何都相当于对命题变量p1,p2,··· ,pn的一个真值赋值，但永真式B的真值与p1,p2,··· ,pn的真值赋值无关，因此A在这个解释和个体变量指派函数下的真值也与B1,B2,··· ,Bn的真值无关，也总是为真，因此A是一阶逻辑公式的永真式。由于一个公式是永真式当且仅当它的否定是矛盾式，因此命题逻辑矛盾式的替换实例是一阶逻辑的矛盾式。
例子3.14（1）不难验证命题逻辑公式p≡ (q ≡ p) 是永真式，因此∈xF(x)≡ (.xG(x,y)≡∈xF(x))是一阶逻辑的永真式。
（2）不难验证命题逻辑公式p≡ p 是永真式，因此∈xF(x)≡∈xF(x)是一阶逻辑的永真式，F(x)≡ F(x)也是一阶逻辑的永真式。可以证明，如果x是A的自由变量，则A是永真式当且仅当∈xA是永真式，因此由F(x)≡ F(x)是永真式可得到∈x(F(x)≡ F(x))也是永真式，虽然它不是命题逻辑永真式p≡ p 的替换实例。
问题3.15判断下面一阶逻辑公式的类型（即是永真式、矛盾式，还是非永真的可满足式）。
（1）∈xF(x)≡.xF(x)（2）.xF(x)≡∈xF(x)
（3）(∈xF(x)..xF(x))≡ (∈xF(x)..xF(x))
【分析】判断一阶逻辑公式的类型首先观察它是否某个合适的命题逻辑公式的替换实例，如果是，则利用命题逻辑的真值表构造或等值演算判断这个命题逻辑公式是否永真式或矛盾式。虽然没有固定方法给出一个一阶逻辑公式是否某个命题逻辑公式的替换实例，但对许多简单的一阶逻辑公式都容易确定它是哪个命题逻辑公式的替换实例。
如果不能通过命题逻辑公式的替换实例判断一阶逻辑公式的类型，则只能根据一阶逻辑公式永真式、矛盾式和可满足式的定义进行判断。对于永真式要证明它在任意解释、任意个体变量指派函数下为真；对于矛盾式要证明它在任意解释、任意个体变量指派函数下为假；而对于非永真的可满足式，则可以给出一个具体的解释和个体变量指派函数使得这个公式为真，并且再给出一个具体的解释和个体变量指派函数使得这个公式为假。当待判断的一阶公式是闭公式时，则可以不考虑个体变量指派函数，因为闭公式的真值与个体变量指派函数无关。
【解答】（1）公式∈xF(x)≡.xF(x)虽然可看作命题逻辑公式p≡ q 的替换实例，但p ≡ q 不是永真式。因此，只能通过定义判断它的类型。对于任意的解释，如果∈xF(x)为假，则整个蕴涵式为真。如果∈xF(x)为真，则对解释的论域的任意元素d有F(d)为真，注意到论域不能为空，因此至少存在一个元素d0使得F(d0)为真，因此.xF(x)也为真，因此蕴涵式∈xF(x)≡.xF(x)也为真。因此，在任意的解释下这个公式的真值都为真，即它是永真式。
（2）同样只能通过定义判断它的类型，直观地看，对任意解释，存在论域一个元素d0使得F(d0)为真不能得到对论域的任意元素d都有F(d)为真，除非这个论域只有一个元素。另一方面，当论域不存在元素d使得F(d)为真时，.xF(x)为假，从而整个蕴涵式为真。因此公式.xF(x)≡∈xF(x)应该是非永真的可满足式。
为了使回答更为严谨，要给出一个具体的解释使得公式为真，以及一个具体的解释
使得公式为假。设解释的论域D = {a,b}，F的解释是D的子集{a}，即F(a)为真，
而F(b)为假。这时.xF(x)为真，而∈xF(x)为假，整个蕴涵式的真值在这个解释下
为假。又设解释的论域D = {a,b}，但F的解释是空集，即F(a)和F(b)都为假，这
时.xF(x)为假，从而整个蕴涵式为真。综上，公式.xF(x)≡∈xF(x)是非永真的可
满足式。
（3）公式(∈xF(x)..xF(x))≡ (∈xF(x)..xF(x))是命题逻辑公式(p.q) ≡ (p.q) 
的替换实例，容易验证这个命题逻辑公式是永真式，因此这个一阶逻辑公式也是永真式。综上，（1）,（3）给出的公式是永真式，而（2）给出的公式是非永真的可满足式。
3.4 一阶逻辑的等值演算
与命题逻辑公式的逻辑等值一样，两个一阶公式是否逻辑等值也可通过永真式判
断，而且命题逻辑公式的逻辑等值式的替换实例也是一阶逻辑公式的逻辑等值式，这使
得一阶逻辑公式中与逻辑运算符相关的等值演算方法与命题逻辑相同，因此本节主要讨

论与量词相关的一阶逻辑等值式。下面先给出两个一阶逻辑公式逻辑等值的定义，然后重点介绍与量词相关的一阶逻辑等值式，最后介绍前束范式，这是具有某种固定形式的一阶逻辑公式。后面会看到，一阶逻辑的自然推理系统中与量词有关的推理规则只能应用于前束范式。
3.4.1 一阶逻辑公式的逻辑等值
定义3.12如果一阶逻辑公式A和B在非逻辑符号集的任意解释及任意个体变
量指派函数下都有相同的真值，则称A和B逻辑等值(logicallyequivalent)，简称等值，记为A. B。通常也称A. B为逻辑等值式。
当在研究两个或一组一阶逻辑公式是否逻辑等值时，总假定所有公式是基于相同的非逻辑符号集和个体变量集构造。因此，后面通常不再给出构造一阶公式的非逻辑符号集和个体变量集，读者可从所研究公式的语法得到构造它们的非逻辑符号集应包括哪些个体常量、函数和谓词符号，以及个体变量集应包括哪些个体变量符号。特别地，在对公式进行约束变量改名或自由变量替换时，假定个体变量集总包含所需的新的个体变量符号。
与命题逻辑相同，两个一阶公式是否逻辑等值也可基于永真式判断，因为根据一阶公式逻辑等值的定义以及逻辑双蕴涵运算符的真值计算方法，可得到下面的定理。
定理3.3一阶逻辑公式A与B逻辑等值当且仅当一阶逻辑公式A～ B 是永真式。
例子3.16不难根据逻辑等值的定义证明有下面的量词交换逻辑等值式：设F是