Том 9, серия 1, номер 4 , 2002 г., Стр. 41-49

УДК 519.716
М. Н. Вялый,  В. К. Леонтьев, М. В. Осетров
Монотонные булевы полиномы

Аннотация:
Булевы функции являются полиномами над полем из двух элементов (полиномы Жегалкина). Рассматриваются монотонные полиномы, соответствующие монотонным булевым функциям. Найдены все монотонные полиномы степеней 1, 2, 3. Доказано, что при фиксированной степени $d$ число существенных переменных в монотонном полиноме степени $d$ ограничено.
Библиогр. 2.

Вялый М. Н. ¹
Леонтьев В. К. ¹
Осетров М. В. ²
1. ВЦ РАН,
ул. Вавилова, 40, 117967 Москва, Россия
2. МГУ, Воробьевы горы,
119992 Москва, Россия
е-mail: vyalyi@mccme.ru, lvk@ccas.ru

Статья поступила 18 июня 2002 г.