Zhegalkin Polynomials

Prove equivalences (6)-(9).

Using the basic equivalences and identities (6)-(9), find equivalent reduced Zhegalkin polynomials and prove the equivalence of the following pairs of formulas:

Under a lexicographic ordering of the tuples of arguments, the values of the Boolean function $f\left(x_{1}, x_{2}, x_{3}\right)$ form the sequence (1001 0001). Write out explicitly the system of equations for finding the Zhegalkin polynomial by the method of undetermined coefficients, find its solution, and construct the Zhegalkin polynomial for $f$.

Find the Zhegalkin polynomials (by the method of undetermined coefficients and using the matrix $J$) for the following functions $f(x, y, z)$. We assume that the tuples of arguments of the functions are ordered lexicographically and their values are given by a sequence of 8 zeros and ones:

Find, using the method of undetermined coefficients, the Zhegalkin polynomials for the following functions:

Prove that for a Boolean function $f\left(x_{1}, x_{2}, \ldots , x_{n}\right)$ the Zhegalkin polynomial can be obtained by expanding the parentheses in the following formula and simplifying it:

Using the previous problem, find the Zhegalkin polynomials for the following functions. The values of the functions $f(x, y, z)$ and $g(x, y, z)$ are given by sequences of zeros and ones under a lexicographic ordering of the arguments:

Prove that a Zhegalkin polynomial is identically equal to zero if and only if all its coefficients $\alpha_{i}$ in the representation (10) are equal to zero.

The length of a Zhegalkin polynomial is the number of its terms. For example, the polynomial $p\left(x_{1}, x_{2}\right)=1 \oplus x_{1} \oplus x_{1} x_{2}$ has length three. Determine how many distinct Zhegalkin polynomials of $n$ variables and length $k$ there are that simultaneously vanish on the tuples $(0,0, \ldots , 0)$ and $(1,1, \ldots , 1)$, consisting of all zeros and all ones, respectively.

Let the reduced Zhegalkin polynomial $p\left(x_{1}, \ldots , x_{n}\right)$ take value 1 on exactly one tuple $(\sigma_{1}, \ldots , \sigma_{n})$. Find its length.

Find a Boolean function of $n$ variables for which the reduced Zhegalkin polynomial has the greatest length.

What happens to a Boolean function if in the Zhegalkin polynomial (10) all the coefficients are changed to their opposites?

Let the reduced Zhegalkin polynomial $p\left(x_{1}, \ldots , x_{n}\right)$ take value 1 on exactly two opposite tuples: $\left(\sigma_{1}, \ldots , \sigma_{n}\right)$ and $(\neg \sigma_{1}, \ldots , \neg \sigma_{n})$. Find its length.

Prove that the reduced Zhegalkin polynomial $p\left(x_{1}, \ldots , x_{n}\right)$ defines a function that is commutative in every pair of arguments if and only if for every $k=0, \ldots , n$ the polynomial either contains all possible terms with $k$ factors, or contains none of them.

Let the length of a Zhegalkin polynomial be defined as in problem 184 on the previous page. By induction on $n \geqslant 1$, prove that for every $k=0, \ldots , 2^{n}$ there exists a Zhegalkin polynomial $p\left(x_{1}, \ldots , x_{n}\right)$ of length no greater than $n$ that equals one on exactly $k$ tuples of arguments.

Let the Zhegalkin polynomial be given by the formula

Prove by induction on $n \geqslant 1$ that this polynomial equals one on exactly $\frac{1}{3}\left(2^{n+1}+(-1)^{n}\right)$ tuples of arguments.

Let a nonzero Zhegalkin polynomial with $n$ variables contain no terms with more than $k$ variables, $k \leqslant n$. Using induction on $n$, prove that the number of ones among the values of this polynomial is at least $2^{n-k}$.