Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:3, 418-435
Volume 26, No 3, 2019, P. 115-140
UDC 519.714.7
I. P Chukhrov
On the minimization of Boolean functions for additive complexity measures
Abstract:
The problem of minimizing Boolean functions for additive complexity measures in a geometric interpretation, as covering a subset of vertices in the unit cube by faces, is a special type of a combinatorial statement of the weighted problem of a minimal covering of a set. Its specificity is determined by the family of covering subsets, the faces of the unit cube, that are contained in the set of the unit vertices of the function, as well as by the complexity measure of the faces, which determines the weight of the faces when calculating the complexity of the covering. To measure the complexity, we need nonnegativity, monotonicity in the inclusion of faces, and equality for isomorphic faces. For additive complexity measures, we introduce a classification in accordance with the order of the growth of the complexity of the faces depending on the dimension of the cube and study the characteristics of the complexity of the minimization of almost all Boolean functions.
Bibliogr. 11.
Keywords: face of a Boolean cube, face complex, Boolean function, complexity measure, minimal face complex.
DOI: 10.33048/daio.2019.26.640
Igor P. Chukhrov 1
1. Institute of Computer Aided Design RAS,
19/18 Vtoraya Brestskaya Street, 123056 Moscow, Russia
e-mail: chip@icad.org.ru
Received November 23, 2018
Revised May 14, 2019
Accepted June 5, 2019
References
[1] Yu. L. Vasil’ev and V. V. Glagolev, Metric properties of disjunctive normal forms, Discrete Mathematics and Mathematical Problems of Cybernetics, Vol. 1 (Nauka, Moscow, 1974), 99–148 [Russian].[2] K. Veber, On various minimality notions of the disjunctive normal forms, Problemy Kibernet. 36, 129–158 (1979) [Russian].
[3] G. P. Gavrilov and A. A. Sapozhenko, Tasks and Exercises in Discrete Mathematics (Fizmatlit, Moscow, 2005) [Russian].
[4] A. A. Sapozhenko and I. P. Chukhrov, Boolean function minimization in the class of disjunctive normal forms, Itogi Nauki Tekh., Ser. Teor. Veroyatnost., Mat. Statist., Teor. Kibern., 25, 68–116 (1987) [Russian] [J. Sov. Math. 46, 2021–2052 (1989)].
[5] I. P. Chukhrov, On complexity measures of complexes of faces in the unit cube, Diskretn. Anal. Issled. Oper. 20 (6), 77–94 (2013) [Russian] [J. Appl. Indust. Math. 8, 9–19 (2014)].
[6] I. P. Chukhrov, On a minimization problem for a set of Boolean functions, Diskretn. Anal. Issled. Oper. 22 (3), 75–97 (2015) [Russian] [J. Appl. Indust. Math. 9, 335–350 (2015)].
[7] I. P. Chukhrov, On the complexity of minimizing quasicyclic Boolean functions, Diskretn. Anal. Issled. Oper. 25 (3), 126–151 (2018) [Russian] [J. Appl. Indust. Math. 12, 426–441 (2018)].
[8] S. V. Yablonskii, Introduction to Discrete Mathematics (Vysshaya Shkola, Moscow, 2003) [Russian].
[9] O. Coudert and T. Sasao, Two-level logic minimization, in Logic Synthesis and Verification (Kluwer Acad. Publ., Norwell, MA, 2002), pp. 1–27.
[10] N. Pippenger, The shortest disjunctive normal form of a random Boolean function, Random Structures & Algorithms 22, 161–186 (2003).
[11] C. Umans, T. Villa, and A. L. Sangiovanni-Vincentelli, Complexity of two-level logic minimization, IEEE Trans. CAD Integrated Circuits Systems 25, 1230–1246 (2006).
