Екатеринбург: УрГУ (Мат. – Мех. фак.), 2008. - 273 с.Пособие разбито на семь глав. Оно содержит теоретический материал, подборку задач, а также ответы и указания к ряду задач и решение некоторых из них. В отличие от многих учебников по математической логике и теории алгоритмов, пособие содержит изложение метода резолюций, критерия полноты функций k-значной логики, значительный материал по сложности алгоритмов. В пособии значительное внимание уделено анализу выразительных возможностей языка математической логики, приведены основные результаты теории NP-полноты.Содержание:
Введение.
Логика высказываний.
Логика предикатов первого порядка.
Исчисление предикатов.
Метод резолюций.
Функции k-значной логики.
Алгоритмы и машины Тьюринга.
Сложность алгоритмов.
Литература.
