- Two-element Boolean algebra
In

mathematics andabstract algebra , the**two-element Boolean algebra**is the Boolean algebra whose "underlying set" (oruniverse or "carrier") "B" is theBoolean domain . The elements of the Boolean domain are 1 and 0 by convention, so that "B"={0,1}.Paul Halmos 's name for this algebra,**2**, has some following in the literature and will be employed here.**Definition**"B" is a partially ordered set and the elements of "B" are also its bounds.

An operation of

arity "n" is a mapping from "B"^{n}to "B". Boolean algebra consists of twobinary operation s and unarycomplementation . The binary operations have been named and notated in various ways. Here they are called 'sum' and 'product', and notated by infix '+' and '.', respectively. Sum and product commute and associate, as in the usual algebra of real numbers. As for theorder of operations , brackets are decisive if present. Otherwise '.' precedes '+'. Hence "A.B + C" is parsed as "(A.B) + C" and not as "A.(B + C)". Complementation is denoted by writing an overbar over its argument. The numerical analog of the complement of "X" is 1-"X". In the language ofuniversal algebra , a Boolean algebra is a $langle\; B,+,.,overline\{..\},1,0\; angle$algebra of type $langle\; 2,2,1,0,0\; angle$.Either

one-to-one correspondence between {0,1} and {"True","False"} yields classicalbivalent logic in equational form, with complementation read as NOT. If 1 is read as "True", '+' is read as OR, and '.' as AND, and vice versa if 1 is read as "False".**ome basic identities****2**can be seen as grounded in the following trivial "Boolean" arithmetic:

* 1+1 = 1+0 = 0+1 = 1

* 0.0 = 0.1 = 1.0 = 0

* 1.1 = 1

* 0+0 = 0

* $overline\{1\}\; =\; 0$

* $overline\{0\}\; =\; 1$Note that:

* '+' and .' work exactly as in numerical arithmetic, except that 1+1=1.'+' and '.' are derived by analogy from numerical arithmetic; simply set any nonzero number to 1.

* Swapping 0 and 1, and '+' and '.' preserves truth; this is the essence of theduality pervading all Boolean algebras.This Boolean arithmetic suffices to verify any equation of**2**, including the axioms, by examining every possible assignment of 0s and 1s to each variable (seedecision procedure ).The following equations may now be verified:

* $A+A=A$

* $A.A=A$

* $A+0=A$

* $A+1=1$

* $A.0=0$

* $overline\{overline\{A=A$Each of '+' and '.' distributes over the other:

*$A.(B+C)\; =\; A.B\; +\; A.C;$

*$A+(B.C)\; =\; (A+B).(A+C).$That '.' distributes over '+' agrees withelementary algebra , but not '+' over '.'. For this and other reasons, a sum of products (leading to aNAND synthesis) is more commonly employed than a product of sums (leading to aNOR synthesis).Each of '+' and '.' can be defined in terms of the other and complementation:

* $A.B=overline\{overline\{A\}+overline\{B$

* $A+B=overline\{overline\{A\}.overline\{B$We only need one binary operation, andconcatenation suffices to denote it. Hence concatenation and overbar suffice to notate**2**. This notation is also that of Quine'sBoolean term schemata . Letting ("X") denote the complement of "X" and "()" denote either 0 or 1 yields thesyntax of the primary algebra.A "basis" for

**2**is a set of equations, calledaxiom s, from which all of the above equations (and more) can be derived. There are many known bases for all Boolean algebras and hence for**2**. An elegant basis notated using only concatenation and overbar is:

# $AB.C\; =\; BC.A$ (This axiom only serves to prove that concatenation commutes, associates)

# $Aoverline\{AB\}\; =\; Aoverline\{B\}$ (**2**is adistributive lattice )

# $overline\{A\}A\; =\; 1$ (the lattice**2**is complemented, with an upper bound of 1)

#$A0\; =\; A$ (0 is the lower bound)This basis makes for an easy approach to proof, called calculation, that proceeds by simplifying expressions to 0 or 1, by invoking axioms (2)-(4), $AA=A,$ and$overline\{overline\{A=A.$**A bit of metatheory**De Morgan's theorem states that if one does the following, in the given order, to anyBoolean function :

* Complement every variable;

* Swap + and . operators (taking care to add brackets to ensure the order of operations remains the same);

* Complement the result,the result is logically equivalent to what you started with. Repeated application of De Morgan's theorem to parts of a function can be used to drive all complements down to the individual variables.A powerful and nontrivial

metatheorem states that any theorem of**2**holds for all Boolean algebras. This theorem is useful because any equation in**2**can be verified by adecision procedure . Logicians refer to this fact as "**2**is decidable". All knowndecision procedure s require a number of steps that is anexponential function of the number of variables "N" appearing in the equation to be verified. Whether there exists a decision procedure whose steps are apolynomial function of "N" falls under theP=NP conjecture.**ee also*** (Simple English Wikipedia)

*Boolean algebra (introduction)

*Boolean algebra (logic)

*Boolean algebra (structure)

*Boolean domain

*Bounded set

*Lattice (order theory)

*Order theory **References**Many elementary texts on Boolean algebra were published in the early years of the computer era. Perhaps the best of the lot, and one still in print, is:

* Mendelson, Elliot, 1970. "Schaum's Outline of Boolean Algebra". McGraw-Hill.The following items reveal how the two-element Boolean algebra is mathematically nontrivial.

*Stanford Encyclopedia of Philosophy : " [*http://plato.stanford.edu/entries/boolalg-math/ The Mathematics of Boolean Algebra,*] " by J. Donald Monk.

* Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. " [*http://www.thoralf.uwaterloo.ca/htdocs/ualg.html A Course in Universal Algebra.*] " Springer-Verlag. ISBN 3-540-90578-2.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Boolean algebra (introduction)**— Boolean algebra, developed in 1854 by George Boole in his book An Investigation of the Laws of Thought , is a variant of ordinary algebra as taught in high school. Boolean algebra differs from ordinary algebra in three ways: in the values that… … Wikipedia**Boolean algebra**— This article discusses the subject referred to as Boolean algebra. For the mathematical objects, see Boolean algebra (structure). Boolean algebra, as developed in 1854 by George Boole in his book An Investigation of the Laws of Thought,[1] is a… … Wikipedia**Boolean algebra (structure)**— For an introduction to the subject, see Boolean algebra#Boolean algebras. For the elementary syntax and axiomatics of the subject, see Boolean algebra (logic). For an alternative presentation, see Boolean algebras canonically defined. In abstract … Wikipedia**Boolean algebra (logic)**— For other uses, see Boolean algebra (disambiguation). Boolean algebra (or Boolean logic) is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of… … Wikipedia**Boolean algebra**— /booh lee euhn/ 1. Logic. a deductive logical system, usually applied to classes, in which, under the operations of intersection and symmetric difference, classes are treated as algebraic quantities. 2. Math. a ring with a multiplicative identity … Universalium**Boolean algebra**— noun a system of symbolic logic devised by George Boole; used in computers • Syn: ↑Boolean logic • Hypernyms: ↑symbolic logic, ↑mathematical logic, ↑formal logic * * * noun Usage: usually capitalized B … Useful english dictionary**Boolean algebra**— noun Date: circa 1889 an algebraic system that consists of a set closed under two binary operations and that can be described by any of various systems of postulates all of which can be deduced from the postulates that each operation is… … New Collegiate Dictionary**Boolean algebra**— /ˌbuliən ˈældʒəbrə/ (say .boohleeuhn aljuhbruh) noun a mathematical system of representing statements in logic using operators such as and , or and not , in which each element or variable has one of only two possible values, as true or false ;… … Australian English dictionary**Canonical form (Boolean algebra)**— In Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. Minterms are called products because they are the logical AND of a set of variables, and maxterms are called sums… … Wikipedia**List of Boolean algebra topics**— This is a list of topics around Boolean algebra and propositional logic. Contents 1 Articles with a wide scope and introductions 2 Boolean functions and connectives 3 Examples of Boolean algebras … Wikipedia