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