Кафедра математической логики и теории алгоритмов

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

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

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

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

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

Лог семинаров в группах 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).
  • Семинар 4, 14.10/21.10.  Выразимые предикаты (ВШ-2, 3.3), доказательство невыразимости при помощи автоморфизмов (ВШ-2, 3.5), элиминация кванторов (ВШ-2, 3.6).

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

Дедлайн указан для групп 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.

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

  1. [ВШ-1] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств
  2. [ВШ-2] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления
  3. [ВШ-3] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции