Skip to the content ForoHackers
Log inJoin

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

Logic in computer science
#3406 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply