| Boolean Algebra (structure) |
Article Index for Boolean Algebra |
Shopping Boolean |
Website Links For Algebra |
Information AboutBoolean Algebra (structure) |
|
In Abstract Algebra , a Boolean algebra is an Algebraic Structure (a collection of elements and operations on them obeying defining Axioms ) that captures essential properties of both Set operations and Logic operations. Specifically, it deals with the Set operations of Intersection , Union , Complement ; and the Logic operations of AND , OR , NOT . For example, the logical assertion that a Statement ''a'' and its negation ¬''a'' cannot both be true, : parallels the set-theory assertion that a subset ''A'' and its complement ''A''''C'' have empty intersection, : Because truth values can be represented as Binary Numbers or as voltage levels in Logic Circuit s, the parallel extends to these as well. Thus the theory of Boolean algebras has many practical applications in Electrical Engineering and Computer Science , as well as in Mathematical Logic . A Boolean algebra is also called a Boolean lattice. The connection to Lattice s (special Partially Ordered Set s) is suggested by the parallel between set Inclusion , ''A'' ⊆ ''B'', and Ordering , ''a'' ≤ ''b''. Consider the lattice of all subsets of {''x'',''y'',''z''}, ordered by set inclusion. This Boolean lattice is a partially ordered set in which, say, {''x''} ≤ {''x'',''y''}. Any two lattice elements, say ''p'' = {''x'',''y''} and ''q'' = {''y'',''z''}, have a least upper bound, here {''x'',''y'',''z''}, and a greatest lower bound, here {''y''}. Suggestively, the least upper bound (or join or supremum) is denoted by the same symbol as logical OR, ''p''∨''q''; and the greatest lower bound (or meet or infimum) is denoted by same symbol as logical AND, ''p''''q''. The lattice interpretation helps in generalizing to Heyting Algebra s, which are Boolean algebras freed from the restriction that either a statement or its negation must be true. Heyting algebras correspond to Intuitionist (constructivist) Logic just as Boolean algebras correspond to Classical Logic . __TOC__ FORMAL DEFINITION A Boolean algebra is a Set ''A'', supplied with two Binary Operation s (called AND), (called OR), a Unary Operation (called NOT) and two elements 0 (called zero) and 1 (called one)Some authors require 0 and 1 to be ''distinct'' elements of the Boolean algebra; others do not. If 0 and 1 are not required to be distinct, then the structure {0}, in which all operations evaluate to 0, is a Boolean algebra, called the ''degenerate Boolean algebra''., such that, for all elements ''a'', ''b'' and ''c'' of set ''A'', the following Axioms hold: The first three pairs of axioms above: associativity, commutativity and absorption, mean that (''A'', , ) is a Lattice . If ''A'' is a lattice and one of the above distributivity laws holds, then the second distributivity law can be proven. Thus, a Boolean algebra can also be equivalently defined as a Distributive Complemented Lattice . From these Axioms , one can show that the smallest element 0, the largest element 1, and the complement ¬''a'' of any element ''a'' are uniquely determined. For all ''a'' and ''b'' in ''A'', the following Identities also follow: EXAMPLES
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||