量词是逻辑学中用于指明某个条件在对象论域内成立范围的表达式。一阶逻辑的两种基本量词是全称量词和存在量词:前者记作 ,意为“对于每一个”;后者记作 ,意为“至少存在一个”。因此, 表示论域中的每一个对象都满足 ,而 则表示论域中至少有一个对象满足该条件。量化将含有变量的表达式转化为关于对象的陈述,而无须逐一指明这些对象的名称。
量词在数学、形式推理和语言的逻辑分析中不可或缺。例如,量词可以区分“每个方程都有某个解”与“存在一个对象能解所有方程”这两个断言,后者比前者强得多。量词的解释取决于论域、算子的位置和作用域,以及变量所取值的对象类型。除通常的全称量化和存在量化外,逻辑系统还使用表达唯一性、数量阈值、无穷性,或对性质与关系进行量化的量词。
历史发展
对量化的研究早于符号逻辑。在亚里士多德的三段论理论中,命题的分类部分依据其量:全称命题涉及某个类的所有成员,特称命题则涉及其中的某些成员。“所有人都会死”和“有些人是哲学家”便是这两种形式的例子。亚里士多德的三段论系统地阐述了这类命题之间的推理,但其标准形式并不具备现代谓词逻辑所特有的不受限制的变量约束和嵌套量化能力。
十九世纪的一项决定性进展,是将命题视为其论元位置可由变量占据的表达式。戈特弗里德·威廉·莱布尼茨早先就曾致力于建立用于推理的符号演算体系,而乔治·布尔则发展了处理类与命题的代数方法。这些工作为现代逻辑的形成奠定了背景,但要分析包含多个量词的关系,还需要超越传统主谓框架的技术。“每个人都仰慕某个人”这样的句子包含两个论元位置,并允许表达依赖关系,而仅仅对单个主词项进行分类,并不足以恰当地表示这些关系。
戈特洛布·弗雷格于1879年出版的《概念文字》提出了一个形式系统,能够对变量进行量化,并具备表达嵌套全称量化的手段。其二维记法与现今的符号体系差异显著,但它明确揭示了数学论证的逻辑结构。查尔斯·桑德斯·皮尔士及其合作者在代数传统内独立发展了量化方法;其中,O. H. 米切尔于1883年以及皮尔士于1885年的工作尤为重要。朱塞佩·皮亚诺在十九世纪九十年代提出的逻辑记法,推动了存在量词符号 的确立。此后,现代教科书逐渐统一采用使用 和 的线性记法,不过其他记法约定仍然存在。
二十世纪的研究将量化公式的语法与它们在数学结构中的解释区分开来。阿尔弗雷德·塔斯基对满足关系进行了系统的语义研究,而库尔特·哥德尔则于1930年证明了一阶逻辑的完备性。哥德尔完备性定理表明,每个在所有结构中都有效的一阶语句,都能在适当的演绎演算系统中得到形式证明。与此同时,关于形式算术与不可判定性的研究表明,精确的量词记法并不能使每一个数学问题都能通过机械程序来判定。
这段历史也说明了为什么“量化”的内涵不限于一对符号。其核心创新在于提供了一种方法,用以在复杂表达式中表示全称性、存在性和依赖关系。后来,语言学、计算领域和数学基础研究的发展,将这种方法扩展到了新的领域和新类型的量词。
语法、辖域与变量约束
在一阶语言中,如果 是公式, 是变量,那么 和 也都是公式。表达式 是这里所示量词的辖域。量词约束其辖域内相应变量的出现,但如果中间有另一个量词在更小的局部范围内约束了同一变量,则这些出现不受外层量词约束。因此,括号及其他分组约定是逻辑结构的一部分,而不仅仅是排版辅助手段。
变量的某次出现如果不受相应量词约束,就称为自由出现;否则称为约束出现。在
中, 在 中的出现是自由出现,在 中的出现是约束出现,而 的出现是自由出现。自由与约束是变量各次出现的性质:同一个变量符号在同一公式中可以既有自由出现,也有约束出现。没有自由变量的公式称为语句或闭公式。含有自由变量的公式可以表达一个条件,而该条件是否满足取决于赋予这些变量的值。
约束变量的名称通常无关紧要。例如, 和 表达相同的条件。这种重命名通常称为 α 转换。只有在保持约束关系不变时,这种转换才是合法的。如果将 中的约束变量改为 ,就会得到 ,从而捕获原本自由出现的 ,改变公式的含义。用一个项替换自由变量时也会遇到同样的问题:替换操作必须避免意外地使该项中的变量受到无关量词的约束。
限定量化范围的记法在数学中尤为常见:
在通常的单类一阶逻辑中,它们分别是下列公式的简写:
蕴涵与合取之间的区别至关重要。全称语句对 的元素施加条件,但不要求每个对象都属于 。存在语句则要求有一个对象既属于 ,又满足 。
语言也可以采用不同的类别,例如人、日期和数,并由变量所属的类别限定其取值范围。在解释某个特定的形式系统时,这不只是记法上的区别:系统的规则必须规定允许哪些类别、各类别的论域,以及这些论域是否可以为空。在所有这些情形下,明确的约束约定都能避免普通文字表述可能遗留的歧义。
结构中的解释
一阶量词的标准语义采用一个论域为 的结构 ,并为其中的关系符号、函数符号和常量符号指定解释。变量赋值 将每个变量对应到 中的一个元素。记号 表示,在赋值 下, 在 中得到满足。这一框架属于模型论,它精确刻画了公式与使公式为真的条件之间的区别。
令 表示这样一个赋值:除将 对应到 外,其余均与 相同。基本量词的语义条款为
以及
这些条款量化的是对象,而不只是为对象命名的表达式。结构中可能包含一些元素,而其语言中并没有为这些元素单独命名的名称。
论域可以改变同一公式的真假。语句
在具有通常次序的自然数中为真,但在有限非空线性序中为假。同样, 在有理数中为假,而在实数中为真。因此,仅凭符号本身无法确定真假:论域以及对运算和关系的解释都是不可或缺的。
标准的一阶语义通常要求论域非空。这一约定使 成为有效式。如果允许空论域,那么在空结构中,全称语句为真,而存在语句为假,因此该蕴涵在其中便不再有效。不过,在通常的非空结构中,受限的全称语句仍可能空真。如果 没有任何元素, 就为真,因为不存在违反 的元素;这并未断言 中是否存在元素。
对于语句而言,由于没有自由变量,其满足与否与变量赋值无关。对于开放公式而言,只有赋予其自由变量的值才会影响其满足与否。如果一个语句在相关类型的每个结构中都为真,就称其为逻辑有效的;相比之下,在某一个结构中为真是一个较弱的、依赖于解释的概念。这一区别是语义论证和形式证明系统的共同基础。
量词的次序与逻辑等价
嵌套量词的次序体现了依赖关系。比较
与
前者允许所选的 随 而变化;后者则要求存在同一个 ,对每个 都成立。在采用通常大小次序的整数域上, 为真,而 为假。用自然语言来说,“每个人都有自己仰慕的人”并不一定意味着“有一个人受到所有人的仰慕”。
相邻的同类量词可以交换次序:
不同种类的量词通常不能交换。蕴涵式
是有效的,但其逆命题并不有效。这里的区别不在于计算过程中碰巧先考虑哪个对象,而在于是否必须由同一个见证对象统一满足要求,还是允许使用不同的见证对象。
在经典逻辑中,否定会使两种基本量词相互转换:
这些是德摩根定律在量化表达式中的对应形式。否认每个对象都具有某种性质,就是断言存在一个反例;否认有任何对象具有这种性质,就是说每个对象都不具有这种性质。反复应用这些等价关系,就能解释为什么对含有多个交替量词的定义取否定时,既要将每个量词转换为另一种量词,也要否定最终的条件。
量词也遵循分配律,但并非在所有情况下都能分配:
相应地,将 对析取进行分配则不成立:每个整数不是偶数就是奇数,但既不是所有整数都是偶数,也不是所有整数都是奇数。存在量化通常也不能对合取进行分配,因为分别满足两个条件的见证对象未必是同一个对象。
将量词移过另一个表达式时,需要留意自由变量。若 在 中不自由出现,那么在标准的非空论域语义下,
若不满足这一条件,移动量词就可能使变量的某些出现不再受约束,或使其被捕获,从而改变命题。因此,量词的变换不仅要遵循看似熟悉的代数模式,还受到句法上的附加条件约束。
演绎系统中的量词
量词规则说明全称命题和存在命题如何进入形式证明。在自然演绎中,全称消去规则允许从 推出 ,前提是代入项 不会造成变量捕获。例如,已知每个群元素都有逆元,就可以推断某个特定元素有逆元。这条规则适用于任何允许代入的项,无论该项是否指称一个经过特别选取的对象。
全称引入规则的推理方向相反,但需要附加限制。要证明 ,推导须针对任意参数 确立 。该参数不得出现在推导所依赖的、尚未撤销的假设中,以免这些假设对它作出特殊限定。否则,就可能从“ 是偶数”推出“每个对象都是偶数”。这一限制将数学中“选取任意对象,而不是选取具有某种未经证明的特殊性质的对象”这一要求形式化。
存在引入规则允许从 推出 。例如,给出一个大于 的具体素数,就能确立这样的素数存在。存在消去规则则更为微妙。从 出发,证明可以临时对一个新参数假设 ,并由此推出结论 。这一结论不得依赖该参数的具体身份,而且该参数必须满足相应的新鲜性条件。这样,论证就能确立 ,而不会误将存在性前提视为指明了某个先前已命名的特定对象。
类似的限制在相继式演算中表现为特征变量条件。另一种表述方式可以采用公理模式和概括规则,但其根本问题相同:必须区分针对任意对象的推导与针对满足特殊假设的对象的推导。这些条件对于可靠性至关重要;所谓可靠性,是指在预期语义下,可推导的结论确实是其前提的逻辑后承。
量词的处理方式也与其所在的逻辑体系相互关联。在直觉主义逻辑中, 的构造性证明被理解为给出一个见证对象,以及该对象满足条件的证明。布劳威尔—海廷—柯尔莫哥洛夫解释将全称命题的证明解释为一种适用于任意输入的方法。经典逻辑中的量词等价式并非全都仍然成立: 仍等价于 ,但 一般不能推出 。未能确立普遍成立,并不一定就能构造出一个反例。
数学定义与依赖关系
量词的排列形式往往承载着数学定义的核心内容。函数 在 处连续,当且仅当
这里, 的选取可以依赖于 ,而点 则由上下文中的陈述固定。一旦选定 ,该蕴涵就必须对每一个符合条件的 成立。量词的顺序表达了对所有邻近输入的控制要求,而不只是针对某个便于处理的输入。
逐点连续与一致连续性的区别,在于依赖关系不同。要在集合 上处处连续,量词的排列形式是
而一致连续性要求
在第二种排列形式中,同一个 必须适用于整个 。函数 在 上连续,但并不一致连续:两个输入可以任意接近,而它们的平方值之差仍不小于某个固定的正数。在每个有界闭区间上,这个函数则是一致连续的。
逐点收敛与一致收敛的区别也具有相同的结构。 在 上逐点收敛于 ,是指
一致收敛则将 放在选取 之后。对于 上的 ,其逐点极限在小于 的点处为 ,在 处为 。这种收敛并不一致,因为对于每个固定的 ,总能选取小于 的点,使 任意接近 。
存在性与唯一性结合了不同的量词要求。记号 读作“存在唯一的 ”,通常是以下公式的缩写:
它并不是带等号的普通一阶逻辑中额外的原始符号。因此,断言解唯一存在的定理包含两个部分:存在一个满足条件的对象,并且任意两个满足该条件的对象都必定相同。
许多其他定义同样是量词结构的简写。单射函数满足一个关于输入对的全称蕴涵条件;满射函数则要求每个目标值都有一个对应的输入作为见证。在概率论和分析学中,“几乎处处”允许存在一个零测例外集,从而限定了全称断言的适用范围。不能把它当作不受限制的“处处”:所用的测度以及对例外集的要求,都是额外的数学条件。
范式、见证与斯科伦化
如果一个含量词的公式中,所有量词都集中在开头的前缀中,后面接着一个不含量词的公式(称为母式),那么该公式就处于前束范式。例如:
在论域非空的经典一阶逻辑中,每个公式都可以转换为等价的前束公式。转换过程包括:在适当之处消去蕴涵,利用量词的对偶关系将否定向内推进,重命名约束变量以避免冲突,以及在满足相应自由变量条件的前提下将量词向外移。
前束形式让量词交替变得清晰可见,但并不会消除其重要性。前缀 与 仍然表达不同的依赖关系。前束形式也未必是计算上最高效的表示方式:移动量词可能掩盖公式的局部结构,也可能引入一些本可通过更细致的转换加以避免的依赖关系。逻辑范式是一种分析工具,并不保证证明会更简短。
斯科伦化用新的函数项替换存在量词约束的变量,这些函数项表示相应的见证。例如,
被替换为
其中, 是一个新引入的函数符号。自变量 记录了见证对前面那个全称量词所约束变量的可能依赖。而对于
替换后的公式则是 ,其中 是一个新引入的常量,因为同一个见证必须对所有 都适用。
斯科伦化通常并非原语言内的等价变换,因为转换后的公式包含新符号。它的核心性质是保持可满足性:在通常的经典元理论中,一个语句有模型,当且仅当其斯科伦化形式有模型。对于转换后语句的模型,只需略去新增符号的解释,就能得到原语句的模型。反过来,通过选取见证,可以为新函数提供解释。对于任意无限结构,这种选取通常需要在允许作出相关选择的集合论背景中加以论证。
这一区别将逻辑中的见证函数与选择公理联系起来,但二者不应混为一谈。集合论中关于每个满足相应条件的集合族都有选择函数的陈述,是一项实质性的原则;它并不是一种纯粹的逻辑推理,不能仅凭任意给定的关系,就断定原论域中已经存在相应的函数对象。扩充语言中新引入的函数符号扮演的是另一种角色。
斯科伦化在自动推理中具有核心地位,因为它将显式涉及存在量词的推理转化为使用项的推理。结合将母式转换为子句的步骤,它为基于归结的证明过程提供了支持。即使原来的存在量词已不再写出,所得的项仍然保留着有关见证依赖关系的信息。
表达能力的局限与量词消去
一阶逻辑的表达能力在很大程度上来自量词,但量词也有一些明确的局限。公式的量词秩是其中量词的最大嵌套深度。例如, 的量词秩为 ,而 的量词秩为 。这一度量既不同于量词总数,也不同于全称量化与存在量化之间的交替次数。
量词秩在结构比较中十分重要。埃伦费希特—弗赖塞博弈刻画了结构在量词秩有界的一阶语句上的一致性:对于具有相同关系符号表的结构,复制者在 轮博弈中存在必胜策略,当且仅当这些结构对所有量词秩不超过 的语句给出相同的真值。这类博弈将有关公式的问题转化为如何匹配有限次选取的元素、同时保持这些元素之间可观察到的关系的问题。它们提供了一种系统的方法,用于证明某个给定性质无法用一阶逻辑定义。
某些理论支持量词消去:在该理论的所有模型中,每个公式都等价于指定语言中的某个无量词公式。对于实闭域,在有序环语言中消去量词,可以将带量词的多项式条件化为多项式等式与不等式的布尔组合。例如,
等价于 。塔斯基的工作确立了这一理论的量词消去性质和可判定性,为实数上多项式条件的推理提供了精确的逻辑基础。
量词消去既相对于理论,也相对于语言而言。公式可能借助某些公理得到简化,而这些公理在任意结构中并不一定成立;添加适当的关系符号,也可能使原本无法在原语言中实现的量词消去成为可能。此外,可判定性并不意味着每个输入都能得到高效处理:有效的量词消去过程可能具有极高的计算复杂度。
紧致性定理揭示了另一种局限。在固定的符号表中,不存在一个一阶语句能够恰好刻画该符号表下的所有有限结构。假如存在这样的语句,那么对每个正整数 ,都加入一个要求至少有 个不同元素的语句,所得语句集的每个有限子集都有模型,但整个语句集却没有模型。紧致性排除了这种情况。一个无穷的一阶语句集可以通过包含上述所有下界要求来保证模型是无限的,这也说明了理论与单个语句为何具有不同的表达能力。
勒文海姆—斯科伦定理对无限基数的控制给出了相关限制。可数语言中的一阶理论只要有无限模型,就也有可数无限模型。因此,普通的一阶量化无法仅凭在某个不可数模型中成立的公理,就强制其论域的基数恰好等于实数集的基数。
高阶量词与广义量词
一阶变量的取值范围是论域中的个体。在二阶逻辑中,还可以引入变量,其取值范围是该论域上的性质、关系或函数。像 这样的公式,是对一元性质 进行量化,而不是对另一个与 同类的个体进行量化。这里的区别在于语义类型,而不在于对象的大小:一阶集合论可以将集合作为个体进行量化,而不会因此成为二阶逻辑。
在完全语义下,二阶一元关系变量的取值范围是个体论域的所有子集,而 元关系变量的取值范围是所有 元关系。这使得一些一阶逻辑无法表达的命题得以表述。二阶归纳公理与适当的算术公理相结合,可以在同构意义下唯一刻画自然数结构。然而,完全二阶逻辑并不存在能够涵盖其所有有效式的可靠、完备且有效的证明演算。
在亨金语义下,高阶变量的取值范围是指定的集合族,而不一定是相应元数的所有关系。这使得我们可以用多类一阶逻辑的方法来处理高阶逻辑,并重新获得相应的完备性定理。代价是,断言归纳法对所有可用性质都成立的公式,其量化范围未必涵盖完全的集合论意义下的每一个子集。因此,除非明确说明所采用的语义约定,否则“对所有性质进行量化”这一说法并不完整。
广义量词扩展了量化所能表达的含义。带等号的普通一阶逻辑可以通过引入三个两两不同的见证对象,表达“至少有三个对象满足 ”。任何固定的有限数量门槛都可以用类似方式处理。相比之下,对于任意结构,“有无穷多个对象满足 ”无法由单个普通一阶公式统一表达。专门的无穷量词增添了这种表达能力。
自然语言中的限定词促使人们研究涉及两个集合的广义量词。在有限论域上,“大多数 是 ”可以解释为
这里, 限定了比较的范围, 则给出了所断言的性质。将“大多数”扩展到无限论域需要额外的解释;仅凭有限计数,无法确定究竟应采用基数比较、某种测度,还是依赖语境的标准。
另一些扩展改变的是依赖模式,而不只是见证对象的数量。分支量词和依赖逻辑可以规定,某个见证对象依赖于一个全称量化的变量,却不依赖于另一个;普通量词前缀的线性排列并不总能忠实表达这种约束。这类系统将量化与博弈论、信息约束以及高阶逻辑的表达能力联系起来。
计算、数据库与自然语言
在显式表示的有限论域上,可以通过逐一搜索对象来求值含量词的公式。全称量化检查每个候选对象,一旦找到反例便判为假;存在量化则在找到见证对象时判为真。对于固定的公式,这提供了一种直接的求值方法,不过嵌套量词可能需要考察大量赋值组合。在无限论域上,同样的解释通常无法转化为可执行的穷举搜索。
量化布尔公式提供了一个格外清晰的计算场景,其变量的取值范围是两个真值。尽管每个量词只有两种可能的赋值,任意交替的量词仍使其真值判定问题成为 PSPACE 完全问题。普通的命题可满足性问题询问是否存在使公式为真的赋值;量化布尔公式则允许存在量化与全称量化的赋值选择交替进行。其递归求值过程可以看作一场有限博弈:存在方力求无论全称方如何选择,最终的布尔条件都为真。
自动定理证明器采用多种互补策略。归结过程使用子句、代换和斯科伦项;语义树过程根据公式的逻辑形式将其展开;可满足性模理论求解器则将逻辑搜索与专门的数学理论相结合。含量词的公式往往需要实例化启发式方法,因为选择用哪些项进行代换可能成为搜索的主要开销。一般的一阶逻辑有效性问题是不可判定的,不过,完备的证明搜索过程最终能够为每个有效语句找到证明。
关系数据库赋予量化以具体的操作含义。查询某位客户是否有订单,就是对订单记录进行存在量化。查询某家供应商是否提供全部必需零件,则使用全称量化,通常通过检查是否不存在缺少相应供货记录的必需零件来实现:
经典关系演算提供了逻辑基础,但在实际使用 SQL 时需要谨慎:NULL 引入了“未知”这一真值,因此,对于涉及缺失值的表达式,直接套用经典二值逻辑中的等价关系可能会失效。
在语言语义学中,辖域可以解释“有一位审稿人读了每篇论文”这类句子的不同解读。一种解读要求有同一位审稿人读过所有论文;另一种解读则允许不同论文由不同审稿人阅读。这一区别对应于 与 的区别,并需对审稿人和论文施加适当限制。词语在语法上的排列顺序并不总能唯一确定语义辖域。
自然语言还区分量化意义与会话暗示。“有些参与者完成了”在逻辑上与所有参与者都完成了相容,尽管在会话中可能暗示“有些完成了,但并非全部”。同样,“每位参与者”通常指语境中相关的一组人,而不是所有地方的每一位参与者。因此,形式分析会区分量词本身、量词的限制成分、其辖域内的谓词,以及语境所提供的语用假设。