Minimization of Boolean functions by combinatorial method

Abstract

The object of solving the problem of minimizing the Boolean function in this work is a block diagram with repetition, what is the truth table of the given function. This allows to leave the minimization principle within the function calculation protocol and, thus, dispense with auxiliary objects like algebraic expressions, Karnaugh map, Veitch diagram, acyclic graph, etc. The algebraic transformations of conjunctors are limited to the verbal form of information, they require active decoding, processing and the addition of algebraic data, therefore, as the number of variable variables increases and the resource of such minimization method is quickly exhausted. In turn, the mathematical apparatus of the combinatorial block diagram with repetition gives more information about the orthogonality, contiguity, uniqueness of truth table blocks, so the application of such minimization system of the Boolean function is more efficient. Equivalent transformations by graphic images, in their properties have a large information capacity, capable of effectively replacing verbal procedures of algebraic transformations. The increased information capacity of the combinatorial method makes it possible to carry out manual minimization of 4, 5-bit Boolean functions quite easily.

Using a block diagram with repetition in tasks of minimizing Boolean function is more advantageous in comparison with analogues for the following factors:

– lower cost of development and implementation, since the principle of minimization of the method remains within the truth table of this function and does not require other auxiliary objects;

– increasing the performance of the manual minimization procedure for 4-, 5-bit functions and increasing the performance of automated minimization with a greater number of variable functions, in particular due to the fact that several search options give the same minimum function.

The combinatorial method for minimizing Boolean functions can find practical application in the development of electronic computer systems, because:

– DNF minimization is one of the multiextremal logical-combinatorial problems, the solution of which is, in particular, the combinatorial device of block-schemes with repetition;

– expands the possibilities of Boolean functions minimization technology for their application in information technology;

– improves the algebraic method of minimizing the Boolean function due to the tabular organization of the method and the introduction of the device of figurative numeration;

– the minimum function can be obtained by several search options that reduces the complexity of the search algorithm, and is the rationale for developing a corresponding function minimization protocol.