Variable libre

Cet article est une ébauche concernant les mathématiques, l’informatique et la logique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En mathématiques, et dans d'autres disciplines comprenant des langages formels dont la logique mathématique, une variable libre est une notation qui spécifie à quelles places dans une expression une substitution peut avoir lieu. Elle s'oppose à la notion de variable muette (encore appelée variable liée).

En programmation informatique une variable libre est une variable référencée dans une fonction, qui n'est ni une variable locale, ni un paramètre de cette fonction.

En mathématiques

Vérifier si une variable (mathématique) dans un terme est libre ou bien est muette revient à tenter de satisfaire l'un des trois critères suivants^[1] :

• remplacer la variable étudiée par une autre « lettre » vierge (qui n'apparaît pas initialement dans l'expression). Si l'on obtient une expression synonyme alors la variable initiale était liée (α-conversion) ;
• s'il est possible de trouver une expression synonyme d'où la variable a complètement disparu, alors la variable est muette :

  ${\displaystyle {\begin{aligned}\int _{0}^{1}x\,\mathrm {d} x&={\frac {1}{2}}\\\sum _{k=0}^{5}{2^{k}}&=2^{0}+2^{1}+2^{2}+2^{3}+2^{4}+2^{5}=63\end{aligned}}}$

• repérer un signe qui rend la variable muette, on parle alors de signes mutificateurs :

  ${\displaystyle \sum _{x\in S}\quad \quad \prod _{x\in S}\quad \quad \int _{0}^{\infty }\cdots {\rm {d}}x\quad \quad \lim _{x\to 0}\quad \quad \forall x\quad \quad \exists x\quad \quad \lambda x\quad \quad \psi x}$

Exemples

Dans l'expression suivante la variable ${\displaystyle x}$ n'est pas libre (on dit qu'elle est liée), tandis que la variable ${\displaystyle y}$ est libre :

${\displaystyle \forall x,\ f(x)=f(y)}$.

Dans l'expression suivante la variable ${\displaystyle z}$ est liée, tandis que la variable ${\displaystyle x}$ est libre :

${\displaystyle \int _{0}^{1}z^{2}x\,\mathrm {d} z}$.

Dans l'expression qui suit x est une variable muette mais y est une variable libre car on « parle » de y :

${\displaystyle \int _{0}^{\infty }x^{y-1}{\rm {e}}^{-x}{\rm {d}}x}$.

Variables libres efficaces

La notion mathématique de variable efficace raffine celle de variable libre. Une variable libre est « inefficace »^{[réf. nécessaire]} lorsque la signification de l'expression dans laquelle elle intervient ne dépend pas de celle de l'objet qui instancie cette variable.

La variable x de l'expression x = x est « inefficace » car x est une variable libre (comme il n'existe aucun signe mutificateur) mais l'énoncé reste vrai quel que soit l'objet désigné par x.

L'expression suivante a en effet pour x, une variable libre efficace : x + 1 = 0.

En lambda-calcul

L'ensemble des variables libres en lambda-calcul, noté ${\displaystyle FV(t)}$, est défini par induction sur les λ-termes :

${\displaystyle FV(x)=\{x\}}$

${\displaystyle FV(tu)=FV(t)\cup FV(u)}$

${\displaystyle FV(\lambda x.t)=FV(t)\setminus \{x\}.}$

Exemples

Dans la fonction ${\displaystyle \lambda u.\lambda t.(uvt)}$, les variables ${\displaystyle u}$ et ${\displaystyle t}$ sont liées, tandis que la variable ${\displaystyle v}$ est libre. En effet,

${\displaystyle FV(uvt)=FV(u)\cup FV(v)\cup FV(t)=\{u,v,t\}}$

et donc

${\displaystyle FV(\lambda u.\lambda t.(uvt))=FV(\lambda t.(uvt))\setminus \{u\}=FV(uvt)\setminus \{u\}\setminus \{t\}}$

${\displaystyle \qquad \qquad \qquad \quad =\{u,v,t\}\setminus \{u\}\setminus \{t\}=\{v\}.}$

Notes et références

Voir aussi

• Fermeture (informatique)
• Clôture (mathématiques)
• Portée (informatique)
• Logique combinatoire

• Portail des mathématiques
• Portail de l’informatique