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.

Automated theorem provers work by representing mathematical knowledge in a formal language, typically first-order logic or higher-order logic. They then apply rules of inference in a systematic way to search for a proof. A key breakthrough was John Alan Robinson’s development of the resolution principle in 1965, a single, efficient rule of inference that is complete for first-order logic. This made it practical to build automated systems that could search for proofs by refutation (a form of proof by contradiction). The system takes the axioms and the negation of the desired theorem and tries to derive a contradiction (the empty clause). If successful, the theorem is proven. ATP systems have been used to solve long-standing open problems, most famously the proof of the Robbins conjecture in 1996 by the EQP prover. They are also critical in industry for formal verification, where they are used to prove the correctness of critical systems like microprocessors and flight control software, ensuring they are free from logical errors.

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

Devido ao tráfego de bots de coleta de dados, atualmente superior a 40 mil por dia, este conteúdo é reservado aos membros da comunidade.
> Login < ou > Registrar < (100% gratuito) para acessar isso, assim como todo o restante do conteúdo e das ferramentas restritas.

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)

Princípios relacionados à invenção, inovação e tecnologia

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