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.
Read more about this topic: Zhegalkin Polynomial
Famous quotes containing the word equivalent:
“Every notable advance in technique or organization has to be paid for, and in most cases the debit is more or less equivalent to the credit. Except of course when its more than equivalent, as it has been with universal education, for example, or wireless, or these damned aeroplanes. In which case, of course, your progress is a step backwards and downwards.”
—Aldous Huxley (18941963)