Математическая логика и теория алгоритмов, Крупский В.Н., Плиско В.Е., 2013

Математическая логика и теория алгоритмов, Крупский В.Н., Плиско В.Е., 2013.

   Учебное пособие создано в соответствии с Федеральным государственным образовательным стандартом по направлениям подготовки «Информатика и вычислительная техника», «Информационные системы», «Фундаментальная информатика и информационные технологии» (квалификация «бакалавр»).
Изложены основные понятия математической логики, а также качественной и количественной теории алгоритмов. Рассмотрены элементы теории множеств, логика высказываний, исчисление высказываний, логика предикатов, элементарные языки, исчисление предикатов, элементарные теории, теория моделей, начальные понятия теории алгоритмов, начала алгоритмической теории множеств, машины Тьюринга и связанный с ними подход к формализации понятия алгоритма, нормальные алгоритмы, рекурсивные функции, наиболее известные результаты об алгоритмической неразрешимости, формальная арифметика, метод резолюций, интуиционистская логика, элементы теории сложности вычислений.
Для студентов учреждений высшего профессионального образования. Может быть полезно широкому кругу читателей, интересующихся основами математической логики и теории вычислимости.




Программа Гильберта.
Несмотря на то, что в теории ZF никаких противоречий не обнаружено, это еще не означает, что противоречия здесь невозможны. Чтобы установить недоказуемость противоречия математическими методами, нужно сделать математически точным понятие доказательства. Программа доказательства непротиворечивости математических теорий была намечена немецким математиком Д. Гильбертом. Он предложил представлять исследуемую математическую теорию в виде формальной аксиоматической системы. Ее построение начинается с выбора подходящего формализованного языка. Сначала фиксируются символы для обозначения основных понятий теории: объектов, операций и отношений, играющих важную роль в этой теории. Используя эти, а также логические и некоторые служебные символы, по фиксированным правилам строятся выражения, являющиеся формальным аналогом предложений теории. На полученном языке записываются аксиомы теории. Наряду с аксиомами фиксируются правила логического вывода, позволяющие из одних предложений получать другие. Эти правила выбираются таким образом, чтобы они отражали способы рассуждений, обычно применяемые в математике.

Теорема данной формальной теории — это предложение, которое) можно получить из аксиом путем последовательного применения правил вывода. Таким образом, предложения данной теории представляются словами в фиксированном алфавите, а доказательства последовательностями таких слов. Исследование этих объектов можно вести строгими математическими методами. При этом проблема непротиворечивости сводится к доказательству невыводимости двух противоречащих друг другу предложений.

СОДЕРЖАНИЕ.
Предисловие.
Введение.
Глава 1. Элементы теории множеств.
1.1. Множества.
1.2. Соответствия и функции.
1.3. Бинарные отношения.
1.4. Числовые множества.
1.5. Эквивалентные множества.
1.6. Парадоксы теории множеств.
1.7. Аксиоматическая система теории множеств.
1.8. Программа Гильберта.
Глава 2. Логика высказываний.
2.1. Высказывания и логические операции.
2.2. Алфавит, буква, слово.
2.3. Пропозициональные формулы.
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. Равносильные формулы.
Глава 5. Элементарные языки.
5.1. Определение элементарного языка.
5.2. Примеры элементарных языков.
5.3. Языки второго порядка.
5-4. Подстановка.
5.5. Алгебраические системы.
5.6. Предваренные формулы.
Глава 6. Исчисление предикатов.
6.1. Логическое следование.
6.2. Аксиомы и правила вывода классического исчисления предикатов.
6.3. Теорема о дедукции и другие допустимые правила вывода.
6.4. Непротиворечивые расширения.
6.5. Теорема Геделя о полноте.
6.6. Секвенциальное исчисление предикатов.
Глава 7. Элементарные теории и модели.
7.1. Аксиоматические теории.
7.2. Элементарные теории с равенством.
7.3. Изоморфизмы и элементарная эквивалентность.
7.4. Аксиоматизируемые классы.
Глава 8. Начальные понятия теории алгоритмов.
8.1. Неформальное понятие алгоритма.
8.2. Конструктивные объекты.
8.3. Алгоритмический процесс.
8.4. Вычислимые функции.
8.5. Сигнализирующее множество.
Глава 9. Алгоритмическая теория множеств.
9.1. Разрешимые множества.
9.2. Полу разрешимые множества.
9.3. Перечислимые множества.
9.4. Равнообъемность понятий перечислимости и полуразрешимости.
9.5. Теорема о графике.
9.6. Эффективно аксиоматизируемые теории.
Глава 10. Машины Тьюринга.
10.1. Одноленточная машина Тьюринга.
10.2. Вычисление функций на машинах Тьюринга.
10.3. Синтез машин Тьюринга.
10.4. Тезис Тьюринга.
10.5. Универсальная машина Тьюринга.
10.6. Теорема о компиляции.
10.7. Многоленточные машины Тьюринга.
Глава 11. Другие формализации вычислимости.
11.1. Рекурсивные функции.
11.2. Нормальные алгорифмы.
Глава 12. Неразрешимые алгоритмические проблемы.
12.1. Нумерации вычислимых числовых функций.
12.2. Нумерации, порожденные машинами Тьюринга.
12.3. Примеры невычислимых функций.
12.4. Теорема Успенскою — Райса.
12.5. Десятая проблема Гильберта.
12.6. Проблема равенства слов в полугруппах.
Глава 13. Формальная арифметика.
13.1. Аксиомы Пеано.
13.2. Нестандартные модели арифметики.
13.3. Арифметические множества и функции.
13.4. Теорема о неподвижной точке.
13.5. Теорема Тарского.
13.6. Теорема Гёделя о неполноте.
13.7. Формальная система арифметики.
13.8. Тождественно истинные предикатные формулы.
13.9. О логике второго порядка.
Глава 14. Метод резолюций.
14.1. Скулемовская форма высказываний.
14.2. Дизъюнктная форма высказываний.
14.3. Теорема Эрбрана.
14.4. Метод резолюций для логики высказываний.
14.5. Алгоритм унификации.
14.6. Метод резолюций для элементарных языков.
14.7. Хорновские дизъюнкты.
14.8. Логические программы.
Глава 15. Интуиционистская логика.
15.1. Что такое интуиционизм.
15.2. Интуиционистская логика высказываний.
15.3. Интуиционистская логика предикатов.
15.4. Рекурсивная реализуемость.
Глава 16. Элементы теории сложности вычислений.
16.1. Предварительные сведения.
16.2. Меры сложности вычислений.
16.3. Класс Р.
16.4. Класс NP.
16.5. Примеры заведомо трудных задач.
Список литературы.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Математическая логика и теория алгоритмов, Крупский В.Н., Плиско В.Е., 2013 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Крупский :: Плиско :: логика