3. Programación Lógica

Importancia de la Programación Lógica

La Programación Lógica permite a los ingenieros resolver problemas declarativos donde se definen las relaciones entre entidades y las condiciones necesarias, dejando que el **motor de inferencia** deduzca automáticamente la solución. Es indispensable para:

Inteligencia Artificial

Sistemas expertos, procesamiento de lenguaje natural (PLN) y bases de conocimiento.

Análisis Gramatical

Parsing automático de sintaxis en compiladores e intérpretes mediante gramáticas de cláusulas definidas (DCG).

Consultas Complejas

Búsqueda en grafos, deducción de dependencias complejas y verificación de teoremas.

1. Repaso de la Lógica de Primer Orden (FOL)

A diferencia de la lógica proposicional, la Lógica de Primer Orden expresa la estructura interna de las proposiciones utilizando objetos, propiedades y relaciones.

Términos: Constantes (ej. juan), Variables (ej. X) y Funciones (ej. padre_de(X)).
Predicados: Expresan relaciones o propiedades que devuelven un valor verdadero/falso (ej. hermano(X, Y)).
Cuantificadores: Universal (∀ – «Para todo») y Existencial (∃ – «Existe al menos uno»).
Conectivos Lógicos: Conjunciones (∧), Disyunciones (∨), Implicaciones (→) y Negaciones (¬).

2. Unificación y Resolución

Son los dos pilares algorítmicos que permiten computar respuestas a partir de premisas lógicas.

Unificación

Proceso de encontrar un Sustituto Unificador MÁS General (MGU) que haga idénticas a dos expresiones atómicas.

Ejemplo de Unificación:
Término 1: padre(X, maria)
Término 2: padre(juan, Y)
MGU (Sustitución): { X = juan, Y = maria }
Resultado Unificado: padre(juan, maria)

Principio de Resolución (Robinson)

Regla de inferencia sintáctica que demuestra por contradicción (refutación). Dada la presencia de P ∨ Q y ¬P ∨ R, permite deducir la cláusula resolvente: Q ∨ R.

3. Cláusulas de Horn

Una Cláusula de Horn es una fórmula lógica formada por una disyunción de literales con **a lo sumo un literal positivo**.

Hecho (Sin antecedente)

A (1 literal positivo, 0 negativos). Afirmación incondicional.

Regla (Definida)

A ← B1 ∧ B2 ∧ ... ∧ Bn (1 literal positivo: A, el resto negativos).

Consulta / Objetivo (Goal)

← B1 ∧ B2 (0 literales positivos, todos negativos). Busca ser refutada.

4. Resolución SLD

SLD (Selective Linear Definite clause resolution) es la regla de inferencia utilizada por los lenguajes de programación lógica como Prolog para ejecutar programas compuestas por cláusulas de Horn definitivas.

S (Selective): Selecciona un literal objetivo de la meta actual.
L (Linear): Sigue un camino resolviendo consecutivamente desde la última meta generada.
D (Definite): Opera exclusivamente sobre Cláusulas Definidas (Horn).

Esquema Visual de Ejecución SLD:

Meta Inicial: ?- abuelo(juan, Z).
↓ (Aplica regla: abuelo(X,Y) :- padre(X,W), padre(W,Y). [X=juan, Y=Z])
Sub-metas: ?- padre(juan, W), padre(W, Z).
↓ (Unifica con Hecho: padre(juan, pedro). [W=pedro])
Sub-meta 2: ?- padre(pedro, Z).
↓ (Unifica con Hecho: padre(pedro, maria). [Z=maria])
Resultado: ÉXITO Cláusula Vacía (□) -> Z = maria

5. Programación Lógica con Cláusulas de Horn

En el lenguaje **Prolog**, la base de conocimiento se estructura directamente usando la sintaxis de las Cláusulas de Horn:

% Base de Conocimiento (Hechos)
padre(juan, pedro).
padre(pedro, maria).
padre(pedro, luis).

% Regla (Cláusula Definida de Horn)
hermano(X, Y) :- padre(P, X), padre(P, Y), X \== Y.
abuelo(X, Y) :- padre(X, Z), padre(Z, Y).

% Consulta (Goal)
% ?- abuelo(juan, Quien).
% Respuesta: Quien = maria ; Quien = luis.

Ejercicios Prácticos de Refuerzo

