b'\n_START_ARTICLE_\nProva autom\xc3\xa1tica de teoremas\n_START_SECTION_\nDecidibilidade do problema\n_START_PARAGRAPH_\nDependendo da l\xc3\xb3gica subjacente, o problema de decidir  a validade de um teorema varia do trivial ao imposs\xc3\xadvel. Para o caso freq\xc3\xbcente da l\xc3\xb3gica proposicional, o problema \xc3\xa9 decid\xc3\xadvel mas NP-completo, e portanto se acredita que apenas algoritmos com complexidade de tempo exponencial existam para tarefas de prova gerais. Para um c\xc3\xa1lculo de predicados de primeira ordem, isto \xc3\xa9, n\xc3\xa3o tendo nenhum axioma pr\xc3\xb3prio, o teorema da completude de G\xc3\xb6del afirma que os teoremas s\xc3\xa3o exatamente as f\xc3\xb3rmulas bem formadas, portanto identificar teoremas \xc3\xa9 recursivamente enumer\xc3\xa1vel, isto \xc3\xa9, dados recursos ilimitados, qualquer teorema v\xc3\xa1lido pode eventualmente ser provado. Senten\xc3\xa7as inv\xc3\xa1lidas, isto \xc3\xa9, f\xc3\xb3rmulas que n\xc3\xa3o s\xc3\xa3o conseq\xc3\xbc\xc3\xaancia de uma dada teoria, nem sempre podem ser reconhecidas. Al\xc3\xa9m disso, uma teoria formal consistente que cont\xc3\xa9m a teoria de primeira ordem dos n\xc3\xbameros naturais (tendo portanto certos axiomas pr\xc3\xb3prios), pelo teorema da incompletude de G\xc3\xb6del, cont\xc3\xa9m uma senten\xc3\xa7a verdadeira que n\xc3\xa3o pode ser provada, caso no qual um provador de teoremas tentando provar tal senten\xc3\xa7a n\xc3\xa3o termina sua execu\xc3\xa7\xc3\xa3o._NEWLINE_Nestes casos, um provador de teoremas de primeira ordem pode falhar em terminar ao procurar por uma prova. Apesar destes limites te\xc3\xb3ricos, provadores de teorema na pr\xc3\xa1tica s\xc3\xa3o capazes de resolver muitos problemas dif\xc3\xadceis nestas l\xc3\xb3gicas.\n_START_SECTION_\nPrinc\xc3\xadpios da L\xc3\xb3gica\n_START_PARAGRAPH_\nEnquanto as ra\xc3\xadzes da l\xc3\xb3gica formal v\xc3\xaam de l\xc3\xb3gica aristot\xc3\xa9lica, no final do s\xc3\xa9culo 19 e no come\xc3\xa7o do s\xc3\xa9culo 20 aconteceu o desenvolvimento da l\xc3\xb3gica moderna e da matem\xc3\xa1tica formal.Frege\'s Begriffsschrift (1879)  introduziu tanto a l\xc3\xb3gica proposicional como o que \xc3\xa9 essencialmente a l\xc3\xb3gica de predicados moderna.  Seu Os Fundamentos da Aritm\xc3\xa9tica, publicado em 1884, expressam (partes da) matem\xc3\xa1tica na l\xc3\xb3gica formal. Esta abordagem foi continuada por Russell e Whitehead em seu influente Principia Mathematica, publicado pela primeira vez em 1910-1913, e revisado em sua segunda edi\xc3\xa7\xc3\xa3o em 1927. Russell e Whitehead pensaram que podiam derivar toda a verdade matem\xc3\xa1tica utilizando axiomas e regras de infer\xc3\xaancia da l\xc3\xb3gica formal, abrindo caminhos para o processo de automatiza\xc3\xa7\xc3\xa3o. Em 1920, Thoralf Skolem simplificou um resultado anterior de Leopold L\xc3\xb6wenheim, levando ao teorema de L\xc3\xb6wenheim\xe2\x80\x93Skolem e, em 1930, \xc3\xa0 no\xc3\xa7\xc3\xa3o do Universo de Herbrand e a uma Interpreta\xc3\xa7\xc3\xa3o de Herbrand que permitia (in)satisfiabilidade das f\xc3\xb3rmulas da l\xc3\xb3gica de primeira ordem (e portanto, a validade de um teorema) para serem reduzidas a (potencialmente infinitos) problemas de satisfatibilidade proposicional._NEWLINE_Em 1929, Moj\xc5\xbcesz Presburger mostrou que a teoria dos n\xc3\xbameros naturais com adi\xc3\xa7\xc3\xa3o e igualdade (agora chamada de Aritm\xc3\xa9tica de Presburger em sua honra) \xc3\xa9 decidabilidade e deu um  algoritmo que pode determinar se uma senten\xc3\xa7a dada neta linguagem era verdadeira ou falsa._NEWLINE_Entretanto, pouco tempo ap\xc3\xb3s esse resultado positivo, Kurt G\xc3\xb6del publicou On Formally Undecidable Propositions of Principia Mathematica e Related Systems (1931), mostrando que em todo sistema axiom\xc3\xa1tico fortemente baseado existem senten\xc3\xa7as que s\xc3\xa3o verdadeiras e que n\xc3\xa3o podem ser provadas.Este tema foi desenvolvido na d\xc3\xa9cada de 1930 por Alonzo Church e Alan Turing, quem por um lado deu duas  defini\xc3\xa7\xc3\xb5es independentes  e  equivalentes da computabilidade, e por outro  deu exemplos concretos para quest\xc3\xb5es indecid\xc3\xadveis.\n_START_SECTION_\nPrimeiras Implementa\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nPouco tempo ap\xc3\xb3s a Segunda Guerra Mundial, o primeiro general decidiu que os computadores deveriam ficar acess\xc3\xadveis. Em 1954, Martin Davis programou o algoritmo de Presburger para um JOHNNIAC, um computador de tubos de v\xc3\xa1cuo pertencente \xc3\xa0 Princeton Institute for Advanced Study. De acordo com Davis, "\xc3\x89 um grande triunfo provar que a soma de dois n\xc3\xbameros pares tamb\xc3\xa9m \xc3\xa9 par". A M\xc3\xa1quina de Teoria L\xc3\xb3gica era mais ambiciosa,  um sistema de dedu\xc3\xa7\xc3\xa3o matem\xc3\xa1tica para a l\xc3\xb3gica proposicional de Principia Mathematica, desenvolvido por Allen Newell, Herbert A. Simon e J. C. Shaw. Este tamb\xc3\xa9m rodava em um JOHANNIAC, a m\xc3\xa1quina de L\xc3\xb3gica Te\xc3\xb3rica construiu provas a partir de uma pequeno conjunto de axiomas e  tr\xc3\xaas regras de dedu\xc3\xa7\xc3\xa3o: modus ponens, substitui\xc3\xa7\xc3\xa3o de vari\xc3\xa1veis proposicionais, e  a substitui\xc3\xa7\xc3\xa3o de de f\xc3\xb3rmulas por suas defini\xc3\xa7\xc3\xb5es. O sistema usava orienta\xc3\xa7\xc3\xa3o heur\xc3\xadstica, e tentando, conseguiu provar 38 dos primeiros 52 teoremas presentes em Principia._NEWLINE_A aproxima\xc3\xa7\xc3\xa3o "heur\xc3\xadstica" da M\xc3\xa1quina de L\xc3\xb3gica Te\xc3\xb3rica tentou emular o racioc\xc3\xadnio humano, e n\xc3\xa3o conseguia garantir que uma prova podia ser encontrada para cada teorema v\xc3\xa1lido a priori. Em contraste, outro, mas algoritmos mais sistem\xc3\xa1ticos alcan\xc3\xa7aram, pelo menos teoricamente,  incompletude para a l\xc3\xb3gica de primeira ordem._NEWLINE_Abordagens iniciais contavam com os resultados de Herbrand e Skolem para converter uma f\xc3\xb3rmula de primeira ordem em conjuntos sucessivamente maiores de f\xc3\xb3rmulas proposicionais por instanciar as vari\xc3\xa1veis com os termos da Universo de Herbrand . As f\xc3\xb3rmulas proposicionais puderam ent\xc3\xa3o ser verificadas para insatisfiabilidade usando uma s\xc3\xa9rie de m\xc3\xa9todos. O epigrama de Gilmore usou convers\xc3\xa3o para forma normal disjuntiva e uma forma onde a satisfabilidade da f\xc3\xb3rmula tornou-se \xc3\xb3bvia.\n_START_SECTION_\nDecibilidade de um problema\n_START_PARAGRAPH_\nDependendo da l\xc3\xb3gica subjacente, o problema de decidir a validade de uma f\xc3\xb3rmula varia do trivial ao imposs\xc3\xadvel. Para o caso freq\xc3\xbcente da l\xc3\xb3gica proposicional, o problema \xc3\xa9 decid\xc3\xadvel, por\xc3\xa9m Co-NP-complete, acredita-se que existam apenas algoritmos em tempo exponencial para tarefas de prova.  Para a primeira ordem de c\xc3\xa1lculo predicativo, com nenhum axioma pr\xc3\xb3prio, o Teorema da Incompletude de G\xc3\xb6del afirma que qualquer f\xc3\xb3rmula v\xc3\xa1lida pode ser comprovada._NEWLINE_Entretanto, f\xc3\xb3rmulas inv\xc3\xa1lidas n\xc3\xa3o podem sempre serem reconhecias e al\xc3\xa9m disso, uma teoria formal consistente que contem l\xc3\xb3gica de primeira ordem dos n\xc3\xbameros naturais (contendo alguns "axiomas adequados"), por Teorema de incompletude de G\xc3\xb6del, cont\xc3\xa9m senten\xc3\xa7as verdadeiras que n\xc3\xa3o podem ser provadas. Nestes casos, uma prova automatizada do teorema pode vir a falhar, pois poder\xc3\xa1 nunca encontrar uma resposta. Apesar destes limites te\xc3\xb3ricos, na pr\xc3\xa1tica, provadores de teoremas pode resolver muitos problemas dif\xc3\xadceis, mesmo nessas l\xc3\xb3gicas indecid\xc3\xadveis.\n_START_SECTION_\nProblemas relatados\n_START_PARAGRAPH_\nUm dos problemas \xc3\xa9 a "verifica\xc3\xa7\xc3\xa3o da prova", onde uma prova existente para um teorema \xc3\xa9 v\xc3\xa1lida. Para isso, \xc3\xa9 geralmente necess\xc3\xa1rio que cada passo individual da prova possa ser verificado por uma fun\xc3\xa7\xc3\xa3o recursiva primitiva ou programa, e portanto o problema \xc3\xa9 sempre decid\xc3\xadvel._NEWLINE_Desde que a prova gerada automaticamente seja tipicamente muito extensa, o problema da compress\xc3\xa3o da prova \xc3\xa9 crucial e v\xc3\xa1rias t\xc3\xa1ticas e t\xc3\xa9cnicas tentam fazer com que a prova seja a mais sucinta poss\xc3\xadvel._NEWLINE_Assistente de Prova: S\xc3\xa3o necess\xc3\xa1rios usu\xc3\xa1rios humanos capazes de dar dicas de como prosseguir com as provas. Dependendo do grau de automa\xc3\xa7\xc3\xa3o, um supervisor pode diminuir drasticamente o tamanho da prova._NEWLINE_Outra distin\xc3\xa7\xc3\xa3o \xc3\xa9 \xc3\xa0s vezes feita entre prova de teoremas de e outras t\xc3\xa9cnicas, onde um processo \xc3\xa9 considerado prova de teoremas se consiste em uma prova tradicional, come\xc3\xa7ando com os axiomas e produzindo novos passos de infer\xc3\xaancia utilizando para tal.Outras t\xc3\xa9cnicas podem incluir checagem do modelo,que no caso mais simples, envolve for\xc3\xa7a bruta, manual e enumera\xc3\xa7\xc3\xa3o dos muitos estados poss\xc3\xadveis (embora a implementa\xc3\xa7\xc3\xa3o real do modelo requeira muita intelig\xc3\xaancia, e n\xc3\xa3o simplesmente redu\xc3\xa7\xc3\xa3o da for\xc3\xa7a bruta e do trabalho manual e/ou artesanal).\n_START_SECTION_\nUsos na ind\xc3\xbastria\n_START_PARAGRAPH_\nO uso comercial de provas dos teoremas automatizados \xc3\xa9 mais concentrada em projectos de circuito integrado e verifica\xc3\xa7\xc3\xa3o. Desde o bug do Pentium FDIV, as complicadas unidades de ponto flutuante de microprocessadores modernos foram concebidas com controle extra. Atualmente AMD, Intel e outros usam a prova automatizada de teoremas para verificar que a divis\xc3\xa3o e as outras opera\xc3\xa7\xc3\xb5es s\xc3\xa3o corretamente implementadas em seus processadores.\n_START_SECTION_\nProvas de teoremas de primeira-ordem\n_START_PARAGRAPH_\nProvas de teoremas de primeira ordem \xc3\xa9 um dos campos mais maduros da prova automatizada de teoremas. A l\xc3\xb3gica \xc3\xa9 expressiva o suficiente para permitir especifica\xc3\xa7\xc3\xb5es de problemas arbitr\xc3\xa1rios, muitas vezes em uma forma intuitiva e razoavelmente natural. Por outro lado, ainda semi-decifr\xc3\xa1vel e um n\xc3\xbamero grande de c\xc3\xa1lculos automatizados j\xc3\xa1 foi desenvolvido, permitindo sistemas totalmente automatizados. L\xc3\xb3gicas mais expressivas, como a l\xc3\xb3gica de ordem superior, permitem a express\xc3\xa3o adequada de uma ampla gama de problemas de l\xc3\xb3gica de primeira ordem, mas a prova de teoremas para estas l\xc3\xb3gicas \xc3\xa9 bem menos desenvolvida.'