La lógica da a la informática un lenguaje preciso para enunciados y demostraciones. Programas, especificaciones, sistemas de tipos, bases de datos y circuitos se pueden describir con ella y comprobar con una máquina. Es la base de los resolvedores SAT y SMT, los asistentes de demostración, los lenguajes de consulta y la verificación de software y hardware.
Conceptos clave
- Lógica proposicional: enunciados unidos con y, o, no e implica; las tablas de verdad y las formas normales los deciden.
- Lógica de primer orden: añade variables, predicados y cuantificadores para hablar de objetos y sus propiedades.
- Sistemas de prueba: la deducción natural y la resolución dan reglas que derivan conclusiones paso a paso.
- Corrección y completitud: lo que prueba un sistema es verdadero, y todo lo verdadero es demostrable, en las lógicas adecuadas.
- Satisfacibilidad: hallar una asignación que haga verdadera una fórmula; es NP-completo, pero los resolvedores modernos manejan instancias enormes.
Vocabulario
- Modelo: una interpretación en la que una fórmula es verdadera o falsa.
- Validez y satisfacibilidad: verdadera en todos los modelos, o verdadera en al menos uno.
- Unificación: hallar una sustitución que haga iguales dos términos, el corazón de Prolog.
- Lógica temporal: lógica con operadores como siempre y eventualmente, usada para especificar el comportamiento de sistemas.
Qué estudiar, en orden
- Tablas de verdad, equivalencias y forma normal conjuntiva, a mano.
- Escribe un pequeño resolvedor SAT con propagación unitaria y vuelta atrás.
- Demuestra teoremas sencillos por deducción natural y por resolución.
- Lógica de primer orden: traduce enunciados del lenguaje natural y prueba un resolvedor SMT con un acertijo.
- Aprende la lógica temporal y úsala para enunciar una propiedad de un protocolo.
Etiquetas relacionadas
#formal-methods #type-theory #databases #knowledge-representation