Minimization of Boolean functions in their various representations is required in logic design of digital devices. EXOR sums (polynomial forms) are considered among other representations. An EXOR sum (a polynomial form) is an expression that is an EXOR sum of products of factors in a certain form. We can accentuate some classes of EXOR sums (of polynomial forms) such that Fixed Polarized Reed-Muller forms, FPRMs (polarized polynomial forms, PPFs), EXOR Sums of Products, ESOPs (polynomial normal forms, PNFs), EXOR Sums of Pseudo-Products, ESPPs (pseudo-polynomial forms, PSPFs), etc. In series of works, minimization algorithms are devised, and bounds are obtained for the length of functions in these classes of EXOR sums. Herewith, there are different aspects in these researches, in particular, to obtain bounds of the length for the most complex functions of n variables for an arbitrary number n and to find the exact length for functions of a small number of variables.

The present work is devoted to finding the exact length for functions of a small number of variables. EXOR Sums of Pseudo-Products, ESPPs (pseudo-polynomial forms, PSPFs) for Boolean functions are considered in it. An EXOR Sum of Pseudo-Products, ESPP (a pseudo-polynomial form, PSPF) is an expression that is an EXOR sum of products of linear functions. The length of an ESPP is the number of its summands; the length of a function in the class of ESPPs is the smallest length among all ESPPs, representing this function. In the work, the complete classification by the length in the class of ESPPs is obtained for functions of four variables. The largest length and the average length in the class of ESPPs are found for functions of five variables.

Svetlana Selezneva, Dr. Sci. (Phys.–Math.), Prof., Lomonosov Moscow State University, build. 52, 1, Leninskiye Gory, 119991, Moscow, Russian Federation, tel.: (495)9395392, email: selezn@cs.msu.ru

Aleksey Lobanov, Student, Lomonosov Moscow State University, build. 52, 1, Leninskiye Gory, 119991, Moscow, Russian Federation, tel.: (495)9395392, email: alex_cmc@likemath.ru

Selezneva S.N., Lobanov A.A. On Length of Boolean Functions of a Small Number of Variables in the Class of Pseudo-Polynomials. The Bulletin of Irkutsk State University. Series Mathematics, 2020, vol. 33, pp. 96-105. https://doi.org/10.26516/1997-7670.2020.33.96

1. Baliuk A. S. Complexity lower bound for Boolean functions in the class of extended operator forms. The Bulletin of Irkutsk State University. Series Mathematics, 2019, vol. 30, pp. 125–140. https://doi.org/10.26516/1997-7670.2019.30.125
2. Ishikawa R., Hirayama T., Koda G., Shimizu K. New three-level Boolean expression based on EXOR gates. IEICE Trans. Inf. & Syst., 2004, vol. E87-D, no 5, pp.214–1222.
3. Kirichenko K. D. An upper bound for complexity of polynomial normal forms of Boolean functions. Discrete Math. Appl., 2005, vol. 15, no. 4, pp. 351–360. https://doi.org/10.1515/156939205774464891
4. Lozhkin S. A., Shupletsov M. S., Konovodov V. A., Danilov B. R., Zhukov V. V., Bagrov N. Yu. Raspredelennaya sistema i algoritmy poiska minimal’nyh i blizkih k nim kontaktnyh shem dlya bolevyh funkthiy malogo chisla peremennyh. Sbornik trudov vserossiyskih nauchno-tehnicheskih konferentsiy “Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh sistem (MES)”, 2016, vol. 1, pp. 40–47. (in Russian)
5. Peryazev N. A. Complexity of Boolean functions in the class of polarized polynomial forms. Algebra and Logic, 1995, vol. 34, pp. 177–179. https://doi.org/10.1007/BF02341875
6. Sasao T., Besslich P. On the complexity of mod-2 sum PLA’s. IEEE Trans. on Comput., 1990, vol. 39, no. 2, pp. 262–266.
7. Selezneva S. N. On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts. Moscow University Computational Mathematics and Cybernetics, 2014, vol. 38, no. 2, pp. 64–68. https://doi.org/10.3103/S0278641914020083
8. Selezneva S. N. Order on the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts. Moscow University Computational Mathematics and Cybernetics, 2016, vol. 40, no. 3, pp. 123–127. https://doi.org/10.3103/S0278641916030043
9. Suprun V. P. Complexity of Boolean functions in a class of canonical polarized polynomials. Discrete Math. Appl., 1994, vol. 4, no. 3, pp. 273–277.
10. Ugryumov E. P. Tsifrovaya shemotehnika [Digital Circuitry]. Saint-Petersburg, BHV-Petersburg Publ., 2004. 528 p.
11. Vinokurov S. F., Kazimirov A. S. On the complexity of one class of Boolean functions. The Bulletin of Irkutsk State University. Series Mathematics, 2010, vol. 4, pp. 2–6. (in Russian)
12. Yablonski S. V. Vvedeniye v diskretnuyu matematiku [Introduction in Discrete Mathematics]. Moscow, Higher School Publ., 2001. 384 p.