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

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

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

Программа курса

Тема 1. Основы теории множеств. Множества, операции над множествами. Мощность множества, конечные множества. Отношения, виды отношений. [1] Гл. 1, разделы 1.1, 1.3; Гл. 3. разделы 3.1, 3.3, 3.5.

Упражнения. [1] Гл. 1, разделы 1.2, 1.4; Гл. 3, разделы 3.2, 3.4, 3.6.

Тема 2. Функции k-значной логики. Формулы. Функции k-значной логики. Таблицы значений, векторы значений. Формулы, эквивалентные формулы, тождества. Эквивалентные преобразования формул, доказательства тождеств. [1] Гл. 1, разделы 1.1, 1.3; Гл. 3. разделы 3.1, 3.3, 3.5. Упражнения. [1] Гл. 1, разделы 1.2, 1.4; Гл. 3, разделы 3.2, 3.4, 3.6.

Тема 3. Функции k-значной логики. Нормальные формы. Представление функций k-значной логики 1-й и 2-й формами. Полные системы. Система Поста. Полнота системы Поста. [1] Гл. 1, разделы 1.1, 1.3; Гл. 3. разделы 3.1, 3.3, 3.5. Упражнения. [1] Гл. 1, разделы 1.2, 1.4; Гл. 3, разделы 3.2, 3.4, 3.6.

Тема 4. Функции k-значной логики. Полиномы. Полиномы по модулю k. Представление функций k-значной логики полиномами по модулю k. Вычисление коэффициентов полиномов функций k-значной логики. [1] Гл. 1, разделы 1.1, 1.3; Гл. 3. разделы 3.1, 3.3, 3.5. Упражнения. [1] Гл. 1, разделы 1.2, 1.4; Гл. 3, разделы 3.2, 3.4, 3.6.

Коллоквиум 1 по темам 2--4.

Литература

1. Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.
2. Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015.
3. Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012.
4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.