Complexity of Boolean Functions in Intelligent Systems for Synthesis of Digital Integrated Circuits

摘要

The representation of an arbitrary Boolean function over different bases in classes of formulas and circuits of functional elements (with and without branching) is considered. It is accompanied by derivation of the corresponding (for different bases) estimates of the following complexity indices such as the number of letters and formula length, the number of subformulas and superposition formula depth, and the number of functional elements in the circuit and its depth. The obtained knowledge should be applied to intelligent systems of integrated circuit synthesis.