aiwiki.page
中文
数学 / 离散数学与逻辑 / free-variable

自由变量

自由变量指表达式中未受约束算子约束的变量;在线性代数中,指可自由选取作为解的参数的未知量。

21 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
逻辑学线性代数一阶逻辑模型论二元关系实数推理规则自然演绎自由变量

自由变量是指在所考察的表达式中不受算子约束的变量。在逻辑学中,变量的某次出现若不在约束该变量的量词或其他算子的作用域内,就是自由出现。它的解释由变量赋值或外围语境提供。在线性代数中,这个术语有一种相关但不同的含义:自由变量是指在对相容线性方程组的解进行参数化时,可以独立选取其值的未知量。因此,自由性是相对于某个表达式、约束语境或约束系统而言的,而不是变量名称本身固有的性质。

自由出现与约束出现

自由变量与约束变量的区别,更精确地说,是变量的各次出现之间的区别。在一阶逻辑中,全称量词 ∀x\forall x 和存在量词 ∃x\exists x 约束各自作用域内 xx 的出现,但其中受嵌套的同变量量词管辖的出现除外。

例如,在

∀x R(x,y),\forall x\,R(x,y),

中,xx 在 R(x,y)R(x,y) 中的出现是约束出现,而 yy 的出现是自由出现。这个公式表示,每个对象都与赋给 yy 的对象具有关系 RR。

同一个变量名在同一公式中可以既有自由出现,也有约束出现:

P(x)∧∃x Q(x).P(x)\land \exists x\,Q(x).

xx 在 P(x)P(x) 中的出现是自由出现;在 Q(x)Q(x) 中的出现则受 ∃x\exists x 约束。该量词的作用域不会向前延伸到第一个合取支。

自由性还取决于所考察的是哪个表达式。变量 xx 在子公式 R(x,y)R(x,y) 中是自由的,但当这个子公式出现在 ∀x R(x,y)\forall x\,R(x,y) 中时,它就是受约束的。

没有自由变量的公式称为语句或闭公式。至少含有一个自由变量的公式通常称为开公式。“闭”并不意味着“真”:闭公式在给定解释下可以为真,也可以为假。

形式定义

表达式 EE 的自由变量集合通常记为 FV⁡(E)\operatorname{FV}(E)。对于通常的一阶语法,这个集合采用递归方式定义。

对于项:

  • 若 xx 是变量,则 FV⁡(x)={x}\operatorname{FV}(x)=\{x\}。

  • 若 cc 是常量符号,则 FV⁡(c)=∅\operatorname{FV}(c)=\varnothing。

  • 若 ff 是 nn 元函数符号,则

    FV⁡(f(t1,…,tn))=⋃i=1nFV⁡(ti).\operatorname{FV}(f(t_1,\ldots,t_n)) = \bigcup_{i=1}^{n}\operatorname{FV}(t_i).

对于公式,原子公式的自由变量就是其各个实参项中出现的变量。否定不改变自由变量集合,二元逻辑联结词则取并集:

FV⁡(¬φ)=FV⁡(φ),\operatorname{FV}(\neg\varphi) = \operatorname{FV}(\varphi),
FV⁡(φ∧ψ)=FV⁡(φ)∪FV⁡(ψ).\operatorname{FV}(\varphi\land\psi) = \operatorname{FV}(\varphi)\cup\operatorname{FV}(\psi).

同样的并集规则也适用于析取和蕴涵。量词则从集合中去掉它所约束的变量:

FV⁡(∀x φ)=FV⁡(φ)∖{x},\operatorname{FV}(\forall x\,\varphi) = \operatorname{FV}(\varphi)\setminus\{x\},
FV⁡(∃x φ)=FV⁡(φ)∖{x}.\operatorname{FV}(\exists x\,\varphi) = \operatorname{FV}(\varphi)\setminus\{x\}.

例如,

FV⁡(∀x (R(x,y)→∃z S(z,x,w)))={y,w}.\operatorname{FV}\bigl(\forall x\,(R(x,y)\to\exists z\,S(z,x,w))\bigr) = \{y,w\}.

这些规则描述的是语法上的自由性。即使改变赋给某个变量的值始终不会改变公式的真值,这个变量也可能自由出现。例如,xx 在 x=xx=x 中是自由的,尽管在通常的带等号一阶逻辑中,这个公式在任何赋值下都为真。

解释与真值

在模型论中,求一个公式的真值通常既需要一个结构 M\mathcal M,用来解释其非逻辑符号,也需要一个变量赋值 ss,用来将论域中的元素赋给变量。记号

M,s⊨φ\mathcal M,s\models\varphi

表示 φ\varphi 在结构 M\mathcal M 中、赋值 ss 下得到满足。

只有赋给自由变量的值才可能影响满足关系。更确切地说,如果赋值 ss 和 s′s' 对 FV⁡(φ)\operatorname{FV}(\varphi) 中每个变量所赋的值都相同,那么

M,s⊨φ⟺M,s′⊨φ.\mathcal M,s\models\varphi \quad\Longleftrightarrow\quad \mathcal M,s'\models\varphi.

因此,语句在一个结构中的真值与变量赋值无关。

开公式可以描述一种二元关系,或更一般地,描述一个元组集合。在实数上,公式

x+y=0x+y=0

定义了满足 a+b=0a+b=0 的数对 (a,b)(a,b)。约束其中一个变量会改变所表达的陈述:

