Two-element Boolean algebra


In mathematics and abstract algebra, the two-element Boolean algebra is the Boolean algebra whose underlying set B is the Boolean domain. The elements of the Boolean domain are 1 and 0 by convention, so that B = . 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 Bn to B. Boolean algebra consists of two binary operations and unary complementation. 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 the order of operations, brackets are decisive if present. Otherwise '∙' precedes '+'. Hence A∙B + C is parsed as + C and not as A∙. Complementation is denoted by writing an overbar over its argument. The numerical analog of the complement of X is 1 − X. In the language of universal algebra, a Boolean algebra is a algebra of type.
Either one-to-one correspondence between and yields classical bivalent 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. These two operations define a commutative semiring, known as the Boolean semiring.

Some basic identities

2 can be seen as grounded in the following trivial "Boolean" arithmetic:
Note that:
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.
The following equations may now be verified:
Each of '+' and '∙' distributes over the other:
That '∙' distributes over '+' agrees with elementary algebra, but not '+' over '∙'. For this and other reasons, a sum of products is more commonly employed than a product of sums.
Each of '+' and '∙' can be defined in terms of the other and complementation:
We only need one binary operation, and concatenation suffices to denote it. Hence concatenation and overbar suffice to notate 2. This notation is also that of Quine's Boolean term schemata. Letting denote the complement of X and "" denote either 0 or 1 yields the syntax of the primary algebra of G. Spencer-Brown's Laws of Form.
A basis for 2 is a set of equations, called axioms, from which all of the above equations 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:
  3. .
Where concatenation = OR, 1 = true, and 0 = false, or concatenation = AND, 1 = false, and 0 = true.
If 0=1, - are the axioms for an abelian group.
only serves to prove that concatenation commutes and associates. First assume that associates from either the left or the right, then prove commutativity. Then prove association from the other direction. Associativity is simply association from the left and right combined.
This basis makes for an easy approach to proof, called "calculation" in Laws of Form, that proceeds by simplifying expressions to 0 or 1, by invoking axioms -, and the elementary identities, and the distributive law.

Metatheory

states that if one does the following, in the given order, to any Boolean function:
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. Conversely, an identity that holds for an arbitrary nontrivial Boolean algebra also holds in 2. Hence all the mathematical content of Boolean algebra is captured by 2. This theorem is useful because any equation in 2 can be verified by a decision procedure. Logicians refer to this fact as "2 is decidable". All known decision procedures require a number of steps that is an exponential function of the number of variables N appearing in the equation to be verified. Whether there exists a decision procedure whose steps are a polynomial function of N falls under the P = NP conjecture.