Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/vestnik/DATA/2009/2/node15
Дата изменения: Unknown
Дата индексирования: Sun Apr 10 02:32:18 2016
Кодировка: Windows-1251
Вестник МГУ. Математика. Механика


УДК 519.95

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

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

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

Библиогр. 6.

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