Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

более чем двух тысяч лет образцом строгого и ясного изложения математической теории-геометрии. Отличительной особенностью дедуктивных теорий является возможность логического вывода большей части их содержания из небольшого числа исходных посылок, называемых аксиомами. К таким теориям относятся, прежде всего, математика и теории математического естествознания (механика, теоретическая физика), а также те науки, в которых широко используются математические методы исследования. Логическая структура дедуктивных теорий может быть представлена наиболее точно и определенно с помош,ью аксиоматического метода. Согласно этому методу, все понятия теории разделяются на немногие основные, или первоначальные, понятия и большинство производных, которые получаются из основных с помош,ью определений. Аналогично этому все утверждения теории разбиваются на два класса: исходные утверждения, или аксиомы, и утверждения, логически выводимые из них с помош,ью правил. Наибольшие успехи в настояш,ее время достигнуты в исследовании структуры математических теорий. Они являются результатом преодоления тех трудностей и парадоксов, которые возникли в теории множеств, считавшейся незыблемым фундаментом классической математики. С этой целью математики стали тш,ательно анализировать исходные понятия и принципы теории множеств. Чтобы избежать парадоксов, обнаруженных в этой теории, ее стали строить в аксиоматической форме. Особого внимания заслуживают результаты исследований К. Гёделя, сформулированные в двух знаменитых его теоремах. В первой из них доказывается, что всякая формальная система, содержащая, по крайней мере, формальную арифметику, суш,ественно неполна. Это означает, что в такой системе всегда можно построить некоторую формулу, которая будет в ней неразрешима, т.е. ни истинность, ни ложность ее нельзя будет доказать. Из этой теоремы следует важный методологический результат: содержательную математику нельзя формализовать полностью. Это свидетельствует о том, что аксиоматический подход имеет свои границы. Вторая теорема устанавливает, что если формальная система непротиворечива, то не суш,ествует доказательства ее непротиворечивости с помош,ью средств, формализуемых в этой системе. Отсюда можно сделать предположение о суш,ествовании целой иерархии формальных систем, в которой каждая из последуюш,их превосходит предыдущую систему по силе средств формализации. Следовательно, в ходе развития дедуктивных наук их формализация не может быть завершена на каком-то исторически определенном этапе. Основной результат немецкого математика Г. Генцена состоит в установлении возможности приведения каждого вывода в исчислении 141