Рекомендуем

Теоретические основы информатикиСтариченко Б.Е. Теоретические основы информатики
Дискретная математика для инженеровПономарев В.Ф. Дискретная математика для инженеров
Алгоритмизация и программирование на Турбо ПаскалеНовичков В.С., Парфилова Н.И., Пылькин А.Н. Алгоритмизация и программирование на Турбо Паскале

Книга

Математическая логика и теория алгоритмов

Учебное пособие для вузов
2-е изд.
2007 г.
176 стр.
Тираж 2000 экз.
Формат 60х90/16 (145x215 мм)
Исполнение: в мягкой обложке
ISBN 5-93517-349-2
ББК 22.12
УДК 510.6
Гриф УМО
Допущено Министерством образования РФ в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям «Комплексное обеспечение информационной безопасности автоматизированных систем», «Организация и технология защиты информации»
Аннотация

Изложены базовые понятия и принципы математической логики и теории алгоритмов. Рассмотрен ряд распространенных логических парадоксов, на примере которых показаны трудности, возникающие в логике. Книга содержит разнообразные логические задачи, упражнения, которые позволяют закрепить теоретический материал.

Для студентов, обучающихся по специальностям "Комплексное обеспечение информационной безопасности автоматизированных систем", "Организация и технология защиты информации", будет полезна студентам других технических специальностей.

Оглавление

Авторское предисловие 3

Глава 1. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ

1. Начальные понятия теории множеств 5
2. Операции над множествами. Диаграммы Венна 9
3. Отношения 13
4. Функции 17
5. Эквивалентность 21
6. Порядок 24

Глава 2. ЛОГИКА ВЫСКАЗЫВАНИЙ

1. Зачем мы изучаем математическую логику? 27
2. Высказывания 30
3. Логические связки 31
4. Формулы логики высказываний 35
5. Равносильность формул 38
6. Тождественно-истинные формулы 41
7. Нормальные формы формул 43
8. Разрешимость для логики высказываний 49

Глава 3. БУЛЕВЫ АЛГЕБРЫ

1. Абстрактное определение булевой алгебры 52
2. Булевы функции. Теорема о нормальной булевой форме 56
3. Полные системы булевых функций 60
4. Переключательные элементы 61

Глава 4. ЛОГИКА ПРЕДИКАТОВ

1. Формулы логики предикатов 67
2. Интерпретации 71
3. Выполнимость и общезначимость 74

Глава 5. ИСЧИСЛЕНИЯ

1. Формальные аксиоматические теории 79
2. Исчисление высказываний 82
3. Исчисление предикатов 90
4. Логический вывод 93
5. Метод резолюций 97
6. Неполнота математики 104

Глава 6. ТЕОРИЯ АЛГОРИТМОВ

1. Понятие алгоритма и неформальная вычислимость 108
2. Частично-рекурсивные функции 110
3. Ламбда-исчисление 115
4. Машины Тьюринга 125
5. Тезис Чёрча 129
6. Некоторые алгоритмически неразрешимые проблемы 130
7. Сложность алгоритмов 132

Глава 7. ЛОГИЧЕСКИЕ ПАРАДОКСЫ 143

Глава 8. МНОГОЗНАЧНЫЕ ЛОГИКИ 148

Решения логических задач 153
Решения упражнений 163

Литература 173