EN|RU
English version: Journal of Applied and Industrial Mathematics, 2021, 15:1, 17-38 |
![]() |
Volume 28, No 1, 2021, P. 68-96 UDC 519.71
Keywords: Boolean function, connected function, prime implicant, maximum face, the number of prime implicants, local extremum. DOI: 10.33048/daio.2021.28.699 Igor P. Chukhrov 1 Received August 23, 2020 References[1] Yu. L. Vasil’ev and V. V. Glagolev, Metric properties of disjunctive normal forms, in Discrete Mathematics and Mathematical Problems of Cybernetics, Vol. 1 (Nauka, Moscow, 1974), pp. 99–148 [Russian].[2] A. A. Sapozhenko and I. P. Chukhrov, Boolean function minimization in the class of disjunctive normal forms, Itogi Nauki Tekh., Ser. Teor. Veroyatn., Mat. Stat., Teor. Kibern. 25, 68–116 (1987) [Russian] [J. Sov. Math., 46 (4), 2021–2052 (1989)]. [3] M. M. Gadzhiev, Maximum length of abbreviated DNF for Boolean functions of five and six variables, in Discrete Analysis, Vol. 18 (Izd. Inst. Mat., Novosibirsk, 1971), pp. 3–24 [Russian]. [4] A. P. Vikulin, Estimation of the number of conjunctions in the abbreviated DNF, in Cybernetics Problems, Vol. 29 (Nauka, Moscow, 1971), pp. 151–166 [Russian]. [5] A. K. Chandra and G. Markovsky, On the number of prime implicants, Discrete Math. 24, 7–11 (1978). [6] A. E. Andreev, On the problem of minimizing disjunctive normal forms, Dokl. Akad. Nauk SSSR 274 (2), 265–269 (1984) [Russian]. [7] N. Kettle, A. King, and T. Strzemecki, Widening ROBDDs with Prime Implicants, in Tools and Algorithms for the Construction and Analysis of Systems (Proc. 12th Int. Conf., Vienna, Austria, Mar. 25–Apr. 2, 2006) (Springer, Heidelberg, 2006), pp. 105–119 (Lect. Notes Comput. Sci., Vol. 3920). [8] R. H. Sloan, B. Szörenyi, and G Turan, On $k$-term DNF with the largest number of prime implicants, SIAM J. Discrete Math. 21 (4), 987–998 (2008). [9] N. Talebanfard, On the structure and the number of prime implicants of 2-CNFs, Discrete Appl. Math. 200, 1–4 (2016). [10] G. P. Gavrilov and A. A. Sapozhenko, Tasks and Exercises in Discrete Mathematics, (Fizmatlit, Moscow, 2005) [Russian]. |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|