С О Д Е Р Ж А Н И Е. Для студентов, специализирующихся в области

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

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

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

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

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

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

Дата добавления: 2014-12-29