Saltar al contenido ForoHackers

Lógica en informática: por dónde empezar

Lógica en informática
#900 · Ophuscado · · Denunciar

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

  1. Tablas de verdad, equivalencias y forma normal conjuntiva, a mano.
  2. Escribe un pequeño resolvedor SAT con propagación unitaria y vuelta atrás.
  3. Demuestra teoremas sencillos por deducción natural y por resolución.
  4. Lógica de primer orden: traduce enunciados del lenguaje natural y prueba un resolvedor SMT con un acertijo.
  5. Aprende la lógica temporal y úsala para enunciar una propiedad de un protocolo.

Etiquetas relacionadas

#formal-methods #type-theory #databases #knowledge-representation

Inicia sesión o únete para responder.