Zhegalkin Polynomial - Boolean Equivalent

Boolean Equivalent

Prior to 1927 boolean algebra had been considered a calculus of logical values with logical operations of conjunction, disjunction, negation, etc. Zhegalkin showed that all boolean operations could be written as ordinary numeric polynomials, thinking of the logical constants 0 and 1 as integers mod 2. The logical operation of conjunction is realized as the arithmetic operation of multiplication xy, and logical exclusive-or as arithmetic addition mod 2, (written here as x⊕y to avoid confusion with the common use of + as a synonym for inclusive-or ∨). Logical complement ¬x is then derived from 1 and ⊕ as x⊕1. Since ∧ and ¬ form a sufficient basis for the whole of boolean algebra, meaning that all other logical operations are obtainable as composites of these basic operations, it follows that the polynomials of ordinary algebra can represent all boolean operations, allowing boolean reasoning to be performed reliably by appealing to the familiar laws of high school algebra without the distraction of the differences from high school algebra that arise with disjunction in place of addition mod 2.

An example application is the representation of the boolean 2-out-of-3 threshold or median operation as the Zhegalkin polynomial xy⊕yz⊕zx, which is 1 when at least two of the variables are 1 and 0 otherwise.