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

Курс для студентов магистратуры кафедры МК, читается в осеннем семестре:

• 1-й курс программы «Дискретные структуры и алгоритмы» — 2 часа лекций и 1 час семинаров в неделю, отчётность экзамен.
• 2-й курс программы «Дискретные управляющие системы» — 2 часа лекций в неделю, отчётность зачёт.

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

Аннотация

В курсе излагаются классические результаты о замкнутости и полноте для булевых функций и функций k-значной логики. Он углубляет сведения, полученные из курса Дискретная математика (1-й курс).

В первой, основной части курса даётся полное описание всех замкнутых классов булевых функций. Во второй части доказывается ряд теорем о полноте для функций k-значной логики. В третьей части курса приводится описание всех предполных классов функций k-значной логики (без доказательств).

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

Программа и основные материалы

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

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

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

Литература

1. Савицкий И.В. Презентации к лекциям. 2025. (в файле присутствует электронное оглавление)
2. Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012. 47 с.
3. Марченков С.С. Избранные главы дискретной математики. М.: Физматлит, 2023. 192 с.
4. Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015. 136 с.

Дополнительная литература

1. Марченков С.С. Основы теории булевых функций. М.: Физматлит, 2014. 135 с.
2. Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. 103 с.
3. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2003. 384 с.
4. Фрейвалд Р.В. Функциональная полнота для не всюду определенных функций алгебры логики // Дискретный анализ. 1966. № 8. С. 55–68.