Ejercicio 1 (Unificación): Encuentra el MGU entre los términos f(X, g(Y)) y f(a, g(b)).

Solución:
MGU: { X = a, Y = b }
Ambas expresiones quedan unificadas como: f(a, g(b)).

Ejercicio 2 (Forma de Horn): Convierte la implicación lógica (P ∧ Q) → R a una sintaxis tipo Prolog.

Solución:
En lógica estándar: R ∨ ¬P ∨ ¬Q (1 solo literal positivo: R).
En sintaxis de Horn / Prolog: R :- P, Q.

Ejercicio 3 (Prolog – Relaciones): Define en Prolog una regla recursiva ancestro(X, Y) partiendo del predicado padre(X, Y).

% Caso Base: Un padre es un ancestro
ancestro(X, Y) :- padre(X, Y).

% Caso Recursivo: X es ancestro de Y si X es padre de Z y Z es ancestro de Y
ancestro(X, Y) :- padre(X, Z), ancestro(Z, Y).

Examen de Conocimientos (15 Preguntas)

1. ¿Qué es una Cláusula de Horn?

Una disyunción de literales con máximo un literal positivo. Una conjunción de literales totalmente positivos. Una fórmula proposicional sin variables ni cuantificadores.

2. ¿Cuál es el propósito del proceso de Unificación?

Convertir código fuente Prolog en ensamblador binario. Encontrar una sustitución de variables que iguale dos expresiones sintácticas. Eliminar la recursión de un predicado lógico.

3. La resolución SLD se caracteriza por ser:

Una estrategia no determinista aplicada solo a lógica proposicional. Una regla de inferencia lineal y selectiva para cláusulas definitivas. Un método de evaluación perezosa en lenguajes funcionales.

4. Un «Hecho» en Prolog representa una Cláusula de Horn con:

1 literal positivo y 0 literales negativos. 0 literales positivos y varios negativos. Únicamente literales negados.

5. ¿Qué significa MGU en el contexto de la unificación?

Minimum Graph Unifier Most General Unifier (Unificador Más General) Main Global Unit

6. La resolución por refutación intenta demostrar una meta:

Negando la meta y buscando llegar a una contradicción (cláusula vacía). Evaluando numéricamente sus variables en tiempo de compilación. Construyendo una tabla de verdad exhaustiva.

7. En Prolog, las variables se identifican porque:

Comienzan siempre con una letra mayúscula o guion bajo (_). Tienen un símbolo `$` al principio. Están encerradas entre comillas simples.

8. ¿Qué representa el símbolo `:-` en Prolog?

Una asignación de variable mutable. Una condicional lógica / implicación hacia la izquierda (←). Un operador aritmético de división entera.

9. ¿Cuál de las siguientes afirmaciones sobre la Lógica de Primer Orden (FOL) es CORRECTA?

Permite cuantificar sobre predicados y relaciones directamente. Incluye objetos, propiedades, relaciones y cuantificadores (∀, ∃). No soporta el uso de funciones complejas.

10. Si intentamos unificar `p(X, a)` con `p(b, Y)`, ¿cuál es el MGU?

{ X = a, Y = b } { X = b, Y = a } No son unificables.

11. En un árbol de resolución SLD, el éxito de una consulta se logra al alcanzar:

Una cláusula vacía (nodo nulo o □). Un bucle infinito de reglas. Una pila llena de variables no asignadas.

12. ¿Cuál es el orden predeterminado en que Prolog evalúa las reglas en su Búsqueda SLD?

De abajo hacia arriba y de derecha a izquierda. De arriba hacia abajo (base de conocimiento) y de izquierda a derecha (sub-metas). Aleatorio mediante algoritmos genéticos.

13. ¿Qué ocurre si intentamos unificar una variable `X` con el término `f(X)` sin la regla del «Occur Check»?

Se genera una estructura de término o bucle infinito. El programa falla devolviendo un error sintáctico. Se asigna automáticamente `X = 0`.

14. Una Consulta u Objetivo (Goal) en Cláusulas de Horn posee:

0 literales positivos (todos son literales negativos). Exactamente 2 literales positivos. Múltiples literales con conectivos `→` únicamente.

15. ¿Cuál es una aplicación clave de la Programación Lógica?

Renderizado de gráficos 3D en tiempo real. Sistemas expertos y motor de inferencia de conocimientos. Controladores de entrada/salida de bajo nivel.

Olga Fortiz