A NEW HEURISTIC ALGORITHM FOR SEQUENTIAL TWO-BLOCK DECOMPOSITION OF BOOLEAN FUNCTIONS

The task of simple decomposition of a Boolean function, generally non-disjunctive, is considered, its solution is reduced in main to search for appropriate weak partitions on the set of arguments. A special attention is paid to the case of presence of a good solution for the given Boolean function, in remaining random. To find it, a two-stage heuristic combinatorial algorithm is offered, optimized on speed. At the first stage the randomized search for “traces” of the decomposition is fulfilled. These traces are represented by some “triads” - the simplest weak partitions corresponding to non-trivial decompositions. At the second stage the whole sought-for partition is restored from the discovered trace. The results of computer experiments confirming practical efficiency of the algorithm are quoted.