С. В. СУДОПЛАТОВ, Е. В. ОВЧИННИКОВА
МАТЕМАТИЧЕСКАЯ
ЛОГИКА И ТЕОРИЯ
АЛГОРИТМОВ
УЧЕБНИК
Издание второе, переработанное
НОВОСИБИРСК
2010
УДК 510.6(075.8)
С892
Рецензенты:
д-р физ.-мат. наук, проф. <...> Математическая логика и теория алгоритмов : учебник / <...> Предикатные временные
´ логики
и их приложение к программированию . <...> Учебник состоит из пяти глав: исчисления высказываний, логика и исчисления предикатов, элементы теории моделей, элементы теории алгоритмов,
неклассические логики. <...> “Алгоритмы и рекурсивные функции” и лекции члена-корреспондента РАН <...> Это и исследование различных логических исчислений (логик ),
из которых основным является классическое исчисление предикатов,
и изучение взаимосвязи синтаксических (информационных) и семантических (реальных) объектов, и разработки в области теории алгоритмов. <...> Теория моделей, или теория алгебраических систем, как раздел математической логики возникла на стыке математической логики и алгебры. <...> Первая глава учебника содержит два основных исчисления высказываний: исчисление высказываний генценовского типа (исчисление секвенций)
и исчисление высказываний гильбертовского типа. <...> Подробно изложен метод резолюций в исчислении предикатов, и показана его роль в организации и работе языков логического программирования. <...> В ней рассматриваются такие
важнейшие понятия, как элементарная эквивалентность, элементарная теория, полная теория, тип. <...> В четвертой главе изложены две основные модели теории алгоритмов:
машины Тьюринга и рекурсивные функции. <...> Излагаются основы нечетких логик, темпоральных (временных
´ или динамических) логик,
а также алгоритмических логик. <...> Определение формального исчисления
Введем общее понятие формального исчисления. <...> ОПРЕДЕЛЕНИЕ ФОРМАЛЬНОГО ИСЧИСЛЕНИЯ
13
Иногда в этой записи символ i будет опускаться, если из контекста ясно,
о каком правиле идет речь:
Φ 1 ; . . . ; Φm
. <...> ¤
Вообще говоря, может не существовать алгоритма, с помощью которого
для произвольного <...>
Математическая_логика_и_теория_алгоритмов.pdf
С. В. СУДОПЛАТОВ, Е. В. ОВЧИННИКОВА
МАТЕМАТИЧЕСКАЯ
ЛОГИКА И ТЕОРИЯ
АЛГОРИТМОВ
УЧЕБНИК
Издание второе, переработанное
НОВОСИБИРСК
2010
Стр.1
УДК 510.6(075.8)
С892
Рецензенты:
д-р физ.-мат. наук, проф. А. Г. Пинус,
канд. техн. наук, доц. В. М. Зыбарев
Судоплатов С. В.
С892 Математическая логика и теория алгоритмов : учебник /
С. В. Судоплатов, Е. В. Овчинникова. – 2-е изд., перераб. – Новосибирск
: Изд-во НГТУ, 2010. – 256 с. (Серия «Учебники НГТУ»)
ISBN 978-5-7782-1348-7
В книге излагаются классические исчисления математической логики: исчисления
высказываний и исчисления предикатов; основы теории моделей,
теории алгоритмов, а также неклассических логик.
Для студентов младших технических вузов, изучающих математическую
логику и теорию алгоритмов.
УДК 510.6(075.8)
ISBN 978-5-7782-1348-7
© Судоплатов С. В., Овчинникова Е. В., 2010
© Новосибирский государственный
технический университет,
2010
Стр.2
Оглавление
Предисловие ко второму изданию . . . . . . . . . . . . . . . . . . . . . . 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
6
§ 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
Стр.4