Variables libres y variables ligadas

Concepto en matemáticas o informática.

En matemáticas y en otras disciplinas que involucran lenguajes formales , incluyendo la lógica matemática y la informática , se puede decir que una variable es libre o ligada. Algunos libros más antiguos usan los términos variable real y variable aparente para variable libre y variable ligada , respectivamente. Una variable libre es una notación (símbolo) que especifica lugares en una expresión donde puede tener lugar la sustitución y no es un parámetro de esta o cualquier expresión contenedora. La idea está relacionada con un marcador de posición (un símbolo que luego será reemplazado por algún valor), o un carácter comodín que representa un símbolo no especificado.

En programación informática , el término variable libre se refiere a las variables utilizadas en una función que no son ni variables locales ni parámetros de esa función. El término variable no local suele ser un sinónimo en este contexto.

Una instancia de un símbolo variable está ligada , por el contrario, si el valor de ese símbolo variable ha sido ligado a un valor específico o rango de valores en el dominio del discurso o universo . Esto puede lograrse mediante el uso de cuantificadores lógicos, operadores de ligadura de variables o una declaración explícita de valores permitidos para la variable (como, por ejemplo, "...donde es un entero positivo"). Un símbolo variable en general está ligado si al menos una ocurrencia de él está ligada. ^{[1] pp.142--143} Dado que el mismo símbolo variable puede aparecer en múltiples lugares en una expresión, algunas ocurrencias del símbolo variable pueden ser libres mientras que otras están ligadas, ^{[1] p.78} por lo tanto, "libre" y "ligado" se definen primero para ocurrencias y luego se generalizan sobre todas las ocurrencias de dicho símbolo variable en la expresión. Independientemente de cómo se haga, la variable deja de ser una variable independiente de la que depende el valor de la expresión, ya sea que ese valor sea un valor de verdad o el resultado numérico de un cálculo o, más generalmente, un elemento de un conjunto de imágenes de una función. ${\displaystyle n}$

Si bien en muchos contextos se entiende el dominio del discurso, cuando no se ha dado un rango explícito de valores para la variable delimitada, puede ser necesario especificar el dominio para evaluar correctamente la expresión. Por ejemplo, considere la siguiente expresión en la que ambas variables están delimitadas por cuantificadores lógicos:

${\displaystyle \forall y\,\exists x\,\left(x={\sqrt {y}}\right).}$

Esta expresión se evalúa como falsa si el dominio de y son los números reales, pero es verdadera si el dominio son los números complejos. ${\displaystyle x}$ ${\displaystyle y}$

El término "variable ficticia" también se utiliza a veces para una variable ligada (más comúnmente en matemáticas generales que en informática), pero esto no debe confundirse con el concepto de variable ficticia, que tiene el mismo nombre pero no está relacionado , tal como se utiliza en estadística, más comúnmente en el análisis de regresión. ^{[2] p.17}

Ejemplos

Antes de dar una definición precisa de variable libre y variable ligada, se presentan a continuación algunos ejemplos que quizás aclaren estos dos conceptos más que la definición:

En la expresión

${\displaystyle \sum _{k=1}^{10}f(k,n),}$

n es una variable libre y k es una variable ligada; en consecuencia, el valor de esta expresión depende del valor de n , pero no hay nada llamado k de lo cual pueda depender.

En la expresión

${\displaystyle \int _{0}^{\infty }x^{y-1}e^{-x}\,dx,}$

y es una variable libre y x es una variable ligada; en consecuencia, el valor de esta expresión depende del valor de y , pero no hay nada llamado x de lo cual pueda depender.

En la expresión

${\displaystyle \lim _{h\rightarrow 0}{\frac {f(x+h)-f(x)}{h}},}$

x es una variable libre y h es una variable ligada; en consecuencia, el valor de esta expresión depende del valor de x , pero no hay nada llamado h de lo cual pueda depender.

En la expresión

${\displaystyle \forall x\ \exists y\ {\Big [}\varphi (x,y,z){\Big ]},}$

z es una variable libre y x e y son variables ligadas, asociadas a cuantificadores lógicos ; en consecuencia, el valor lógico de esta expresión depende del valor de z , pero no hay nada llamado x o y de lo cual pueda depender.

En términos más generales, en la mayoría de las demostraciones se utilizan variables ligadas. Por ejemplo, la siguiente demostración muestra que todos los cuadrados de los números enteros pares positivos son divisibles por ${\displaystyle 4}$

Sea un entero par positivo. Entonces existe un entero tal que . Como , tenemos que es divisible por ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n=2k}$ ${\displaystyle n^{2}=4k^{2}}$ ${\displaystyle n^{2}}$ ${\displaystyle 4}$

No sólo k sino también n se han utilizado como variables ligadas en su conjunto en la prueba.

Operadores de vinculación de variables

La siguiente

