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

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

Статус: Курс обязательный (Информационная безопасность)

Направление: 10.03.01. Информационная безопасность

Кто читает: Департамент прикладной математики

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 2-й курс, 4 модуль

Формат изучения: с онлайн-курсом

Преподаватели: Славнов Сергей Андреевич

Язык: русский

Кредиты: 3

Контактные часы: 28

Программа дисциплины

Аннотация

Математическая логика относится к теоретическому фундаменту, на котором основаны все существующие и будущие информационные технологии. С помощью логики выражаются семантика языков программирования, спецификация программ (что программа делать), выполняется верификация программ (проверяется, делает ли программа в точности то, что от нее ожидают). Целями освоения дисциплины Математическая логика являются • получение представления об основных структурах, объектах и задачах математической логики и теории алгоритмов; • получение знания об основных результатах классической математической логики и теории алгоритмов; • развитие логической и алгоритмической интуиции. В результате освоения дисциплины студент должен: • Владеть основными методами преобразования логических выражений. • Уметь записывать содержательные математические утверждения в языке исчисления предикатов. • Владеть методами доказательства теорем в исчислении высказываний и исчислении предикатов. • Владеть основными понятиями теории алгоритмов: вычислимость, разрешимость, перечислимость. • Уметь решать простые задачи о неразрешимости алгоритмических проблем.

Цель освоения дисциплины

• Получение представления об основных структурах, объектах и задачах математической логики и теории алгоритмов
• Получение знания об основных результатах классической математической логики и теории алгоритмов;
• Развитие логической и алгоритмической интуиции.

Планируемые результаты обучения

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

Содержание учебной дисциплины

• Логика высказываний
  Булевы связки и формулы. Логическое следование. Выполнимость и общезначимость. Основные тавтологии и равносильности. Выводимость. Теорема о дедукции. Теорема о полноте.
• Логика предикатов
  Язык логики первого порядка. Свободные и связанные переменные. Выполнимость и общезначимость в логике предикатов. Выводимость. Теории первого порядка.
• Вычислимость
  Машина Тьюринга. Вычислимые функции. Тезис Тьюринга. Универсальная машина и универсальная функция. Разрешимость и перечислимость. Проблема остановки. Теорема Райса.

Элементы контроля

• Домашние задания
• Контрольная работа
• экзамен

Промежуточная аттестация

• Промежуточная аттестация (4 модуль)
  0.5 * Контрольная работа + 0.5 * экзамен

Список литературы

Рекомендуемая основная литература

• Введение в математическую логику, Мендельсон, Э., 1971
• Введение в математическую логику, Мендельсон, Э., 1976
• Введение в математическую логику, Мендельсон, Э., 1984

Рекомендуемая дополнительная литература

• Лекции по математической логике и теории алгоритмов. Ч.2: Языки и исчисления, Верещагин, Н. К., 2002
• Лекции по математической логике и теории алгоритмов. Ч.2: Языки и исчисления, Верещагин, Н. К., 2012