Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Математическая логика

Математическая логика сложилась как научная дисциплина в начале XX века в результате так называемого кризиса в основаниях математики. Выдающихся математиков и философов той героической эпохи (Гильберт, Пуанкаре, Брауэр, Вейль, Фреге, Рассел и др.) волновали такие фундаментальные вопросы, как:

  • Что означает доказать математическую теорему? Какие средства при этом законно использовать?
  • Что значит выразить то или иное математическое понятие или утверждение в том или ином языке?
  • Как построить непротиворечивую систему аксиом теории множеств?
  • Можно ли доказать любое истинное утверждение, скажем, относящееся к арифметике целых чисел?
  • Противоречива ли математика? И если нет, то каким образом это можно установить?

Все эти вопросы привели к первым формулировкам строгих математических моделей таких понятий как доказуемость, выразимость, истинность, до тех пор относившихся к чистой философии, и сделали возможным их изучение математическими методами. Так возникла математическая логика как особая область исследований внутри математики.

 

Формальные языки и формальные системы впервые возникли именно в математической логике, поэтому неудивительно, что наиболее практически значимые системы такого рода — вычислительные модели, языки программирования — также обязаны своим открытием нашей науке. Важным толчком к анализу понятия вычислимости послужила формулировка Гильбертом так называемой Entscheidungsproblem — проблемы существования алгоритма, по данному утверждению в логике предикатов отвечающего на вопрос, доказуемо ли оно. Отрицательное решение этой проблемы, вместе со строгой формулировкой понятий вычислимой функции (и алгоритмически разрешимой проблемы) было дано А. Черчем и, независимо, А. Тьюрингом в 1935-36 годах. При этом Тьюринг сформулировал ставшее классическим понятие универсальной вычислительной машины, ключевые черты которой были еще через 15 лет воплощены, в том числе и самим Тьюрингом, в реально работающих компьютерах. (Работа Черча, основанная на другой универсальной вычислительной модели, λ-исчислении, так же не осталась забытой — это исчисление послужило прообразом целого класса языков программирования, так называемых функциональных языков, весьма популярных в настоящее время.)

При том, что проблематика оснований математики, теории доказательств и теории алгоритмов по прежнему остается актуальной, к настоящему времени область приложений методов математической логики значительно расширилась. Возникает более широкое понимание того, что составляет предмет и задачи математической логики.

Математическая логика и теория алгоритмов строят математические модели того, как человек мыслит, передает мысли другому, преобразует мысли в действия. Это явное присутствие человека отличает наш предмет от других областей математики, делает его особенно интересным и нужным, приводит к использованию, в том числе, гуманитарных источников задач и приложений. О гуманитарной природе всей математики можно читать в работах профессора Владимира Андреевича Успенского, который с 1995 по 2018 г. заведовал нашей кафедрой.

Математическая логика и теория алгоритмов являются фундаментальной основой когнитивных наук, начавших наиболее бурное развитие в XXI веке. Если XIX был веком математических моделей механических систем (включая модели «небесной механики» и «тепловых машин»), основной научно-технологического прогресса в XX веке были математические модели информационных систем, то в XXI веке математики строят модели, позволяющие сделать «точными», снабдить математическим аппаратом такие области знания, как биология и гуманитарные: психологию, философию, лингвистику, педагогику. Эти модели строятся именно в нашей области математики и, кроме того, служат основой для построения систем искусственного интеллекта. Не удивительно, что именно В. А. Успенскому принадлежала инициатива реформы лингвистического образования, введения в него курса математики. Реализацией этой инициативы стало открытие отделения «точного языкознания» (отделения теоретической и прикладной лингвистики) на филологическом факультете МГУ. Наша кафедра продолжает традицию сотрудничества с этим отделением — сотрудники и аспиранты преподают там математику и ведут научные семинары.