∃y (x+y=0)\exists y\,(x+y=0)

对赋给 xx 的任意实数值都得到满足,而

∀y (x+y=0)\forall y\,(x+y=0)

则对赋给 xx 的任何实数值都不满足。

自由变量也与逻辑推理规则的使用限制有关。在自然演绎中,全称引入规则要求满足一定条件,以确保被全称概括的变量不依赖于尚未解除的假设。如果没有这些条件,就可能把关于某个特定赋值对象的断言错误地推广为关于所有对象的断言。

代换与变量捕获

代换是用一个项替换某个变量的自由出现。代换必须保持自由出现与约束出现之间的区别。

设

φ=∃y R(x,y).\varphi=\exists y\,R(x,y).

直接将 xx 替换为 yy,会得到

∃y R(y,y).\exists y\,R(y,y).

插入的 yy 原本应保持自由,却变成了受约束的变量。这就是变量捕获,它通常会改变原本要表达的含义。

避免捕获的代换会先将约束变量改为一个新的名称:

∃y R(x,y)⇝∃z R(x,z).\exists y\,R(x,y) \quad\rightsquigarrow\quad \exists z\,R(x,z).

然后再将 xx 替换为 yy,就可以安全地得到

∃z R(y,z).\exists z\,R(y,z).

对约束变量进行一致的、避免捕获的重命名,称为 α重命名。仅有这种重命名差异的表达式称为 α等价。因此,∀x P(x)\forall x\,P(x) 和 ∀z P(z)\forall z\,P(z) 是 α 等价的,而 P(x)P(x) 和 P(z)P(z) 通常不是:它们的自由变量可能指向不同的赋值对象。

数学记号中的约束

约束现象遍见于数学,并不限于带量词的公式。在定积分

∫01f(x,a) dx,\int_0^1 f(x,a)\,dx,

中,xx 是受约束的积分变量,而 aa 仍是自由参数,前提是没有外围的约束算子约束它。将积分变量改为一个新的符号,不会改变这个积分:

∫01f(t,a) dt.\int_0^1 f(t,a)\,dt.

类似地,在

∑i=1nai,\sum_{i=1}^{n}a_i,

中,ii 是受约束的指标,而 nn 以及 aa 所代表的数据则由外围语境给出。

在集合论中,变量 xx 在集合描述式

{x∈A:P(x,y)},\{x\in A:P(x,y)\},

中受约束,而 yy 则是自由的,除非它在别处受到约束。因此,所得集合可能依赖于赋给 yy 的值。

这些例子说明了为什么约束变量也常被称为哑变量:只要重命名遵守作用域并避免捕获,改变它的名称就不会改变表达式所指的对象。

λ演算与程序设计语言

在λ演算中,抽象式 λx.M\lambda x.M 约束其主体 MM 中的 xx。自由变量的规则为

FV⁡(MN)=FV⁡(M)∪FV⁡(N),\operatorname{FV}(MN) = \operatorname{FV}(M)\cup\operatorname{FV}(N),
FV⁡(λx.M)=FV⁡(M)∖{x}.\operatorname{FV}(\lambda x.M) = \operatorname{FV}(M)\setminus\{x\}.

例如,

FV⁡(λx. x y)={y}.\operatorname{FV}(\lambda x.\,x\,y)=\{y\}.

没有自由变量的 λ 项称为闭项。避免捕获的代换对于下述归约规则至关重要:

(λx.M) N⟶M[x:=N].(\lambda x.M)\,N\longrightarrow M[x:=N].

在程序设计语言中,一个变量相对于某个函数体可能是自由的,但在外围作用域中却受到约束。在词法作用域下,例如表示 x↦x+yx\mapsto x+y 的匿名函数,会将 xx 作为参数,并从其外围环境中获取 yy。闭包(计算机科学)将可执行的函数代码与这类引用所需的环境关联起来。

因此,“自由变量”并不一定意味着“未定义的变量”。该变量可能在当前所考察的表达式之外有一个有效的绑定。

线性方程组中的自由变量

在线性方程组

Ax=b,A\mathbf x=\mathbf b,

中,经高斯消元法将系数矩阵化为行阶梯形后,不对应主元列的坐标就是自由变量。对于相容方程组,这些变量可以在所用的域(数学)中任意取值,而主元变量的值随之由它们确定。

例如,

x+2y−z=3x+2y-z=3

可以通过令 y=sy=s、z=tz=t 来参数化:

(x,y,z)=(3−2s+t, s, t).(x,y,z)=(3-2s+t,\ s,\ t).

这里,yy 和 zz 充当自由变量。与逻辑中的自由性不同,这里涉及的是方程所施加的关系,而不是约束算子的作用域。

若 AA 有 nn 列,且其矩阵的秩为 rr,则其标准行阶梯形参数化中有 n−rn-r 个自由变量。根据秩—零化度定理,这个数就是 AA 的零空间的维数。

当方程组相容时,其解集具有如下形式:

x=xp+v,v∈ker⁡A,\mathbf x=\mathbf x_p+\mathbf v, \qquad \mathbf v\in\ker A,

其中,xp\mathbf x_p 是一个特解。这个解集是具有 n−rn-r 个独立参数的仿射空间。

如果对未知量重新排序,或采用另一种参数化方式,自由坐标的选择可能改变,但其数量不变。此外,不相容方程组没有解,即使其系数矩阵存在非主元列也是如此。在这种情况下,非主元未知量并不能用于参数化任何解。