Boolean functions minimization by the method of figurative transformations
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
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.
Copyright (c) 2018 Mykhailo Solomko
This work is licensed under a Creative Commons Attribution 4.0 International License.
Our journal abides by the Creative Commons CC BY copyright rights and permissions for open access journals.
Authors, who are published in this journal, agree to the following conditions:
1. The authors reserve the right to authorship of the work and pass the first publication right of this work to the journal under the terms of a Creative Commons CC BY, which allows others to freely distribute the published research with the obligatory reference to the authors of the original work and the first publication of the work in this journal.
2. The authors have the right to conclude separate supplement agreements that relate to non-exclusive work distribution in the form in which it has been published by the journal (for example, to upload the work to the online storage of the journal or publish it as part of a monograph), provided that the reference to the first publication of the work in this journal is included.
