DOI: https://doi.org/10.15587/2312-8372.2018.146312

Minimization of conjunctive normal forms of boolean functions by combinatorial method

Volodymyr Riznyk, Mykhailo Solomko

Abstract


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.

Keywords


minimization of conjunctive normal forms; combinatorial method of minimizing Boolean functions; block diagram with repetition

References


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.


GOST Style Citations


Riznyk V., Solomko M. Minimization of Boolean functions by combinatorial method // Technology Audit and Production Reserves. 2017. Vol. 4, Issue 2 (36). P. 49–64. doi: http://doi.org/10.15587/2312-8372.2017.108532 

Riznyk V., Solomko M. Application of super-sticking algebraic operation of variables for Boolean functions minimization by combinatorial method // Technology Audit and Production Reserves. 2017. Vol. 6, Issue 2 (38). P. 60–76. doi: http://doi.org/10.15587/2312-8372.2017.118336 

Riznyk V., Solomko M. Research of 5-bit boolean functions minimization protocols by combinatorial method // Technology Audit and Production Reserves. 2018. Vol. 4, Issue 2 (42). P. 41–52. doi: http://doi.org/10.15587/2312-8372.2018.140351 

Cepek O., Kucera P., Savicky P. Boolean functions with a simple certificate for CNF complexity // Discrete Applied Mathematics. 2012. Vol. 160, Issue 4-5. P. 365–382. doi: http://doi.org/10.1016/j.dam.2011.05.013 

Hemaspaandra E., Schnoor H. Minimization for Generalized Boolean Formulas // Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. 2012. P. 566–571.

Boros E., Cepek O., Kucera P. A decomposition method for CNF minimality proofs // Theoretical Computer Science. 2013. Vol. 510. P. 111–126. doi: http://doi.org/10.1016/j.tcs.2013.09.016 

Gursk´y, S. Minimization of Matched Formulas // WDS'11 Proceedings of Contributed Papers. Part 1. 2011. P. 101–105.

Bernasconi A., Ciriani V., Luccio F., Pagli L. Three-level logic minimization based on function regularities // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2003. Vol. 22, Issue 8. P. 1005–1016. doi: http://doi.org/10.1109/tcad.2003.814950 

Nosrati M., Karimi R. An Algorithm for Minimizing of Boolean Functions Based on Graph DS // World Applied Programming. 2011. Vol. 1, Issue 3. Р. 209–214.

Valli M., Periyasamy Dr. R., Amudhavel J. A state of appraoches on minimization of boolean functions // Journal of Advanced Research in Dynamical and Control Systems. 2017. Issue 12. P. 1322–1341. URL: http://www.jardcs.org/abstract.php?archiveid=1323#

Boyar J., Peralta R. A New Combinational Logic Minimization Technique with Applications to Cryptology. Lecture Notes in Computer Science. Berlin: Springer, 2010. P. 178–189. doi: http://doi.org/10.1007/978-3-642-13193-6_16 

Fiser P., Toman D. 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, 2009. doi: http://doi.org/10.1109/dsd.2009.157 

Pynko A. P. Minimal sequent calculi for monotonic chain finitely-valued logics // Bulletin of the Section of Logic. 2014. Vol. 43, Issue 1-2. P. 99–112.

Pyn'ko A. P. Minimizaciya KNF chastichno-monotonnykh bulevykh funkciy // Dopovіdі Nacіonal'noi akademіi nauk Ukraini. 2017. Issue 3. P. 18–21.

Bulevy funkcii. URL: http://any-book.org/download/88296.html

Rytsar B. Ye. New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification // Upravlyayushhie sistemy i mashiny. 2015. Issue 2. P. 39–57. URL: http://dspace.nbuv.gov.ua/handle/123456789/87194

Rytsar B. Ye. Minimizatsiia systemy lohichnykh funktsii metodom paralelnoho rozcheplennia koniunktermiv // Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Radioelektronika ta telekomunikatsii. 2013. Issue 766. P. 18–27. URL: http://nbuv.gov.ua/UJRN/VNULPPT_2013_766_6

Martyniuk O. M. Osnovy dyskretnoi matematyky. Konspekt lektsii. Odesa: Odeskyi natsionalnyi politekhnichnyi universytet: Nauka i tekhnika, 2008. 300 p.







Copyright (c) 2018 Volodymyr Riznyk, Mykhailo Solomko

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN (print) 2226-3780, ISSN (on-line) 2312-8372