Курс математической логики и теории вычислимости

Герасимов А. С.

под заказ

Цена в интернет-магазине: 1639,00 руб.

ISBN: 978-5-8114-1666-0
Внешнее покрытие издания: в пер.
Тираж издания: 1000
Фамилия автора в заголовке: Герасимов
Инициалы автора (личного имени (имен)): А. С.
Код отношений (роль соавтора в издании): 070 Автор
Основное заглавие: Курс математической логики и теории вычислимости
Сведения, относящиеся к заглавию: Учебное пособие
Первые сведения об ответственности: А. С. Герасимов
Сведения об издании: 4-е изд.
Дополнительные сведения об издании: перераб., доп.
Место издания: Санкт-Петербург
Издатель: Лань
Дата издания: 2014
Объем издания (количество страниц): 416
Высота, см.: 21
Определитель УДК: (075.8)
Полная форма имени (имен) и отчества: Александр Сергеевич
Индекс УДК: 510.5
Статус записи (Тип информации): В наличии
Ширина, см: 13,3
Толщина, см: 2
Вес в граммах: 430
Индекс ББК: 22.12я73
Артикул: 2639699

Описание

Настоящее учебное пособие предназначено для изучения математической логики и теории алгоритмов. В нём описаны язык логики высказываний и язык логики предикатов первого порядка, семантика этих языков. На основе общего понятия исчисления изложены исчисления гильбертовского типа, секвенциальные исчисления и метод резолюций как способы формального математического доказательства. Рассмотрены основные формальные аксиоматические теории: элементарная арифметика и теория множеств Цермело-Френкеля. Теория алгоритмов представлена теорией вычислимости, в рамках которой дано несколько точных определений понятия алгоритма (машины Тьюринга, нормальные алгоритмы Маркова, лямбда-исчисление, частично рекурсивные функции) и доказана неразрешимость ряда проблем, среди которых проблема остановки машин Тьюринга, проблема равенства для полугрупп, проблемы общезначимости и выводимости для исчисления предикатов. Рассмотрены теоремы Гёделя о неполноте. Изложено исчисление Хоара для формального доказательства корректности программ некоторого императивного языка программирования. В книге имеется более 200 упражнений. Учебное пособие адресовано в первую очередь студентам, обучающимся по направлениям подготовки укрупнённых групп "Компьютерные и информационные науки", "Информатика и вычислительная техника", но будет полезно и студентам группы направлений "Математика и механика", а также всем желающим начать самостоятельное изучение математической логики.