RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Иркутского государственного университета. Серия «Математика» // Архив

Известия Иркутского государственного университета. Серия Математика, 2010, том 3, выпуск 4, страницы 2–6 (Mi iigum171)

Эта публикация цитируется в 2 статьях

О сложности одного класса булевых функций

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

Восточно-Сибирская государственная академия образования

Аннотация: В работе исследуется сложность представления булевых функций в классе полиномиальных нормальных форм, которая определяется по числу слагаемых в минимальном полиноме. Рассматривается класс булевых функций, которые имеют наибольшую сложность среди всех функций от 6 переменных и менее. Получено точное значение сложности функций этого класса, зависящих от 7 переменных.

Ключевые слова: булевы функции; полиномиальные формы; операторные формы; минимизация; сложность.

УДК: 519.716.322



© МИАН, 2024