Que tipo de problemas de matemática pode ser resolvido por provadores de teoremas automatizados?

Posso provar as seguintes declarações usando provadores de teoremas automatizados disponíveis?

. $(a+b)^2=a^2+b^2+2ab$
Se , então . $11 \mid 2a-3b$ $11 \mid 7a-5b$
Se , . $ax^2+bx+c=0$ $x=\frac{-b\pm\sqrt{b^2-4ac} }{2a}$
Se é par, então é par. $a$ $4a$

e assim por diante!

Estou fazendo essa pergunta porque acabei de encontrar a aplicação de provadores de teoremas automatizados para provar teoremas em lógica.

automated-theorem-proving Math-fort
fonte

Certamente você pode provar tudo isso (exceto talvez 3, o que está errado conforme escrito) usando todos os assistentes de prova padrão, embora provavelmente não seja automático.

Yuval Filmus

@YuvalFilmus. Obrigado! Então, que tipo de problemas podem ser resolvidos automaticamente?

Math-fort

Você pode simplificar as expressões automaticamente, embora este seja um serviço fornecido pela Computer Algebra Systems. Eu não acho que os assistentes de prova modernos possam provar automaticamente algo substancial, embora seja melhor perguntar aos especialistas.

Yuval Filmus

@YuvalFilmus Eu acho que o que você diz é frequentemente verdadeiro, no sentido de que apenas quando um método de prova automatizado dá resultados interessantes, estamos dispostos a chamá-lo de uma parte de um CAS ...

lagarto Discrete

"(a + b) ^ 2 == a ^ 2 + b ^ 2 + 2ab" em WolframAlpha

Nat

Respostas:

Como muitas de suas declarações são álgebra elementar, elas podem ser comprovadas automaticamente por um sistema de álgebra computacional (CAS), como Maple ou Mathematica.

(Caso você esteja interessado na matemática por trás do CAS, eu posso recomendar o livro Álgebra Moderna de Computador, de Joachim von zur Gathen e Jürgen Gerhard, um belo livro, considerado a 'Bíblia' do campo)

A prova automatizada de teoremas tende a ser principalmente um caso de pesquisa heurística em uma estrutura que representa provas, se a prova não for um dos poucos casos para os quais existe um algoritmo que pode resolvê-la conclusivamente. Dado que essas declarações não são muito complicadas, é provável que um fornecedor automatizado seja capaz de 'encontrar' uma prova.

No entanto, acho interessante dizer um pouco mais sobre as declarações para as quais existem bons algoritmos:

A afirmação 3 é (um caso muito simples de) sobre raízes de um (sistema de) equações polinomiais e pode ser resolvida encontrando uma base de Gröbner com o algoritmo de Buchberger. A base de Gröbner e o algoritmo de Buchberger para encontrar uma são ferramentas muito boas para a prova automatizada de teoremas. Por exemplo, podemos provar automaticamente teoremas elementares em geometria, transformando automaticamente o problema para encontrar a raiz de uma equação polinomial de maneira inteligente!

Outra classe interessante de teoremas são afirmações expressas na aritmética de Presburger sem quantificador (em particular, essa aritmética é sem multiplicação, portanto não se aplica às suas afirmações), pois existe um algoritmo para resolver todas essas afirmações, mesmo que o algoritmo é um pouco lento.

Lagarto discreto
fonte