Minimization of conjunctive normal forms of boolean functions by combinatorial method

Volodymyr Riznyk; Mykhailo Solomko

doi:10.15587/2312-8372.2018.146312

Автор(и)

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.2018.146312

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

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

Анотація

Об'єктом дослідження є комбінаторний метод мінімізації кон’юктивних нормальних форм (КНФ) булевих функцій з метою зменшення його алгоритмічної складності. Одним з найпроблемніших місць мінімізації КНФ булевих функцій є складність алгоритму мінімізації та гарантія отримання мінімальної функції.

У ході дослідження використовувався метод рівносильних образних перетворень, який ґрунтується на законах та аксіомах алгебри логіки, протоколи мінімізації КНФ булевих функцій.

Отримано зменшення обчислювальної складності процесу мінімізації КНФ булевих функцій комбінаторним методом за новими встановленими критеріями, завдяки використанню ряду особливостей алгоритму пошуку мінімальних диз’юктивних нормальних форм (ДНФ) та КНФ логічних функцій, зокрема:

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

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

У порівнянні з аналогічними відомими методами мінімізації булевих функцій запропонований метод дозволяє:

зменшити алгоритмічну складність мінімізації КНФ булевих функцій;
збільшити наочність процесу мінімізації ДНФ або КНФ булевих функцій;
забезпечити самодостатність комбінаторного методу мінімізації булевих функцій за рахунок впровадження ознаки мінімальної функції та мінімізації на повній таблиці ДНФ і КНФ.

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

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

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

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

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

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

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

Посилання

Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi: http://doi.org/10.15587/2312-8372.2017.108532
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: http://doi.org/10.15587/2312-8372.2017.118336
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: http://doi.org/10.15587/2312-8372.2018.140351
Cepek, O., Kucera, P., Savicky, P. (2012). Boolean functions with a simple certificate for CNF complexity. Discrete Applied Mathematics, 160 (4-5), 365–382. doi: http://doi.org/10.1016/j.dam.2011.05.013
Hemaspaandra, E., Schnoor, H. (2012). Minimization for Generalized Boolean Formulas. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, 566–571.
Boros, E., Cepek, O., Kucera, P. (2013). A decomposition method for CNF minimality proofs. Theoretical Computer Science, 510, 111–126. doi: http://doi.org/10.1016/j.tcs.2013.09.016
Gursk´y, S. (2011). Minimization of Matched Formulas. WDS'11 Proceedings of Contributed Papers. Part 1, 101–105.
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: http://doi.org/10.1109/tcad.2003.814950
Nosrati, M., Karimi, R. (2011). An Algorithm for Minimizing of Boolean Functions Based on Graph DS. World Applied Programming, 1 (3), 209–214.
Valli, M., Periyasamy, Dr. R., Amudhavel, J. (2017). A state of appraoches on minimization of boolean functions. Journal of Advanced Research in Dynamical and Control Systems, 12, 1322–1341. Available at: http://www.jardcs.org/abstract.php?archiveid=1323#
Boyar, J., Peralta, R. (2010). A New Combinational Logic Minimization Technique with Applications to Cryptology. Lecture Notes in Computer Science. Berlin: Springer, 178–189. doi: http://doi.org/10.1007/978-3-642-13193-6_16
Fiser, P., Toman, D. (2009). A Fast SOP Minimizer for Logic Funcions Described by Many Product Terms. 2009 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools. Patras. doi: http://doi.org/10.1109/dsd.2009.157
Pynko, A. P. (2014). Minimal sequent calculi for monotonic chain finitely-valued logics. Bulletin of the Section of Logic, 43 (1-2), 99–112.
Pyn'ko, A. P. (2017). Minimizaciya KNF chastichno-monotonnykh bulevykh funkciy. Dopovіdі Nacіonal'noi akademіi nauk Ukraini, 3, 18–21.
Bulevy funkcii. Available at: http://any-book.org/download/88296.html
Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Upravlyayushhie sistemy i mashiny, 2, 39–57. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87194
Rytsar, B. Ye. (2013). Minimizatsiia systemy lohichnykh funktsii metodom paralelnoho rozcheplennia koniunktermiv. Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Radioelektronika ta telekomunikatsii, 766, 18–27. Available at: http://nbuv.gov.ua/UJRN/VNULPPT_2013_766_6
Martyniuk, O. M. (2008). Osnovy dyskretnoi matematyky. Konspekt lektsii. Odesa: Odeskyi natsionalnyi politekhnichnyi universytet: Nauka i tekhnika, 300.