22 Variables libres y variables ligadas ‣ Parte V Sintaxis de la logica de predicados ‣ Lógica‣ Parte V Sintaxis de la logica de predicados ‣ Lógica

Definición 22.1.

Sea $\displaystyle x$ un simbolo de variable que aparece en una formula $\displaystyle\varphi$ .

Decimos que una aparicion de $\displaystyle x$ en $\displaystyle\varphi$ es ligada si esta afectada por un cuantificador. En particular la aparicion de una variable justo despues de un cuantificador se considera ligada.
Decimos que una aparicion de $\displaystyle x$ en $\displaystyle\varphi$ es libre si no es ligada.
Decimos que una variable $\displaystyle x$ es libre en la formula $\displaystyle\varphi$ si tiene alguna aparicion libre.
Decimos que una variable $\displaystyle x$ es ligada en la formula $\displaystyle\varphi$ si no es libre, es decir, si todas sus apariciones son ligadas.

Definición 22.2.

Sea $\displaystyle\varphi$ una formula. Decimos que es:

Abierta si hay alguna variable que aparece libre en $\displaystyle\varphi$ .
Cerrada si no es abierta, es decir, si todas las variables que aparezcan en $\displaystyle\varphi$ son ligadas.

Ejemplo.

$\displaystyle\forall x(P(x)\rightarrow Q(x))\wedge R(x)$

Las 3 primeras apariciones de $\displaystyle x$ son ligadas. La cuarta es libre. La formula es abierta.
$\displaystyle\forall x(P(x)\rightarrow Q(x)\wedge R(x))$

Las 4 apariciones de $\displaystyle x$ son ligadas. La formula es cerrada.
$\displaystyle\exists x(P(x)\wedge Q(y))\vee\forall y(P(y)\rightarrow Q(x))$

Las 2 primeras apariciones de $\displaystyle x$ son ligadas. La tercera es libre. La primera aparicion de $\displaystyle y$ es libre. Las 2 ultimas son ligadas. La formula es abierta.
$\displaystyle\exists x\forall y((P(x)\wedge Q(y))\vee(P(y)\rightarrow Q(x)))$

Todas las apariciones de $\displaystyle x$ e $\displaystyle y$ son ligadas. La formula es cerrada.

Observación.

Estamos interesados, sobre todo, en formulas cerradas. Siempre usaremos formulas cerradas para formalizar enunciados. Las formulas abiertas aparecen porque son necesarias como pasos intermedios para poder dar la definicion recursiva de formula.

Ejemplo.

Definir por recursion una funcion que, dada una formula cualquiera de la logica de predicados, devuelva el conjunto formado por todas las variables libres de la formula.

Empezamos definiendo una funcion que devuelva las variables de un termino.

	$\displaystyle var\colon\mathcal{{T}}$	$\displaystyle\longrightarrow\mathcal{{P}}(V)$
	$\displaystyle t$	$\displaystyle\longmapsto\text{conjunto de variables de t}$

donde $\displaystyle V=\{x\mid x\text{ es un simbolo de variable}\}$ .

1.

Terminos atomicos:

Si $\displaystyle c$ es simbolo de constante: $\displaystyle var(c)=\varnothing$ .

Si $\displaystyle x$ es simbolo de variable: $\displaystyle var(x)=\{x\}$ .
2.

Terminos compuestos:

Si $\displaystyle f$ es un simbolo de funcion de aridad $\displaystyle n\geq 1$ y $\displaystyle t_{1},t_{2},\ldots,t_{n}$ son terminos, $\displaystyle var(f(t_{1},t_{2},\ldots,t_{n}))=\bigcup_{i=1}^{n}var(t_{i})$ .

Ahora definimos

	$\displaystyle lib\colon\mathcal{{F}}_{1}$	$\displaystyle\longrightarrow\mathcal{{P}}(V)$
	$\displaystyle\varphi$	$\displaystyle\longmapsto\text{cjto de variables libres de }\varphi$

3.

Formulas atomicas:

$\displaystyle lib(\top)=lib(\perp)=lib(p)=\varnothing$ donde $\displaystyle p$ es simbolo de proposicion atomica.

Si $\displaystyle P$ es un simbolo de predicado de aridad $\displaystyle n\geq 1$ y $\displaystyle t_{1},t_{2},\ldots,t_{n}$ son terminos: $\displaystyle lib(P(t_{1},t_{2},\ldots,t_{n}))=\bigcup_{i=1}^{n}var(t_{i})$

$\displaystyle lib((t_{1}=t_{2}))=lib(t_{1})\cup lib(t_{2})$
4.

Negacion:

Si $\displaystyle\varphi\in\mathcal{{F}}_{1}\Rightarrow lib(\neg\varphi)=lib(\varphi)$
5.

Conectiva binaria:

Dados $\displaystyle\varphi,\psi\in\mathcal{{F}}_{1}\Rightarrow lib((\varphi\circ\psi% ))=lib(\varphi)\cup lib(\psi)$
6.

Cuantificadores:

Sea $\displaystyle\varphi$ una formula y $\displaystyle x$ un simbolo de variable:

$\displaystyle lib(\forall x\varphi)=lib(\varphi)\setminus\{x\}$

$\displaystyle lib(\exists x\varphi)=lib(\varphi)\setminus\{x\}$

Ejemplo.

Definir por recursion una funcion que, dada una formula cualquiera de la logica de predicados, devuelva el conjunto formado por todas las variables ligadas de la formula.

	$\displaystyle lig\colon\mathcal{{F}}_{1}$	$\displaystyle\longrightarrow\mathcal{{P}}(V)$
	$\displaystyle\varphi$	$\displaystyle\longmapsto\text{conjunto de las variables ligadas de }\varphi$

1.

Formulas atomicas:

Si $\displaystyle\varphi$ es atomica $\displaystyle\Rightarrow lib(\varphi)=\varnothing$
2.

Negacion:

$\displaystyle\varphi\in\mathcal{{F}}_{1}\Rightarrow lig(\neg\varphi)=lig(\varphi)$
3.

Conectiva binaria:

$\displaystyle\varphi,\psi\in\mathcal{{F}}_{1}\Rightarrow lig((\varphi\circ\psi% ))=(lig(\varphi)\cup lig(\psi))\setminus(lib(\varphi)\cup lib(\psi))$
4.

Cuantificadores:

$\displaystyle\varphi\in\mathcal{{F}}_{1},x$ variable.

$\displaystyle lig(\forall x\varphi)=lig(\exists x\varphi)=lig(\varphi)\cup\{x\}$