Download programación lógica - paradigmas

PROGRAMACIÓN
LÓGICA
PROGRAMACIÓN LÓGICA
 Programación
paradigma imperativo: Función que
a partir estado inicial define los valores del estado
final luego de la evolución del algoritmo.
 Problema intrínseco: la presencia de la asignación
hace que l valor denotado de una variable sea
dependiente del lugar del programa en que esta
ocurre.
PROGRAMACIÓN LÓGICA
 Programación
paradigma lógico: Permite definir
relaciones sobre ciertos dominios dados.
 Se sustenta en la idea de que un programa puede
ser descripto definiendo ciertas relaciones entre
conjuntos de objetos, a partir de las cuales otras
pueden ser calculadas empleando deducción.
PROGRAMACIÓN LÓGICA





Modo de programación no convencional
Consiste en describir el problema en si mismo
Concentrar el esfuerzo en su estructura lógica, sin
pensar en como resuelve la computadora
Describir los conocimientos relevantes que una vez
especificados se someten al interprete que relaciona
e infiere consecuencias lógicas
que de ellas se derivan.
La programación en lógica se ocupa del "que" y no
del "como" .
PROGRAMACIÓN LÓGICA
 Según
Robert Kowalski:
Algoritmo = lógica + control
 En
programación lógica el "como" a cargo del
interprete podemos decir:
Algoritmo = lógica
PROGRAMACIÓN LÓGICA
 Etapas




del desarrollo de una programación lógica:
Planteo del problema en lenguaje natural impreciso.
Mejorar especificación lenguaje natural preciso sin
ambigüedades.
Especificación correcta en lenguaje formal y preciso.
PROLOG:(PROgramación in LOGic) fue desarrollado a
partir de 1972 por Grupo de inteligencia artificial Universidad de Marsella (A. Colmerauer y Ph, Roussel).
PROGRAMACIÓN LÓGICA
 Programación
lógico ligada a Inteligencia Artificial
con numerosas aplicaciones. Ej.:






Demostración de teoremas: álgebra y geometría.
Juegos: técnicas de exploración de espacios de
búsqueda .
Robótica: diseño de robots inteligentes.
Percepción visual: reconocimiento de contornos y
formas.
Procesamiento del lenguaje natural: reconocimiento
y expresión.
Sistemas expertos: capacidad de "aprender".
INTRODUCCIÓN A
PROGRAMACIÓN EN LÓGICA
 Un
programa en lógica permite definir relaciones
sobre ciertos dominios dados. Ej.:
PADRE (Nombre, Nombre)
 Nombre
= Dominio que contiene nombre de
personas.
PADRE (josé, julieta)
PADRE (josé, virginia)
PADRE (juan, raquel)
PADRE (julio, melina)
INTRODUCCIÓN A
PROGRAMACIÓN EN LÓGICA
 Según
la definición el nombre en primer término, es
el padre del segundo y así es posible operar: con
operaciones clásicas:



restricciones (subconjuntos).
proyecciones sobre dominios para definir nuevas
relaciones.
preguntas de pertenencia.
 Por
su aspecto relacional no se introducen
"direcciones" en el sentido clásico de datos.
 Por el nivel de expresión es posible pasar del
lenguaje natural a una programación en lógica
INTERPRETACIÓN LÓGICA
REALIDAD
concreta o matemática)
modelización
SISTEMA FORMAL
Interpretación
UNIVERSO O DOMINIOS



Conceptos de lógica que se definen.
Mecanismos de derivación a partir de reglas de inferencias.
Unificación (realiza dicha operación en presencia de
variables).
INTERPRETACIÓN LÓGICA
PROGRAMA
LÓGICO
CONJUNTO DE
REGLAS
O DEFINICIÓN DE
TEORIA AXIOMÁTICA
EJECUCIÓN
EVALUACIÓN DE
UNA
INTERROGACIÓN DE
ALGUNA RELACIÓN
DEFINIDA
O sea un demostrar automático de teoremas y toma
valor cuando existen parámetros reales y producen
una respuesta.
SINTAXIS DE LA PROGRAMACIÓN EN
LÓGICA
 Proviene
