page_title: Zhegalkin polynomial
section_title: The summation method
hierarchical_section_title: Zhegalkin polynomial / Method of computation / The summation method
caption_attribution_description: Русский: Графическое представление коэффициентов полинома Жегалкина для функций с разным числом переменных
context_page_description: Zhegalkin polynomials form one of many possible representations of the operations of Boolean algebra. Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927, they are the polynomial ring over the integers modulo 2. The resulting degeneracies of modular arithmetic result in Zhegalkin polynomials being simpler than ordinary polynomials, requiring neither coefficients nor exponents. Coefficients are redundant because 1 is the only nonzero coefficient. Exponents are redundant because in arithmetic mod 2, x² = x. Hence a polynomial such as 3x²y⁵z is congruent to, and can therefore be rewritten as, xyz.
context_section_description: According to the truth table, it is easy to calculate the individual coefficients of the Zhegalkin polynomial. To do this, sum up modulo 2 the values of the function in those rows of the truth table where variables that are not in the conjunction (that corresponds to the coefficient being calculated) take zero values.
  Suppose, for example, that we need to find the coefficient of the xz conjunction for the function of three variables . There is no variable y in this conjunction. Find the input sets in which the variable y takes a zero value. These are the sets 0, 1, 4, 5 (000, 001, 100, 101). Then the coefficient at conjunction xz is
  Since there are no variables with the constant term,
  .
  For a term which includes all variables, the sum includes all values of the function:
  Let us graphically represent the coefficients of the Zhegalkin polynomial as sums modulo 2 of values of functions at certain points. To do this, we construct a square table, where each column represents the value of the function at one of the points, and the row is the coefficient of the Zhegalkin polynomial. The point at the intersection of some column and row means that the value of the function at this point is included in the sum for the given coefficient of the polynomial (see figure). We call this table , where N is the number of variables of the function. 
  There is a pattern that allows you to get a table for a function of N variables, having a table for a function of  variables. The new table  is arranged as a 2 × 2 matrix of  tables, and the right upper block of the matrix is cleared.
caption: Graphic representation of the coefficients of the Zhegalkin polynomial for functions with different numbers of variables.
exif: {}