Boolean functions minimization by the method of figurative transformations

  • Mykhailo Solomko National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028
Keywords: Boolean functions minimization by figurative transformations, DNF, CNF, combinatorial block diagram with repetition, minterm, maxterm

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

Downloads

Download data is not yet available.

Author Biography

Mykhailo Solomko, National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028

PhD, Associate Professor

Department of Computer Engineering

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.


👁 375
⬇ 288
Published
2018-11-28
How to Cite
Solomko, M. (2018). Boolean functions minimization by the method of figurative transformations. Technology Transfer: Fundamental Principles and Innovative Technical Solutions, 18-25. https://doi.org/10.21303/2585-6847.2018.00755
Section
Computer Sciences