Мінімізація булевих функцій комбінаторним методом

Автор(и)

  • Volodymyr Riznyk Національний університет «Львівська політехніка», вул. С. Бандери, 12, м. Львів, Україна, 79013, Україна https://orcid.org/0000-0002-3880-4595
  • Mykhailo Solomko Національний університет водного господарства та природокористування, вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-0168-5657

DOI:

https://doi.org/10.15587/2312-8372.2017.108532

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

булева функція, метод мінімізації, мінімізація логічної функції, блок-схема з повторенням, мінтерм

Анотація

Розглянуто поширення принципу мінімізації за допомогою алгебричних перетворень на метод мінімізації з використанням комбінаторної блок-схеми з повторенням. Математичний апарат блок-схеми з повторенням дає більше інформації стосовно ортогональності, суміжності, однозначності блоків комбінаторної системи, якою є власне таблиця істинності заданої функції, тому застосування такої системи мінімізації функції є більш ефективним.

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

Volodymyr Riznyk, Національний університет «Львівська політехніка», вул. С. Бандери, 12, м. Львів, Україна, 79013

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

Кафедра автоматизованих систем управління

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

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

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

Посилання

  1. Matviienko, M. P. (2012). Kompiuterna lohika. Kyiv: TOV «Tsentr navchalnoi literatury», 288.
  2. Igoshin, V. I. (2007). Matematicheskaia logika i teoriia algoritmov. Moscow: Izdatel'skii tsentr «Akademiia», 304.
  3. Kutiura, L. (2011). Algebra logiki. Moscow: Librokom, 128.
  4. Kolmogorov, A. N., Dragalin, A. G. (2006). Matematicheskaia logika. Ed. 3. Moscow: KomKniga, 240.
  5. Venn, J. (1880). I.On the diagrammatic and mechanical representation of propositions and reasonings. Philosophical Magazine Series 5, 10 (59), 1–18. doi:10.1080/14786448008626877
  6. Nelson, V. P., Troy Nagle, H., Carroll, B. D., Irwin, D. (1995). Digital Logic Circuit Analysis and Design. Pearson, 842.
  7. Manojlovic, V. (2013). Minimization of Switching Functions using Quine-McCluskey Method. International Journal of Computer Applications, 82 (4), 12–16. doi:10.5120/14103-2127
  8. Rytsar, B. (2015). The Minimization Method of Boolean Functions in Polynomial Set-theoretical Format. Conference: Proc. 24th Inter. Workshop, CS@P’2015, Sept. 28–30, 2015, Vol. 2. Poland, Rzeszow, 130–146. Available: http://dspace.nbuv.gov.ua/handle/123456789/87194
  9. 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:10.1080/09747338.2014.921412
  10. Rotar, D. (2010). Software for The Minimization of The Combinational Logic Functions. The Romanian Review Precision Mechanics, Optics & Mechatronics, 37, 95–99.
  11. Bernasconi, A., Ciriani, V., Luccio, F., Pagli, L. (2003). Three-level logic minimization based on function regularities. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22 (8), 1005–1016. doi:10.1109/tcad.2003.814950
  12. Zolfaghari, B., Sheidaeian, H. (2011). A New Case for Image Compression Using Logic Function Minimization. The International Journal of Multimedia & Its Applications, 3 (2), 45–62. doi:10.5121/ijma.2011.3204
  13. Mohana Ranga Rao, R. (2011). An Innovative procedure to minimize Boolean function. International Journal of Advanced Engineering Sciences and Technologies, 3 (1), 12–14.
  14. Nosrati, M., Karimi, R., Nariri, M. (2012). Minimization of Boolean Functions Using Genetic Algorithm. Annals. Computer Science Series, 10 (1), 73–77.
  15. Nosrati, M., Nariri, M. (2011). An Algorithm for Minimizing of Boolean Functions Based on Graph DS. World Applied Programming, 1 (3), 209–214.
  16. 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:10.5120/1959-2621
  17. Buniak, A. (2001). Elektronika ta mikroskhemotekhnika. Ternopil: Aston, 382.
  18. Tonchev, V. (1988). Kombinatornye konfiguratsii. Blok-shemy, kody, grafy. Kyiv: Holovne vydavnytstvo vydavnychoho obiednannia «Vyshcha shkola», 178.
  19. Plehanov, A. (2016, March 8). Simmetrichnye karty kak sredstvo minimizatsii bulevyh funktsii. Geektimes. Available: https://geektimes.ru/post/272294/
  20. Sudnitson, A. (2008). Diskretnaia matematika. F.4. Minimizatsiia bulevyh funktsii. Available: http://ati.ttu.ee/~alsu/DM%20_MinBF_2008_lecture.pdf. Last accessed: 15.07.2017.
  21. Kudriavtsev, V. B., Andreev, A. E. (2006). O slozhnosti algoritmov. Intellektual'nye sistemy, 10 (1-4), 695–760. Available: http://intsys.msu.ru/magazine/archive/v10(1-4)/andreev-695-760.pdf
  22. Nechiporuk, E. I. (1968). O korrektnosti obryvov v ventil'nyh i kontaktnyh shemah. Kibernetika, 5, 40–48.
  23. Redkin, N. P. (1978). O samokorrektirovanii kontaktnyh shem. Problemy kibernetiki, 33, 119–138.
  24. Kirienko, G. I. (1970). Sintez samokorrektiruiushchihsia shem iz funktsional'nyh elementov dlia sluchaia rastushchego chisla oshibok v sheme. Diskretnyi analiz, 16, 38–43.
  25. Serikov, Yu. A. (1972). Algebraicheskii metod resheniia logicheskih uravnenii. Izvestiia AN SSSR. Tehnicheskaia kibernetika, 2, 114–124.
  26. Zhabin, V. I., Zhukov, I. A., Klymenko, I. A., Tkachenko, V. V. (2009). Prykladna teoriia tsyfrovykh avtomativ. Ed. 2. Kyiv: Vydavnytstvo Natsionalnoho aviatsiinoho universytetu «NAU – druk», 360.
  27. Bitiutskii, V. P., Grigorieva, S. V. (2012). Minimizatsiia perekliuchatel'nyh funktsii. Ekaterinburg: UrFU, 22. Available: http://docplayer.ru/46853788-Minimizaciya-pereklyuchatelnyh-funkciy.html
  28. Amerbaev, V. M., Solovyev, R. A., Telpukhov, D. V. (2013). Library implementation of modular arithmetic operations, based on logic functions minimization algorithms. Izvestiya SFedU. Engineering Sciences, 7, 221–225. Available: http://izv-tn.tti.sfedu.ru/wp-content/uploads/2013/7/40.pdf

##submission.downloads##

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

2017-07-25

Як цитувати

Riznyk, V., & Solomko, M. (2017). Мінімізація булевих функцій комбінаторним методом. Technology Audit and Production Reserves, 4(2(36), 49–64. https://doi.org/10.15587/2312-8372.2017.108532

Номер

Том 4 № 2(36) (2017): Інформаційно-керуючі системи

Розділ

Математичне моделювання: Оригінальне дослідження

Ліцензія

Авторське право (c) 2017 Volodymyr Riznyk, Mykhailo Solomko

Creative Commons License

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

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