Product Design, Manufacturing & Innovation Resources
Hogar » Demostración automatizada de teoremas (ATP)

Demostración automatizada de teoremas (ATP)

1960
Informático realizando demostraciones automáticas de teoremas en una oficina de la década de 1960.

(Imagen generada únicamente con fines ilustrativos)

La demostración automatizada de teoremas (ATP) es un subcampo de la informática y la lógica matemática dedicado a la demostración de teoremas matemáticos mediante programas informáticos. Los sistemas ATP, o demostradores, utilizan el razonamiento lógico para deducir nuevos teoremas a partir de un conjunto de axiomas e hipótesis. Se diferencian de los asistentes de demostración, que requieren mayor orientación humana, aunque ambos campos se solapan significativamente.

Los demostradores automáticos de teoremas funcionan representando el conocimiento matemático en un lenguaje formal, típicamente lógica de primer orden o lógica de orden superior. Luego aplican reglas de inferencia de manera sistemática para buscar una demostración. Un avance clave fue el desarrollo del principio de resolución por John Alan Robinson en 1965, una regla de inferencia única y eficiente que es completa para la lógica de primer orden. Esto hizo práctico construir sistemas automatizados que pudieran buscar demostraciones por refutación (una forma de demostración por contradicción). El sistema toma los axiomas y la negación del teorema deseado e intenta derivar una contradicción (la cláusula vacía). Si tiene éxito, el teorema queda demostrado. Los sistemas ATP se han utilizado para resolver problemas abiertos de larga data, el más famoso de ellos la demostración de la conjetura de Robbins en 1996 por el demostrador EQP. También son fundamentales en la industria para verificación formaldonde se utilizan para demostrar la corrección de sistemas críticos como los microprocesadores y control de vuelo software, garantizando que estén libres de errores lógicos.

UNESCO Nomenclature: 1203
Ciencias de la computación

Tipo

Software/Algoritmo

Ruptura

Incremental

Uso

Nicho/Especialización

Precursores

  • El sueño de Leibniz de un "cálculo razonador" (un cálculo lógico universal)
  • Desarrollo de la lógica formal por Boole, Frege y Russell
  • El trabajo de Turing sobre la computabilidad y la máquina de Turing
  • El advenimiento de las computadoras digitales
  • El programa del Teórico Lógico (1956)

Aplicaciones

  • verificación formal del hardware (por ejemplo, diseño de CPU) y del software
  • investigación en inteligencia artificial
  • Resolver problemas abiertos en matemáticas (por ejemplo, la conjetura de Robbins)
  • programación lógica y sistemas expertos
  • Asistentes de prueba interactivos como Coq e Isabelle/HOL

Patentes:

NA

Ideas para posibles innovaciones

  • verification of smart contracts on blockchain platforms
  • Descubrimiento automatizado de vulnerabilidades y exploits de software
  • IA generativa para crear nuevas conjeturas y pruebas matemáticas
  • verificación formal de las propiedades de seguridad y alineación de la IA
  • Sistemas de calificación automatizados para la educación en matemáticas y lógica
  • optimization of compilador design based on provably correct transformations
  • Descubrimiento de fármacos mediante el modelado lógico de interacciones moleculares
  • razonamiento jurídico automatizado y análisis de contratos
  • Diseño de sistemas de votación electrónica demostrablemente justos y seguros
  • desarrollo de sistemas de software de autoverificación
Relacionado con: demostración automatizada de teoremas, ATP, verificación formal, inteligencia artificial, lógica, principio de resolución, demostrador de teoremas, asistente de pruebas, informática, métodos formales.

Contexto histórico

Demostración automatizada de teoremas (ATP)

1950
1953
1960
1960
1967
1970
1970
1950
1952
1956
1960
1967
1967
1970
1970

(Si la fecha es desconocida o no es relevante, por ejemplo "mecánica de fluidos", se proporciona una estimación redondeada de su aparición notable)

décimo año aniversario

Las imágenes en tamaño completo y las descargas solo están disponibles, de forma totalmente gratuita, para los miembros registrados.

> Acceso <