Избранные вопросы дискретной математики

Курс читает Селезнева Светлана Николаевна

Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.

Лекции

Часть 1. Функции k-значной логики.

Лекция 1. Функции k-значной логики. Формулы. Тождества. Представимость функций k-значной логики в 1-й и 2-й формах.

Лекция 2. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.

Лекция 3. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.

Лекция 4. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Алгоритм распознавания полноты в P_k.

Лекция 5. Замкнутые классы. Отношения. Сохранение функцией отношения. Замкнутость класса всех функций, сохраняющих заданное отношение. Классы функций, сохраняющих некоторые отношения.

Лекция 6. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k.

Лекция 7. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k.

Коллоквиум по теме "Функции k-значной логики".

Литература

Основная:

1. Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
2. Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
3. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.

Дополнительная:

1. Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2016. Глава 1.
2. Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. Глава 1.
3. Яблонский С.В., Гаврилов Г.П., Набебин А.А. Предполные классы в многозначных логиках. М.: МЭИ, 1997. Часть 1.
4. Lau D. Function Algebras on Finite Sets. Springer, 2006.
5. Горшков С.П., Тарасов А.В. Сложность решения систем булевых уравнений. М.: Курс, 2017.