A tradução deste artigo está abaixo da qualidade média aceitável. Talvez tenha sido feita por um tradutor automático ou alguém que não conhece bem o português ou a língua original. Caso queira colaborar com a Wikipédia, tente encontrar a página original e melhore este verbete conforme o guia de tradução.(Abril de 2014)
Prova automática de teoremas (PAT) ou dedução automática(DA) é a prova de teoremas matemáticos por um programa de computador. É atualmente a sub-área mais desenvolvida do raciocínio automatizado (RA).
Decidibilidade do problema
Dependendo da lógica subjacente, o problema de decidir a validade de um teorema varia do trivial ao impossível. Para o caso freqüente da lógica proposicional, o problema é decidível mas NP-completo, e portanto se acredita que apenas algoritmos com complexidade de tempo exponencial existam para tarefas de prova gerais. Para um cálculo de predicados de primeira ordem, isto é, não tendo nenhum axioma próprio, o teorema da completude de Gödel afirma que os teoremas são exatamente as fórmulas bem formadas, portanto identificar teoremas é recursivamente enumerável, isto é, dados recursos ilimitados, qualquer teorema válido pode eventualmente ser provado. Sentenças inválidas, isto é, fórmulas que não são conseqüência de uma dada teoria, nem sempre podem ser reconhecidas. Além disso, uma teoria formal consistente que contém a teoria de primeira ordem dos números naturais (tendo portanto certos axiomas próprios), pelo teorema da incompletude de Gödel, contém uma sentença verdadeira que não pode ser provada, caso no qual um provador de teoremas tentando provar tal sentença não termina sua execução.
Nestes casos, um provador de teoremas de primeira ordem pode falhar em terminar ao procurar por uma prova. Apesar destes limites teóricos, provadores de teorema na prática são capazes de resolver muitos problemas difíceis nestas lógicas.
Princípios da Lógica
Enquanto as raízes da lógica formal vêm de lógica aristotélica, no final do século XIX e início do século XX aconteceu o desenvolvimento da lógica moderna e da matemática formal. Begriffsschrift (1879), de Gottlob Frege, introduziu tanto a lógica proposicional como o que é essencialmente a lógica de predicados moderna.[1] Seu Os Fundamentos da Aritmética, publicado em 1884,[2] expressam (partes da) matemática na lógica formal. Esta abordagem foi continuada por Russell e Whitehead em seu influentePrincipia Mathematica, publicado pela primeira vez em 1910-1913,[3] e revisado em sua segunda edição em 1927.[4] Russell e Whitehead pensaram que podiam derivar toda a verdade matemática utilizando axiomas e regras de inferência da lógica formal, abrindo caminhos para o processo de automatização. Em 1920, Thoralf Skolem simplificou um resultado anterior de Leopold Löwenheim, levando ao teorema de Löwenheim–Skolem e, em 1930, à noção do Universo de Herbrand e a uma Interpretação de Herbrand que permitia (in)satisfiabilidade das fórmulas da lógica de primeira ordem (e portanto, a validade de um teorema) para serem reduzidas a (potencialmente infinitos) problemas de satisfatibilidade proposicional.[5]
Pouco tempo após a Segunda Guerra Mundial, o primeiro general decidiu que os computadores deveriam ficar acessíveis. Em 1954, Martin Davis programou o algoritmo de Presburger para um JOHNNIAC, um computador de tubos de vácuo pertencente à Princeton Institute for Advanced Study. De acordo com Davis, "É um grande triunfo provar que a soma de dois números pares também é par".[7][8] A Máquina de Teoria Lógica era mais ambiciosa, um sistema de dedução matemática para a lógica proposicional de Principia Mathematica, desenvolvido por Allen Newell, Herbert A. Simon e J. C. Shaw. Este também rodava em um JOHANNIAC, a máquina de Lógica Teórica construiu provas a partir de uma pequeno conjunto de axiomas e três regras de dedução: modus ponens, substituição de variáveis proposicionais, e a substituição de de fórmulas por suas definições. O sistema usava orientação heurística, e tentando, conseguiu provar 38 dos primeiros 52 teoremas presentes em Principia.[7]
A aproximação "heurística" da Máquina de Lógica Teórica tentou emular o raciocínio humano, e não conseguia garantir que uma prova podia ser encontrada para cada teorema válido a priori. Em contraste, outro, mas algoritmos mais sistemáticos alcançaram, pelo menos teoricamente, incompletude para a lógica de primeira ordem.
Abordagens iniciais contavam com os resultados de Herbrand e Skolem para converter uma fórmula de primeira ordem em conjuntos sucessivamente maiores de fórmulas proposicionais por instanciar as variáveis com os termos da Universo de Herbrand . As fórmulas proposicionais puderam então ser verificadas para insatisfiabilidade usando uma série de métodos. O epigrama de Gilmore usou conversão para forma normal disjuntiva e uma forma onde a satisfabilidade da fórmula tornou-se óbvia.[7][9]
Decibilidade de um problema
Dependendo da lógica subjacente, o problema de decidir a validade de uma fórmula varia do trivial ao impossível. Para o caso freqüente da lógica proposicional, o problema é decidível, porém Co-NP-complete, acredita-se que existam apenas algoritmos em tempo exponencial para tarefas de prova. Para a primeira ordem de cálculo predicativo, com nenhum axioma próprio, o Teorema da Incompletude de Gödel afirma que qualquer fórmula válida pode ser comprovada.
Entretanto, fórmulas inválidas não podem sempre serem reconhecias e além disso, uma teoria formal consistente que contem lógica de primeira ordem dos números naturais (contendo alguns "axiomas adequados"), por Teorema de incompletude de Gödel, contém sentenças verdadeiras que não podem ser provadas. Nestes casos, uma prova automatizada do teorema pode vir a falhar, pois poderá nunca encontrar uma resposta. Apesar destes limites teóricos, na prática, provadores de teoremas pode resolver muitos problemas difíceis, mesmo nessas lógicas indecidíveis.
Problemas relatados
Um dos problemas é a "verificação da prova", onde uma prova existente para um teorema é válida. Para isso, é geralmente necessário que cada passo individual da prova possa ser verificado por uma função recursiva primitiva ou programa, e portanto o problema é sempre decidível.
Desde que a prova gerada automaticamente seja tipicamente muito extensa, o problema da compressão da prova é crucial e várias táticas e técnicas tentam fazer com que a prova seja a mais sucinta possível.
Assistente de Prova: São necessários usuários humanos capazes de dar dicas de como prosseguir com as provas. Dependendo do grau de automação, um supervisor pode diminuir drasticamente o tamanho da prova.
Outra distinção é às vezes feita entre prova de teoremas de e outras técnicas, onde um processo é considerado prova de teoremas se consiste em uma prova tradicional, começando com os axiomas e produzindo novos passos de inferência utilizando para tal.Outras técnicas podem incluir checagem do modelo,que no caso mais simples, envolve força bruta, manual e enumeração dos muitos estados possíveis (embora a implementação real do modelo requeira muita inteligência, e não simplesmente redução da força bruta e do trabalho manual e/ou artesanal).
Usos na indústria
O uso comercial de provas dos teoremas automatizados é mais concentrada em projectos de circuito integrado e verificação. Desde o bug do Pentium FDIV, as complicadas unidades de ponto flutuante de microprocessadores modernos foram concebidas com controle extra. Atualmente [vago]AMD, Intel e outros usam a prova automatizada de teoremas para verificar que a divisão e as outras operações são corretamente implementadas em seus processadores.
Provas de teoremas de primeira-ordem
Provas de teoremas de primeira ordem é um dos campos mais maduros da prova automatizada de teoremas. A lógica é expressiva o suficiente para permitir especificações de problemas arbitrários, muitas vezes em uma forma intuitiva e razoavelmente natural. Por outro lado, ainda semi-decifrável e um número grande de cálculos automatizados já foi desenvolvido, permitindo sistemas totalmente automatizados. Lógicas mais expressivas, como a lógica de ordem superior, permitem a expressão adequada de uma ampla gama de problemas de lógica de primeira ordem, mas a prova de teoremas para estas lógicas é bem menos desenvolvida.
Benchmarks e Competições
A qualidade dos sistemas implementados foi beneficiada pela existência de uma robusta biblioteca de exemplos de benchmark: "The Thousands of Problems for Theorem Provers (TPTP) Problem Library"[10] — cedidas pela CADE ATP System Competition (CASC), uma competição anual de sistemas de Lógica de primeira ordem para classes importantes de problemas Lógica desse tipo.
Alguns Sistemas importantes (Todos ganharam ao menos uma divisão da competição CASC ) são listadas a seguir:
E é um provedor de alta performance totalmente dedicado a lógica de primeira ordem, mas construído em um cálculo equacional puro, desenvolvido primordialmente no grupo de automação de sistemas racionais da Technical University of Munich.
SETHEO é um sistema de alta performance baseado em metas diretas de modelos eliminatórios de cálculo. É desenvolvido no grupo de automação de sistemas racionais n a Universidade Técnica de Munique. E e SETHEO tem sidos combinados (com outros sistemas) na composição do provedor de teoremas E-SETHEO.
Vampire é desenvolvido e implementado na Manchester University por Andrei Voronkov e Krystof Hoder, formalmente também por Alexandre Riazanov. Ele ganhou o CADE ATP System Competition na mais prestigiada categoria: CNF (conjunctive normal form or clausal normal form) por 11 anos (1999, 2001–2010).
Waldmeister é um sistema especializado para unificação equacional de lógica de primeira ordem. Ele ganhou a categoria CASC (CADE ATP System Competition) nos últimos quatorze anos. (1997–2010).
William McCuneArgonne National Laboratory, author of Otter, the first high-performance theorem prover. Many important papers, recipient of the Herbrand Award 2000.
J. Alan Robinson Syracuse University. Developed original resolution e unification based first order theorem proving, co-editor of the "Handbook of Automated Reasoning", recipient of the Herbrand Award 1996
Metamath - a language for developing strictly formalized mathematical definitions e proofs accompanied by a proof checker for this language e a growing database of thousands of proved theorems; while the Metamath language is not accompanied with an automated theorem prover, it can be regarded as important because the formal language behind it allows development of such a softwarePredefinição:Why?; as of March, 2012, there is no "widely" known such software, so it is not a subject of "automated theorem proving" (it can become such a subject Predefinição:Why?), but it is a proof assistant.[carece de fontes?]
Notas
Referências
↑Frege, Gottlob (1879). Begriffsschrift. [S.l.]: Verlag Louis Neuert
↑Frege, Gottlob (1884). Die Grundlagen der Arithmetik(PDF). Breslau: Wilhelm Kobner. Consultado em 27 de setembro de 2013. Arquivado do original(PDF) em 26 de setembro de 2007
↑Bertrand Russell; Alfred North Whitehead (1910–1913). Principia Mathematica 1st ed. [S.l.]: Cambridge University PressA referência emprega parâmetros obsoletos |coautor= (ajuda)
↑Bertrand Russell; Alfred North Whitehead (1927). Principia Mathematica 2nd ed. [S.l.]: Cambridge University PressA referência emprega parâmetros obsoletos |coautor= (ajuda)
↑Herbrand, Jaques (1930). Recherches sur la théorie de la démonstration. [S.l.: s.n.]
↑Presburger, Mojżesz (1929). «Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt». Warszawa. Comptes Rendus du I congrès de Mathématiciens des Pays Slaves: 92–101
Chin-Liang Chang; Richard Char-Tung Lee (1973). Symbolic Logic e Mechanical Theorem Proving. [S.l.]: Academic PressA referência emprega parâmetros obsoletos |coautor= (ajuda)
Loveland, Donald W. (1978). Automated Theorem Proving: A Logical Basis. Fundamental Studies in Computer Science Volume 6. [S.l.]: North-Holland Publishing
