Implementation of the method of image transformations for minimizing the Sheffer functions

Authors

DOI:

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

Keywords:

method of image transformations, minimization of the Sheffer functions, Sheffer stroke, Sheffer term, ENSF-1, ENSF-2

Abstract

The studies have established the possibility of reducing computational complexity, higher productivity of minimization of the Boolean functions in the class of expanded normal forms of the Sheffer algebra functions by the method of image transformations.

Expansion of the method of image transformations to the minimization of functions of the Sheffer algebra makes it possible to identify new algebraic rules of logical transformations. Simplification of the Sheffer functions on binary structures of the 2-(n, b)-designs) features exceptional situations. They are used both when deriving the result of simplification of functions from a binary matrix and introducing the Sheffer function to the matrix.

It was shown that the expanded normal form of the n-digit Sheffer function can be represented by binary sets or a matrix. Logical operations with the matrix structure provide the result of simplification of the Sheffer functions. This makes it possible to concentrate the principle of minimization within the truth table of a given function and do without auxiliary objects, such as Karnaugh map, Weich diagrams, coverage tables, etc.

Compared with the analogs of minimizing the Sheffer algebra functions, the method under the study makes the following to be possible:

‒ reduce algorithmic complexity of minimizing expanded normal forms of the Sheffer functions (ENSF-1 and ENSF-2);

‒ increase the productivity of minimizing the Sheffer algebra functions by 100‒150 %;

‒ demonstrate clarity of the process of minimizing the ENSF-1 or ENSF-2;

‒ ensure self-sufficiency of the method of image transformations to minimize the Sheffer algebra functions by introducing the tag of minimum function and minimization in the complete truth table of the ENSF-1 and ENSF-2.

There are reasons to assert that application of the method of image transformations to the minimization of the Sheffer algebra functions brings the problem of minimization of the ENSF-1 and ENSF-2 to the level of a well-studied problem in the class of disjunctive-conjunctive normal forms (DCNF) of Boolean functions

Author Biographies

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

PhD, Associate Professor

Department of Computer Engineering

Nataliia Khomiuk, Lesya Ukrainka Eastern European National University Voli ave., 13, Lutsk, Ukraine, 43025

PhD

Department of International Economic Relations and Project Management

Yakiv Ivashchuk, National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028

PhD

Department of Higher Mathematics

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

PhD

Department of Computer Engineering

Vikroriia Reinska, National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028

PhD, Associate Professor

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

Anzhela Popova, Kharkiv National Automobile and Highway University Yaroslava Mudroho str., 25, Kharkiv, Ukraine, 61002

PhD

Department of Accounting, Taxation and International Economic Relations

References

  1. Pucknell, D. A. (1990). Fundamentals of Digital Logic Design: With VLSI Circuit applications. Prentice Hall, 486.
  2. Mano, M. M., Kime, C. (2003). Logic and Computer Design Fundamentals. Prentice Hall, 650.
  3. Baranov, S. (2008). Logic and System Design of Digital Systems. Tallinn: TUT Press.
  4. De Micheli, G. (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill, 597.
  5. Zakrevskij, A., Pottosin, Yu., Cheremisinova, L. (2009). Optimization in Boolean Space. Tallinn: TUT Press. Available at: http://www.ester.ee/record=b2461762*est
  6. Luba, T. (2000). Synteza układ´ow logicznych. Warszawa: WSISiZ.
  7. Rawski, M., Łuba, T., Jachna, Z., Tomaszewicz, P. (2005). The Influence of Functional Decomposition on Modern Digital Design Process. Design of Embedded Control Systems, 193–204. doi: https://doi.org/10.1007/0-387-28327-7_17
  8. Bibilo, N. (2009). Decomposition of Boolean Functions by Means of Solving Logical Equations. Minsk: Belaruskaya Navuka.
  9. Borowik, G., Łabiak, G., Bukowiec, A. (2015). FSM-Based Logic Controller Synthesis in Programmable Devices with Embedded Memory Blocks. Topics in Intelligent Engineering and Informatics, 123–151. doi: https://doi.org/10.1007/978-3-319-12652-4_8
  10. 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. doi: https://doi.org/10.15587/1729-4061.2020.206308
  11. Baranov, S., Karatkevich, A. (2018). On Transformation of a Logical Circuit to a Circuit with NAND and NOR Gates Only. INTL JOURNAL OF ELECTRONICS AND TELECOMMUNICATIONS, 64 (3), 373–378. doi: http://doi.org/10.24425/123535
  12. Maxfield, M. (2018). Implementing Logic Functions Using Only NAND or NOR Gates. Available at: https://www.eeweb.com/implementing-logic-functions-using-only-nand-or-nor-gates/
  13. An algorithm to implement a boolean function using only NAND's or only NOR's. Available at: https://cnx.org/contents/vJcXn_C0@4.9:vLMEHoQ0@6/An-algorithm-to-implement-a-boolean-function-using-only-NAND-s-or-only-NOR-s
  14. Kana, A. F. (2008). Implimenting logical circuit using NAND and NOR gate only. Digital Logic Design, 47–54. Available at: http://american.cs.ucdavis.edu/academic/ecs154a.sum14/postscript/cosc205.pdf
  15. Shaik, E. haq, Rangaswamy, N. (2017). Realization of all-optical NAND and NOR logic functions with photonic crystal based NOT, OR and AND gates using De Morgan’s theorem. Journal of Optics, 47 (1), 8–21. doi: https://doi.org/10.1007/s12596-017-0441-y
  16. Rajaei, A., Houshmand, M., Rouhani, M. (2011). Optimization of Combinational Logic Circuits Using NAND Gates and Genetic Programming. Soft Computing in Industrial Applications, 405–414. doi: https://doi.org/10.1007/978-3-642-20505-7_36
  17. Macia, J., Sole, R. (2014). How to Make a Synthetic Multicellular Computer. PLoS ONE, 9 (2), e81248. doi: https://doi.org/10.1371/journal.pone.0081248
  18. Dychka, I. A., Tarasenko, V. P., Onai, M. V. (2019). Osnovy prykladnoi teoriyi tsyfrovykh avtomativ. Kyiv: KPI im. Ihoria Sikorskoho, 508.
  19. 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
  20. 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
  21. Havrylenko, S. Yu., Klymenko, A. M., Noskov, V. I. (2014). Lohika dyskretnykh avtomativ. Kharkiv, 129. Available at: http://web.kpi.kharkov.ua/otp/wp-content/uploads/sites/152/2016/05/Kompyuterna_logika_2sem_praktikum.pdf
  22. 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
  23. Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Upravlyayushchie sistemy i mashiny, 2, 39–57.
  24. 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

Downloads

Published

2020-10-31

How to Cite

Solomko, M., Khomiuk, N., Ivashchuk, Y., Nazaruk, V., Reinska, V., Zubyk, L., & Popova, A. (2020). Implementation of the method of image transformations for minimizing the Sheffer functions. Eastern-European Journal of Enterprise Technologies, 5(4 (107), 19–34. https://doi.org/10.15587/1729-4061.2020.214899

Issue

Vol. 5 No. 4 (107) (2020): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2020 Mykhailo Solomko, Nataliia Khomiuk, Yakiv Ivashchuk, Vitalii Nazaruk, Vikroriia Reinska, Liudmyla Zubyk, Anzhela Popova

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.