О сложности и структуре минимальной каскадной контактной схемы, реализующей стандартную мультиплексорную функцию

Abstract

Рассматривается задача индивидуального синтеза каскадных контактных схем для стандартной мультиплексорной функции порядка $n$. Доказано, что минимальная сложность указанной реализации равна $3 \cdot 2^n - 2$ и достигается только на канонической мультиплексорной каскадной контактной схеме порядка $n$, рассматриваемой с точностью до изоморфизма, переименования булевых переменных и применения операции свертывания.