Министерство образования Российской Федерации

Министерство Российской Федерации по атомной энергии

Московский инженерно-физический институт

(государственный университет)

Ф.К. Алиев, и.А. Юров

КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

И ТЕОРИИ АЛГОРИТМОВ

Для студентов, специализирующихся в области

защиты информации

Москва 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