一阶逻辑

数理逻辑的最基本部分或基础部分。一阶逻辑除研究复合命题的逻辑性质及推理关系外，还把命题分析成组成命题的非命题成份，即个体词、谓词和量词，揭示简单命题的形式结构——命题形式，研究它们的逻辑性质和规律，重点是研究量词的逻辑性质和关于量词的推理规律。一阶逻辑包含命题逻辑作为子系统，但为了研究方便，也由于命题逻辑具有某些重要性质，通常把它作为一个独立的系统先行研究。一阶逻辑又称为一阶谓词逻辑或狭义谓词逻辑。G．弗雷格在1879年建立了第一个完整的一阶逻辑系统。G．皮亚诺，B．罗素等人对一阶逻辑的发展作出了贡献。K．哥德尔等人系统深入地研究了一阶逻辑的元逻辑问题，证明了重要的定理。

最简单的命题，即所谓原子命题，都可分析成个体词和谓词两类成分。例如，在“5是素数”和“苏州在上海与南京之间”这两个命题中，“5”，“苏州”，“上海”，“南京”是个体词，“是素数”，“在…之间”是谓词。在逻辑中，一个论域中的元素称为个体，论域也称个体域。个体词是表示个体的符号，表示论域中任意个体的符号称为个体变元，表示某一论域中的一特定个体的符号称为个体常元。谓词表示个体的性质或个体间的关系。用符号x，y，z，…表示个体变元，用F，G表示谓词，上面举例的两个命题可表示成如下形式：F(x)，G(x，y，z)。性质(又称一元谓词或一元关系)可以看作是论域中元素的一个子集，即那些具有此性质的个体所成的集合。一个n元谓词(关系)F，是论域中个体的n元组(a，a，…，a)所成集合的一个子集，即使得F(a，a，…，a)为真的那些n元组所成的集合。

除个体词和谓词外，组成命题的成份还有量词。量词是命题中表示数量的词，分为全称量词和存在量词。例如，在命题“对任一自然数，都有一比它大的素数”，“任一”是全称量词，“有一”是存在量词。全称量词用符号后跟一个体变元表示，如x，读作“所有个体”或“对任一个体”，或简单地读作“所有x”，“任一x”。存在量词用符号后面跟一个体变元表示，如x，读作“存在个体”或“有一个体”，或简单地读作“存在x”，“有一x”。上面举例的命题的形式可表示如下：x(F(x)→y(G(y)∧H(x，y)))；设F(x)表示“x是自然数”，G(y)表示“y的素数”，H(x，y)表示“y大于x”，上述命题形式就表示命题：对于所有x，如果x是自然数，则有－y，y是素数并且y大于x。

从原子命题出发，应用量词和命题联结词，就可以构成任何复杂的命题。从原子命题的形式，经用量词符号和联结词的符号，就可构造出表示各种复杂命题的形式的公式。

只加在论域的个体上的量词，或者说，只约束个体变元的量词，称为一阶量词。一阶逻辑是只有一阶量词的逻辑。关于个体的性质或关系的谓词，则称为一阶谓词。如果量词加在一阶谓词，或者说，约束一阶谓词变元，就称为二阶量词。如“所有关系”、“有一关系”是二阶量词。此外还有更高阶的量词。相应的逻辑称为二阶逻辑，高阶逻辑。

一阶逻辑的公式经解释后就成为真或假的命题。一个解释由一个非空的个体域D和一个赋值v组成，记作(D，v)。对每一个体变元x，v都赋以D中的一个个体为值，对每一n元谓词符号F，v把F对应于D上的一n元关系。对于原子公式F(x，x，…，x)，如果v对x，x，…，xn赋与D中个体的n元组a，a，…，a为值，把F对应于D上的n元关系R，F(x，x，…，x)在此解释下就为命题R(a，a，…，a)。如果a，a，…，a对关系R成立，公式F(x，x，…，x)在此解释下成为一真命题，否则为假。对于公式xA(x)，设v对A的赋值，除x的外，已经给定，若对D中每一个体a，A(a)真，则xA(x)在解释(D，v)下为真，否则为假。对公式xA(x)，设A的赋值已经给定，若有－D中个体a，使A(a)真，xA(x)在解释(D，v)下为真，否则为假。联结词按通常的解释赋值。一个解释(D，v)也称为一个结构或模型。

一阶逻辑的公式分成常真的(普遍有效的)、可满足的以及不可满足的3类。一个公式A称为可满足的，如果有一解释，在此解释下，A为真。一个公式A称为普遍有效的，如果对任一解释，即对任一不空的个体域和任一赋值，A常为真。A常真记作A。一个公式A是不可满足的(常假)，当且仅当它的否定A普遍有效。普遍有效的公式表达逻辑规律。

