ИСТИНА

В работе исследуется сложность реализации функций из замкнутых классов плоскими (клеточными) схемами. Плоскую схему можно представлять, как укладку схемы из функциональных элементов на целочисленную решётку на плоскости таким образом, что провода заменяются на клеточные элементы, реализующие тождественные функции. В качестве меры сложности рассматривается мощность схем, а именно, средний и максимальный потенциал, равный среднему и, соответственно, максимальному количеству единиц на выходах элементов схемы (эта мера также называется активностью схемы). Ранее был получен порядок функции Шеннона потенциала почти всех функций от n переменных. В данной работе получен порядок функции Шеннона потенциала для класса монотонных функций. Как следствие этой оценки и ранее полученных результатов, получены порядки функции Шеннона потенциала для всех замкнутых классов булевых функций.