ALGUNAS APLICACIONES DE LP

ALGUNAS APLICACIONES DE LP
• Diversas son las aplicaciones directas de lógica proposicional.
• A continuación veremos como un problema de búsqueda (típico de aplicaciones de InteligenciaArtificial) se puede modelar usando lógica proposicional.
Algoritmos para Encontrar Satisfactibilidad
• La alternativa más ingenua para encontrar una valuación que haga verdadera a una fórmula es usando unatabla de verdad.
• El problema de esto es que, para una fórmula de n variables, deberemos revisar, en promedio 2 n−1 valuaciones.
El algoritmo DPLL
• Este es un algoritmo sistemático para encontrarsatisfactibilidad.
• Propuesto en 1962, utiliza formulas en FNC y asigna un valor de verdad de tal manera de simplificar al máximo la fórmula.
• Normalmente en muchos problemas de satisfactibilidad, loque interesa es además cuál es la valuación que hace verdadera a la fórmula.
• Este algoritmo se puede extender trivialmente para encontrar una valuación.
GSAT
• Una forma alternativa de resolverel problema de satisfactibilidad es a través de algoritmos estocásticos (no sistemáticos).
• Estos algoritmos han tenido gran ´éxito en aplicaciones de inteligencia artificial.
• La idea es partir deuna valuación aleatoria e ir modificándola hasta encontrar una valuación precisa.
• Si tenemos “suerte” encontraremos una valuación rápidamente.
Diagnóstico en Circuitos Lógicos
• Es posible modelarlógicamente el comportamiento del circuito.
• Si una compuerta funciona correctamente, entonces el comportamiento del ´esta es el correcto.
OTTER
• Sus características son las siguientes:
• Puedeusar resolución estándar o híper-resolución.
• Recibe como entrada a fórmulas proposicionales de cualquier tipo.
• Para el caso proposicional, es correcto y completo, porque implementa resoluciónproposicional.
• La entrada común de otter son dos listas:
• La lista usable: las fórmulas de la base de conocimiento.
• La lista SOS: contiene las fórmulas queremos obtener como consecuencia de la...