Алексейчук А. Н., Конюшок С. Н.
Алгебраически вырожденные приближения булевых функций

Исследуются свойства k-мерных приближений булевых функций. Одним из основных результатов является теорема о строении k-мерных функций степени d, находящихся на расстоянии не более <$E 2 sup n-d ~(1~-~ epsilon ~symbol <174> ~(0,1)>, от заданной булевой функции и переменных, <$E 1~symbol Г~d~symbol Г~k~symbol Г~n> <$E epsilon ~symbol <174> ~(0,1)>. Эта теорема существенно усиливает ранее известный результат П. Гопалана и позволяет заметно повысить эффективность предложенного им алгоритма построения всех указанных k-мерных булевых функций.

PDF

Бібліографічний опис:
Алексейчук А. Н., Конюшок С. Н. Алгебраически вырожденные приближения булевых функций. Кибернетика и системный анализ. 2014. Т. 50, № 6. С. 3-14. URL: http://jnas.nbuv.gov.ua/article/UJRN-0001313821