Том 9, серия 1, номер 1, 2002 г., Стр. 84-94
УДК 519.714
Д. Ю. Черухин
О сложности реализации формулами произведений булевых функций
Аннотация:
Рассматривается операция бесповторного произведения булевых функций как обобщение степени булевой функции, введенной Б. А. Субботовской в 1963 г. и использованной ею и автором при решении задачи сравнения булевых базисов. Дан критерий реализуемости последовательности произведений булевых функций формулами в базисе Б с линейной сложностью.
Библиогр. 5.
Черухин Д. Ю. 1
1. MГУ, мех.-мат. факультет, Воробьевы горы,
119899 Москва, Россия
е-mail: dyucher@mech.math.msu.su
Статья поступила 25 июля 2001 г.
