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

Учебное пособие для вузов

Зюзьков В.М., Шелупанов А.А.

2-е изд.

176 стр.

Учебное издание

Формат 60х90/16 (145x215 мм)

Исполнение: в мягкой обложке

ISBN 5-93517-349-2

ББК 22.12

УДК 510.6

Гриф
Допущено Министерством образования РФ в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям «Комплексное обеспечение информационной безопасности автоматизированных систем», «Организация и технология защиты информации»

Аннотация

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

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

Оглавление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

Рекомендуем

Книга

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