The algorithm for minimizing Boolean functions using a method of the optimal combination of the sequence of figurative transformations

Authors

DOI:

https://doi.org/10.15587/1729-4061.2020.206308

Keywords:

Boolean function minimization, optimal combination of the sequence of figurative transformations, Mahoney map

Abstract

The reported study has established the possibility of improving the productivity of an algorithm for the minimization of Boolean functions using a method of the optimal combination of the sequence of logical operations applying different techniques for gluing the variables ‒ simple gluing and super-gluing.

The correspondence of intervals I(α, β) in the Boolean space ẞnhas been established, given by a pair of Boolean vectors α and β, such that α≼β, with a complete combinatorial system with the repeated 2-(n, b)-designs. The internal components of the interval I(α, β) correspond to the complete 2-(n, b)-design system while external ones are determined by calculating the number of zeros or unities in the columns of the truth table of the assigned logical function. This makes it possible to use the theory of I(α, β) intervals in the mathematical apparatus of 2-(n, b)-design combinatorial systems to minimize Boolean functions by the method of equivalent figurative transformations, in particular, to perform automated search for the 2-(n, b)-design systems in the structure of a truth table.

Experimental study has confirmed that the combinatorial 2-(n, b)-design system and the consistent alternation of logical operations of super-gluing the variables (if such an operation is possible) and the simple gluing of variables in the first truth table improves the efficiency of the process and the reliability of results from minimizing the Boolean functions. This simplifies algorithmizing the search for the 2-(n, b)-design system in the structure of a truth table of the assigned logical function, which would provide for the tool to further automate the search for the 2-(n, b)-design system. In comparison with analogs, it enables increasing the productivity of the Boolean function minimization process by 100–200 % by using an optimum alternation of operations of super gluing and simple gluing of variables by the method of equivalent figurative transformations.

There are reasons to argue about the possibility to improve the productivity of the Boolean function minimization process by the optimal combination of the sequences of the logical operations of super-gluing the variables and the simple gluing of variables by the method of equivalent figurative transformations

Author Biographies

Volodymyr Riznyk, Lviv Polytechnic National University S. Bandery str., 12, Lviv, Ukraine, 79013

Doctor of Technical Sciences, Professor

Department of Automated Control Systems

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

PhD, Associate Professor

Department of Computer Engineering

Petro Tadeyev, National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028

PhD, Doctor of Pedagogical Sciences, Professor

Department of Higher Mathematics

Vitalii Nazaruk, National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028

PhD

Department of Computer Engineering

Liudmyla Zubyk, Taras Shevchenko National University of Kyiv Volodymyrska str., 60, Kyiv, Ukraine, 01033

PhD, Associate Professor

Department of Software Systems and Technologies

Volodymyr Voloshyn, National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028

PhD

Department of Computer Technology and Economic Cybernetics

