Основное содержание дисциплины ориентировано на овладение умения работы с логическими объектами; подготовку к осознанному использованию исчисления высказываний, исчисления предикатов, функциональных исчислений. Дисциплина позволяет сформировать представление о роли, которую играет математическая логика в современной математике и информатике; о математически точном построении логических исчислений, аксиоматических системах и доказательствах теорем в рамках аксиоматических систем. Работа с математическими объектами, математическая строгость мышления, осуществляемые в рамках данной дисциплины необходимы для исследовательской работы в области физико-математического образования и образования в области информатики и вычислительной техники. Решаемые с помощью аппарата математической логики классы задач, и методы, применяемые для их решения, в дальнейшем будут основой для исследования задач искусственного интеллекта.
Основные понятия математической логики. Роль математической логики, как теоретической основы математики и информатики. Влияние математической логики на развитие информатики. Формулы исчисления высказываний и их интерпретация. Алгебра логики и равносильные преобразования. Нормальные формы. Алгоритм Девиса-Патнема для проверки выполнимости нормальных форм. Метод резолюций в исчислении высказываний. Проблема дедукции и ее значение в математической логике и информатике. Прямая Теорема Робинсона и правило резолюций. Понятие предиката. Синтаксис и семантика формул исчисления предикатов. Предваренные и нормальные формы. Сколемовские и клаузальные формы. Метод резолюций в исчислении предикатов. Проблема дедукции в исчислении предикатов. Связь исчисления предикатов с системами представления знаний в задачах искусственного интеллекта. Определение аксиоматических теорий. Полнота и минимальность. Правила вывода и доказательства, примеры доказательства теорем. Аксиоматические теории натурального вывода. Теорема Геделя о неполноте. Теория доказательств первого порядка.