Семинары по курсу «Введение в математическую логику и теорию алгоритмов», 2021, группы 209/210.

Видеозаписи лекций.

Ссылка на таблицу с баллами в группах 209/210.

Способы получения баллов:

решить задачу на лекции (до 3 баллов);
сдать задачи из семинарских листочков (до 15 баллов) — прислать мне решения на почту ansidiana@yandex.ru или в телеграм @ansidiana, после чего коротко обсудить решения;
активно поучаствовать в просеминаре (до 5 баллов).

(обновлено 24.12.2021) Список студентов, получивших бонусы, разослан по электронной почте.

Лог семинаров в группах 209/210.

Семинар 1, 02.09/09.09. Наивная теория множеств (ВШ-1, 1.1), равномощные множества (ВШ-1, 1.3), вполне упорядоченные множества (ВШ-1, 2.4), теорема Цермело, лемма Цорна и базис Гамеля (ВШ-1, 2.5-2.8).
Семинар 2, 16.09/23.09. Теорема Кантора-Бернштейна (ВШ-1, 1.5), формулы первого порядка и интерпретации (ВШ-2, 3.1), истинность формулы в модели (ВШ-2, 3.2), выполнимые и общезначимые формулы (ВШ-2, 4.1).
Семинар 3, 30.09/07.10. Аксиомы и правила вывода исчисления предикатов (ВШ-2, 4.2), примеры выводов (ВШ-2, 4.4), полнота исчисления предикатов и теорема о компактности (ВШ-2, 4.5), теории с равенством (ВШ-2, 5.1). Слайды 209/210.
Семинар 4, 14.10/21.10. Выразимые предикаты (ВШ-2, 3.3), доказательство невыразимости при помощи автоморфизмов (ВШ-2, 3.5), элиминация кванторов (ВШ-2, 3.6).
Семинар 5, 28.10/28.10. Модальная логика, модели Крипке (Шап, лекция 1; CZ, 3.1, 3.2), задание свойств отношения R на множестве W модальной формулой (CZ, 3.5), минимальная модальная логика К (CZ, 3.6), модальная логика S4 (CZ, 3.8). Видео. Слайды.
Семинар 6, 11.11/18.11. Спектр замкнутой формулы, теоремы Лёвенгейма-Сколема [ВШ-2, 5.2 и 3.11], полные теории, категоричные в данной мощности теории, критерий Лося-Воота, разрешимые теории, конечно аксиоматизируемые теории [ВШ-2, 5.3]. (Рекомендуется также раздел [ВШ-2, 5.4] для самостоятельного изучения.)
Семинар 7, 25.11/02.12. Вычислимые функции [ВШ-3, 1.1], разрешимые множества [ВШ-3, 1.2], перечислимые множества [ВШ-3, 1.3], теорема Поста [ВШ-3, 1.4], некоторые свойства перечислимых множеств [ВШ-3, 1.5], универсальная вычислимая функция [ВШ-3, 2.1], диагональная функция [ВШ-3, 2.2], существование перечислимого неразрешимого множества [ВШ-3, 2.3].
Семинар 8, 16.12/16.12 Предварённая нормальная форма [ВШ-2, 4.7], игра Эренфойхта [ВШ-2, 3.10].

Задачи для подготовки к экзамену.

Листочки с задачами.

Дедлайн указан для групп 209/210 (до косой черты — для группы 209, после косой черты — для группы 210).

Листок 1. Теория множеств. Сдать до 21.09/30.09.
Листок 2. Языки первого порядка. Сдать до 22.10/29.10.
Листок 3. Компактность. Сдать до 22.10/29.10.
Листок 4. Выразимость. Сдать до 05.11/12.11.
Листок 5. Элиминация кванторов. Сдать до 05.11/12.11.
Листок 6. Модальная логика. Сдать до 21.11/21.11.
Листок 7. Теория моделей. Сдать до 02.12/09.12.
Листок 8. Вычислимость. Сдать до 16.12/23.12.
Листок с трудными задачами. Можно сдавать до 23.12.

Семинары по курсу «Введение в математическую логику и теорию алгоритмов», 2021, группы 209/210.

Лог семинаров в группах 209/210.

Листочки с задачами.

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