УДК 519.6

О сложностной иерархии булевых базисов / Черухин Д.Ю. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. C. 48-50.

Исследуется зависимость сложности булевых функций в классе формул от функционального базиса. В связи с этим на множестве базисов вводится отношение частичного порядка (как это было сделано в работах Б.А. Субботовской, В.А. Стеценко и автора). Основным результатом работы является критерий, позволяющий устанавливать выполнимость этого отношения для произвольных базисов.

Библиогр. 4.