Из соотношения (19) видно, что условие p0 > 0, эквивалентное неравенству µ− λ(1 − β(µ))(1 + µa) > 0, есть необходимое условие существования эргодического распределения. <...> Оно также и достаточное в силу того, что из соотношения (20) величина π(y) однозначно выражается через p0 и является единственным стационарным решением системы (2). <...> Теорема доказана. ломки прибора µ =0, то производящаяфункциядлячисла требований в системе примет вид π(y)= (1−λb)(1 −y)β(λ−λy) β(λ−λy)−y , где b — среднее времяобслуживания требования. <...> Это в точности совпадает с известной формулой Поллачека–Хинчина дляпроизводящей функции числа требований в обыкновенной системе M|G|1|∞ с надежным прибором и одинаково распределенными временами обслуживания (см., например, [3]). <...> Однолинейная система массового обслуживания с ненадежным прибором // Укр. матем. журн. <...> Поступила в редакцию 20.04.2012 УДК 519.6 О НИЖНИХ ОЦЕНКАХ СЛОЖНОСТИ СХЕМ В БАЗИСЕ АНТИЦЕПНЫХ ФУНКЦИЙ О. В. <...> Подольская1 Антицепной функцией называется характеристическая функция антицепи в булевом кубе. <...> Множество всех антицепных функций образует бесконечный полный базис. <...> В работе изучается сложность реализации булевых функций схемами в этом базисе. <...> Доказаны нижние оценки порядка √n для сложности реализации линейной функции, функции голосования и почти всех функций от n переменных. <...> The antichain function is a characteristic function of an antichain in the Boolean cube. <...> The set of antichain functions is an infinite complete basis.We study the computational complexity 1Подольская Ольга Викторовна — студ. каф. дискретной математики мех.-мат. ф-та МГУ, e-mail: olgavikonov@gmail.com. <...> Если дляописанной системы предположить, что G(x) ≡ B(x) и интенсивность по17 18 вестн. моск. ун-та. сер. <...> №2 of Boolean functions over an antichain functional basis. <...> Мы будем изучать сложность реализации булевых функций схемами из функциональных элементов в бесконечном полном базисе, состоящем из всевозможных булевых функций, которые принимают значение 1 только на попарно несравнимых наборах. <...> Под сложностью схемы в базисе AC будем понимать число входящих <...>