Математическая логика и теория алгоритмов: учебное пособие для бакалавров, обучающихся по направлениям подготовки "Информатика и вычислительная техника", "Информационные системы"

Крупский В.Н., Плиско В.Е. «Математическая логика и теория алгоритмов» (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