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 106
- Downloads 0
Development of technology of industrial wastes treatment products disposal by ferritization in the matrix of alkali-activated cements
<p><em>The object of research is liquid and solid wastes resulting from the processing of highly concentrated wastewater from industrial enterprises using the ferritization method. It is known that galvanic production cr...
Improvement of the method of calculation of mechanical characteristics of a traction motor of direct current with combined excitation
<p><em>The object of the study is the process of appearing an electromagnetic moment in traction motors of combined excitation of a trolleybus at synchronous inclusion of both components of the excitation system. This pr...
Improvement of tax policy of territorial communities in the context of budget decentralization
<p><em>The object of research is the process of improving tax policy at the level of territorial communities, taking into account the specifics of fiscal decentralization. One of the most problematic places is the redist...
Implementation of the system of economic security in the enterprise and its impact on the results of the economic activity of the enterprise
<p><em>The object of research is implementation process of the economic security system in the enterprise and its impact on the results of the economic activity of the enterprise. One of the most problematic places is th...
Development of a method for calculating the safe position of military units by using artificial neural networks based on swarm algorithms
<p class="a"><em>The object of research is development of a method for finding a safe position for military units in combat conditions, using swarm algorithms and neural networks. One of the most problematic places is th...