Minimization of conjunctive normal forms of boolean functions by combinatorial method
Journal Title: Технологический аудит и резервы производства - Year 2018, Vol 5, Issue 2
Abstract
<p class="SA"><em>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.</em></p><p class="SA"><em>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.</em></p><p class="SA"><em>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 particular</em></p><ul><li><em>the 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;</em></li><li><em>equivalent figurative transformations allow with the effect to replace verbal procedures of algebraic transformations due to the greater information capacity of matrix images;</em></li><li><em>result of minimization is estimated on the basis of the minimal function;</em></li><li><em>minimal DNF or CNF of the functions are obtained regardless of the normal form of the given logical function;</em></li><li><em>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.</em></li></ul><p class="SA"><em>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.</em></p><p class="SA"><em>Compared with similar known methods of minimizing Boolean functions, the proposed method allows</em></p><ul><li><em>reduce the algorithmic complexity of minimizing CNF of Boolean functions;</em></li><li><em>increase the visibility of the minimization process of DNF or CNF of Boolean functions;</em></li><li><em>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.</em></li></ul>
Authors and Affiliations
Volodymyr Riznyk, Mykhailo Solomko
Keywords
Related Articles
- EP ID EP527512
- DOI 10.15587/2312-8372.2018.146312
- Views 123
- Downloads 0
Resolving epistemological issues in theoretical and methodological apparatus of institutional theories of organizations
<p><em>Agency-structure debate has become one of the central issues in modern organizational sociology and the most problematic theoretical area in institutional analysis. Since then researchers in new institutional soci...
Substantiation of organizational and economic complex for increase of social responsibility of business in Ukraine
<p><em>The object of research is the organizational and economic processes of socialization of Ukrainian business. One of the most problematic areas is the formation of an adequate strategy for the behavior of Ukrainian...
Accounting of switching device errors for system with sliding redundancy based on dynamic fault tree
<p class="Abstract"><em>The object of research is a non-renewable system with a single sliding reservation. Such system consists of two main subsystems, one redundancy and two switching devices. While both main subsystem...
Research of methods and technologies for determining the position of the mobile object in space
<p><em>The object of research is the process of tracking the position of a mobile object in space. One of the weakest points in tracking systems for the position of a mobile object in space is the problem of eliminating...
Activities of international agroholdings in the world market of foreign investments: investigation of trends and factors of impact in сurrent financing conditions
<p><em>The activity of international agroholdings is considered as an object of research. Insufficient formalization of cause-effect relationships on the basis of analytical dependencies determining the prospects for the...