Download Apuntes Lógica

Departamento de Informática
Lenguajes de Programación
Universidad Técnica Federico Santa María
Capítulo V:
Programación Lógica
1
Departamento de Informática
Lenguajes de Programación
Universidad Técnica Federico Santa María
5.1 Breve Introducción al Cálculo
de Predicados
2
Departamento de Informática
Universidad Técnica Federico Santa María
Lenguajes de Programación
Definiciones Básicas
• Proposición: sentencia lógica que puede ser
verdadera o falsa.
– Se construye de objetos y relaciones.
– Lógica formal provee métodos para verificar su validez
• Lógica Simbólica: permite expresar
proposiciones, relaciones entre proposiciones y
cómo inferir nuevas proposiciones que son
verdaderas.
• Cálculo de Predicado: Forma particular de lógica
simbólica usada en programación lógica.
V-1-3
1
Departamento de Informática
Lenguajes de Programación
Universidad Técnica Federico Santa María
Objetos y Términos Compuestos
• Objetos se representan como un único término,
que puede ser:
– constante : representa un único objeto
– variable : puede representar diferentes objetos
• Término compuesto: consiste de functor y una
lista de parámetros
– Un término con n parámetros se denomina n-tupla.
– El término padre(maria, jesús) es una 2-tupla.
V-1-4
Departamento de Informática
Lenguajes de Programación
Universidad Técnica Federico Santa María
Proposiciones
• Proposiciones pueden ser:
– Atómicas: corresponde a un único término compuesto
– Compuestas: dos o más proposiciones atómicas
conectadas por operadores lógicos.
• Una proposiciones puede ser:
– Hecho: se define como una verdad (axioma)
– Consulta: la verdad debe ser probada (teorema)
V-1-5
Departamento de Informática
Lenguajes de Programación
Universidad Técnica Federico Santa María
Conectores Lógicos
NOMBRE
SIMBOLO
EJEMPLO
¬
¬a
conjunción
∩ (∧)
a∧b
disjunción
∪ (∨)
a∨b
equivalencia
≡ (⇔)
a≡b
implicancia
⊃ (⇒)
⊂ (⇐)
a⊃b
b⊂a
negación
V-1-6
2
Departamento de Informática
Lenguajes de Programación
Universidad Técnica Federico Santa María
Cuantificadores
• Cuantificador Universal
∀X.P
: Para todo X, P es verdadero
• Cuantificador Existencial
∃X.P
: Existe un valor X tal que P es
verdadero
EJEMPLOS
• ∀X.(mujer(X) ⊃ humano(X))
• ∃X.(madre(maria, X) ∩ masculino(X))
V-1-7
Departamento de Informática
Universidad Técnica Federico Santa María
Lenguajes de Programación
Forma de Cláusula
• Para automatizar se requiere reducir redundancia
en la expresión de proposiciones.
• La forma de cláusula simplifica proposiciones, sin
pérdida de generalidad.
• Una cláusula tiene la siguiente forma:
B1 ∪ B2 ∪ … ∪ Bn ⊂ A1 ∩ A2 ∩ … ∩ Am
• Donde As y Bs son términos
• Una cláusula significa: “Si todos los As son
verdaderos, entonces al menos un B es verdadero”
V-1-8
Departamento de Informática
Universidad Técnica Federico Santa María
Lenguajes de Programación
Características de Cláusulas
• Una forma clausal no requiere de cuantificadores
existenciales.
• Cuantificadores universales están implícitos en el
uso de variables de proposiciones atómicas.
• No se requiere de otro conector que la conjunción
y disjunción, apareciendo sólo en el orden
definido por una cláusula (derecha e izquierda).
• Cualquier proposición de cálculo de predicado se
puede transformar en una cláusula.
V-1-9
3
Departamento de Informática
Lenguajes de Programación
Universidad Técnica Federico Santa María
Ejemplo de Cláusula
gusta(ana, fiesta)
⊂ gusta(joven, fiesta) ∩ joven(ana)
consecuencia
padre(luis, juan) ∪
padre(luis, maria)
antecedente
⊂ padre(juan, pepe) ∩
madre(maria, pepe) ∩ abuelo(luis, pepe)
V-1-10
Departamento de Informática
Lenguajes de Programación
Universidad Técnica Federico Santa María
Resolución
• Cálculo de Predicado provee método para
expresar conjunto de proposiciones
• Aplicación interesante o útil es inferir de
las proposiciones dadas nuevos hechos.
• Una aplicación es descubrir nuevos
teoremas
• Resolución es proceso que permite inferir
proposiciones de proposiciones dadas.
V-1-11
Departamento de Informática
Universidad Técnica Federico Santa María
Lenguajes de Programación
Ejemplo de Resolución
Si se tiene:
papa(juan, pato) ∪ mama(juan, pato) ⊂ padre(juan, pato)
abuelo(juan, roro)
⊂ papa(juan, pato) ∩ papa(pato, roro)
Se puede resolver que:
abuelo(juan, roro) ∪ mama(juan, pato)
⊂ padre(juan, pato) ∩ papa(pato, roro)
¡Proceso de resolución consiste en conectar términos de la
izquierda y de la derecha, y luego eliminar términos redundantes!
V-1-12
4
Departamento de Informática
Lenguajes de Programación
Universidad Técnica Federico Santa María
Tautologías Importantes
para Resolución
A⊂B
C⊂D
A∪B⊂C∩B
A∪C⊂B∩D
A⊂C
V-1-13
Departamento de Informática
Universidad Técnica Federico Santa María
Lenguajes de Programación
Proceso de Resolución
• La resolución es un proceso complejo
• Presencia de variables requiere de un proceso de
calce (matching) que al reemplazar sus valores
produce una verdad (éxito).
• Este proceso se denomina unificación.
• Asignación temporal de valores a variables se
denomina instanciación.
• Fallas (no éxito) en la instanciación requiere de
backtracking.
V-1-14
Departamento de Informática
Universidad Técnica Federico Santa María
Lenguajes de Programación
Cláusulas de Horn
• Cláusulas de Horn simplifican el proceso de
resolución, y permiten representar la mayoría de
las proposiciones lógicas.
• Sólo permite dos tipos de formas:
– Existe sólo una proposición atómica en la izquierda de
la cláusula (cláusula con cabeza)
– El lado izquierdo está vacío (cláusula sin cabeza)
• Cláusulas con cabeza se usan para definir reglas,
en cambio cláusulas sin cabezas sólo establecen
ciertos hechos.
V-1-15
5
Departamento de Informática
Universidad Técnica Federico Santa María
Lenguajes de Programación
Conclusiones
• Programación Lógica consiste básicamente
en definir un conjunto de reglas y hechos
(hipótesis).
• El sistema luego debe ser capaz de inferir si
una determinada proposición (meta) es una
verdad.
• Prolog está basado en el uso de cláusulas de
Horn.
V-1-16
6