Fundamentos de inteligencia artificial

Paradigma l´gico
o
L´gica proposicional
o
Resoluci´n
o

Programaci´n L´gica
o o
Eduardo Bonelli
Departamento de Computaci´n
o
FCEyN
UBA

10 de octubre, 2006

Eduardo Bonelli

Programaci´n L´gica
o
o

Paradigma l´gico
o
L´gica proposicional
o
Resoluci´n
o

Introducci´n
o
Prolog

Paradigma l´gico
o

Se basa en el uso de la l´gica como un lenguaje de
oprogramaci´n
o
Se especifican
ciertos hechos y reglas de inferencia
un objetivo (“goal”) a probar

Un motor de inferencia trata de probar que el objetivo es
consecuencia de los hechos y reglas
Es declarativo: se especifican hechos, reglas y objetivo sin
indicar c´mo se obtiene ´ste ultimo a partir de los primeros
o
e
´

Eduardo Bonelli

Programaci´n L´gica
o
o

Paradigma l´gico
oL´gica proposicional
o
Resoluci´n
o

Introducci´n
o
Prolog

Prolog

Lenguaje de programaci´n basado en este esquema que fue
o
introducido a fines de 1971 (cf. “The Birth of Prolog”,
A. Colmerauer y P. Roussel, www.lif-sud.univ-mrs.fr/∼colmer/)
Los programas se escriben en un subconjunto de la l´gica de
o
primer orden
El mecanismo te´rico en el que se basa es el m´todo de
o
eresoluci´n
o
Para motivar y comprender este mecanismo primero lo vamos
a estudiar en el ´mbito de la l´gica proposicional
a
o

Eduardo Bonelli

Programaci´n L´gica
o
o

Paradigma l´gico
o
L´gica proposicional
o
Resoluci´n
o

Introducci´n
o
Prolog

Prolog

Ejemplo de programa PROLOG
habla(ale,ruso).
habla(juan,ingles).
habla(maria,ruso).
habla(maria,ingles).seComunicaCon(X,Y):-habla(X,L),habla(Y,L),X\=Y
Ejemplo de goal
seComunicaCon(X,ale)

Eduardo Bonelli

Programaci´n L´gica
o
o

Paradigma l´gico
o
L´gica proposicional
o
Resoluci´n
o

Introducci´n
o
Prolog

Nuestro enfoque

1

L´gica proposicional (Clase 1/4)
o

2

M´todo de resoluci´n para l´gica proposicional (Clase 1/4)
e
o
o

3

M´todo de resoluci´n para l´gica de primerorden (Clase 2/4)
e
o
o

4

Cl´usulas de Horn y resoluci´n SLD, programaci´n l´gica
a
o
o o
(Clase 3/4)

5

Int´rprete para MiniProlog (Clase 4/4)
e

Eduardo Bonelli

Programaci´n L´gica
o
o

Paradigma l´gico
o
L´gica proposicional
o
Resoluci´n
o

Sintaxis
Valuaciones, Satisfactibilidad, Tautolog´
ıas
Forma normal conjuntiva

Sintaxis de la l´gicaproposicional
o
Dado un conjunto V de variables proposicionales, podemos definir
inductivamente al conjunto de f´rmulas proposicionales (o
o
proposiciones) (Prop) de la siguiente manera:
1

Una variable proposicional P0 , P1 , . . . es una proposici´n
o

2

Si A, B son proposiciones, entonces:
¬A es una proposici´n
o
A ∧ B es una proposici´n
o
A ∨ B es una proposici´n
o
A ⊃ B es unaproposici´n
o
A ⇐⇒ B es una proposici´n
o

Ejemplos: A ∨ ¬B, (A ∧ B) ⊃ (A ∨ A)

Eduardo Bonelli

Programaci´n L´gica
o
o

Paradigma l´gico
o
L´gica proposicional
o
Resoluci´n
o

Sintaxis
Valuaciones, Satisfactibilidad, Tautolog´
ıas
Forma normal conjuntiva

Valuaciones
Definici´n
o
Una valuaci´n es una funci´n v : V → {T, F} que asigna
o
o
valores de verdad a las variablesproposicionales
Una valuaci´n satisface una proposici´n A si v |= A donde:
o
o
v |= P sii
v |= ¬A sii

v (P) = T
v |= A

v |= A ∨ B sii

v |= A o v |= B

v |= A ∧ B sii

v |= A y v |= B

v |= A ⊃ B sii

v |= A o v |= B

v |= A ⇐⇒ B sii

Eduardo Bonelli

(v |= A sii v |= B)

Programaci´n L´gica
o
o

Paradigma l´gico
o
L´gica proposicional
o
Resoluci´n
oSintaxis
Valuaciones, Satisfactibilidad, Tautolog´
ıas
Forma normal conjuntiva

Tautolog´ y satisfactibilidad
ıas

Definici´n
o
Una proposici´n A es
o
una tautolog´ si v |= A para toda valuaci´n v .
ıa
o
satisfactible si existe una valuaci´n v tal que v |= A
o
insatisfactible si no es satisfactible
Un conjunto de proposiciones S es
satisfactible si existe una valuaci´n v tal que...