Характеристики

ISBN/ISSN 978-5-7782-1348-7
Год издания 2010
Автор Судоплатов С.В., Овчинникова Е.В.
Вид издания уч.НГТУ
Кафедра АиМЛ
Типография НГТУ
Факультет ФПМИ
480 руб.

В книге излагаются классические исчисления математической логики: исчисления высказываний и исчисления предикатов; основы теории моделей, теории алгоритмов, а так же неклассических логик.
Для студентов младших курсов технических вузов, изучающих математическую логику и теорию алгоритмов.

В книге излагаются классические исчисления математической логики: исчисления высказываний и исчисления предикатов; основы теории моделей, теории алгоритмов, а так же неклассических логик.
Для студентов младших курсов технических вузов, изучающих математическую логику и теорию алгоритмов.


Оглавление
Предисловие ко второму изданию . . . . . . . . . . . . . . . . . . . . . . 7
Предисловие к первому изданию . . . . . . . . . . . . . . . . . . . . . . 8
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Глава 1. Исчисления высказываний . . . . . . . . . . . . . . . . . . . . 12
§ 1.1. Определение формального исчисления . . . . . . . . . . . . . . 12
§ 1.2. Исчисление высказываний генценовского типа . . . . . . . . . 14
§ 1.3. Эквивалентность формул . . . . . . . . . . . . . . . . . . . . . 21
§ 1.4. Нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . 23
§ 1.5. Семантика исчисления секвенций . . . . . . . . . . . . . . . . . 25
§ 1.6. Исчисление высказываний гильбертовского типа . . . . . . . . 31
§ 1.7. Алгоритмы проверки общезначимости
и противоречивости в ИВ . . . . . . . . . . . . . . . . . . . . . 35
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 42
Глава 2. Логика и исчисления предикатов . . . . . . . . . . . . . . . . 46
§ 2.1. Формулы сигнатуры Σ. Истинность формулы
на алгебраической системе . . . . . . . . . . . . . . . . . . . . . 47
§ 2.2. Секвенциальное исчисление предикатов . . . . . . . . . . . . . 54
§ 2.3. Эквивалентность формул в ИПCΣ . . . . . . . . . . . . . . . . 62
§ 2.4. Нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . 64
§ 2.5. Теорема о существовании модели . . . . . . . . . . . . . . . . . 66
§ 2.6. Исчисление предикатов гильбертовского типа . . . . . . . . . 71
§ 2.7. Скулемизация алгебраических систем . . . . . . . . . . . . . . 74
§ 2.8. Метод резолюций в исчислении предикатов . . . . . . . . . . . 77
§ 2.9. Логические программы . . . . . . . . . . . . . . . . . . . . . . . 87
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 91
Глава 3. Элементы теории моделей . . . . . . . . . . . . . . . . . . . . 100
§ 3.1. Элементарная эквивалентность.
Теоремы Л¨евенгейма — Скулема . . . . . . . . . . . . . . . . . 100
§ 3.2. Элементарные теории . . . . . . . . . . . . . . . . . . . . . . . . 107
§ 3.3. Типы. Основные классы моделей . . . . . . . . . . . . . . . . . 113
§ 3.4. Категоричность. Спектры моделей полных теорий . . . . . . . 122
§ 3.5. Система аксиом арифметики Пеано.
Нестандартные модели арифметики . . . . . . . . . . . . . . . 130
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 133
Глава 4. Элементы теории алгоритмов . . . . . . . . . . . . . . . . . . 135
§ 4.1. Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . 136
§ 4.2. Рекурсивные функции и отношения . . . . . . . . . . . . . . . 145
§ 4.3. Эквивалентность моделей алгоритмов . . . . . . . . . . . . . . 153
§ 4.4. Универсальные частично рекурсивные функции.
Теорема Райса . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
§ 4.5. Рекурсивно перечислимые отношения . . . . . . . . . . . . . . 164
§ 4.6. Неразрешимость исчисления предикатов. Теорема Г¨еделя
о неполноте. Разрешимые и неразрешимые теории . . . . . . . 169
§ 4.7. Характеристики сложности алгоритмов . . . . . . . . . . . . . 177
§ 4.8. Переборные задачи . . . . . . . . . . . . . . . . . . . . . . . . . 180
§ 4.9. Алгоритмы сортировки . . . . . . . . . . . . . . . . . . . . . . . 188
§ 4.10. Конечные автоматы . . . . . . . . . . . . . . . . . . . . . . . . . 191
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 194
Глава 5. Неклассические логики . . . . . . . . . . . . . . . . . . . . . . 197
§ 5.1. Пропозициональные логики . . . . . . . . . . . . . . . . . . . . 197
§ 5.2. Предикатные логики . . . . . . . . . . . . . . . . . . . . . . . . 209
§ 5.3. Предикатные временн´ые логики
и их приложение к программированию . . . . . . . . . . . . . . 213
§ 5.4. Алгоритмические логики . . . . . . . . . . . . . . . . . . . . . . 218
Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . 222
Библиографический список . . . . . . . . . . . . . . . . . . . . . . . . . . 224
Приложение. Варианты типового расчета . . . . . . . . . . . . . . . . 227
Указатель терминов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
Указатель обозначений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

Данные подготавливаются.

Вернуться к списку