Minimization of conjunctive normal forms of boolean functions by combinatorial method
| Autor: | Volodymyr Riznyk, Mykhailo Solomko |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Computational complexity theory Computer science 020209 energy Truth table 0211 other engineering and technologies TheoryofComputation_GENERAL 02 engineering and technology Function (mathematics) lcsh:Business Computer Science::Computational Complexity minimization of conjunctive normal forms Reduction (complexity) Transformation (function) block diagram with repetition lcsh:Technology (General) 021105 building & construction 0202 electrical engineering electronic engineering information engineering lcsh:T1-995 Adjacency list combinatorial method of minimizing Boolean functions Combinatorial method lcsh:HF5001-6182 Boolean function |
| Zdroj: | Tehnologìčnij Audit ta Rezervi Virobnictva, Vol 5, Iss 2(43), Pp 42-55 (2018) |
| ISSN: | 2312-8372 2226-3780 |
| DOI: | 10.15587/2312-8372.2018.146312 |
| 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 particular 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; 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 allows reduce 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: |
|