100
правок
Изменения
м
→Теорема
Рассмотрим произвольную схему из [[Классы NC и AC| класса]] <tex>\mathrm{AC^0}</tex>. Не умаляя общности, будем считать, что:
# Выходная степень каждого элемента равна <tex>1</tex>.
# Схема имеет <tex>2n_0</tex> входных провода, причем последние <tex>n_0</tex> из них являются отрицанием первых <tex>nn_0</tex> входов.
# Элементы <tex>\lor</tex> и <tex>\land</tex> чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
# Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.
