RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические вопросы криптографии // Архив

Матем. вопр. криптогр., 2012, том 3, выпуск 2, страницы 117–130 (Mi mvk57)

Cвойства систем образующих универсальных алгебр, порождаемых булевыми биюнктивными функциями

А. В. Тарасов

Московский государственный технический университет радиотехники, электроники и автоматики, г. Москва

Аннотация: В работе исследуются два подхода к описанию систем образующих универсальных алгебр, порождаемых булевыми биюнктивными функциями. Основными множествами этих алгебр являются множества выполняющих векторов булевых функций, представимых в виде $2$-КНФ; алгебры имеют одну тернарную операцию, определяемую покоординатным применением функции голосования от трех переменных к тройкам двоичных $n$-мерных векторов. Первый подход состоит в исследовании графов соответствующих $2$-КНФ, второй основан на применении задачи о покрытиях множеств.

Ключевые слова: $2$-КНФ, биюнктивная функция, универсальная алгебра.

УДК: 519.571

Получено 20.V.2011

DOI: 10.4213/mvk57



© МИАН, 2024