${\displaystyle \sum _{x\in S}\quad \quad \prod _{x\in S}\quad \quad \int _{0}^{\infty }\cdots \,dx\quad \quad \lim _{x\to 0}\quad \quad \forall x\quad \quad \exists x}$

son algunos operadores comunes de vinculación de variables . Cada uno de ellos vincula la variable x para un conjunto S.

Muchos de estos son operadores que actúan sobre funciones de la variable vinculada. En contextos más complicados, estas notaciones pueden resultar incómodas y confusas. Puede resultar útil cambiar a notaciones que hagan explícita la vinculación, como

${\displaystyle \sum _{1,\ldots ,10}\left(k\mapsto f(k,n)\right)}$

para sumas o

${\displaystyle D\left(x\mapsto x^{2}+2x+1\right)}$

para la diferenciación.

Explicación formal

Árbol que resume la sintaxis de la expresión ${\displaystyle \forall x\,((\exists y\,A(x))\vee B(z))}$

Los mecanismos de vinculación de variables se dan en diferentes contextos en matemáticas, lógica y ciencias de la computación. En todos los casos, sin embargo, son propiedades puramente sintácticas de expresiones y variables en ellas. Para esta sección podemos resumir la sintaxis identificando una expresión con un árbol cuyos nodos hoja son variables, constantes, constantes de función o constantes de predicado y cuyos nodos no hoja son operadores lógicos. Esta expresión puede entonces determinarse haciendo un recorrido en orden del árbol. Los operadores de vinculación de variables son operadores lógicos que se dan en casi todos los lenguajes formales. Un operador de vinculación Q toma dos argumentos: una variable v y una expresión P , y cuando se aplica a sus argumentos produce una nueva expresión Q( v , P ). El significado de los operadores de vinculación lo proporciona la semántica del lenguaje y no nos concierne aquí.

La vinculación de variables relaciona tres cosas: una variable v , una ubicación a para esa variable en una expresión y un nodo no hoja n de la forma Q( v , P ). Nota: definimos una ubicación en una expresión como un nodo hoja en el árbol sintáctico. La vinculación de variables ocurre cuando esa ubicación está debajo del nodo n .

En el cálculo lambda , xes una variable ligada en el término M = λx. Ty una variable libre en el término T. Decimos xque está ligada en My libre en T. Si Tcontiene un subtérmino , λx. Uentonces xes reenlazada en este término. xSe dice que esta ligadura interna anidada de "ensombrece" la ligadura externa. Las ocurrencias de xen Uson ocurrencias libres del nuevo x. ^[3]

Las variables enlazadas en el nivel superior de un programa son técnicamente variables libres dentro de los términos a los que están enlazadas, pero a menudo reciben un tratamiento especial porque se pueden compilar como direcciones fijas. De manera similar, un identificador enlazado a una función recursiva también es técnicamente una variable libre dentro de su propio cuerpo, pero recibe un tratamiento especial.

Un término cerrado es aquel que no contiene variables libres.

Expresiones de función

Para dar un ejemplo matemático, considere una expresión que define una función.

${\displaystyle f=\left[(x_{1},\ldots ,x_{n})\mapsto t\right]}$

donde t es una expresión. t puede contener algunas, todas o ninguna de las x ₁ , …, x _n y puede contener otras variables. En este caso decimos que la definición de función vincula las variables x ₁ , …, x _n .

De esta manera, las expresiones de definición de función del tipo que se muestra arriba pueden considerarse como el operador de enlace de variable, de manera análoga a las expresiones lambda del cálculo lambda . Otros operadores de enlace, como el signo de suma , pueden considerarse funciones de orden superior que se aplican a una función. Por ejemplo, la expresión

${\displaystyle \sum _{x\in S}{x^{2}}}$

Podría tratarse como una notación para

${\displaystyle \sum _{S}{(x\mapsto x^{2})}}$

donde es un operador con dos parámetros: una función de un parámetro y un conjunto sobre el que evaluar esa función. Los otros operadores enumerados anteriormente se pueden expresar de manera similar; por ejemplo, el cuantificador universal se puede considerar como un operador que evalúa la conjunción lógica de la función de valor booleano P aplicada sobre el conjunto (posiblemente infinito) S . ${\displaystyle \sum _{S}{f}}$ ${\displaystyle \forall x\in S\ P(x)}$

Lenguaje natural

Cuando se analizan desde la perspectiva de la semántica formal , se puede observar que los lenguajes naturales tienen variables libres y variables ligadas . En inglés, los pronombres personales como he , she , they , etc. pueden actuar como variables libres.

Lisa encontró su libro.

