Какие математические задачи могут быть решены с помощью автоматизированных проверок теорем?

Могу ли я доказать следующие утверждения, используя доступные автоматические средства проверки теорем?

. $(a+b)^2=a^2+b^2+2ab$
Если , а затем . $11 \mid 2a-3b$ $11 \mid 7a-5b$
Если , то $ax^2+bx+c=0$ . $x=\frac{-b\pm\sqrt{b^2-4ac} }{2a}$
Если четное, то четное. $a$ $4a$

и так далее!

Я задаю этот вопрос, потому что я только что нашел применение автоматических доказательств теорем в доказательстве теорем в логике.

automated-theorem-proving Math-крепость
источник

Вы, безусловно, можете доказать все это (кроме, возможно, 3, что не так, как написано), используя все стандартные помощники доказательства, хотя это, вероятно, не будет автоматическим.

Юваль Фильмус

@YuvalFilmus. Благодарность! Так какие проблемы могут быть решены автоматически?

Math-

Вы можете упростить выражения автоматически, хотя это услуга, предоставляемая Computer Algebra Systems. Я не думаю, что современные ассистенты могут автоматически доказать что-либо существенное, хотя лучше спросить экспертов.

Юваль Фильмус

@YuvalFilmus Я думаю, что то, что вы говорите, часто является правдой, в том смысле, что только когда автоматический метод доказательства дает интересные результаты, мы готовы назвать его частью CAS ...

Дискретная ящерица

"(a + b) ^ 2 == a ^ 2 + b ^ 2 + 2ab" на WolframAlpha

Nat

Ответы:

Большинство ваших утверждений являются элементарной алгеброй, поэтому они могут быть автоматически доказаны системой компьютерной алгебры (CAS), такой как Maple или Mathematica.

(Если вам интересна математика, стоящая за CAS, я могу порекомендовать книгу « Современная компьютерная алгебра » Иоахима фон цур Гатена и Юргена Герхарда, прекрасную книгу, которая считается «библией» области)

Автоматическое доказательство теорем имеет тенденцию быть в основном случаем эвристического поиска в структуре, которая представляет доказательства, если доказательство не является одним из немногих случаев, для которых существует алгоритм, который может окончательно решить его. Учитывая, что эти утверждения не очень сложны, вполне вероятно, что автоматическое средство проверки может «найти» доказательство.

Тем не менее, я думаю, что было бы интересно сказать немного больше об утверждениях, для которых есть хорошие алгоритмы:

Утверждение 3 (очень простой случай) о корнях (системы) полиномиальных уравнений и может быть решено путем нахождения базиса Гребнера с помощью алгоритма Бухбергера. Базис Грёбнера и алгоритм Бухбергера для его поиска являются очень хорошими инструментами для автоматического доказательства теорем. Например, мы можем даже автоматически доказать элементарные теоремы в геометрии, автоматически преобразовав задачу в нахождение корня полиномиального уравнения умным способом!

Еще один интересный класс теорем - это операторы, выражаемые в арифметике Пресбургера без квантификаторов (в частности, эта арифметика без умножения, поэтому она не применима к вашим операторам), поскольку существует алгоритм для решения всех таких операторов, даже если алгоритм немного медленно

Дискретная ящерица
источник