Интеллектуальные системы.
Теория и приложения

Аннотация

В работе рассматриваются вопросы асимптотической сложности реализации систем булевых функций в модели клеточных схем из функциональных и коммутационных элементов. Основное внимание уделено получению асимптотических оценок высокой степени точности для площади клеточных схем, реализующих достаточно большие классы булевых функций. Сформулированы методы получения верхних и нижних асимптотических оценок, применимые к широким классам функций. На основе этих методов как следствие получены асимптотические оценки высокой степени точности для системы всех самодвойственных булевых функций. Для получения верхних оценок используется конструктивный подход, основанный на сведении исследуемых классов функций к универсальным многополюсникам меньшего порядка и последующей модификации реализующих их клеточных схем. В результате для класса самодвойственных булевых функций установлены согласованные верхние и нижние асимптотические оценки площади, что приводит к асимптотическому равенству порядка роста сложности их реализации в модели клеточных схем.

Ключевые слова: клеточные схемы, площадь схемы, асимптотические оценки, асимптотические оценки высокой степени точности, системы булевых функций, самодвойственные функции, универсальный многополюсник