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

Definition 22.1.

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

•

Decimos que una aparicion de $x$ en $\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 $x$ en $\varphi$ es libre si no es ligada.
•

Decimos que una variable $x$ es libre en la formula $\varphi$ si tiene alguna aparicion libre.
•

Decimos que una variable $x$ es ligada en la formula $\varphi$ si no es libre, es decir, si todas sus apariciones son ligadas.

Definition 22.2.

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

•

Abierta si hay alguna variable que aparece libre en $\varphi$ .
•

Cerrada si no es abierta, es decir, si todas las variables que aparezcan en $\varphi$ son ligadas.

Example 22.3.

•

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

Las 3 primeras apariciones de $x$ son ligadas. La cuarta es libre. La formula es abierta.
•

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

Las 4 apariciones de $x$ son ligadas. La formula es cerrada.
•

$\exists x(P(x)\wedge Q(y))\vee\forall y(P(y)\rightarrow Q(x))$

Las 2 primeras apariciones de $x$ son ligadas. La tercera es libre. La primera aparicion de $y$ es libre. Las 2 ultimas son ligadas. La formula es abierta.
•

$\exists x\forall y((P(x)\wedge Q(y))\vee(P(y)\rightarrow Q(x)))$

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

Remark 22.4.

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.

Example 22.5.

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 $V=\left\{x\mid x\text{ es un simbolo de variable}\right\}$ .

1.

Terminos atomicos:

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

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

Terminos compuestos:

Si $f$ es un simbolo de funcion de aridad $n\geq 1$ y $t_{1},t_{2},\ldots,t_{n}$ son terminos, $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

[resume]
1.

Formulas atomicas:

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

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

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

Negacion:

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

Conectiva binaria:

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

Cuantificadores:

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

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

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

Example 22.6.

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 $\varphi$ es atomica $\Rightarrow lib(\varphi)=\varnothing$
2.

Negacion:

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

Conectiva binaria:

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

Cuantificadores:

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

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