de la lógica de predicados de primer
orden y se dispone de:

Un conjunto de elementos simples llamados átomos.
 Los
átomos están representados por caracteres
minúsculas (Ej.: a, b, julieta, 23, etc.).

Un vocabulario V de variables (X, Y, Z).
 Las

variables están representadas-en mayúsculas (X, Y, Z).
Un vocabulario F de símbolos funcionales.
 Los
símbolos funcionales se representan en minúsculas.
SINTAXIS DE LA PROGRAMACIÓN EN
LÓGICA

Un vocabulario P de símbolos predicativos.
 Los
símbolos predicativos en mayúsculas (Ej.: PADRE (josé,
julieta).


Cualquier predicado puede negarse -PADRE (josé, julieta),
Un conjunto de conectivos.
𝐶𝑜𝑛𝑗𝑢𝑛𝑐𝑖ó𝑛 𝑦 .
 ⋁𝐷𝑖𝑠𝑦𝑢𝑛𝑐𝑖ó𝑛(𝑜).
 → 𝐼𝑚𝑝𝑙𝑖𝑐𝑎𝑐𝑖ó𝑛 𝑠𝑖 .
 ↔ 𝐸𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑐𝑖𝑎(𝑠𝑖 𝑦 𝑠𝑜𝑙𝑜 𝑠𝑖).


Un conjunto de cuantificadores.
X
cuantificador universal (para todo X).
 X cuantificador existencial (existe un X)
SINTAXIS DE LA PROGRAMACIÓN EN
LÓGICA
SINTAXIS DE LA PROGRAMACIÓN EN
LÓGICA
 El
conjunto de sentencias que pueden construirse
usando definiciones anteriores constituye un
lenguaje en lógica de primer orden.
 Primer orden: no admite cuantificación sobre los
predicados y funciones.
SINTAXIS DE LA PROGRAMACIÓN EN
LÓGICA
SINTAXIS DE LA PROGRAMACIÓN EN
LÓGICA
 Cuando
una variable está bajo el alcance de un
cuantificador, se dice ligada a él; caso contrario es
libre.
 Símbolo funcional muy especial y denotado por "."
permite definir expresiones simbólicas (árboles
binarios).

Ej.: [𝑎. [𝑏. 𝑐𝑙] [[[𝑥. 𝑡] . 𝑦] . [𝑟𝑒 𝑎. 𝑝 ]]
SINTAXIS DE LA PROGRAMACIÓN EN
LÓGICA
 Visualizado
como árboles tendría la siguiente
representación:
.
.
a
r
.
b
.
y
.
c
x
 Para
.
.
.
f
a
p
la definición recursiva de árboles es necesario
considerar el nulo [ ] o "NIL".
SEMÁNTICA DE LA PROGRAMACIÓN
EN LÓGICA
 Interpretación:
Sea R un programa en lógica con
sus vocabulario V de átomos, F de símbolos
funcionales y P de significado predicativos Sea D
un conjunto (dominio) dado.
Una interpretación I (D) sobre el programa R asigna a
cada elemento de V, F, Y P los correspondientes
elementos de D.
 Satisfacción lógica: Una interpretación I (D)
satisface a una fórmula, si su aplicación resulta
verdadera.
SEMÁNTICA DE LA PROGRAMACIÓN
EN LÓGICA

Consecuencia lógica o deducción:Una fórmula f es
consecuencia lógica o se deduce, de un conjunto de
fórmulas R, si todo dominio D, toda interpretación I (D)
que satisface a R, satisface también a f.
𝑅 ∶= 𝑓.
Permite determinar la forma en que los programas son
evaluados.
Inferencia lógica: Conjunto inicial de fórmulas son
sentencia válidas y se las llama axiomas. Los axiomas
junto a las reglas de inferencia constituyen sistemas de
formas.
Elemento de derivación sintáctica que a partir de
conjunto de fórmulas permite derivar nuevas fórmulas.

SEMÁNTICA DE LA PROGRAMACIÓN
EN LÓGICA
AXIOMAS
• SENTENCIAS
VÁLIDAS DEL
LENGUAJE
DERIVACIÓN
SINTÁCTICA
• REGLAS DE
INFERENCIA
NUEVO
CONJUNTO DE
FÓRMULAS
• SISTEMA DE
FÓRMULAS
SEMÁNTICA DE LA PROGRAMACIÓN
EN LÓGICA
Regla básica de inferencias: De las fórmulas 𝐴 𝑦 𝐴 ⟶ 𝐵
se puede inferir B-. Un paso de inferencia corresponde a
la aplicación de una regla para inferir una nueva
fórmula.
𝐴
𝐴⟶𝐵
𝐵
 Demostración: Será sucesión de F1, F2, ....Fnde fórmulas
del lenguaje.
FI es axioma o de obtiene de fórmulas anteriores por
aplicar una regla de inferencia.
 Teorema: Una fórmula F es un teorema si existe una
demostración en la que F es el último término de la
sucesión.
: −𝐹

SEMÁNTICA DE LA PROGRAMACIÓN
EN LÓGICA
SEMÁNTICA DE LA PROGRAMACIÓN
EN LÓGICA

Completitud: Sea P un programa en lógica y
𝑃 𝐶𝑙á𝑢𝑠𝑢𝑙𝑎𝑠 𝑑𝑒𝑙 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑎
𝑄 𝑅𝑒𝑔𝑙𝑎 𝑑𝑒 𝑖𝑛𝑓𝑒𝑟𝑒𝑛𝑐𝑖𝑎
𝑃 ∶ − 𝑝 ( 𝑝 𝑒𝑠 𝑑𝑒𝑑𝑢𝑐𝑖𝑏𝑙𝑒 𝑑𝑒 𝑃)
𝑃 ∶= 𝑝 (𝑃 𝑒𝑠 𝑐𝑜𝑛𝑠𝑒𝑐𝑢𝑒𝑛𝑐𝑖𝑎 𝑙ó𝑔𝑖𝑐𝑎 𝑑𝑒 𝑝)

Regla de resolución: Sean A1, A2, … , An y
𝐵1, 𝐵2, … , 𝐵𝑚símbolos predicativos, la regla provee:
∼ 𝐴1, … , … 𝐴𝑘, … , 𝐴𝑛
𝐴𝐾 ⟵ 𝐵1, … , 𝐵𝑚
∼ 𝐴1, … , 𝐴𝑘 − 1, 𝐵1, … , 𝐵𝑀, 𝐴𝑘 + 1, … , 𝐴𝑛
SEMÁNTICA DE LA PROGRAMACIÓN
EN LÓGICA
SEMÁNTICA DE LA PROGRAMACIÓN
EN LÓGICA
SEMÁNTICA DE LA PROGRAMACIÓN
EN LÓGICA
PROGRAMAS LÓGICOS
 Un
programa lógico es un conjunto de sentencia o
cláusulas.
𝐵 ⟵ (hecho)(cláu. Horn - afirmación incondicional)
𝐵 ⟵ 𝐴1, 𝐴2, … , 𝐴𝑛 (regla) (afirmación condicionada)
B se denomina "cabeza" y
los antecedentes "cuerpo"
 El
conjunto de todas las cláusulas que tienen como
cabeza el mismo predicado, constituye su
definición.
PROGRAMAS LÓGICOS
 Otra
clausula que interesa es la denominada
"clausula objetivo" o "goal".
 Los compiladores de lenguajes lógicos son
interpretes capaces de llevar a cabo el proceso de
inferencia con el fin de que los programas lógicos
se ejecuten.
 Cada alternativa de respuesta da lugar a una
ramificación adicional que deberá ser explorada
para obtener todas las soluciones alternativas al
problema.
PROGRAMAS LÓGICOS
 Recursividad:
Un algoritmo es recursivo si está
definido en términos de si mismo.
En un algoritmo recursivo se re ejecuta la totalidad del
algoritmo desde el principio.
Casos característicos de recursividad:
 Reglas que tienen como antecedente el mismo
predicado que en la cabeza.
 En términos (objetos) compuestos que tienen como
argumento a los mismo términos.