上面说的解释、赋值、真假、普遍有效性和可满足性等，都是语义的概念。

普遍有效公式在一定意义上都是逻辑规律。为了系统地研究这类逻辑规律，需要对它们作整体的考虑，建立一阶逻辑的形式系统。一阶逻辑的形式系统，通常称为一阶谓词演算，也称为狭义谓词演算。形式系统的初始符号中包括等词=的称为带等词的一阶逻辑，不带等词的就称一阶逻辑。下面建立形式系统F。

一阶逻辑的形式系统F包括3个部分：它的语言，称为一阶语言，(逻辑)公理以及推演规则。

F的语言包括初始符号和形成规则两部分。初始符号有以下4类：①个体变元：x，y，z，…；②对每一n，n元的函数符号：f，g，…，个体常元：a，b，c，…，n元的谓词符号：F，G，H，…，其中有一个二元谓词符号=；③命题联结词，∧，∨，→，和量词符号和；④技术性符号：(，)及逗号，。

①、③两项和等词是逻辑符号，其它为非逻辑符号。

形成规则分项形成规则和合式公式形成规则。项形成规则规定怎样的初始符号序列是项。项是那些指示个体的表达式。合式公式形成规则规定怎样的初始符号序列是合式公式。合式公式经解释后是有意义的。在元语言中，使用下列元语言符号：①黑体的x，y，…，表示任意的个体变元，②t，t，…表示任意的项，③大写的X，Y，Z，…表示任意的符号的有序序列，④A，B，C，…表示任意的合式公式。

项形成规则：

①每一个体变元和个体常元是项；

②如果f是n元函数符号，t，…，t是项，则f(t，…，t)是项。

合式公式形成规则：

①若P是一n元谓词符号，t，…，t是项，则P(t，…，t)是合式公式，称为原子公式。

②如果X，Y是合式公式，则X，X∧Y，X∨Y，X→Y，XY是合式公式。

③如果X是合式公式，x是一个体变元，则xX，xX是合式公式。

合式公式简称公式。

F的公理分3组：

①命题联结词的公理 P的15条公理都是F的公理。公理中出现的A，B，C现在表示F中的任意公式(参见命题逻辑)。

②量词的公理

(16)xA(x)→A(t)，A(t)是以t替换x在A中的出现而得，t对于A(x)中的x是自由的。

(17)A(t)→xA(x)

③等词公理

(18)l=l

(19)t=t→(t=t→…(t=t→f(t，t，…，t)=f(t，t，…，t))…)

(20)t=t→(t=t…(t=t→(A(t，…，t)→A(t，…，t)))…)

F的推演规则

R1分离规则 从A→B和A可推出B。

R2后件概括规则 若x不在A中自由出现，从A→B(x)可推出A→xB(x)。

R3前件存在规则 若x不在B中自由出现，从A(x)→B可推出xA(x)→B。

F的定理可归纳地定义如下：

①F的公理都是F的定理。

②如果F的一个推演规则的前提是F的定理，则此规则的结论也是F的定理。

一阶逻辑系统F具有许多重要的元逻辑性质。可以验证，F的公理都是普遍有效的。从普遍有效的公式应用F的推演规则而得的公式也是普遍有效的。根据定理的定义，F的所有定理都是普遍有效的。即有：如果┝A，则A。这个性质称为可靠性或有效性。

从F的有效性也可得出F是协调的：不存在F中的公式A，A和A都是F的定理。

F的另一个重要性质是K．哥德尔所证明的完全性：凡是普遍有效的公式都是F的定理。这个定理称为哥德尔完全性定理。完全性定理还有一个更强的形式。设Φ是F的公式的集合。如果Φ是协调的，则Φ是可满足的，或者如果ΦA，则Φ┝A。

从上述完全性定理，可以推出紧致性定理和勒文海姆-司寇伦定理。这两个定理是模型论的基础性定理，对模型论的发展起重要的作用。这两个定理还刻划了一阶逻辑的特征：一阶逻辑是在运算，∧，∨下封闭的唯一满足紧致性定理和勒文海姆－司寇伦定理的逻辑。

一个具有以下形式的公式称为前束范式：QxQx…QxB。其中QxQx…Qx称为前束词，每一Qx是x或x，B中无量词。F的每一公式A，都有一个与它等值的前束范式。前束范式可用于对F的公式进行分类。此时可以只考虑前束范式中的量词，将它作为公式复杂性的一种测度。

前束范式可用于一阶逻辑的判定问题的研究。A．丘奇在1936年证明，一阶逻辑是不可判定的，但是某些特殊类型的公式是可判定的，而一些特殊类型的公式则不可判定。这时，就是按照公式的前束范式进行分类。王浩在1961年证明，具有xyzM(x，y，z)形式的一阶逻辑公式的集合是不可判定的。