Boolean functions minimization by the method of figurative transformations

Mykhailo Solomko

Abstract


The object of research is the method of figurative transformations for Boolean functions minimization. One of the most problematic places to minimize Boolean functions is the complexity of the minimization algorithm and the guarantee of obtaining a minimal function.

During the study, the method of equivalent figurative transformations was used, which is based on the laws and axioms of the algebra of logic; minimization protocols for Boolean functions that are used when the truth table of a given function has a complete binary combinatorial system with repetition or an incomplete binary combinatorial system with repetition.

A reduction in the complexity of the minimization process for Boolean functions is obtained, new criteria for finding minimal functions are established. This is due to the fact that the proposed method of Boolean functions minimization has a number of peculiarities of solving the problem of finding minimal logical functions, in particular:

– mathematical apparatus of the block diagram with repetition makes it possible to obtain more information about the orthogonality, adjacency, uniqueness of the truth table blocks;

– equivalent figurative transformations due to the greater information capacity are capable of replacing verbal procedures of algebraic transformations;

– result of minimization is estimated based on the sign of the minimum function;

– minimum DNF or CNF functions are obtained regardless of the given normal form of the logical function, which means that it is necessary to minimize the given function for two normal forms — DNF and CNF using the full truth table;

This ensures that it is possible to obtain an optimal reduction in the number of variables of a given function without losing its functionality. The effectiveness of the use of equivalent figurative transformations for Boolean functions minimization is demonstrated by examples of minimization of functions borrowed from other methods for the purpose of comparison.

Compared with similar well-known methods of Boolean functions minimization, this provides:

– less complexity of the minimization procedure for Boolean functions;

– guaranteed Boolean functions minimization;

– self-sufficiency of the specified method of Boolean functions minimization due to the introduction of features of the minimal function and minimization of two normal forms – DNF and CNF on the complete truth table of a given Boolean function

Keywords


Boolean functions minimization by figurative transformations; DNF; CNF; combinatorial block diagram with repetition; minterm; maxterm

Full Text:

PDF

References


Quine–McCluskey algorithm. Wikipedia. Available at: https://en.wikipedia.org/wiki/Quine–McCluskey_algorithm

Rathore, T. S. (2014). Minimal Realizations of Logic Functions Using Truth Table Method with Distributed Simplification. IETE Journal of Education, 55 (1), 26–32. doi: http://doi.org/10.1080/09747338.2014.921412

Nosrati, M., Karimi, R., Nariri, M. (2012). Minimization of boolean functions using genetic algorithm. Anale. Seria Informatica, X fasc. 1, 73–77. Available at: https://pdf.semanticscholar.org/c53d/2240a2aa5531832a7707ad186dee23129ed8.pdf

Gursky, S. (2011). Minimization of Matched Formulas. WDS'11 Proceedings of Contributed Papers, Part I, 101–105.

Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi: http://doi.org/10.15587/2312-8372.2017.108532

Riznyk, V., Solomko, M. (2017). Application of super-sticking algebraic operation of variables for Boolean functions minimization by combinatorial method. Technology Audit and Production Reserves, 6 (2 (38)), 60–76. doi: http://doi.org/10.15587/2312-8372.2017.118336

Riznyk, V., Solomko, M. (2018). Research of 5-bit boolean functions minimization protocols by combinatorial method. Technology Audit and Production Reserves, 4 (2 (42)), 41–52. doi: http://doi.org/10.15587/2312-8372.2018.140351

Ivanov, Yu. D., Zakharova, О. S. (2004). Algorithm for synthesizing infimum disjunctive normal forms of logical functions. Proceedings of the Odessa Polytechnic University, 2 (22), 1–7. Available at: http://pratsi.opu.ua/app/webroot/articles/1313074117.pdf

Quine's construction algorithm for an abbreviated DNF (2014). Available at: https://studfiles.net/preview/952550/page:15/

Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Control systems and machines, 2, 39–57. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87194

Nelson's method (2016). Available at: https://studfiles.net/preview/5475041/page:26/

Martynyuk, О. М. (2008). Basics of discrete mathematics. Odessa National Polytechnic University: Science and Technology, 300.




DOI: http://dx.doi.org/10.21303/2585-6847.2018.00755

Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Mykhailo Solomko

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN 2585-6847 (Online), ISSN 2585-6839 (Print)