SCI Библиотека

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

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

В учебном пособии изложены элементы теории множеств,
алгебры логики и предикатов, булевых функций, контактных
схем и алгоритмов. Показана методика решения типовых задач.
Предназначено для обучающихся по направлению
подготовки 09.03.02 Информационные системы и технологии,
направленность «Создание, модификация и сопровождение ин-
формационных систем, администрирование баз данных».

В учебном пособии изложены элементы теории множеств, алгебры логики и предикатов, булевых функций, контактных схем и алгоритмов. Показана методика решения типовых задач. Предназначено для обучающихся по направлению подготовки 09.03.02 Информационные системы и технологии, направленность «Создание, модификация и сопровождение информационных систем, администрирование баз данных»