Том 7, серия 1, номер 1, 2000 г., Стр. 94-101

УДК 519.7
А. В. Чашкин
$(s,d,\varepsilon)$-Pазложение булевых функций

Аннотация:
Рассматривается специальное $(s,d,\varepsilon)$-разложение произвольной булевой функции $f$, зависящей от $n$ переменных. Элементами этого разложения являются $s$, $s<n$, частичных функций, каждая из которых определена и совпадает с $f$ на некоторой области мощности $d$, где минимально возможное $d$ не более чем в $n^3$ раз превосходит сложность реализации функции $f$ схемами из функциональных элементов. Получены критерии существования $(s,d,\varepsilon)$-разложений.
Библиогр. 8.

Чашкин А. В. ¹
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия
е-mail: chash@glasnet.ru

Статья поступила 2 декабря 1999 г.