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

Документы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание занятий

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

• Высказывания. Примеры высказываний.
• Логические операции над высказываниями (отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность).
• Формулы логики высказываний. Равносильные формулы, тавтологии, противоречия.
• Основные равносильности.
• Логическое следование. Теорема о логическом следствии.
• Важнейшие правила следования.
• Применения языка логики высказываний (упрощение систем высказываний, анализ рассуждений, релейно-контактные схемы).
• Понятие множества. Операции над множествами. Основные тождества.
• Понятие отображения. Образы и прообразы. Основные классы отображений.
• Принцип Дирихле. Примеры.
• Композиция отображений. Обратное отображение. Критерий обратимости.
• Бинарные отношения. Операции над бинарными отношениями.
• Основные классы бинарных отношений. Отношения эквивалентности.
• Отображения как функциональные отношения.
• Недостаточность логики высказываний для анализа рассуждений.
• Понятие предиката. Логические операции над предикатами.
• Кванторы.
• Формулы логики предикатов. Классификация формул.
• Применение логики предикатов для описания математических понятий.

Глава 2. Комбинаторика

• Основные правила комбинаторики (правила суммы, произведения и вычитания, биективное правило). Примеры.
• Выборки. Типы выборок.
• Размещения без повторений и с повторениями. Перестановки.
• Сочетания без повторений и с повторениями. Связь сочетаний с задачами о числе решений специальных диофантовых уравнений.
• Биномиальная теорема. Бином Ньютона.
• Биномиальные тождества.
• Полиномиальный коэффициент. Мультимножества. Перестановки мультимножеств.
• Полиномиальная теорема.
• Разбиения множеств и чисел. Числа Стирлинга второго рода.
• Функциональное представление комбинаторных объектов.
• Формула включений и исключений.
• Применения формулы включений и исключений («счастливые билеты», «беспорядки», число сюръективных отображений, формула Эйлера).
• Рекуррентные соотношения. Линейные однородные рекуррентные соотношения второго порядка с постоянными коэффициентами.
• Линейные однородные рекуррентные соотношения k-го порядка с постоянными коэффициентами.
• Производящие функции. Операции над производящими функциями.
• Основные последовательности и связанные с ними производящие функции.
• Производящие функции и комбинаторные подсчеты.
• Решение рекуррентных соотношений методом производящих функций.
• Примеры нелинейных рекуррентностей. Числа Каталана.

Глава 3. Булевы функции

• Булевы функции. Табличное задание булевых функций.
• Элементарные булевы функции.
• Существенные и фиктивные переменные булевых функций.
• Представление булевых функций посредством формул. Равносильные формулы. Основные равносильности.
• Дизъюнктивные нормальные формы (ДНФ и СДНФ). Алгоритмы построения СДНФ.
• Конъюнктивные нормальные формы (КНФ и СКНФ). Алгоритмы построения СКНФ.
• Разложение Шеннона булевых функций. Единственность СДНФ.
• Двойственность. Принцип двойственности. Единственность СКНФ.
• Полиномиальные нормальные формы. Полином Жегалкина. Единственность полинома Жегалкина.
• Методы построения полинома Жегалкина (метод преобразования СДНФ, метод неопределенных коэффициентов, метод треугольника, метод деления таблицы истинности пополам).
• Замыкание. Замкнутые классы булевых функций. Понятие полной системы. Примеры полных систем.
• Основные замкнутые классы и их свойства (классы T0, T1, L, S, M).
• Теорема Поста (критерий полноты).
• Понятие базиса. Теорема о максимальном числе функций в базисе.
• Предполные классы булевых функций. Теорема о предполных классах.
• Минимизация булевых функций в классе ДНФ. Метод Квайна и метод Блейк-–Порецкого.
• Функции k-значной логики (основные понятия).

Литература

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

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

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

• 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
• Холл М. Комбинаторика

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

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