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