Boolean Algebra

In 1854 George Boole introduced a systematic treatment of logic and developed for this purpose a systematic system now called boolean algebra. In 1938 C. E. Shannon introduced a two-valued Boolean algebra called switching algebra, in which he demonstrated that the properties of bistable electrical switching circuits can be represented by this algebra. in 1904 E. V. Huntington introduced a set of formal postulates defining boolean algebra.

Boolean algebra is an algebraic system defined on a set of elements B together with two binary operators + and ·.

  1. Closure with respect to the operators + and ·.

  2. Identity elements
    1. 0 is an identity element with respect to +:     x + 0 = x.
    2. 1 is an identity element with respect to ·:     x·1 = x

  3. Commutative with respect to the operators + and ·.

  4. Distributative with respect to both + and ·.
    1. · is distributive over +:     x·(y+z) = x·y + x·z
    2. + is distributive over ·:     x+(y·z) = x+y · x+z

  5. For every element x in B, there exists an element x' in B (called the complement of x) such that (a) x+x' = 1 and (b) x·x' = 0.

  6. There exists at least two elements x and y in B such that x ¹ y.
Postulate 2 x + 0 = x x · 1 = x
Postulate 5 x + x' = 1 x · x' = 0
Theorem 1 x + x = x x · x = x
Theorem 2 x + 1 = 1 x · 0 = 0
Theorem 3, involution (x')' = x
Postulate 3, commutative x + y = y + x x · y = y · x
Theorem 4, associative x + (y + z) = (x + y) + z x · (y · z) = (x· y) · z
Postulate 4, distributive x · (y + z) = x · y + x · z x+(y · z) = x + y · x + z
Theorem 5, DeMorgan (x + y)' = x'·y' (x·y)' = x' + y'
Theorem 6, absorption x + (x · y) = x x · (x + y) = x

Duality

The duality principle states that a valid algebraic expression in boolean algebra remains valid if the operators and identity elements are interchanged. The rightmost two columns in the table above are duals.

Maintained by John Loomis, last updated 11 Sept 1999