Бакалавриат
2024/2025
Научно-исследовательский семинар "Логика и алгоритмы"
Статус:
Курс обязательный (Совместный бакалавриат НИУ ВШЭ и ЦПМ)
Направление:
01.03.01. Математика
Кто читает:
Факультет математики
Где читается:
Факультет математики
Когда читается:
2-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Рыбаков Михаил Николаевич
Язык:
русский
Кредиты:
6
Программа дисциплины
Аннотация
Целями освоения дисциплины Логика и алгоритмы являются • получение представления об основных структурах, объектах и задачах математической логики и теории алгоритмов; • получение знания об основных результатах классической математической логики и теории алгоритмов; • получение представления о методах работы с формализованными логическими теориями; • развитие логической и алгоритмической интуиции. В результате освоения дисциплины студент должен: • Владеть основными методами преобразования логических выражений. • Владеть основными понятиями теории множеств. • Уметь записывать содержательные математические утверждения в языке исчисления предикатов. • Владеть методами доказательства теорем в исчислении высказываний и исчислении предикатов. • Владеть основными понятиями теории алгоритмов: вычислимость, разрешимость, перечислимость. • Уметь строить модели формул и теорий первого порядка. • Уметь реализовывать простые алгоритмы с помощью машин Тьюринга. • Знать важнейшие теоремы классической теории алгоритмов. • Уметь решать простые задачи о неразрешимости алгоритмических проблем. Для специализации математика настоящая дисциплина является базовой, относится к математическому и естественнонаучному циклу. Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин: математический анализ, алгебра, топология.
Цель освоения дисциплины
- Получение представления об основных структурах, объектах и задачах математической логики и теории алгоритмов
- Получение знания об основных результатах классической математической логики и теории алгоритмов;
- Получение представления о методах работы с формализованными логическими теориями;
- Развитие логической и алгоритмической интуиции.
Планируемые результаты обучения
- Владеть методами доказательства теорем в исчислении высказываний
- Владеть основными методами преобразования логических выражений, владеть основными понятиями теории множеств.
- Владеть основными понятиями теории алгоритмов: вычислимость, разрешимость, перечислимость. Уметь строить модели формул и теорий первого порядка. Уметь реализовывать простые алгоритмы с помощью машин Тьюринга. Знать важнейшие теоремы классической теории алгоритмов. Уметь решать простые задачи о неразрешимости алгоритмических проблем
- Уметь записывать содержательные математические утверждения в языке исчисления предикатов, и методами доказательства теорем в исчислении предикатов
Содержание учебной дисциплины
- Логика высказываний и элементы теории множеств
- Логика предикатов
- Теория алгоритмов
- Введение.Предмет математической логики. Вопросы оснований математики.
- Аксиоматическое построение элементарной геометрии, роль аксиомы о парал-лельных. Парадоксы теории множеств, семантические парадоксы. Формальный аксиоматический метод Гильберта, программа Гильбертаю Роль теорем Гёделя о неполноте.
- Логика высказываний. Теорема о дизъюнктивной нормальной форме. Исчисле-ние высказываний в секвенциальной форме Генцена. Теорема о полноте.
- Интуиционизм как философия математики. Интерпретация интуиционистской логики по Брауэру-Гейтингу-Колмогорову. Интуиционистская логика высказы-ваний, е модели Крипке. Теорема Крипке о полноте интуиционистской логики высказываний. Дизъюнктивное свойство. Теорема Гливенко.
- Модальности и их возможные интерпретации. Модальные логики, логика S4, пе-ревод Гёделя. Теорема о несоотвествии интуиционистской логики и модальной логики S4. Эпистемическое понимание модальности для системы с несколькими агентами. Логика S5, ее полнота по Крипке. Модальность как доказуемость, ло-гика доказуемости Гёделя-Лёба.
- Логика предикатов.
- Предикаты. Переменные и их области изменения. Кванторы.
- Языки первого порядка: термы, формулы, подформулы. Примеры языков первого порядка: язык арифметики, язык элементарной геометрии.
- Аксиомы и правила вывода исчисления предикатов (без доказательств). Теорема о компактности для логики предикатов.
- Нестандартные модели арифметики, их существование.
- Описание отношения порядка для счетных нестандартных моделей арифметики.
- Элиминация кванторов. Теореиа Тарского о разрешимости теории поля вещественных чисел и элементарной геометрии.
- Формальная арифметика, ее стандартная модель.
- Интерпретации (алгебраические системы, модели) для данного языка первого порядка. Истинность замкнутой формулы в данной интерпретации. Предикаты, выразимые в данной интерпретации.
- Сигма-определитель в стандартной модели арифметики.
- Эквивалентность понятий перечислимого и сигма-определимого множества. Неперечислимость множества арифметических истин. Проблема распознавания истинности замкнутых арифметических формул, ее алгоритмическая неразреши-мость. Теорема Гёделя о неполноте формальной арифметики (вторая теорема Гёделя о неполноте без доказательства)
Элементы контроля
- Домашние заданияРегулярные домашние задания, для которых будет общий суммарный балл.
- Контрольная работа
- Экзамен
Промежуточная аттестация
- 2024/2025 4th module0.15 * Домашние задания + 0.15 * Домашние задания + 0.4 * Контрольная работа + 0.3 * Экзамен
