RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2009, номер 2, страницы 72–75 (Mi vmumm866)

Эта публикация цитируется в 4 статьях

Краткие сообщения

О глубине $\alpha$-пополнения систем булевых функций

Д. В. Трущин

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

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

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

УДК: 519.95

Поступила в редакцию: 26.09.2008



Реферативные базы данных:


© МИАН, 2024