The Zhegalkin Polynomial of Multiseat Sole Sufficient Operator

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.

1. S. V. Yablonskiy, Introduction into discrete mathematics, 5th ed. HSE, 2008.

2. N. M. Martin, Systems of Logic. Cambridge University Press, 1989.

3. R. L. Graham, “On n-Valued Functionally Complete Truth Functions,” The Journal of Symbolic Logic, vol. 32, no. 2, pp. 190–195, 1967.

4. T. C. Wesselkamper, “A sole sufficient operator,” NDJFAM, vol. 16, no. 1, pp. 86–88, 1975.

5. S. N. Selezneva, “O slozhnosti raspoznavaniya polnoty mnozhestv bulevyh funkcij, realizovannyh polinomami Zhegalkina,” DMA, vol. 9, no. 4, pp. 24–31, 1997.

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.

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

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

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

12. A. I. Kostrikin, Vvedenie v algebpu. Chast' 1. Osnovy algebpy. Fizmatlit, 2000.