Дискретная математика и математическая логика — 2020

Лекции

Материалы лекций можно найти здесь.

Практические занятия

Условия задач на белорусском языке

Первый семестр

Задачи первого-второго практического занятия (Высказывания. Логические операции над высказываниями. Формулы)(исходник)

Задачи третьего практического занятия (Приложения логики высказываний)(исходник)

Задачи четвёртого-пятого-шестого практического занятия (Множества. Отображения. Принцип Дирихле)(исходник)

Задачи седьмого практического занятия (Бинарные отношения. Отношения эквивалентности)(исходник)

Задачи восьмого практического занятия (Логика предикатов)(исходник)

Задачи девятого практического занятия (Основные правила комбинаторики)([ исходник])

Задачи десятого практического занятия (Размещения. Перестановки. Сочетания)(исходник)

Задачи одиннадцатого практического занятия (Перестановки с повторениями)(исходник)

Задачи двенадцатого практического занятия (Разбиения множеств и чисел. Метод включения и исключения)(исходник)

Задачи тринадцатого практического занятия (Рекуррентные соотношения. Производящие функции)(исходник)

Основные сведения по комбинаторике (будет дополняться)(исходник)

Второй семестр

Основные сведения о булевых функциях. Упрощения формул. Существенные и фиктивные переменные(исходник)

Основные представления булевых функций: ДНФ, КНФ, СДНФ, СКНФ, полином Жегалкина(исходник)

Замкнутость и полнота. Основные классы замкнутых функций(исходник)

Теорема Поста. Минимизация булевых функций(исходник)

Азбука теории графов(исходник)

Деревья: основные свойства, степенная последовательность, код Прюфера(исходник)

Плоские и планарные графы: формула Эйлера, оценка на число рёбер, критерий планарности (Понтрягина-Куратовского, Вагнера)(исходник)

Обходы в графах: эйлеровы графы, критерий эйлеровости, гамильтоновы графы, достаточное условие гамильтоновости(исходник)

Понятие пораждающей грамматики, классы грамматик. Контекстно-свободные грамматики(исходник)

Автоматные грамматики и регулярные выражения. Леммы "о накачке"(исходник)

Детерминированные и недетерминированные конечные автоматы(исходник)

Машины Тьюринга(исходник)

Литература

Элементы математической логики и теории множеств

• Гладкий А.В. Математическая логика
• Игошин В.И. Математическая логика и теория алгоритмов
• Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов
• Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов

Комбинаторика

• Bona M. Introduction to enumerative combinatorics
• Duane DeTemple, William Webb. Combinatorial Reasoning: An Introduction to the Art of Counting
• Herman J., Kucera R., Simsa J. Counting and configurations. Problems in Combinatorics, Arithmetic, and Geometry
• Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика
• Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики
• Липский В. Комбинаторика для программистов
• Стенли Р. Перечислительная комбинаторика. Том 1
• Холл М. Комбинаторика

Булевы функции

• Дехтярь М.И. Булевы функции (Лекции по дискретной математике)
• Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике
• Ерусалимский Я.М. Дискретная математика - теория, задачи, приложения
• Марченков С.С. Булевы функции