Научно-исследовательский семинар "Логика и алгоритмы"

Бакалавриат 2022/2023

Статус: Курс обязательный (Совместный бакалавриат НИУ ВШЭ и ЦПМ)

Направление: 01.03.01. Математика

Кто читает: Факультет математики

Где читается: Факультет математики

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

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

Охват аудитории: для своего кампуса

Преподаватели: Запрягаев Александр Александрович, Рыбаков Михаил Николаевич

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

Кредиты: 5

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

Дополнительные материалы в LMS Задать вопрос

Аннотация

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

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

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

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

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

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

Введение.Предмет математической логики. Вопросы оснований математики.
Логика высказываний и элементы теории множеств
Логика высказываний. Теорема о дизъюнктивной нормальной форме. Исчисле-ние высказываний в секвенциальной форме Генцена. Теорема о полноте.
Интуиционизм как философия математики. Интерпретация интуиционистской логики по Брауэру-Гейтингу-Колмогорову. Интуиционистская логика высказы-ваний, е модели Крипке. Теорема Крипке о полноте интуиционистской логики высказываний. Дизъюнктивное свойство. Теорема Гливенко.
Логика предикатов
Предикаты. Переменные и их области изменения. Кванторы.
Языки первого порядка: термы, формулы, подформулы. Примеры языков первого порядка: язык арифметики, язык элементарной геометрии.
Интерпретации (алгебраические системы, модели) для данного языка первого порядка. Истинность замкнутой формулы в данной интерпретации. Предикаты, выразимые в данной интерпретации.
Аксиомы и правила вывода исчисления предикатов (без доказательств). Теорема о компактности для логики предикатов.
Теория алгоритмов
Вычислительные модели: многоленточные машины Тьюринга, частично-рекурсивные функции, машины с неограниченными регистрами. Оценка времени и памяти, необходимых для реализации основных арифметических алгоритмов. Тезис Чёрча.
Понятие вычислимой функции, разрешимого множества.
Перечислимые множества.
Перечислимость и разрешимость (теорема Поста, теорема о проекции разреши-мого множества).
Универсальные вычислимые функции.
Построение перечислимого неразрешимого множества.
Алгоритмически неразрешимые проблемы в теории алгоритмов.
Примеры других алгоритмически неразрешимых проблем в алгебре и теории чисел.
Модальности и их возможные интерпретации. Модальные логики, логика S4, пе-ревод Гёделя. Теорема о несоотвествии интуиционистской логики и модальной логики S4. Эпистемическое понимание модальности для системы с несколькими агентами. Логика S5, ее полнота по Крипке. Модальность как доказуемость, ло-гика доказуемости Гёделя-Лёба.

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

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

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

2022/2023 учебный год 4 модуль
0.15 * Домашнее задание + 0.4 * Контрольная работа + 0.3 * Экзамен

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

Авторы

Рыбаков Михаил Николаевич

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