Дискретная математика и математическая логика — 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
  • Холл М. Комбинаторика

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

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