References

  1. Curtis, H. A. (1962). A new approach to the design of switching circuits. N.J.: Princeton, Toronto, 635.
  2. Mayorov, S. A. (Ed.) (1972). Proektirovanie tsifrovyh vychislitel'nyh mashin. Moscow: Vysshaya shkola, 344.
  3. Pospelov, D. A. (1974). Logicheskie metody analiza i sinteza shem. Moscow: Energiya, 368.
  4. Zakrevskiy, A. D. (1981). Logicheskiy sintez kaskadnyh shem. Moscow: Nauka, 416.
  5. Rytsar, B. E. (1997). Metod minimizatsii bulevyh funktsiy. Problemy upravleniya i informatiki, 2, 100–113.
  6. Riznyk, V., Solomko, M. (2018). Minimization of conjunctive normal forms of boolean functions by combinatorial method. Technology Audit and Production Reserves, 5 (2 (43)), 42–55. doi: https://doi.org/10.15587/2312-8372.2018.146312
  7. Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi: https://doi.org/10.15587/2312-8372.2017.108532
  8. 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: https://doi.org/10.15587/2312-8372.2017.118336
  9. 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: https://doi.org/10.15587/2312-8372.2018.140351
  10. Dan, R. (2010). Software for The Minimization of The Combinational Logic Functions. The Romanian Review Precision Mechanics, Optics & Mchatronics, 37, 95–99. Available at: https://pdfs.semanticscholar.org/b881/59ffd963e4cb44d513eba58230e56f1e5605.pdf
  11. Huang, J. (2014). Programing implementation of the Quine-McCluskey method for minimization of Boolean expression. arXiv. Available at: https://arxiv.org/ftp/arxiv/papers/1410/1410.1059.pdf
  12. Nosrati, M., Karimi, R. (2011). An Algorithm for Minimizing of Boolean Functions Based on Graph DS. World Applied Programming, 1 (3), 209–214.
  13. Solairaju, A., Periyasamy, R. (2011). Optimal Boolean Function Simplification through K-Map using Object-Oriented Algorithm. International Journal of Computer Applications, 15 (7), 28–32. doi: https://doi.org/10.5120/1959-2621
  14. Boyar, J., Peralta, R. (2010). A New Combinational Logic Minimization Technique with Applications to Cryptology. Lecture Notes in Computer Science, 178–189. doi: https://doi.org/10.1007/978-3-642-13193-6_16
  15. Chen, Z., Ma, H., Zhang, Y. (2014). A Rapid Granular Method for Minimization of Boolean Functions. Lecture Notes in Computer Science, 577–585. doi: https://doi.org/10.1007/978-3-319-11740-9_53
  16. Papakonstantinou, K. G., Papakonstantinou, G. (2018). A Nonlinear Integer Programming Approach for the Minimization of Boolean Expressions. Journal of Circuits, Systems and Computers, 27 (10), 1850163. doi: https://doi.org/10.1142/s0218126618501633
  17. Kabalan, K. Y., El-Hajj, A., Fakhreddine, S., Smari, W. S. (1995). Computer tool for minimizing logic functions. Computer Applications in Engineering Education, 3 (1), 55–64. doi: https://doi.org/10.1002/cae.6180030108
  18. Bulevy konstanty i vektory. Available at: https://studfile.net/preview/4243601/
  19. Nazarova, I. A. (2012). Dyskretnyi analiz. Donetsk, 277. Available at: http://ea.donntu.edu.ua/bitstream/123456789/27328/1/%D0%9D%D0%9F_%D0%94%D0%90_%D0%A3%D0%9A%D0%A0%20%28%D0%9F%D0%BE%D0%BB%D0%BD%D0%B8%D0%B9%29.pdf
  20. Samofalov, K. G., Romlinkevich, A. M., Valuyskiy, V. N., Kanevskiy, Yu. S, Pinevich, M. M. (1987). Prikladnaya teoriya tsifrovyh avtomatov. Kyiv, 375. Available at: http://stu.scask.ru/book_pta.php?id=62
  21. Bonal, D. (2013). Karnaugh and Mahoney – Map Methods for Minimizing Boolean Expressions. Available at: http://davidbonal.com/karnaugh-and-mahoney-map-methods-for-minimizing-boolean-expressions/
  22. Filippov, V. M., Manohina, T. V., Evdokimov, A. A., Zayats, D. S. (2016). Minimizatsiya funktsiy algebry logiki metodom nenapravlennogo grafa. Mezhdunarodniy zhurnal prikladnyh i fundamental'nyh issledovaniy, 8 (4), 509–511. Available at: https://applied-research.ru/ru/article/view?id=10112
  23. Kumar, R., Rawat, S. (2016). Cubical Representation and Minimization through Cubical Technique A Tabular Approach. International Journal of Applied Engineering Research, 11 (7), 4822–4829.

Downloads

Published

2020-06-30

How to Cite

Riznyk, V., Solomko, M., Tadeyev, P., Nazaruk, V., Zubyk, L., & Voloshyn, V. (2020). The algorithm for minimizing Boolean functions using a method of the optimal combination of the sequence of figurative transformations. Eastern-European Journal of Enterprise Technologies, 3(4 (105), 43–60. https://doi.org/10.15587/1729-4061.2020.206308

Issue

Vol. 3 No. 4 (105) (2020): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2020 Volodymyr Riznyk, Mykhailo Solomko, Petro Tadeyev, Vitalii Nazaruk, Liudmyla Zubyk, Volodymyr Voloshyn

Creative Commons License

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

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.