Devising a method of figurative transformations for minimizing boolean functions in the implicative basis

Authors

DOI:

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

Keywords:

method of figurative transformations, minimization of functions of the implicative basis, implication function, PINF-1, PINF-2

Abstract

This paper reports a study that has established the possibility of reducing computational complexity while improving the productivity of simplification of Boolean functions in the class of perfect implied normal forms (PINF-1 and PINF-2) using a method of figurative transformations.

The method of figurative transformations has been expanded to cover the process of simplifying the functions of the implicative basis by using the developed algebra of the implicative basis in the form of rules that simplify the PINF-1 and PINF-2 functions of the implicative basis. A special feature in simplifying the functions of the implicative basis on the binary structures of 2-(n, b)-designs) is the use of analogs of perfect disjunctive normal forms (PDNF) and perfect conjunctive normal forms (PCNF) of Boolean functions. The specified forms of the functions define transformation rules for the functions of the implicative basis on binary structures.

It is shown that the perfect implicative normal form of n-place function of the implicative basis can be represented by the binary sets or a matrix. Logical operations over the structure of the matrix ensure the result from simplifying the functions of the implicative basis. This makes it possible to focus the minimization principle within the truth table of the assigned function and avoid auxiliary objects such as Carnot map, Weich charts, etc.

The method under consideration makes it possible:

– to reduce the algorithmic complexity of PINF-1 and PINF-2 simplification;

– to improve the performance of simplifying the functions of the implied basis by 100‒200 %;

– to visualize the process of PINF-1 or PINF-2 minimization;

There is reason to argue that minimizing the functions of the implicative basis using a method of figurative transformations brings the task of PINF-1 and PINF-2 minimization to the level of well-researched problems within the class of disjunctive-conjunctive normal forms 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

Iuliia Batyshkina, Rivne State University of Humanities St. Bandery str., 12, Rivne, Ukraine, 33028

PhD, Associate Professor

Department of Information and Communication Technologies and Methods of Teaching Informatics

Ihor Voitovych, Rivne State University of Humanities St. Bandery str., 12, Rivne, Ukraine, 33028

Doctor of Pedagogical Sciences, Professor

Department of Information and Communication Technologies and Methods of Teaching Informatics

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

PhD, Associate Professor

Department of Software Systems and Technologies

Stepaniia Babych, Rivne State University of Humanities St. Bandery str., 12, Rivne, Ukraine, 33028

PhD, Associate Professor

Department of Information and Communication Technologies and Methods of Teaching Informatics

Kateryna Muzychuk, Rivne State University of Humanities St. Bandery str., 12, Rivne, Ukraine, 33028

PhD, Associate Professor

Department of Information and Communication Technologies and Methods of Teaching Informatics

