ИГУ - «Известия Иркутского государственного университета»

«Известия Иркутского государственного университета»

Журнал ИГУ

Список выпусков > Серия «Математика» №2, 2009

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

Автор(ы)
С. Ф. Винокуров, А. С. Казимиров

Аннотация

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

Ключевые слова
булевафункция, полиномиальнаяформа, операторы, специальная операторная форма, классификация по группе преобразований

УДК
519.716.322

Литература

1. ЛогачевО.А. Булевыфункциивтеориикодированияикриптологии/О.А. Логачев,А.А. Сальников, В.В. Ященко — М.: МЦНМО, 2004. — 470 с.

2. Черемушкин А.В. Линейная и аффинная классификация дискретных функций(обзор публикаций) / А.В. Черемушкин // Математические вопросы кибернетики, 2005. — С. 261–280.

3. Избранные вопросы теории булевых функций: Монография / А.С. Балюк, С.Ф. Винокуров, А.И. Гайдуков и др.; Под ред. С.Ф. Винокурова, Н.А. Перязева. — М.: Физматлит, 2001. — 192 с.