Розроблення методу образних перетворень для мінімізації булевих функцій в імплікативному базисі

Автор(и)

  • Mykhailo Solomko Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-0168-5657
  • Iuliia Batyshkina Рівненський державний гуманітарний університет вул. Степана Бандери, 12, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0002-5390-9029
  • Ihor Voitovych Рівненський державний гуманітарний університет вул. Степана Бандери, 12, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-2813-5225
  • Liudmyla Zubyk Київський національний університет імені Тараса Шевченка вул. Володимирська, 60, м. Київ, Україна, 01033, Україна https://orcid.org/0000-0002-2087-5379
  • Stepaniia Babych Рівненський державний гуманітарний університет вул. Степана Бандери, 12, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-2145-6392
  • Kateryna Muzychuk Рівненський державний гуманітарний університет вул. Степана Бандери, 12, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0002-4360-1530

DOI:

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

Ключові слова:

метод образних перетворень, мінімізація функцій імплікативного базису, функція імплікації, ДІНФ-1, ДІНФ-2

Анотація

Проведеними дослідженнями встановлена можливість зменшення обчислювальної складності, збільшення продуктивності спрощення булевих функцій у класі досконалих імплікативних нормальних форм (ДІНФ-1 та ДІНФ-2) методом образних перетворень.

Поширення методу образних перетворень на процес спрощення функцій імплікативного базису здійснено за допомогою розробленої алгебри імплікативного базису у вигляді правил спрощення ДІНФ-1 та ДІНФ-2 функцій імплікативного базису. Особливістю спрощення функцій імплікативного базису на бінарних структурах 2-(n, b)-блок-схем (англ. 2-(n, b)-designs) є використання аналогів досконалих диз’юктивних нормальних форм (ДДНФ) та досконалих кон’юктивних нормальних форм (ДКНФ) булевих функцій. Зазначені форми функцій визначають правила перетворення на бінарних структурах функцій імплікативного базису.

Показано, що досконалу імплікативну нормальну форму n-місткої функції імплікативного базису можна подати бінарними наборами або матрицею. Логічні операції над структурою матриці забезпечують результат спрощення функцій імплікативного базису. Це дозволяє зосередити принцип мінімізації у межах таблиці істинності заданої функції та обійтись без допоміжних об’єктів, як то карта Карно, діаграми Вейча та ін.

Розглянутий метод дозволяє:

– зменшити алгоритмічну складність спрощення ДІНФ-1 та ДІНФ-2;

– збільшити продуктивність спрощення функцій імплікативного базису на 100–200 %;

– демонструвати наочність процесу мінімізації ДІНФ-1 або ДІНФ-2;

Є підстави стверджувати, що мінімізація функцій імплікативного базису методом образних перетворень виводить проблему мінімізації ДІНФ-1 та ДІНФ-2 на рівень добре досліджених задач у класі диз’юнктивно-кон’юнктивних нормальних форм булевих функцій

Біографії авторів

Mykhailo Solomko, Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028

Кандидат технічних наук, доцент

Кафедра обчислювальної техніки

Iuliia Batyshkina, Рівненський державний гуманітарний університет вул. Степана Бандери, 12, м. Рівне, Україна, 33028

Кандидат технічних наук, доцент

Кафедра інформаційно-комунікаційних технологій та методики викладання інформатики

Ihor Voitovych, Рівненський державний гуманітарний університет вул. Степана Бандери, 12, м. Рівне, Україна, 33028

Доктор педагогічних наук, професор

Кафедра інформаційно-комунікаційних технологій та методики викладання інформатики

Liudmyla Zubyk, Київський національний університет імені Тараса Шевченка вул. Володимирська, 60, м. Київ, Україна, 01033

Кандидат педагогічних наук, доцент

Кафедра програмних систем і технологій

Stepaniia Babych, Рівненський державний гуманітарний університет вул. Степана Бандери, 12, м. Рівне, Україна, 33028

Кандидат технічних наук, доцент

Кафедра інформаційно-комунікаційних технологій та методики викладання інформатики

Kateryna Muzychuk, Рівненський державний гуманітарний університет вул. Степана Бандери, 12, м. Рівне, Україна, 33028

Кандидат технічних наук, доцент

Кафедра інформаційно-комунікаційних технологій та методики викладання інформатики

Посилання

  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

##submission.downloads##

Опубліковано

2020-12-31

Як цитувати

Solomko, M., Batyshkina, I., Voitovych, I., Zubyk, L., Babych, S., & Muzychuk, K. (2020). Розроблення методу образних перетворень для мінімізації булевих функцій в імплікативному базисі. Eastern-European Journal of Enterprise Technologies, 6(4 (108), 32–47. https://doi.org/10.15587/1729-4061.2020.220094

Номер

Том 6 № 4 (108) (2020): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2020 Mykhailo Solomko, Iuliia Batyshkina, Ihor Voitovych, Liudmyla Zubyk, Stepaniia Babych, Kateryna Muzychuk

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.