Saltar al contenido ForoHackers

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

Lógica en informática
#3406 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder