Выявлены вогнутые продолжения дискретных функций, определенных на вершинах n-мерного единичного куба, n-мерного произвольного куба и n-мерного произвольного параллелепипеда. Конструктивно доказано, что, во-первых, любая дискретная функция fD, определенная на вершинах G - одного из этих трех множеств, имеет бесконечно много вогнутых продолжений на G и, во-вторых, существует функция fNR, являющаяся минимумом среди всех ее вогнутых продолжений на G. Также доказано, что функция fNR на G непрерывна и единственна.
Изучается множество булевых функций от малого числа переменных с оптимальными показателями алгебраической и корреляционной иммунности. Исследуется возможность использования данных функций в качестве координатных функций S-блока.
В пособии излагаются основные вопросы теории булевых функций, прежде всего связанные с доказательством фундаментальной теоремы Э. Поста о функциональной полноте. Рассмотрен вопрос о применении булевых функций для проектирования схем из функциональных элементов и анализу их сложности. Особое внимание уделено доказательству NP-полноты и coNP-полноты ряда проблем распознавания для булевых функций. Рассмотрены некоторые вопросы, связанные с построением схем из функциональных элементов. В пособие включен основной материал по теории k-значных функций (функций k-значной логики), включая теорему А. В. Кузнецова о функциональной полноте. Пособие предназначено для студентов, обучающихся по специальности “Компьютерная безопасность’’ и по направлению “Информационная безопасность’’. Оно может быть использовано при изучении дисциплин “Дискретная математика’’, “Математическая логика и теория алгоритмов’’, “Теория алгоритмов’’, “Сложность вычислений’’, “Криптографические методы защиты информации’’, “Модели безопасности компьютерных систем’’ и “Криптографические протоколы’’, а также специальных дисциплин.
В пособии излагаются основные вопросы теории булевых функций, прежде всего связанные с доказательством фундаментальной теоремы Э. Поста о функциональной полноте. Рассмотрен вопрос о применении булевых функций для проектирования схем из функциональных элементов и анализу их сложности. Особое внимание уделено доказательству NP-полноты и coNP-полноты ряда проблем распознавания для булевых функций. Рассмотрены некоторые вопросы, связанные с построением схем из функциональных элементов. В пособие включен основной материал по теории k-значных функций (функций k-значной логики), включая теорему А. В. Кузнецова о функциональной полноте. Пособие предназначено для студентов, обучающихся по специальности “Компьютерная безопасность’’ и по направлению “Информационная безопасность’’. Оно может быть использовано при изучении дисциплин “Дискретная математика’’, “Математическая логика и теория алгоритмов’’, “Теория алгоритмов’’, “Сложность вычислений’’, “Криптографические методы защиты информации’’, “Модели безопасности компьютерных систем’’ и “Криптографические протоколы’’, а также специальных дисциплин.
В учебном пособии изложены элементы теории множеств,
алгебры логики и предикатов, булевых функций, контактных
схем и алгоритмов. Показана методика решения типовых задач.
Предназначено для обучающихся по направлению
подготовки 09.03.02 Информационные системы и технологии,
направленность «Создание, модификация и сопровождение ин-
формационных систем, администрирование баз данных».
В учебном пособии изложены элементы теории множеств, алгебры логики и предикатов, булевых функций, контактных схем и алгоритмов. Показана методика решения типовых задач. Предназначено для обучающихся по направлению подготовки 09.03.02 Информационные системы и технологии, направленность «Создание, модификация и сопровождение информационных систем, администрирование баз данных»
Среди полных систем булевых функций особый интерес представляют самодостаточные операторы. Они обладают широкой областью применимости и не ограничиваются двухместным случаем. В данной работе формулируются условия, накладываемые на коэффициенты полинома Жегалкина, необходимые и достаточные для того, чтобы полином соответствовал самодостаточному оператору. Рассмотрено полиномиальное представление булевых функций, сохраняющих константу. Показано, что свойства монотонности и линейности не требуют специального рассмотрения при описании самодостаточного оператора. Вводится понятие полинома двойственного остатка, значение которого позволяет определить самодвойственность булевой функции. Доказано, что сохраняющая 0 и 1 или не сохраняющая ни 0, ни 1 булева функция является самодвойственной тогда и только тогда, когда двойственный остаток соответствующего ей полинома Жегалкина равен 0 для любых наборов значений переменных функции. На основании этого факта получена система ведущих коэффициентов. Решение данной системы позволило сформулировать критерий самодвойственности булевой функции, представленной полиномом Жегалкина, накладывающий необходимые и достаточные условия на коэффициенты полинома. Таким образом, показано, что полиномы Жегалкина являются достаточно удобным инструментом при исследовании предполных классов булевых функций.
Одной из перспективных областей применения дискретной математики являются протоколы аутентификации с нулевым разглашением знаний, построенные на основе модулярных кодов класса вычетов. Использование этих кодов позволяет заменить вычислительное устройство, реализующее операцию возведения в степень по модулю, на кодопреобразователь. В результате сложная вычислительная операция будет выполнена за один такт. Эффективность работы кодопреобразователей во многом зависит от правильности перехода от таблицы истинности к совершенным нормальным формам булевых функций. Авторами данной статьи разработаны программный код и графическое интерактивное приложение для ЭВМ, которое позволяет получать совершенные дизъюнктивные и (или) совершенные конъюнктивные нормальные формы согласно описанному пользователем содержанию таблиц истинности и выводить результат в соответствующем поле с использованием логических функций библиотеки Logic или в виде формулы. Совершенные формы можно получить с использованием описания таблицы истинности в виде минтермов (макстермов) булевой функции, а также номеров наборов минтермов (макстермов). В разработанном приложении существует возможность выбора типа получаемой совершенной формы, и оно содержит справочные данные по использованию. Программный код и весь графический интерфейс написаны с помощью встроенного языка и библиотек системы компьютерной алгебры Maple. Созданное интерактивное приложение интуитивно понятно и доступно даже непрофессиональным программистам (преподавателям математики, студентам). Для удобства программный код оформлен в виде графического приложения, требующего для работы установленной на компьютере системы Maple. Разработанное приложение может быть использовано образовательными организациями, в которых преподаются математическая логика, дискретная математика или их разделы.