Lógica de predicados
La lógica de predicados, también conocida como lógica de primer orden, es una extensión de la Lógica proposicional que nos permite expresar y razonar sobre las propiedades de objetos individuales y las relaciones entre ellos.
Todos los griegos son mortales.
Nicolai es griego.
Por tanto, Nicolai es mortal.
A diferencia de la lógica proposicional, la lógica de predicados nos permite validar este tipo de razonamiento mediante el uso de:
- Predicados (como 'ser griego' o 'ser mortal')
- Cuantificadores (para expresar 'todos')
- Constantes individuales (como 'Nicolai')"
Sintaxis
En lógica de predicados trabajamos con un dominio y tres elementos fundamentales:
- Símbolos de función (Σ): Define las funciones que podemos usar Por ejemplo: Σ = [c/0, f/1, g/2, h/3] donde:
- c/0: constantes (aridad 0)
- f/1: funciones unarias como padre(x)
- g/2: funciones binarias como suma(x,y)
-
h/3: funciones ternarias como entre(x,y,z)
-
Símbolos de predicado (PΣ): Define las relaciones que podemos expresar Por ejemplo: PΣ = {P/1, Q/2} donde:
- P/1: predicados unarios como esAlto(x)
-
Q/2: predicados binarios como mayorQue(x,y)
-
Cuantificadores: Nos permiten expresar afirmaciones sobre el dominio
- Cuantificador universal (∀): "para todo"
- ∀x P(x) significa "para todo x se cumple P(x)"
- Ejemplo: ∀x (Humano(x) → Mortal(x))
- Cuantificador existencial (∃): "existe"
- ∃x P(x) significa "existe al menos un x que cumple P(x)"
- Ejemplo: ∃x (Planeta(x) ∧ TieneVida(x))
La notación "f/n" indica que f es una función/predicado de aridad n.
Aridad
La aridad indica el número de argumentos que acepta una función o predicado: - Aridad 0: Constantes (c) - Aridad 1: Funciones unarias (f(x)) - Aridad 2: Funciones binarias (g(x,y)) - Aridad 3: Funciones ternarias (h(x,y,z))
Ejemplo: - esEstudiante(x) → aridad 1 - hijoDe(x,y) → aridad 2 - entre(x,y,z) → aridad 3
Reglas de Formación
- Términos:
- Toda constante es un término
- Toda variable es un término
-
Si f es una función de aridad n y t₁,...,tₙ son términos, entonces f(t₁,...,tₙ) es un término
-
Fórmulas atómicas:
-
Si P es un predicado de aridad n y t₁,...,tₙ son términos, entonces P(t₁,...,tₙ) es una fórmula atómica
-
Fórmulas compuestas:
- Toda fórmula atómica es una fórmula
- Si φ es una fórmula, entonces ¬φ es una fórmula
- Si φ y ψ son fórmulas, entonces (φ ∧ ψ), (φ ∨ ψ), (φ → ψ) son fórmulas
- Si φ es una fórmula y x es una variable, entonces ∀x φ y ∃x φ son fórmulas
Ejemplos Prácticos
-
Expresar "Todos los estudiantes son jóvenes": ∀x (Estudiante(x) → Joven(x))
-
Expresar "Existe algún estudiante que es alto": ∃x (Estudiante(x) ∧ Alto(x))
-
Expresar "Juan es más alto que todos los estudiantes": ∀x (Estudiante(x) → MásAltoQue(juan, x))
-
Expresar "Todo número tiene un sucesor": ∀x ∃y (Sucesor(x,y))
Errores Comunes
- No confundir ∀x ∃y con ∃y ∀x
- ∀x ∃y P(x,y): "Para cada x hay algún y..."
-
∃y ∀x P(x,y): "Hay algún y que sirve para todo x..."
-
Mantener los paréntesis necesarios
- Correcto: ∀x (P(x) → Q(x))
-
Incorrecto: ∀x P(x) → Q(x)
-
Usar variables ligadas correctamente
- Correcto: ∀x P(x) ∧ ∀x Q(x)
- Redundante: ∀x (P(x) ∧ Q(x))
Semántica
3. Semántica de la lógica de primer orden
El objetivo de la semántica es atribuir significado a los elementos de un lenguaje. En lógica proposicional se atribuye significado a una fórmula determinando su valor veritativo, verdadero o falso, en función del valor de los símbolos proposicionales que la formaban. En lógica de predicados, además, se tiene que determinar el valor de términos que representan a los individuos del universo del discurso y por eso se han de usar estructuras e interpretaciones.
Una Σ-estructura $$\mathcal{A}$$ se define como:
$$ \mathcal{A} = \left(A, { f^A \mid f \in F_\Sigma }, { P^A \mid P \in P_\Sigma }\right) $$
donde:
- $A$ es un conjunto no vacío denominado universo de discurso o dominio.
- ${ f^A \mid f \in F_\Sigma }$ es el conjunto de interpretaciones de las funciones $f$ en el lenguaje.
- ${ P^A \mid P \in P_\Sigma }$: Es el conjunto de interpretaciones de los predicados $P$ en el lenguaje.
Los significados de $\mathcal{A}$ son definidos a partir de estas estructuras.
La semántica en lógica de predicados nos dice cómo interpretar los símbolos y fórmulas para darles significado. Para ello necesitamos:
- Interpretación (A): Consiste en:
- Un conjunto no vacío A (el dominio)
- Para cada símbolo de función f/n en Σ, una función fᴬ: Aⁿ → A
- Para cada símbolo de predicado P/n en PΣ, una relación Pᴬ ⊆ Aⁿ
Ejemplo: Si queremos interpretar la fórmula Padre(juan, maría): - A podría ser el conjunto de todas las personas - Padre/2 se interpretaría como la relación real de paternidad - juan y maría se interpretarían como personas específicas
- Estado (σ):
- Asigna valores del dominio a las variables
- σ(x) nos dice qué elemento del dominio representa la variable x
Ejemplo: Si x representa personas: - σ₁(x) = Juan - σ₂(x) = María
- Evaluación: Para evaluar una fórmula necesitamos tanto la interpretación como el estado:
Ejemplo práctico:
Para la fórmula EsAlto(x):
- A = {personas}
- EsAltoᴬ = {personas que miden más de 1.80m}
- Si σ(x) = Juan y Juan mide 1.85m, entonces
Lema de Coincidencia
El Lema de Coincidencia nos dice que el valor de verdad de una fórmula solo depende de: 1. Cómo se interpreten los símbolos que aparecen en ella 2. Qué valores tengan sus variables libres
Ejemplo práctico: Consideremos la fórmula: ∀y (Mayor(x,y)) - Solo importa: * Cómo interpretemos Mayor/2 * Qué valor tenga x (porque es libre) * El dominio A para y (porque está cuantificada) - NO importa: * Valores de otras variables * Interpretación de otros predicados
Notación Práctica
Para representar estados usamos la notación: $$ \begin{bmatrix} x₁ & x₂ & \cdots & xₙ \ a₁ & a₂ & \cdots & aₙ \end{bmatrix} $$
Reglas de inferencia
Son válidas las reglas de inferencia que se utilizan en Lógica proposicional: modus ponens, Y-Eliminación, Y-Introducción, O-Introducción y Resolución. Se añaden nuevas, para lo que usaremos la Notación SUST:
Eliminación Universal (EU)
Para cualquier expresión α, variable v y término de base g:
$$\frac{\forall v \space \alpha}{Sust({v/g}, \alpha)}$$
Donde $Sust({v/g}, \alpha)$ significa sustituir v por g en α.
Ejemplo: - De $\forall x \space LeGusta(x, Marisco)$ - Podemos inferir $LeGusta(Juan, Marisco)$ sustituyendo x por Juan
Eliminación Existencial (EE)
Para toda expresión α, variable v y constante k:
$$\frac{\exists v \cdot \alpha}{Sust({v/k}, \alpha)}$$
Ejemplo: - De $\exists x \space Matar(x, Victima)$ - Podemos inferir $Matar(asesino, Victima)$
[!danger] En la eliminación existencial, la constante usada para sustituir la variable debe ser nueva para evitar inconsistencias. Esto se debe a que la oración existencial solo afirma que existe algún objeto que satisface una condición, y al eliminar el cuantificador estamos dando nombre a dicho objeto. Este nombre no debe haber sido usado previamente para referirse a otro objeto.
Introducción Existencial (IE)
Para toda expresión α, variable v que no esté en α, y término de base g que no esté en α:
$$\frac{\alpha}{\exists v \space Sust({g/v}, \alpha)}$$
Ejemplo: - De $LeGusta(Pepe, Marisco)$ - Podemos inferir $\exists x \space LeGusta(x, Marisco)$
Tips para Evitar estos Errores
- Para Eliminación Existencial:
- Siempre usa una constante que no aparezca en ninguna parte
-
Si tienes dudas, inventa un nombre completamente nuevo
-
Para Introducción Universal:
- Usa una variable nueva que no aparezca en las premisas
-
Asegúrate de que no estás usando propiedades específicas
-
Para Sustituciones:
- Identifica claramente qué variables están libres
-
Solo sustituye variables que no estén bajo cuantificadores
-
Para Orden de Cuantificadores:
- Piensa en ejemplos concretos
- Dibuja diagramas si es necesario
- Recuerda que el orden importa
Vease importancia de Cláusulas de Horn
Vease Modus ponens generalizado
Resolución
Se identifican en el enunciado: - el universo $A$ - las funciones $f^A$ - los predicados $P^A$ - los cuantificadores
Ejemplo:
Ramón es miope.
Cuando alguien es miope lo es su madre o su padre.
Todo el mundo ama a su padre y a su madre.
Por tanto, algún miope es amado por alguien.
$$ A = {personas, F= {MadreDe/1, PadreDe/1, Amado/2}, P = {EsMiope}} $$ Constante = r = ramón
- Formalizar en lenguaje lógico.
1. Eliminar símbolos de implicación (→)
- Regla: P → Q se convierte en ¬P ∨ Q
- Ejemplos:
- A → B se convierte en ¬A ∨ B
- (P ∧ Q) → R se convierte en ¬(P ∧ Q) ∨ R
- P → (Q → R) se convierte en ¬P ∨ (¬Q ∨ R)
2. Mover negaciones hasta fórmulas atómicas
Usar las leyes de De Morgan: - ¬(P ∧ Q) = ¬P ∨ ¬Q - ¬(P ∨ Q) = ¬P ∧ ¬Q - ¬(¬P) = P - ¬(∀x P(x)) = ∃x ¬P(x) - ¬(∃x P(x)) = ∀x ¬P(x)
3. Estandarizar variables (renombrar)
- Dar nombres únicos a variables bajo diferentes cuantificadores
- Ejemplo:
- ∀x P(x) ∧ ∀x Q(x) se convierte en ∀x₁ P(x₁) ∧ ∀x₂ Q(x₂)
4. Eliminar cuantificadores existenciales (Skolemización)
Reglas: 1. Si ∃x aparece al principio: reemplazar x por una constante nueva * ∃x P(x) → P(c) donde c es nueva 2. Si ∃x está dentro del alcance de ∀y₁,...,∀yₙ: reemplazar x por f(y₁,...,yₙ) * ∀y ∃x P(x,y) → ∀y P(f(y),y) donde f es nueva * ∀y₁ ∀y₂ ∃x P(x,y₁,y₂) → ∀y₁ ∀y₂ P(f(y₁,y₂),y₁,y₂)
5. Mover cuantificadores universales
- Mover todos los ∀ al inicio de la fórmula
- Ejemplo:
- (∀x P(x)) ∧ (∀y Q(y)) se convierte en ∀x ∀y (P(x) ∧ Q(y))
6. Eliminar conjunciones (∧)
- Separar las fórmulas unidas por ∧
- Ejemplo:
- P ∧ Q se convierte en dos cláusulas: P, Q
- (A ∨ B) ∧ C se convierte en: (A ∨ B), C
7. Convertir a conjunto de cláusulas
- Una cláusula es una disyunción de literales
- Cada literal es un predicado o su negación
- Ejemplo final:
- Cláusula 1: P(x) ∨ ¬Q(x)
- Cláusula 2: R(x,y) ∨ S(x)
- Cláusula 3: ¬T(x)
Ejemplo Completo: El caso de Ramón
Enunciado original
"Demuestra que la siguiente argumentación es correcta: - Ramón es miope - Cuando alguien es miope, o su padre o su madre también lo son - Todo el mundo ama a su padre y a su madre Por tanto, algún miope es amado por alguien"
Paso Preliminar: Formalización
Identificamos: - Universo: personas - Constantes: r (Ramón) - Funciones: * p(x): padre de x * m(x): madre de x - Predicados: * M(x): x es miope * A(x,y): x ama a y
Formalizamos: 1. M(r) 2. ∀x(M(x) → (M(p(x)) ∨ M(m(x)))) 3. ∀x(A(x,p(x)) ∧ A(x,m(x))) 4. Conclusión: ∃x∃y(A(y,x) ∧ M(x))
Negamos la conclusión para refutación: ¬∃x∃y(A(y,x) ∧ M(x))
Paso 1: Eliminar implicaciones
- M(r) [sin cambios]
- ∀x(¬M(x) ∨ M(p(x)) ∨ M(m(x)))
- ∀x(A(x,p(x)) ∧ A(x,m(x))) [sin cambios]
- ¬∃x∃y(A(y,x) ∧ M(x)) [sin cambios]
Paso 2: Mover negaciones
- M(r) [sin cambios]
- ∀x(¬M(x) ∨ M(p(x)) ∨ M(m(x))) [sin cambios]
- ∀x(A(x,p(x)) ∧ A(x,m(x))) [sin cambios]
- ∀x∀y(¬A(y,x) ∨ ¬M(x))
Paso 3: Estandarizar variables
- M(r) [sin cambios]
- ∀x₁(¬M(x₁) ∨ M(p(x₁)) ∨ M(m(x₁)))
- ∀x₂(A(x₂,p(x₂)) ∧ A(x₂,m(x₂)))
- ∀x₃∀y₁(¬A(y₁,x₃) ∨ ¬M(x₃))
Paso 4: Eliminar cuantificadores existenciales
No hay cuantificadores existenciales que eliminar.
Paso 5: Mover cuantificadores universales
Los cuantificadores universales ya están al inicio de cada fórmula.
Paso 6: Eliminar conjunciones
- M(r)
- ∀x₁(¬M(x₁) ∨ M(p(x₁)) ∨ M(m(x₁))) 3a. ∀x₂(A(x₂,p(x₂))) 3b. ∀x₂(A(x₂,m(x₂)))
- ∀x₃∀y₁(¬A(y₁,x₃) ∨ ¬M(x₃))
Paso 7: Convertir a conjunto de cláusulas
- {M(r)}
- {¬M(x₁) ∨ M(p(x₁)) ∨ M(m(x₁))}
- {A(x₂,p(x₂))}
- {A(x₂,m(x₂))}
- {¬A(y₁,x₃) ∨ ¬M(x₃)}
Resolución
Ahora podemos empezar el proceso de resolución:
- M(r) con ¬M(x₁) ∨ M(p(x₁)) ∨ M(m(x₁))
- Unificación: x₁/r
-
Resolvente: {M(p(r)) ∨ M(m(r))}
-
M(p(r)) ∨ M(m(r)) con ¬A(y₂,x₂) ∨ ¬M(y₂)
- Unificación: y₂/p(r)
-
Resolvente: {M(m(r)) ∨ ¬A(x₂,p(r))}
-
M(m(r)) ∨ ¬A(x₂,p(r)) con ¬A(y₃,x₃) ∨ ¬M(y₃)
- Unificación: y₃/m(r)
-
Resolvente: {¬A(x₂,p(r)) ∨ ¬A(x₃,m(r))}
-
¬A(x₂,p(r)) ∨ ¬A(x₃,m(r)) con A(x₄,p(x₄))
- Unificación: x₂/r, x₄/r
-
Resolvente: {¬A(x₃,m(r))}
-
¬A(x₃,m(r)) con A(x₄,m(x₄))
- Unificación: x₃/r, x₄/r
- Resolvente: { } (cláusula vacía)
La obtención de la cláusula vacía demuestra que el argumento es válido.
1.4 Skolemización
Eliminar cuantificadores existenciales: - Si no hay universales: usar constante - Si hay universales: usar función Skolem
Ejemplo:
∀x ∃y P(x,y)
⇒ ∀x P(x,f(x)) // f es función Skolem
2. Unificación
La unificación encuentra sustituciones que hacen iguales dos expresiones.
Reglas de Unificación
- f(t₁,...,tₙ) y f(s₁,...,sₙ) unifican si t₁,...,tₙ unifican con s₁,...,sₙ
- Una variable unifica con cualquier término que no la contenga
- Las constantes unifican solo consigo mismas
Ejemplos de Unificación
Expresión 1 Expresión 2 Unificador
P(x,a) P(b,y) {x/b, y/a}
P(x,x) P(y,a) {x/a, y/a}
P(x,f(x)) P(a,y) {x/a, y/f(a)}
No Unificables
P(x,f(x)) P(x,y) No unifica (occur check)
P(x,a) P(x,b) No unifica (a≠b)
Tips y Trucos
- Para la Forma Clausal:
- Seguir el orden de los pasos es crucial
-
Tener cuidado con la Skolemización
-
Para la Unificación:
- Comprobar siempre el occur check
-
Mantener las sustituciones lo más simples posible
-
Para la Resolución:
- Empezar con cláusulas unitarias
- Dibujar un árbol de resolución
- Buscar el camino más corto a la contradicción
Errores Comunes
- En Skolemización:
- Olvidar dependencias de cuantificadores universales
-
Usar funciones cuando basta con constantes
-
En Unificación:
- Olvidar el occur check
-
Unificar términos no unificables
-
En Resolución:
- No estandarizar variables
- Resolver sobre variables ligadas