Книга: БУЛЕВЫ ФУНКЦИИ

В пособии излагаются основные вопросы теории булевых функций, прежде всего связанные с доказательством фундаментальной теоремы Э. Поста о функциональной полноте. Рассмотрен вопрос о применении булевых функций для проектирования схем из функциональных элементов и анализу их сложности. Особое внимание уделено доказательству NP-полноты и coNP-полноты ряда проблем распознавания для булевых функций. Рассмотрены некоторые вопросы, связанные с построением схем из функциональных элементов. В пособие включен основной материал по теории k-значных функций (функций k-значной логики), включая теорему А. В. Кузнецова о функциональной полноте. Пособие предназначено для студентов, обучающихся по специальности “Компьютерная безопасность’’ и по направлению “Информационная безопасность’’. Оно может быть использовано при изучении дисциплин “Дискретная математика’’, “Математическая логика и теория алгоритмов’’, “Теория алгоритмов’’, “Сложность вычислений’’, “Криптографические методы защиты информации’’, “Модели безопасности компьютерных систем’’ и “Криптографические протоколы’’, а также специальных дисциплин.