Описание раздела
Учебное пособие содержит полное изложение материала учебных дисциплин «Математическая логика и теория алгоритмов» и «Дискретные функции» Государственного образовательного стандарта высшего профессионального образования по специальностям и направлениям «Компьютерная безопасность», «Информационная безопасность автоматизированных систем» и некоторым другим смежным специальностям. Пособие состоит из трех взаимосвязанных частей, представляющих основы математической логики, теории дискретных функций и теории алгоритмов. Предназначено для студентов вузов, обучающихся по специальностям и направлениям в области информационной безопасности, а также для аспирантов и студентов вузов других технических специальностей и направлений, изучающих дискретную математику. Содержание Предисловие Часть I. Математическая логика Глава 1. Множества с отношениями и операциями 1.1. Множества и операции над ними 1.2. Отображения множеств 1.3. Отношения на множестве. Отношения эквивалентности и порядка 1.4. Множества с операциями 1.5. Аксиоматическое построение системы натуральных чисел 1.6. Мощность множества. Конечные и бесконечные множества Глава 2. Алгебра высказываний 2.1. Основные логические операции и их свойства 2.2. Формулы алгебры высказываний 2.3. Эквивалентные формулы 2.4. Приведенные формулы и нормальные формы 2.5. Выполнимые и тождественно истинные формулы 2.6. Сокращенные, тупиковые и минимальные ДНФ 2.7. Алгоритм нахождения тупиковых ДНФ по сокращенной ДНФ Глава 3. Исчисление высказываний 3.1. Общее понятие о логическом исчислении 3.2. Язык, аксиомы и правила вывода исчисления высказываний 3.3. Доказуемые формулы исчисления высказываний 3.4. Вспомогательные правила вывода 3.5. Полнота и непротиворечивость исчисления высказываний Глава 4. Алгебра предикатов 4.1. Предикаты и операции над ними 4.2. Формулы алгебры предикатов 4.3. Эквивалентность формул. Основные соотношения эквивалентности 4.4. Приведенные и предваренные формулы Глава 5. Исчисление предикатов 5.1. Язык, аксиомы и правила вывода исчисления предикатов 5.2. Выводимость и доказуемость формул 5.3. Семантика исчисления предикатов 5.4. Понятие о теории моделей 5.5. Проблема разрешимости в логике предикатов Часть II. Дискретные функции Глава 1. Дискретные функции и способы их задания 1.1. Способы задания булевых функций 1.2. Полные системы и замкнутые классы булевых функций 1.3. Функции k-значной логики и способы их задания. Полные системы 1.4. Критерии полноты систем функций k-значной логики 1.5. Полиномиальное представление функций k-значной логики Глава 2. Представление дискретных функций в базисах функциональных пространств 2.1. Базисы линейных функциональных пространств. Базис характеров 2.2. Преобразование Фурье. Коэффициенты Фурье и Уолша-Адамара 2.3. Матричный подход к представлению булевых функций Глава 3. Классификация дискретных функций с помощью групп преобразований 3.1. Эквивалентность функций. Группы инерции 3.2. Функции, инвариантные относительно группы 3.3. Функции с тривиальной группой инерции в аффинной группе 3.4. Перечисление G-типов. Лемма Бернсайда 3.5. Инварианты. Нахождение групп инерции и проверка эквивалентности Глава 4. Вероятностные и комбинаторные свойства и параметры дискретных функций 4.1. Вероятностная функция булевой функции 4.2. Линейные приближения (аппроксимации) булевых функций 4.3. Коэффициент аддитивности дискретных функций Глава 5. Некоторые специальные классы дискретных функций 5.1. Корреляционно-иммунные функции 5.2. k-устойчивые функции 5.3. Бент-функции 5.4. Бент-отображения Глава 6. Декомпозиция булевых функций 6.1. Простая декомпозиция 6.2. Разложимые функции 6.3. Сложные декомпозиции 6.4. Группы инерции суперпозиции булевых функций в группах Еn, Sn, Qn Часть III. Теория алгоритмов Глава 1. Элементы теории алгоритмов 1.1. Нормальные алгоритмы 1.2. Принцип нормализации алгоритмов 1.3. Машины Тьюринга 1.4. Нумерация слов и арифметизация алгоритмов 1.5. Рекурсивные функции 1.6. Примеры алгоритмически неразрешимых проблем Глава 2. Сложность алгоритмов и вычислений 2.1. Сложность нормальных алгоритмов, вычисляющих булевы функции 2.2. Сложности вычислений на машинах Тьюринга 2.3. Классификации задач по сложности их решения на машинах Тьюринга 2.4. О сложностной классификации систем булевых уравнений 2.5. Асимптотические оценки сложности алгоритмов 2.6. Дискретные преобразования Фурье 2.7. Понятие о вероятностных алгоритмах Приложение. Методические рекомендации по организации изучения математической логики, теории алгоритмов, теории дискретных функций Литература
