Математическая логика и теория алгоритмов: Учебное пособие. - 2-е изд.

Учебное пособие соответствует государственному образовательному стандарту дисциплины ''Математическая логика и теория алгоритмов'' направления подготовки дипломированных специалистов 654600 - ''Информатика и вычислительная техника'' (Специальность 220100 -''Вычислительные машины, комплексы, системы и сети'') и направления подготовки бакалавров 552800 - ''Информатика и вычислительная техника''.В пособии излагаются разделы математической логики и теории алгоритмов, необходимые для освоения общепрофессиональных и специальных дисциплин специальности 220100. Достаточно подробно изложены основы логики высказываний и логики предикатов, включая приложение логики предикатов к доказательству правильности алгоритмов. Пособие содержит вводный материал по логическому программированию и клаузальной логике, а также основные понятия нечеткой и модальной логики. Приведены основы теории алгоритмов и алгоритмической разрешимости, доказательство эквивалентности моделей алгоритмов Тьюринга и рекурсивных схем Клини. Пособие содержит также введение в теорию эффективной вычислимости, переборных NP-полных и NP-трудных задач