One Approach to Synthesizing Predicate Circuits on the Basis of Generalized Variables

摘要

The asymptotic behavior of the Shannon's function L_&(n) is studied for complexity of n-variable predicate implementation with the use of predicate circuits over arbitrary complete basis & A new definition of the reduced weight of the predicate is introduced, regarding it as a solution of a specific linear programming problem based on a system of predicate's generalized variables. New, more exact upper elements for L_&(n) in a number of bases are acquired by the means of special decompositions of initial predicates using universal sets of predicates constructed for circuits consisting of bases elements with minimal reduced weight.