自由变量和约束变量

(重定向自自由變量和約束變量

数学和其他涉及形式语言的学科中,包括数理逻辑计算机科学自由变量是在表达式中用于表示一个位置或一些位置的符号,某些明确的代换英语Substitution_(logic)可以在其中发生,或某些运算(比如总和量化)可以在其上发生。这个概念有关于占位符(它是以后会被文字串英语String literal所替换),或表示未指定符号的通配符,但更加深入和复杂。

变量x成为约束变量,比如

对于所有 x,(x + 1)2 = x2 + 2x + 1。

存在x,使得 x2 = 2。

在任何这种命题中,是否使用x或其他什么字母在逻辑上不重要。但是,在复合命题的其他地方再次使用同一个字母可能导致冲突。就是说,自由变量变成了约束的,并在支持公式的格式化的进一步工作中在某种意义上“退休”了。

例子

在陈述自由变量约束变量(或虚变量)的严格定义之前,我们會給出一些例子,使这两个概念比定义看起來更加清楚:

在表达式

 

中y是自由变量而x是约束变量(或虚变量);因此这个表达式的值依赖于y的值。

在表达式

 

中x是自由变量而y是约束变量;因此这个表达式的值依赖于x的值。

在表达式

 

中y是自由变量而x是约束变量;因此这个表达式的值依赖于y的值。

在表达式

 

中x是自由变量而h是约束变量;因此这个表达式的值依赖于x的值。

在表达式

 

中z是自由变量而x和y是约束变量;因此这个表达式的真值依赖于z的值。

变量约束算子

下列的

 

都是变量约束算子,它们都约束变量x。

形式解释

变量约束机制出现在数学、逻辑和计算机科学中的不同情況中,但是在所有情形下它们是其中的表达式和变量的纯粹语法性质。本节中我们用叶子节点是变量、函数常量或谓词常量,而节点是逻辑运算符的树,识别表达式来总结语法。变量约束的运算符是几乎出现在所有形式语言中的逻辑运算符。没有它们的语言实际上要么是非常缺乏表達能力,要么非常难于使用。约束的运算符 Q 接受两个参数:变量v和表达式P,把 Q 应用于它的参数時就會生成新表达式 Q(v, P) 。约束运算符的意义由这个语言的语义提供而不是我们现在关心的。

 
 

变量约束有关于三个事情:变量v,这个变量在表达式中的位置a,和形成 Q(v, P) 的节点n。注意: 我们定义在表达式中位置为在这个语法树中的叶子节点。变量约束在这个位置在节点n之下的时候发生。

举个數學的例子,考虑定义了一个函数的表达式

 

这里的t是一个表达式。t可以包含某些、所有的、或者不包含x1, ..., xn的任意一個,并可以包含其他变量。在这种情况下我们称函数的定义约束了这些变量 x1, ..., xn

λ演算中,如果x是项M = λ x. T中的约束变量,而且是T中的自由变量,则我们称x在M中是约束的,在T中是自由的。如果T包含一个子项 λ x . U,则x在这个项中是再约束的。这种嵌套的、内层的x的约束被称为外层约束的“阴影”。 x在U中的出现是新x的自由出现。

在程序顶层的变量约束在技术上在它们所约束的项之内是自由变量,但是经常特殊对待,因为它们可以被编译为固定地址。类似的,约束于递归函数的标识符被称为在它归属的函数体内是自由变量但要特殊对待。

封闭项是不包含自由变量的项。

参见

引用

A small part of this article was originally based on material from the Free On-line Dictionary of Computing and is used with permission under the GFDL. Most of what now appears here is the result of later editing.