Fine precision estimation of Boolean formulas' complexity in some bases consisting of gates with direct and iterative inputs

Background. One of the main problems in mathematical cybernetics is the problem of control systems synthesis, consisting in building of a circuit from the given class that will realize the given function of logic algebra. At solving of the problem one often needs to take into account various limitations of control systems' structure and parameters. Such limitations often describe real calculations more precisely, and the research of function complexity in models with limitation is of great theoretical interest. In the present work the limitation is associated with methods of gates connection in a circuit. Circuit gates' inputs are divided into 2 types - direct and iterative. Iterative inputs are used for connection of other gates' outputs to them, and direct inputs serve as circuits' inputs. The synthesis problem in this model is considered for a case of formulas, i.e. circuits without gates' inputs branching. The aim of the work is to estimate the Shannon function of fine precision for formulas' complexity in some complete bases of the given type, i.e. the estimates that reveal asymptotics of the second term of asymptotic expansion of the said function. Earlier there has only been obtained the asymptotics of the Shannon function for bases, iterative bridging of which includes a class of monotonic functions; estimates of fine precision for wide basis classes in the present model haven't been revealed. Materials and methods. In this work in particular the authors show the modification of the previously known optimal method of formulas synthesis using the technique of logic-algebra functions modeling by variables on components of special partitions of multiple sets of the Boolean cube. These structures are based on the building of special formulas that realize functions, having gate partitions of multiple own variables with constant entropy. Results. The authors obtained estimates of fine precision of the Shannon function for formulas complexity of logic algebra in some complete bases with direct and iterative variables, iterative bridging of which includes a class of monotonic functions. Conclusions. For the first time in the class of formulas in bases with direct and iterative inputs there has been singled out quite a wide sub-class, in which there has been obtained the estimates of fine precision of the Shannon function for complexity thereof.