«Математика» 2009 2

Перечисление операторных классов булевых функций

Авторы: С. Ф. Винокуров, А. С. Казимиров
Аннотация:

Работа посвящена задаче классификации булевых функций. Классификация производится по группе преобразований, являющейся расширением группы инвертирования переменных. Такие преобразования представляют интерес в связи с тем,что сохраняют сложность(количество слагаемых)полиномов,представляющих булевы функции. Группа этих преобразований описана с использованием операторного языка и названа группой операторных преобразований. Для нее решена задача перечисления — одна из подзадач классификации, заключающаяся в нахождении числа классов эквивалентности.

Ключевые слова: булевафункция, полиномиальнаяформа, операторы, специальная операторная форма, классификация по группе преобразований
УДК: 519.716.322
Литература: 1. ЛогачевО.А. Булевыфункциивтеориикодированияикриптологии/О.А. Логачев,А.А. Сальников, В.В. Ященко — М.: МЦНМО, 2004. — 470 с.
2. Черемушкин А.В. Линейная и аффинная классификация дискретных функций(обзор публикаций) / А.В. Черемушкин // Математические вопросы кибернетики, 2005. — С. 261–280.
3. Избранные вопросы теории булевых функций: Монография / А.С. Балюк, С.Ф. Винокуров, А.И. Гайдуков и др.; Под ред. С.Ф. Винокурова, Н.А. Перязева. — М.: Физматлит, 2001. — 192 с.