Учебное пособие создано в соответствии с Федеральным государственным образовательным стандартом по направлениям подготовки "Информатика и вычислительная техника", "Информационные системы", "Фундаментальная информатика и информационные технологии" (квалификация "бакалавр").
Изложены основные понятия математической логики, а также качественной и количественной теории алгоритмов. Рассмотрены элементы теории множеств, логика высказываний, исчисление высказываний, логика предикатов, элементарные языки, исчисление предикатов, элементарные теории, теория моделей, начальные понятия теории алгоритмов, начала алгоритмической теории множеств, машины Тьюринга и связанный с ними подход к формализации понятия алгоритма, нормальные алгоритмы, рекурсивные функции, наиболее известные результаты об алгоритмической неразрешимости, формальная арифметика, метод резолюций, интуиционистская логика, элементы теории сложности вычислений.
Для студентов учреждений высшего профессионального образования. Может быть полезно широкому кругу читателей, интересующихся основами математической логики и теории вычислимости.
Author(s): Крупский В.Н., Плиско В.Е.
Series: Высшее профессиональное образование
Publisher: Дрофа
Year: 2013
Language: Russian
Pages: 416
City: Москва
Крупский В.Н., Плиско В.Е. «Математическая логика и теория алгоритмов» (2013) ......Page 1
Предисловие ......Page 4
Введение ......Page 9
1.1. Множества ......Page 15
1.2. Соответствия и функции ......Page 18
1.3. Бинарные отношения ......Page 21
1.4. Числовые множества ......Page 23
1.5. Эквивалентные множества ......Page 27
1.6. Парадоксы теории множеств ......Page 30
1.7. Аксиоматическая система теории множеств ......Page 32
1.8. Программа Гильберта ......Page 34
2.1. Высказывания и логические операции ......Page 36
2.2. Алфавит, буква, слово ......Page 38
2.3. Пропозициональные формулы ......Page 43
2.4. Истинностные таблицы ......Page 48
2.5. Тавтологии ......Page 51
2.6. Равносильные формулы ......Page 54
2.7. Принцип двойственности ......Page 57
2.8. Нормальные формы в логике высказываний ......Page 61
2.9. Выполнимость и логическое следование в логике высказываний ......Page 68
3.1. Общее понятие исчисления ......Page 72
3.2. Классическое исчисление высказываний ......Page 73
3.3. Теорема о дедукции и допустимые правила вывода ......Page 76
3.4. Корректность и полнота исчисления высказываний ......Page 80
3.5. Секвенциальное исчисление высказываний ......Page 86
4.1. Высказывательные формы и кванторы ......Page 94
4.2. Понятие предиката ......Page 96
4.3. Предикатные формулы ......Page 98
4.4. Выполнимость и общезначимость ......Page 101
4.5. Равносильные формулы ......Page 109
5.1. Определение элементарного языка ......Page 112
5.2. Примеры элементарных языков ......Page 116
5.3. Языки второго порядка ......Page 122
5.4. Подстановка ......Page 125
5.5. Алгебраические системы ......Page 131
5.6. Предваренные формулы ......Page 144
6.1. Логическое следование ......Page 146
6.2. Аксиомы и правила вывода классического исчисления предикатов ......Page 147
6.3. Теорема о дедукции и другие допустимые правила вывода ......Page 151
6.4. Непротиворечивые расширения ......Page 158
6.5. Теорема Гёделя о полноте ......Page 164
6.6. Секвенциальное исчисление предикатов ......Page 169
7.1. Аксиоматические теории ......Page 173
7.2. Элементарные теории с равенством ......Page 179
7.3. Изоморфизмы и элементарная эквивалентность ......Page 190
7.4. Аксиоматизируемые классы ......Page 196
8.1. Неформальное понятие алгоритма ......Page 203
8.2. Конструктивные объекты ......Page 205
8.3. Алгоритмический процесс ......Page 212
8.4. Вычислимые функции ......Page 214
8.5. Сигнализирующее множество ......Page 217
9.1. Разрешимые множества ......Page 219
9.2. Полуразрешимые множества ......Page 222
9.3. Перечислимые множества ......Page 226
9.4. Равнообъемность понятий перечислимости и полуразрешимости ......Page 230
9.5. Теорема о графике ......Page 233
9.6. Эффективно аксиоматизируемые теории ......Page 236
Глава 10. Машины Тьюринга ......Page 240
10.1. Одноленточная машина Тьюринга ......Page 241
10.2. Вычисление функций на машинах Тьюринга ......Page 245
10.3. Синтез машин Тьюринга ......Page 248
10.4. Тезис Тьюринга ......Page 249
10.5. Универсальная машина Тьюринга ......Page 251
10.6. Теорема о компиляции ......Page 254
10.7. Многоленточные машины Тьюринга ......Page 257
11.1. Рекурсивные функции ......Page 265
11.2. Нормальные алгорифмы ......Page 286
12.1. Нумерации вычислимых числовых функций ......Page 291
12.2. Нумерации, порожденные машинами Тьюринга ......Page 295
12.3. Примеры невычислимых функций ......Page 298
12.4. Теорема Успенского — Райса ......Page 301
12.5. Десятая проблема Гильберта ......Page 304
12.6. Проблема равенства слов в полугруппах ......Page 305
13.1. Аксиомы Пеано ......Page 312
13.2. Нестандартные модели арифметики ......Page 314
13.3. Арифметические множества и функции ......Page 316
13.4. Теорема о неподвижной точке ......Page 319
13.5. Теорема Тарского ......Page 321
13.6. Теорема Гёделя о неполноте ......Page 322
13.7. Формальная система арифметики ......Page 325
13.8. Тождественно истинные предикатные формулы ......Page 333
13.9. О логике второго порядка ......Page 336
Глава 14. Метод резолюций ......Page 341
14.1. Скулемовская форма высказываний ......Page 342
14.2. Дизъюнктная форма высказываний ......Page 347
14.3. Теорема Эрбрана ......Page 349
14.4. Метод резолюций для логики высказываний ......Page 355
14.5. Алгоритм унификации ......Page 358
14.6. Метод резолюций для элементарных языков ......Page 361
14.7. Хорновские дизъюнкты ......Page 366
14.8. Логические программы ......Page 368
15.1. Что такое интуиционизм ......Page 376
15.2. Интуиционистская логика высказываний ......Page 379
15.3. Интуиционистская логика предикатов ......Page 389
15.4. Рекурсивная реализуемость ......Page 394
16.1. Предварительные сведения ......Page 397
16.2. Меры сложности вычислений ......Page 399
16.3. Класс Р ......Page 401
16.4. Класс NP ......Page 405
16.5. Примеры заведомо трудных задач ......Page 410
Список литературы ......Page 413
Оглавление ......Page 415
