Geodesic
The zhegalkin polynomial of multiseat sole sufficient operator
Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 2, pp. 106-127.

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

Among functionally complete sets of Boolean functions, sole sufficient operators are of particular interest. They have a wide range of applicability and are not limited to the two-seat case. In this paper, the conditions, imposed on the Zhegalkin polynomial coefficients, are formulated. The conditions are necessary and sufficient for the polynomial to correspond to a sole sufficient operator. The polynomial representation of constant-preserving Boolean functions is considered. It is shown that the properties of monotone and linearity do not require special consideration in describing a sole sufficient operator. The concept of a dual remainder polynomial is introduced. The value of it allows one to determine the self-duality of a Boolean function. It is proved that the preserving 0 and 1 or preserving neither 0 nor 1 Boolean function is self-dual if and only if the dual remainder of its corresponding Zhegalkin polynomial is equal to 0 for any sets of function variable values. Based on this fact, a system of leading coefficients is obtained. The solution of the system made it possible to formulate the criterion for the self-duality of the Boolean function represented by the Zhegalkin polynomial. It imposes necessary and sufficient conditions on the polynomial coefficients. Thus, it is shown that Zhegalkin polynomials are a rather convenient tool for studying precomplete classes of Boolean functions.
Keywords: Zhegalkin polynomial, sole sufficient operator, Sheffer function, precomplete classes, constant-preserving Boolean functions, self-dual Boolean functions, dual remainder polynomial, leading coefficient. 
@article{MAIS_2023_30_2_a0,
     author = {L. Yu. Bystrov and E. V. Kuzmin},
     title = {The zhegalkin polynomial of multiseat sole sufficient operator},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {106--127},
     publisher = {mathdoc},
     volume = {30},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2023_30_2_a0/}
}
TY  - JOUR
AU  - L. Yu. Bystrov
AU  - E. V. Kuzmin
TI  - The zhegalkin polynomial of multiseat sole sufficient operator
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2023
SP  - 106
EP  - 127
VL  - 30
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2023_30_2_a0/
LA  - ru
ID  - MAIS_2023_30_2_a0
ER  - 
%0 Journal Article
%A L. Yu. Bystrov
%A E. V. Kuzmin
%T The zhegalkin polynomial of multiseat sole sufficient operator
%J Modelirovanie i analiz informacionnyh sistem
%D 2023
%P 106-127
%V 30
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2023_30_2_a0/
%G ru
%F MAIS_2023_30_2_a0
L. Yu. Bystrov; E. V. Kuzmin. The zhegalkin polynomial of multiseat sole sufficient operator. Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 2, pp. 106-127. http://geodesic.mathdoc.fr/item/MAIS_2023_30_2_a0/

[1] S. V. Yablonskiy, Introduction into discrete mathematics, 5th ed., HSE, 2008 | MR

[2] N. M. Martin, Systems of Logic, Cambridge University Press, 1989 | MR | Zbl

[3] R. L. Graham, “On n-Valued Functionally Complete Truth Functions”, The Journal of Symbolic Logic, 32:2 (1967), 190–195 | DOI | MR | Zbl

[4] T. C. Wesselkamper, “A sole sufficient operator”, NDJFAM, 16:1 (1975), 86–88 | MR | Zbl

[5] S. N. Selezneva, “O slozhnosti raspoznavaniya polnoty mnozhestv bulevyh funkcij, realizovannyh polinomami Zhegalkina”, DMA, 9:4 (1997), 24–31 | Zbl

[6] S. S. Marchenkov, Zamknutye klassy bulevyh funkcij, Fizmatlit, 2000

[7] V. P. Barashev and S. A. Unuchek, Diskretnaya matematika, RTU MIREA, 2012

[8] G. P. Gavrilov and A. A. Sapozhenko, Zadachi i uprazhneniya po diskretnoj matematike, Fizmatlit, 2005 | MR

[9] N. V. Nikonov, “O svyazyah i otlichiyah poluzapretov I, II-go roda i zapretov K-znachnyh funkcij”, Forestry bulletin, 2006, no. 1, 124–133

[10] S. S. Marchenkov, Osnovy teorii bulevyh funkcij, Fizmatlit, 2014

[11] L. Y. Bystrov and V. S. Rublev, “Bulevy funkcii, ne prinadlezhashchie predpolnym klassam”, Zametki po informatike i matematike, 13, P.G. Demidov Yaroslavl State University, Yaroslavl, 2021, 22–26

[12] A. I. Kostrikin, Vvedenie v algebpu, v. 1, Osnovy algebpy, Fizmatlit, 2000