Бакалавриат
2020/2021



Математическая логика
Статус:
Курс обязательный (Информационная безопасность)
Направление:
10.03.01. Информационная безопасность
Кто читает:
Департамент прикладной математики
Когда читается:
2-й курс, 4 модуль
Формат изучения:
с онлайн-курсом
Преподаватели:
Славнов Сергей Андреевич
Язык:
русский
Кредиты:
3
Контактные часы:
28
Программа дисциплины
Аннотация
Математическая логика относится к теоретическому фундаменту, на котором основаны все существующие и будущие информационные технологии. С помощью логики выражаются семантика языков программирования, спецификация программ (что программа делать), выполняется верификация программ (проверяется, делает ли программа в точности то, что от нее ожидают). Целями освоения дисциплины Математическая логика являются • получение представления об основных структурах, объектах и задачах математической логики и теории алгоритмов; • получение знания об основных результатах классической математической логики и теории алгоритмов; • развитие логической и алгоритмической интуиции. В результате освоения дисциплины студент должен: • Владеть основными методами преобразования логических выражений. • Уметь записывать содержательные математические утверждения в языке исчисления предикатов. • Владеть методами доказательства теорем в исчислении высказываний и исчислении предикатов. • Владеть основными понятиями теории алгоритмов: вычислимость, разрешимость, перечислимость. • Уметь решать простые задачи о неразрешимости алгоритмических проблем.
Цель освоения дисциплины
- Получение представления об основных структурах, объектах и задачах математической логики и теории алгоритмов
- Получение знания об основных результатах классической математической логики и теории алгоритмов;
- Развитие логической и алгоритмической интуиции.
Планируемые результаты обучения
- Владеть методами доказательства теорем в исчислении высказываний
- Владеть основными методами преобразования логических выражений
- Уметь записывать содержательные математические утверждения в языке исчисления предикатов
- Владеть методами доказательства теорем в исчислении предикатов
- Владеть основными понятиями теории алгоритмов: вычислимость, разрешимость, перечислимость. Уметь строить модели формул и теорий первого порядка. Уметь реализовывать простые алгоритмы с помощью машин Тьюринга. Знать важнейшие теоремы классической теории алгоритмов. Уметь решать простые задачи о неразрешимости алгоритмических проблем
Содержание учебной дисциплины
- Логика высказыванийБулевы связки и формулы. Логическое следование. Выполнимость и общезначимость. Основные тавтологии и равносильности. Выводимость. Теорема о дедукции. Теорема о полноте.
- Логика предикатовЯзык логики первого порядка. Свободные и связанные переменные. Выполнимость и общезначимость в логике предикатов. Выводимость. Теории первого порядка.
- ВычислимостьМашина Тьюринга. Вычислимые функции. Тезис Тьюринга. Универсальная машина и универсальная функция. Разрешимость и перечислимость. Проблема остановки. Теорема Райса.
Список литературы
Рекомендуемая основная литература
- Введение в математическую логику, Мендельсон, Э., 1971
- Введение в математическую логику, Мендельсон, Э., 1976
- Введение в математическую логику, Мендельсон, Э., 1984
Рекомендуемая дополнительная литература
- Лекции по математической логике и теории алгоритмов. Ч.2: Языки и исчисления, Верещагин, Н. К., 2002
- Лекции по математической логике и теории алгоритмов. Ч.2: Языки и исчисления, Верещагин, Н. К., 2012