Математическая логика и теория алгоритмов, Судоплатов С.В., Овчинникова Б.В., 2004

Математическая логика и теория алгоритмов, Судоплатов С.В., Овчинникова Б.В., 2004.

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




ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.
При изучении дискретной математики и формальных исчислений мы рассматривали большое количество различных алгоритмов. Это и алгоритм Евклида нахождения наибольших общих делителей, и алгоритмы нахождения кратчайших маршрутов во взвешенном графе, и алгоритм распознавания доказуемости формул исчисления высказываний.

Отметим несколько основных общих черт алгоритмов.
1. Алгоритм — это процесс последовательного построения (вычисления) величин, протекающий в дискретном времени так, что в начальный момент времени задается исходная конечная система величин, а в каждый последующий момент система величин получается по определенному закону (программе) из системы величин, имевшихся в предыдущий момент времени (дискретность алгоритма).

2. Система величин, получаемых в любой не начальный момент времени, однозначно определяется системой величин, полученных в предыдущие моменты времени (детерминированность алгоритма).

3. Закон получения последующей системы величин из предшествующей должен быть простым (элементарность шагов алгоритма).

4. Если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указало, что надо считать результатом алгоритма (направленность алгоритма).

Оглавление
Предисловие
Введение
Глава 1. Исчисления высказываний
§1.1. Определение формального исчисления
§1.2. Исчисление высказываний генценовского типа
§1.3. Эквивалентность формул
§1.4. Нормальные формы
§1.5. Семантика исчисления секвенций
§1.6. Исчисление высказываний гильбертовского типа
§1.7. Алгоритмы проверки общезначимости и противоречивости в ИВ
§1.8. Логические задачи
Задачи и упражнения
Глава 2. Логика и исчисления предикатов
§2.1. Формулы сигнатуры Σ. Истинность формулы на алгебраической системе
§2.2. Секвенциальное исчисление предикатов
§2.3. Эквивалентность формул в IIПСΣ
§2.4. Нормальные формы
§2.5. Теорема о существовании модели
§2.6. Исчисление предикатов гильбертовского типа
§2.7. Скулемнзация алгебраических систем
§2.8. Метод резолюций в исчислении предикатов
§2.9. Логические программы
Задачи и упражнения
Глава 3. Элементы теории моделей
§3.1. Элементарная эквивалентность. Теоремы Лёвенгейма — Скулема
§3.2. Элементарные теории
§3.3. Типы. Основные классы моделей
§3.4. Категоричность. Спектры моделей полных теорий
§3.5. Система аксиом арифметики Пеано. Нестандартные модели арифметики
Задачи и упражнения
Глава 4. Элементы теории алгоритмов
§4.1. Машины Тьюринга
§4.2. Рекурсивные функции и отношения
§4.3. Эквивалентность моделей алгоритмов
§4.4. Универсальные частично рекурсивные функции. Теорема Райса
§4.5. Рекурсивно перечислимые отношения
§4.6. Неразрешимость исчисления предикатов. Теорема Гёделя о неполноте. Разрешимые и неразрешимые теории
§4.7. Характеристики сложности алгоритмов
§4.8. Переборные задачи
§4.9. Алгоритмы сортировки
§4.10. Конечные автоматы
Задачи и упражнения
Глава 5. Неклассические логики
§5.1. Пропозициональные логики
§5.2. Предикатные логики
§5.3. Предикатные временные логики и их приложение к программированию
§5.4. Алгоритмические логики
Задачи и упражнения
Список литературы
Предметный указатель.

Купить .





Теги: учебник по математике :: математика :: Судоплатов :: Овчинникова