The Zhegalkin Polynomial of Multiseat Sole Sufficient Operator

Abstract

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