Minimization of conjunctive normal forms of boolean functions by combinatorial method

Autor: Riznyk, Volodymyr, Solomko, Mykhailo
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Zdroj: Technology audit and production reserves; Том 5, № 2(43) (2018): Information and control systems; 42-55
Технологічний аудит та резерви виробництва; Том 5, № 2(43) (2018): Інформаційно-керуючі системи; 42-55
Технологический аудит и резервы производства; Том 5, № 2(43) (2018): Информационно-управляющие системы; 42-55
ISSN: 2226-3780
2312-8372
Popis: The object of research is the combinatorial method of minimizing conjunctive normal forms (CNF) of Boolean functions in order to reduce its algorithmic complexity. One of the most places to minimize CNF of Boolean functions is the complexity of the minimization algorithm and the guarantee of obtaining the minimum function.In the course of the study, the method of equivalent figurative transformations based on the laws and axioms of the algebra of logic, protocols for minimizing CNF of Boolean functions is used.The reduction of the computational complexity of the process of minimization of the CNF of the Boolean functions by the combinatorial method according to the new established criteria has been obtained, thanks to the use of a number of features of the algorithm for finding minimal disjunctive normal forms (DNF) and CNF of logical functions, in particularthe use of the mathematical apparatus of transforming flowcharts with repetition allows to increase the information component of the figurative transformation with respect to the orthogonality, adjacency, uniqueness of truth table blocks;equivalent figurative transformations allow with the effect to replace verbal procedures of algebraic transformations due to the greater information capacity of matrix images;result of minimization is estimated on the basis of the minimal function;minimal DNF or CNF of the functions are obtained regardless of the normal form of the given logical function;minimization protocols for CNF of Boolean functions make up a library of protocols for the process of minimization of CNF of Boolean functions as standard procedures.Due to the above, it is possible to optimally reduce the number of variables of a given function without losing its functionality. The effectiveness of the use of figurative transformations is demonstrated by examples of minimizing functions borrowed from other methods for the purpose of comparison.Compared with similar known methods of minimizing Boolean functions, the proposed method allowsreduce the algorithmic complexity of minimizing CNF of Boolean functions;increase the visibility of the minimization process of DNF or CNF of Boolean functions;ensure the self-sufficiency of the combinatorial method of minimizing Boolean functions by introducing features of the minimal function and minimization on the full table of DNF and CNF.
Объектом исследования является комбинаторный метод минимизации конъюктивных нормальных форм (КНФ) булевых функций с целью снижения его алгоритмической сложности. Одним из самых проблемных мест минимизации КНФ булевых функций является сложность алгоритма минимизации и гарантия получения минимальной функции.В ходе исследования использовался метод равносильных образных преобразований, основанный на законах и аксиомах алгебры логики, протоколы минимизации КНФ булевых функций.Получено уменьшение вычислительной сложности процесса минимизации КНФ булевых функций комбинаторным методом по новым установленным критериям, благодаря использованию ряда особенностей алгоритма поиска минимальных дизьюктивных нормальных форм (ДНФ) и КНФ логических функций, в частности:применение математического аппарата преобразования блок-схем с повторением позволяет увеличить информационную компоненту образного преобразования относительно ортогональности, смежности, однозначности блоков таблицы истинности;равносильные образные преобразования позволяют с эффектом заменить вербальные процедуры алгебраических преобразований за счет большей информационной емкости матричных образов;результат минимизации оценивается по признаку минимальной функции;минимальные ДНФ или КНФ функции получаются независимо от нормальной формы заданной логической функции;протоколы минимизации КНФ булевых функций составляют библиотеку протоколов для процесса минимизации КНФ булевых функций как стандартные процедуры.Благодаря вышеизложенному обеспечивается возможность оптимального уменьшения количества переменных заданной функции без потери ее функциональности. Эффективность применения образных преобразований демонстрируется примерами минимизации функций, заимствованных из других методов с целью сравнения.По сравнению с аналогичными известными методами минимизации булевых функций предложенный метод позволяет:уменьшить алгоритмическую сложность минимизации КНФ булевых функций;увеличить наглядность процесса минимизации ДНФ или КНФ булевых функций;обеспечить самодостаточность комбинаторного метода минимизации булевых функций за счет внедрения признака минимальной функции и минимизации на полной таблице ДНФ и КНФ.
Об'єктом дослідження є комбінаторний метод мінімізації кон’юктивних нормальних форм (КНФ) булевих функцій з метою зменшення його алгоритмічної складності. Одним з найпроблемніших місць мінімізації КНФ булевих функцій є складність алгоритму мінімізації та гарантія отримання мінімальної функції.У ході дослідження використовувався метод рівносильних образних перетворень, який ґрунтується на законах та аксіомах алгебри логіки, протоколи мінімізації КНФ булевих функцій.Отримано зменшення обчислювальної складності процесу мінімізації КНФ булевих функцій комбінаторним методом за новими встановленими критеріями, завдяки використанню ряду особливостей алгоритму пошуку мінімальних диз’юктивних нормальних форм (ДНФ) та КНФ логічних функцій, зокрема:застосування математичного апарату перетворення блок-схем з повторенням дає змогу збільшити інформаційну компоненту образного перетворення стосовно ортогональності, суміжності, однозначності блоків таблиці істинності;рівносильні образні перетворення дозволяють з ефектом замінити вербальні процедури алгебричних перетворень за рахунок більшої інформаційної ємності матричних образів;результат мінімізації оцінюється за ознакою мінімальної функції;мінімальні ДНФ або КНФ функції отримуються незалежно від нормальної форми заданої логічної функції;протоколи мінімізації КНФ булевих функцій складають бібліотеку протоколів для процесу мінімізації КНФ булевих функцій як стандартні процедури.Завдяки вищевикладеному забезпечується можливість оптимального зменшення кількості змінних заданої функцій без втрати її функціональності. Ефективність застосування образних перетворень демонструється прикладами мінімізації функцій, запозичених з інших методів з метою порівняння.У порівнянні з аналогічними відомими методами мінімізації булевих функцій запропонований метод дозволяє:зменшити алгоритмічну складність мінімізації КНФ булевих функцій;збільшити наочність процесу мінімізації ДНФ або КНФ булевих функцій;забезпечити самодостатність комбінаторного методу мінімізації булевих функцій за рахунок впровадження ознаки мінімальної функції та мінімізації на повній таблиці ДНФ і КНФ.
Databáze: OpenAIRE
Externí odkaz: