Geodesic
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, Tome 33 (2020), pp. 96-105

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: Boolean function, Zhegalkin polynomial, EXOR Sum of Pseudo-Products, length, classification by the length.
Mots-clés : ESPP (pseudo-polynomial form, PSPF) 
@article{IIGUM_2020_33_a6,
     author = {S. N. Selezneva and A. A. Lobanov},
     title = {On length of {Boolean} functions of a small number of variables in the class of pseudo-polynomials},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {96--105},
     publisher = {mathdoc},
     volume = {33},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2020_33_a6/}
}
TY  - JOUR
AU  - S. N. Selezneva
AU  - A. A. Lobanov
TI  - On length of Boolean functions of a small number of variables in the class of pseudo-polynomials
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2020
SP  - 96
EP  - 105
VL  - 33
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2020_33_a6/
LA  - en
ID  - IIGUM_2020_33_a6
ER  - 
%0 Journal Article
%A S. N. Selezneva
%A A. A. Lobanov
%T On length of Boolean functions of a small number of variables in the class of pseudo-polynomials
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2020
%P 96-105
%V 33
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IIGUM_2020_33_a6/
%G en
%F IIGUM_2020_33_a6
S. N. Selezneva; A. A. Lobanov. 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, Tome 33 (2020), pp. 96-105. http://geodesic.mathdoc.fr/item/IIGUM_2020_33_a6/