Autor Tema: Obtener las variables libres de una fórmula

0 Usuarios y 1 Visitante están viendo este tema.

26 Julio, 2011, 03:53 am
Leído 1406 veces

jdcc

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 12
  • Karma: +0/-0
  • Sexo: Masculino
¿Alguien mepodríadar el algoritmo para calcuar las variables libres que contiene una fórmula?

Gracias.

26 Julio, 2011, 10:28 am
Respuesta #1

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

La definición recursiva es la siguiente ( \( Var(\varphi) \) representa el conjunto de todas las variables, libres o no, de \( \varphi \) y \( Free(\varphi) \) el conjunto de sus variables libres):

Si \( \varphi \) es atómica (esto es, de la forma \( t_1=t_2 \) o \( Rt_1...t_n \)) entonces \( Free(\varphi)=Var(\varphi) \).

Si \( \varphi = \neg \psi \) entonces \( Free(\varphi) = Free(\psi) \)
Si \( \varphi = \psi_1 * \psi_2 \), donde * es cualquier conector binario (\( \wedge, \vee, \rightarrow, \leftrightarrow \)) entonces \( Free(\varphi) = Free(\psi_1) \cup Free(\psi_2) \)
Si \( \varphi = Qx \psi \) donde Q es un cuantificador (\( \exists, \forall \)) entonces \( Free(\varphi) = Free(\psi) - \{x \} \)

Con esto puedes calcular el conjunto de variables libres de cualquier fórmula. Por ejemplo, si \( \varphi = \exists x (Px \vee (Py \rightarrow \forall z Pz) \), tenemos \( Free(\varphi) = Free (Px \vee (Py \rightarrow \forall z Pz) - \{ x \} = (Free(Px) \cup Free(Py \rightarrow \forall z Pz)) - \{ x \} = ( \{ x \} \cup Free(Py) \cup Free( \forall z Pz) ) - \{x \} = ( \{x \} \cup \{y \} \cup ( Free(Pz) - \{z \} ) ) - \{x \} = ( \{ x, y \} \cup ( \{ z \} - \{ z \}) ) - \{x \} = \{ x,y \} - \{x \} = \{y \}  \)

, así que la única variable libre es y.

Por supuesto no hace falta ser tan explícito ni llegar a tal nivel de detalle, y de hecho en cuanto te has acostumbrado las variables libres y ligadas se ven a ojo, simplemente mirando qué variables caen bajo el alcance de un cuantificados (estas son las ligadas) y cuales no (estas son las libres).

Saludos

26 Julio, 2011, 02:55 pm
Respuesta #2

jdcc

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 12
  • Karma: +0/-0
  • Sexo: Masculino