УДК 519.95

О глубине \alpha-пополнения систем булевых функций / Д. В. Трущин. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2009. № 2. С. 72-75.

Рассматривается задача о реализации булевых функций \alpha-формулами — такими формулами, в которых каждая подформула содержит не более одной нетривиальной главной подформулы. В качестве меры сложности формул рассматривается глубина. Получены полиномиальные верхние и нижние оценки функций Шеннона для \alpha-пополнений конечных систем булевых функций.

Ключевые слова: булева функция, формула, сложность, глубина.

Библиогр. 6.

К оглавлению номера  Go!