- •Ф.К. Алиев, и.А. Юров
- •Введение
- •Основные способы задания двоичных функций
- •1.1. Табличный способ задания
- •1.2. Геометрический способ задания
- •1.3. Задание двоичных функций формулами
- •Основные способы задания двоичных функций (продолжение)
- •2.1. Нормальные формы двоичных функций
- •2.2. Многочлен Жегалкина и действительный многочлен двоичной функции
- •2.3. Теорема о разложении в ряд Фурье
- •Полнота и замкнутость. Критерий полноты системы. Функционально полные системы. Замкнутые классы булевых функций
- •3.1. Полнота и замкнутость. Функционально полные системы
- •3.2. Замкнутые классы булевых функций
- •3.3. Критерий полноты системы булевых функций
- •4.1. Псевдобулевы функции
- •4.2. Функции k-значной логики
- •5.1 Минимизация двоичных функции
- •5.2. Геометрическая интерпретация минимизации днф
- •6.1. Метод Квайна — Мак-Класки нахождения сокращённой днф двоичной функции
- •6.2. Метод нахождения тупиковых днф
- •6.3. Метод Петрика нахождения тупиковых днф
- •Алгебраические системы
- •7.1. Алгебраические системы. Булевы алгебры
- •7.2. Изоморфизм алгебраических систем
- •Алгебры высказываний. Предикаты и операции над ними
- •8.1. Основные логические операции и их свойства
- •8.2. Предикаты и операции над ними
- •Исчисление предикатов
- •9.1. Общее понятие о логическом исчислении
- •9.2. Формулы алгебры предикатов
- •9.3. Равносильность формул. Основные отношения равносильности
- •9.4. Использование равносильностей для упрощения формул
- •9.5. Построение исчисления предикатов
- •9.6. Выводимость и доказуемость формул
- •9.7. Семантика исчисления предикатов
- •Понятие о теории моделей
- •Элементы теории алгоритмов
- •11.1. Основные требования к алгоритмам
- •11.2. Машина Тьюринга и функции, вычислимые по Тьюрингу
- •11.3. Машины произвольного доступа и вычислимые функции
- •Частично рекурсивные функции и их вычислимость
- •Вычислимость суперпозиции
- •Вычислимость рекурсии
- •Вычислимость минимизации
- •Нумерация наборов чисел и слов
- •Нормальные алгоритмы
- •Нумерация алгоритмов
- •1. Нумерация машин Тьюринга
- •2. Нумерация мпд-программ
- •Универсальные функции
- •Алгоритмически неразрешимые проблемы
- •16.1. Алгоритмически неразрешимые проблемы
- •16.2. Примечательные алгоритмически неразрешимые проблемы
- •Характеристики сложности вычислений
- •Характеристика сложности вычислительных задач
- •18.1. Классы сложности p и np и их взаимосвязь
- •18.3. Основные np-полные задачи. Сильная np-полнота
- •Список Литературы
Министерство образования Российской Федерации
Министерство Российской Федерации по атомной энергии
Московский инженерно-физический институт
(государственный университет)
Ф.К. Алиев, и.А. Юров
КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
И ТЕОРИИ АЛГОРИТМОВ
Для студентов, специализирующихся в области
защиты информации
Москва 2003
Аннотация к учебному пособию «Курс лекций по математической логики и теории алгоритмов для студентов специализирующихся в области защиты информации».
В настоящем учебном пособии изложены основы теории двоичных функций, исчисления предикатов, теории моделей, элементов теории алгоритмов и теории сложности вычислительных задач.
Книга предназначена для студентов, специализирующихся в областях, связанных с информационной безопасностью, а также для преподавателей дискретной математики.
УДК
ББК
А
Алиев Ф.К., Юров И.А. Курс лекций по математической логике и теории алгоритмов: Учебное пособие. М.: МИФИ, 2003. — с.
Рецензеты: С.В. Синицын, П.П. Порешин, Г.Н. Поваров
Рекомендовано редсоветом МИФИ
в качестве учебного пособия
Московский инженерно-физический институт
(государственный университет), 2003
С О Д Е Р Ж А Н И Е
Введение 5
Лекция 1. Основные способы задания двоичных функций 6
1.1. Табличный способ задания 6
1.2. Геометрический способ задания 9
1.3. Задание двоичных функций формулами 10
Лекция 2. Основные способы задания двоичных функций (продолжение) 13
2.1. Нормальные формы двоичных функций 13
2.2. Многочлен Жегалкина и действительный многочлен
двоичной функции 17
2.3. Теорема о разложении в ряд Фурье 20
Лекция 3. Полнота и замкнутость. Критерий полноты системы.
Функционально полные системы.
Замкнутые классы булевых функций 23
3.1. Полнота и замкнутость. Функционально полные системы 23
3.2. Замкнутые классы булевых функций 25
3.3. Критерий полноты системы булевых функций 28
Лекция 4. 30
4.1. Псевдобулевы функции 30
4.2. Функции k-значной логики 32
Лекция 5. 36
5.1. Минимизация двоичных функций 36
5.2. Геометрическая интерпретация минимизации ДНФ 38
Лекция 6. 40
6.1. Метод Квайна — Мак-Класки нахождения
сокращенной ДНФ двоичной функции 40
6.2. Метод нахождения тупиковых ДНФ 42
6.3. Метод Петрика нахождения тупиковых ДНФ 42
Лекция 7. Алгебраические системы 45
7.1. Алгебраические системы. Булевы алгебры 45
7.2. Изоморфизм алгебраических систем 48
Лекция 8. Алгебры высказываний. Предикаты и операции над ними 51
8.1. Основные логические операции и их свойства 51
8.2. Предикаты и операции над ними 52
Лекция 9. Исчисление предикатов 57
9.1. Общее понятие о логическом исчислении 57
9.2. Формулы алгебры предикатов 58
9.3. Равносильность формул. Основные отношения равносильности 64
9.4. Использование равносильностей для упрощения формул 69
9.5. Построение исчисления предикатов 71
9.6. Выводимость и доказуемость формул 73
9.7. Семантика исчисления предикатов 82
Лекция 10. Понятие о теории моделей 91
Лекция 11. Элементы теории алгоритмов 99
11.1. Основные требования к алгоритмам 102
11.2. Машина Тьюринга и функции, вычислимые по Тьюрингу 106
11.3. Машины произвольного доступа и вычислимые функции 116
Лекция 12. Частично рекурсивные функции и их вычислимость 123
Лекция 13. Нумерация наборов чисел и слов 133
Лекция 14. Нормальные алгоритмы 139
Лекция 15. Нумерация алгоритмов 144
15.1. Нумерация машин Тьюринга 144
15.2. Нумерация МПД-программ 146
15.3. Универсальные функции 149
Лекция 16. Алгоритмически неразрешимые проблемы 153
16.1. Алгоритмически неразрешимые проблемы 153
16.2. Примечательные алгоритмически неразрешимые проблемы 163
Лекция 17. Характеристики сложности вычислений 166
Лекция 18. Характеристика сложности вычислительных задач 173
18.1. Классы сложности P и NP и их взаимосвязь 173
18.2. NP-полные задачи. Теорема Кука 181
18.3. Основные NP-полные задачи. Сильная NP-полнота 186
Список литературы 197