References

  1. Bulkin, V. (2014). Modelling of the relation of implication with use of the directed relational networks. Eastern-European Journal of Enterprise Technologies, 6 (4 (72)), 30–37. doi: https://doi.org/10.15587/1729-4061.2014.30567
  2. Dychka, I. A., Tarasenko, V. P., Onai, M. V. (2019). Osnovy prykladnoi teoriyi tsyfrovykh avtomativ. Kyiv: KPI im. Ihoria Sikorskoho, 508. Available at: https://core.ac.uk/download/pdf/323531874.pdf
  3. 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
  4. Kvatinsky, S., Satat, G., Wald, N., Friedman, E. G., Kolodny, A., Weiser, U. C. (2014). Memristor-Based Material Implication (IMPLY) Logic: Design Principles and Methodologies. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 22 (10), 2054–2066. doi: https://doi.org/10.1109/tvlsi.2013.2282132
  5. Shirinzadeh, S., Datta, K., Drechsler, R. (2018). Logic Design Using Memristors: An Emerging Technology. 2018 IEEE 48th International Symposium on Multiple-Valued Logic (ISMVL). doi: https://doi.org/10.1109/ismvl.2018.00029
  6. Teodorovic, P., Vukobratovic, B., Struharik, R., Dautovic, S., Nauka, F. tehnickih, Sad, N. (2012). Sequence generator for computing arbitrary n-input Boolean function using two memristors. 2012 20th Telecommunications Forum (TELFOR). doi: https://doi.org/10.1109/telfor.2012.6419391
  7. Rohani, S. G., TaheriNejad, N. (2017). An improved algorithm for IMPLY logic based memristive Full-adder. 2017 IEEE 30th Canadian Conference on Electrical and Computer Engineering (CCECE). doi: https://doi.org/10.1109/ccece.2017.7946813
  8. Wang, X., Han, J., Yang, Y., Li, Y. (2019). An Improved Mapping and Optimization Method for Implication-based Memristive Circuits Using And-Inverter Graph. Journal of Physics: Conference Series, 1237, 032026. doi: https://doi.org/10.1088/1742-6596/1237/3/032026
  9. Teimoory, M., Amirsoleimani, A., Shamsi, J., Ahmadi, A., Alirezaee, S., Ahmadi, M. (2014). Optimized implementation of memristor-based full adder by material implication logic. 2014 21st IEEE International Conference on Electronics, Circuits and Systems (ICECS). doi: https://doi.org/10.1109/icecs.2014.7050047
  10. Borghetti, J., Snider, G. S., Kuekes, P. J., Yang, J. J., Stewart, D. R., Williams, R. S. (2010). “Memristive” switches enable “stateful” logic operations via material implication. Nature, 464 (7290), 873–876. doi: https://doi.org/10.1038/nature08940
  11. Lehtonen, E., Laiho, M. (2009). Stateful implication logic with memristors. 2009 IEEE/ACM International Symposium on Nanoscale Architectures. doi: https://doi.org/10.1109/nanoarch.2009.5226356
  12. Raghuvanshi, A., Perkowski, M. (2014). Logic synthesis and a generalized notation for memristor-realized material implication gates. 2014 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). doi: https://doi.org/10.1109/iccad.2014.7001393
  13. Lehtonen, E., Poikonen, J. H., Laiho, M. (2010). Two memristors suffice to compute all Boolean functions. Electronics Letters, 46 (3), 230. doi: https://doi.org/10.1049/el.2010.3407
  14. Chua, L. (1971). Memristor-The missing circuit element. IEEE Transactions on Circuit Theory, 18 (5), 507–519. doi: https://doi.org/10.1109/tct.1971.1083337
  15. Krivulya, G., Syrevich, E., Vlasov, I., Pavlov, O. (2013). Osobennosti primeneniya nanomemristornoy logiki dlya proektirovaniya tsifrovyh sistem. Visnyk Khersonskoho natsionalnoho tekhnichnoho universytetu, 1 (46), 280–286. Available at: http://nbuv.gov.ua/UJRN/Vkhdtu_2013_1_54
  16. Eliseev, N. (2010). Memristors and Crossbars: Nanotechnologies for Processors. Electronics: Science, Technology, Business, 8, 84–89. Available at: https://www.electronics.ru/files/article_pdf/0/article_149_323.pdf
  17. Pospelov, D. A. (1974). Logicheskie metody analiza i sinteza shem. Moscow: Energiya, 368. Available at: http://urss.ru/cgi-bin/db.pl?lang=Ru&blang=ru&page=Book&id=25326
  18. 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
  19. 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
  20. Nikishechkin, A. P. (2019). Diskretnaya matematika i diskretnye sistemy upravleniya. Moscow: Yurayt, 298. Available at: https://urait.ru/book/diskretnaya-matematika-i-diskretnye-sistemy-upravleniya-442305
  21. Primery resheniy: minimizatsiya DNF. Available at: https://www.matburo.ru/ex_dm.php?p1=bfmin
  22. 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-12-31

How to Cite

Solomko, M., Batyshkina, I., Voitovych, I., Zubyk, L., Babych, S., & Muzychuk, K. (2020). Devising a method of figurative transformations for minimizing boolean functions in the implicative basis. Eastern-European Journal of Enterprise Technologies, 6(4 (108), 32–47. https://doi.org/10.15587/1729-4061.2020.220094

Issue

Vol. 6 No. 4 (108) (2020): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2020 Mykhailo Solomko, Iuliia Batyshkina, Ihor Voitovych, Liudmyla Zubyk, Stepaniia Babych, Kateryna Muzychuk

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.