En la oración anterior, el pronombre posesivo her es una variable libre. Puede referirse a la mencionada Lisa o a cualquier otra mujer. En otras palabras, her book podría estar haciendo referencia al libro de Lisa (una instancia de correferencia ) o a un libro que pertenece a una mujer diferente (por ejemplo, el libro de Jane). Quien sea el referente de her se puede establecer de acuerdo con el contexto situacional (es decir, pragmático ). La identidad del referente se puede mostrar utilizando subíndices de coindexación donde i indica un referente y j indica un segundo referente (distinto de i ). Por lo tanto, la oración Lisa encontró su libro tiene las siguientes interpretaciones:

Lisa _{, encontré} su _libro . (interpretación #1: ella = de Lisa )

Lisa _{, encontré} su libro _J. (interpretación #2: ella = de una mujer que no es Lisa)

La distinción no es puramente de interés académico, ya que algunos idiomas tienen, de hecho, formas diferentes para her _i y her _j : por ejemplo, el noruego y el sueco traducen her _i correferente como sin y her _j no correferente como hennes .

El inglés permite especificar la correferencia, pero es opcional, ya que ambas interpretaciones del ejemplo anterior son válidas (la interpretación no gramatical se indica con un asterisco):

Lisa _{, encontré} su _propio libro. (interpretación #1: ella = de Lisa )

* Lisa _encontré su _propio libro. (interpretación #2: ella = de una mujer que no es Lisa)

Sin embargo, los pronombres reflexivos , como himself , themselves , etc., y los pronombres recíprocos , como each other , actúan como variables ligadas. En una oración como la siguiente:

Jane se lastimó .

El reflexivo themselves solo puede referirse al antecedente mencionado anteriormente , en este caso Jane , y nunca puede referirse a una persona femenina diferente. En este ejemplo, la variable themselves está ligada al sustantivo Jane que aparece en posición de sujeto . Para indicar la coindexación, la primera interpretación con Jane y themselves coindexadas es permisible, pero la otra interpretación donde no están coindexadas es agramatical :

Jane _se hizo daño a sí misma _. (interpretación #1: ella misma = Jane )

* Jane _se hizo daño _j . (interpretación #2: ella misma = una mujer que no es Jane)

La unión de correferencia se puede representar mediante una expresión lambda como se mencionó en la sección Explicación formal anterior. La oración con el reflexivo podría representarse como

(λ x . x lastimó x )Jane

en el que Jane es el argumento referente del sujeto y λx.x lastimó a x es la función predicativa (una abstracción lambda) con la notación lambda y x indicando tanto el sujeto semántico como el objeto semántico de la oración como vinculados. Esto devuelve la interpretación semántica JANE lastimó a JANE donde JANE es la misma persona.

Los pronombres también pueden comportarse de forma diferente. En la oración siguiente

Ashley la golpeó .

El pronombre her solo puede referirse a una mujer que no sea Ashley. Esto significa que nunca puede tener un significado reflexivo equivalente a Ashley se golpeó a sí misma . Las interpretaciones gramaticales y no gramaticales son:

* Ashley la golpeé _{. (} interpretación #1 : ella = Ashley )

Ashley, le pegué _{un puñetazo} . (interpretación #2: ella = una mujer que no es Ashley)

La primera interpretación es imposible. La gramática sólo permite la segunda interpretación.

De este modo, se puede observar que los reflexivos y los recíprocos son variables ligadas (conocidas técnicamente como anáforas ), mientras que los pronombres verdaderos son variables libres en algunas estructuras gramaticales, pero variables que no pueden ligarse en otras. El fenómeno de ligadura que se encuentra en las lenguas naturales fue particularmente importante para el gobierno sintáctico y la teoría de la ligadura (véase también: Ligadura (lingüística) ).

Véase también

• Cierre (informática)
• Lógica combinatoria
• Elevación de lambda
• Vinculación de nombres
• Alcance (programación)
• Alcance (lógica)

Referencias

1. WVO Quine, Lógica matemática (1981). Harvard University Press, 0-674-55451-5.
2. Robert S. Wolf, Un recorrido por la lógica matemática (2005). 978-0-88385-036-7
3. Thompson 1991, pág. 33.

• Thompson, Simon (1991). Teoría de tipos y programación funcional . Wokingham, Inglaterra: Addison-Wesley. ISBN 0201416670.OCLC 23287456  .
• Wolf, Robert S. (2005). Un recorrido por la lógica matemática . Vol. 30. Asociación Matemática de Estados Unidos. ISBN 978-0-88385-042-8.JSTOR  10.4169/j.ctt5hh94h .

Lectura adicional

• Gowers, Timothy ; Barrow-Green, June ; Leader, Imre , eds. (2008). The Princeton Companion to Mathematics . Princeton, Nueva Jersey : Princeton University Press . págs. 15–16. doi :10.1515/9781400830398. ISBN 978-0-691-11880-2. JSTOR  j.ctt7sd01. LCCN  2008020450. MR  2467561. OCLC  227205932. OL  19327100M. Zbl  1242.00016.