Zhegalkin Polynomial

Zhegalkin Polynomial

Zhegalkin (also Zegalkin or Gegalkine) polynomials form one of many possible representations of the operations of boolean algebra. Introduced by the Russian mathematician I.I. Zhegalkin in 1927, they are the polynomials of ordinary high school algebra interpreted over the integers mod 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, x2 = x. Hence a polynomial such as 3x2y5z is congruent to, and can therefore be rewritten as, xyz.