Функциональные системы

Курс по магистерской программе Дискретные структуры и алгоритмы.

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

2024-2025 учебный год

Лектор — Савицкий Игорь Владимирович.

Зачёт и экзамен

Зачёт у группы 218мк_дус пройдёт 26 декабря (четверг) в 12:15.

Экзамен у группы 118мк_дус пройдёт 6 января (понедельник) в 9:00 в ауд. 503.

Вопросы к экзамену и зачёту

Материалы

Презентации к лекциям (в файле присутствует электронное оглавление)

Диаграмма Поста (изображение всех замкнутых классов булевых функций с отношением включения)

2023-2024 учебный год

Лектор — проф. Марченков Сергей Серафимович.

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

Диаграмма Поста (изображение всех замкнутых классов булевых функций с отношением включения)

Программа курса (вопросы к экзамену и зачёту)

Литература

• Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012. 47 с.
• Марченков С.С. Основы теории булевых функций. М.: Физматлит, 2014. 135 с.
• Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. 103 с.
• Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2003. 384 с.
• Фрейвалд Р.В. Функциональная полнота для не всюду определенных функций алгебры логики // Дискретный анализ. 1966. Вып. 8. С. 55-68.