Relación con Lógica

Como sabemos que un programa lógico dice lo que queremos que diga?

El significado de un programa lógico $P$ (o su modelo $M(P)$), es el conjunto de todos los hechos que podemos deducir de $P$.

Hay muchas reglas de inferencia

e.g., modus ponens, modus tolens, ...
$P \rightarrow Q$
$P$
---
$Q$

$P \rightarrow Q$
$\neg Q$
---
$\neg P$

La más estudiada es resolución: por ser completa (deduce todo lo que se puede - aunque en realidad es refutation complete) y correcta (todo lo que deduce es cierto).

El corazón del modelo de computación de programas lógicos es el algoritmo de unificación.

Ejemplo de resolución: $P \rightarrow Q$
$P \leftarrow$
---
$Q$

Un unificador de dos términos es una substitución que hace los dos términos iguales.

El unificador más general o mgu es un unificador tal que si existe otro unificador éste es más específico (el mgu es único).

Dada una cláusula $C$ con una literal $L_1$, del lado izquierdo y otra cláusula $D$ con una literal $L_2$ del lado derecho, tal que $L_1$ y $L_2$ tienen un $mgu (\theta)$, podemos construir una nueva cláusula con la unión de $C$ y $D$ sin $L_1$ y $L_2$:

$((C - \{L_1\}) \wedge (D - \{L_2\})) \theta$

En general hay que encontrar instanciaciones por medio de unificación.

hijo(X,X) :- papa(Y,X).
papa(juan,juanito).
---------------------
hijo(juanito,juan).

alumno(X,progIA) :- estudia(X,prolog).
es_de_univ(X,Univ) :- alumno(A,Materia), imparte(Univ,Materia)

[B: X/A, progIA/Materia]

es_de_univ(B,progIA) :- estudia(B, prolog), imparte(Univ,progIA).

Para demostrar que algo es consecuencia lógica (i.e., $\cal T \models A$), se hace prueba por refutación (i.e., añadimos $\neg \cal A$ a $\cal T$ y demostramos que eso es inconsistente) $\cal A \wedge \cal T \vdash \Box$.

Cuando hacemos una querie, en realidad estamos buscando inconsistencias (es como agregar $\neg querie$ a nuestra teoría y demostrar (con resolución) una inconsistencia.

Cuando hay variables involucradas, obtenemos instanciaciones con valores particulares.

Teoria:                               Querie:

papa(juan,juanito).  (b)              ?- abuelo(X,Y).
papa(juan,juana).                     ?- papa(X,Z), papa(Z,Y).
papa(juanito,pepe).
papa(juanito,patricia). (a)
abuelo(A,B):- papa(A,C), papa(C,B).

Si tomamos la segunda cláusula con (a): ?- papa(X,juanito) [Y = patricia] Tomando ésta con (b): [X = juan, Y = patricia]

G = abuelo(X,Y)$\Theta_1$$\Theta_2$ = abuelo(juan,patricia).

El razonamiento con resolución es un proceso combinatorio. En general, hay muchas inferencias que se pueden hacer cada vez que se hace una.

Hay diferentes formas de control (i.e., escoger cual hacer). Lo más fácil es hacer deducciones en un orden fijo (aunque sea arbitrario): ésto es lo que hace Prolog

Existen otros (e.g., MRS) donde se puede expresar el control, sin embargo es más ineficiente.

Estrategia de Prolog:

• Escoge la meta más a la izquierda
• Busca secuencial con backtracking

Si hacemos el mismo ejemplo pero siguiendo la estrategia de Prolog:

?- papa(X,Y), papa(Z,Y) 
la primera con (b):
?- papa(juanito,Y)   [X = juan]
con la tercera:
[Y = pepe]

Otro ejemplo para ilustrar el caso más sencillo de backtracking:

gusta(maria,comida).
gusta(maria,vino).
gusta(juan,vino).

?- gusta(maria,X), gusta(juan,X).

En otras palabras, actúa como un stack (depth-first search).

Esto provoca que:

1. El orden de las reglas determina el orden en que las soluciones se encuentran
2. El orden de las metas (en los cuerpos de las reglas) determina el árbol de búsqueda.

hijo(X,Y) :- padre(Y,X), hombre(X).
hijo(X,Y) :- madre(Y,X), hombre(X).

abuelo(X,Z) :- padre(X,Y), padre(Y,Z).
abuelo(X,Z) :- padre(X,Y), madre(Y,Z).
abuelo(X,Z) :- madre(X,Y), padre(Y,Z).
abuelo(X,Z) :- madre(X,Y), madre(Y,Z).

Alternativa:
procreador(X,Y) :- madre(X,Y).
procreador(X,Y) :- padre(X,Y).

hijo(X,Y) :- procreador(Y,X), hombre(X).

abuelo(X,Z):- procreador(X,Y), procreador(Y,Z).

Disjunción:

P :- Q ; R.

P :- Q.
P :- R.

P :- Q, R ; S, T, U.
P :- (Q,R) ; (S,T,U).

Hacer trace de:

gusta(maria, comida).
gusta(maria,vino).
gusta(juan, vino).
gusta(juan, maria).

    ?- gusta(maria,X), gusta(juan,X).