Математическая логика и теория алгоритмов. Анкудинов Г.И

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