Дискретная математика. Избранные вопросы. Кривой С. Л. Киево-Могилянская академия

В пособии рассматриваются основные понятия теории множеств и отношений, общей алгебры, математической логики и теории алгоритмов. В частности, описываются алгебры множеств и отношений, алгебра булевых функций и графическое представление булевых функций в виде упорядоченных бинарных диаграмм решений, а также важнейшие применения этого представления для задания отношений, графов, конечных автоматов и т.д. Представлены формальные логические языки (логика высказываний, линейная темпоральная логика и логика предикатов первого порядка), основные методы проверки выполнимости формул в этих языках и метод резолюций с унификацией. Рассмотрены основные понятия теории сложности вычислений по Тьюрингу и основные классы сложности вычислений, а также описаны такие модели вычислений, как НАМ и РКАМ (для оценки последовательных и параллельных алгоритмов). В последних разделах рассматриваются методы анализа сетей Петри. Учебное пособие предназначено для студентов старших курсов высших учебных заведений и аспирантов, обучающихся по направлению