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

Бакалавриат 2024/2025

Статус: Курс по выбору (Прикладная математика и информатика)

Кто читает: Департамент больших данных и информационного поиска

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

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

Преподаватели: Кудинов Андрей Валерьевич

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

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

Этот курс -- попытка представить математическую логику через призму программирования на Python. Такой подход, позволяет студентам использовать интуицию и опыт программирования для изучения логики и, будем надеяться, сделает логику более доступной и наглядной. Практическая работа с кодом позволяет глубже понять концепции математической логики и увидеть работу этих концепций в реальных программах. В рамках домашних заданий нужно будет реализовать два проекта (модуля) - один для работы с логикой высказываний, и второй - с логикой предикатов.

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

Теорема о дедукции. Примеры выводов с помощью теоремы о дедукции. Контрпримеры.
Существование предваренной нормальной формы. Приведение формулы к предваренной нормальной форме.
Изоморфизмы и автоморфизмы. Выразимые предикаты. Доказательство невыразимости предикатов.
Теории с равенством, нормальные модели. Теорема о существовании нормальной модели.
Примеры теорий и моделей из математики: теория множеств, арифметика, группы, поля, упорядоченные множества, графы, элементарная геометрия.
Теорема о полноте: выведение модели или противоречия для замкнутого множества, замыкание множества, теорема о полноте.
(Если хватит времени) Взгляд на математическую логику II: Теорема Гёделя о неполноте: полные и неполные теории, нумерация Гёделя, неразрешимость проблемы остановки, теорема о неполноте.

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

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

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

Синтаксис логики высказываний
Семантика логики высказываний
Булевы связки, понятия подстановки, полные системы связок
Вывод в логике высказываний, теорема корректности
Доказательство индукцией по длине вывода. Теорема дедукции, допустимые правила примеры выводов
Полезные леммы, доказательство от противного
Теорема о полноте
Синтаксис и семантика предикатной логики
Минимизация сигнатуры - избавление от функциональных символов и равенства
Теории, теории с равенством, нормальные модели. Изоморфизмы и автоморфизмы, выразимость предикатов
Выводы в логике предикатов. Теорема о дедукции

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

Домашнее задание 1
Проект-модуль на Python, реализующий работу с булевыми формулами и реализующий основные конструкции из логики высказываний. Состоит из 6 частей. Оценивается от 0 до 10. Оценка считается, как процент пройденных тестов, деленный на 10.
Домашнее задание 2
Проект-модуль на Python, реализующий работу с формулами логики предикатов и реализующий основные конструкции из логики предикатов. Состоит из 6 частей. Оценивается от 0 до 10. Оценка считается, как процент пройденных тестов, деленный на 10.
Коллоквиум
Коллоквиум проводится устно. Выдается билет, в билете дается два теоретических вопроса и одно практическое задание.За каждый пункт дается от 0 до 3 балла и еще 1 балл можно получить за дополнительные вопросы. Вопросы покрывают пройденный в 3 модуле материал. Проводится во время сессии после 3 модуля.
Экзамен
Экзамен проводится устно. Выдается билет, в билете дается два теоретических вопроса и одно практическое задание. За каждый пункт дается от 0 до 3 балла и еще 1 балл можно получить за дополнительные вопросы. Вопросы покрывают пройденный в 4 модуле материал.

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

2024/2025 4th module
В формуле участвуют: ДЗ -- доля пройденных тестов в заданиях на Python умноженная на 10. Колл -- оценка за коллоквиум, который пройдет после 3 модуля во время сессии (по 10 бальной шкале). Экз -- оценка за экзамен (по 10 бальной шкале) Автомат будет выставлятся при условии, что MIN(ДЗ, Колл) >= 8. В этом случае итоговая оценка будет равна (2*ДЗ+Колл)/3, с округлением к ближайшему целому числу. Итоговая оценка = 0.5 ДЗ + 0.25 Колл + 0.25 Экз

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

Авторы

Кудинов Андрей Валерьевич

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