Product Design, Manufacturing & Innovation Resources
Lar » Prova Automatizada de Teoremas (ATP)

Prova Automatizada de Teoremas (ATP)

1960
Computer scientist conducting automated theorem proving in a 1960s office.

(Imagem gerada apenas para fins ilustrativos)

A demonstração automática de teoremas (ATP, na sigla em inglês) é um subcampo da ciência da computação e da lógica matemática dedicado à demonstração de teoremas matemáticos por meio de programas de computador. Os sistemas ATP, ou demonstradores, utilizam o raciocínio lógico para deduzir novos teoremas a partir de um conjunto de axiomas e hipóteses. Eles se distinguem dos assistentes de demonstração, que requerem maior intervenção humana, embora os campos se sobreponham significativamente.

Os provadores de teoremas automatizados funcionam representando o conhecimento matemático em uma linguagem formal, tipicamente lógica de primeira ordem ou lógica de ordem superior. Em seguida, aplicam regras de inferência de forma sistemática para buscar uma prova. Um avanço fundamental foi o desenvolvimento do princípio da resolução por John Alan Robinson em 1965, uma regra de inferência única e eficiente que é completa para a lógica de primeira ordem. Isso tornou viável a construção de sistemas automatizados capazes de buscar provas por refutação (uma forma de prova por contradição). O sistema recebe os axiomas e a negação do teorema desejado e tenta derivar uma contradição (a cláusula vazia). Se bem-sucedido, o teorema é provado. Os sistemas ATP têm sido usados ​​para resolver problemas em aberto de longa data, sendo o mais famoso deles a prova da conjectura de Robbins em 1996 pelo provador EQP. Eles também são cruciais na indústria para verificação formal, onde são usados ​​para comprovar a correção de sistemas críticos como microprocessadores e controle de voo software, garantindo que estejam livres de erros lógicos.

UNESCO Nomenclature: 1203
Ciências da Computação

Tipo

Software/Algoritmo

Interrupção

Incremental

Uso

Nicho/Especializado

Precursores

  • O sonho de Leibniz de um "raciocinador de cálculo" (um cálculo lógico universal)
  • Desenvolvimento da lógica formal por Boole, Frege e Russell
  • O trabalho de Turing sobre computabilidade e a máquina de Turing
  • O advento dos computadores digitais
  • O programa do Teórico da Lógica (1956)

Aplicações

  • verificação formal de hardware (ex.: projeto de CPU) e software
  • pesquisa em inteligência artificial
  • Resolver problemas em aberto na matemática (por exemplo, a conjectura de Robbins)
  • Programação lógica e sistemas especialistas
  • assistentes de prova interativos como Coq e Isabelle/HOL

Patentes:

NA

Ideias de Inovação Potencial

  • verification of smart contracts on blockchain platforms
  • automated discovery of software vulnerabilities and exploits
  • generative AI for creating novel mathematical conjectures and proofs
  • formal verification of AI safety and alignment properties
  • automated grading systems for mathematics and logic education
  • optimization of compilador design based on provably correct transformations
  • drug discovery through logical modeling of molecular interactions
  • automated legal reasoning and contract analysis
  • design of provably fair and secure electronic voting systems
  • development of self-verifying software systems
Relacionado a: demonstração automática de teoremas, ATP, verificação formal, inteligência artificial, lógica, princípio da resolução, provador de teoremas, assistente de provas, ciência da computação, métodos formais.

Contexto histórico

Prova Automatizada de Teoremas (ATP)

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

(Caso a data seja desconhecida ou irrelevante, por exemplo, "mecânica dos fluidos", é fornecida uma estimativa aproximada de seu surgimento notável)

10º ano aniversário

Imagens em tamanho real e downloads estão disponíveis apenas, 100% gratuitos, para membros registrados.