Two-element Boolean algebra

From Wikipedia, the free encyclopedia

The two-element Boolean algebra is the simplest Boolean algebra, one having just two elements, named 1 and 0 by convention. Paul Halmos's name for this algebra, 2, has some following in the literature and will be employed here.

Associated with any Boolean algebra is a partially ordered set B called the carrier, such that the operations of the Boolean algebra are mappings from Bn to B. The carrier is bounded by its distinguished members 0 and 1. 2 is simply the Boolean algebra whose carrier is identical to the set of its bounds, so that B={0,1}.

There are several names and notations for the two binary operations of Boolean algebra. Here they are called 'sum' and 'product', notated by infix '+' and '.', respectively. Product is often denoted by simply concatenating the operands. Sum and product commute and associate, as in the usual algebra of real numbers. As for order of operations, '.' precedes '+', but brackets may override. Hence A.B + C is parsed as (A.B) + C not A.(B + C).

The unary operation is always referred to as 'complementation', notated herein by placing an overbar over its argument. The numerical analog of the complement of x is 1-x. In the language of universal algebra, all Boolean algebras are then $\langle B,+,.,\overline{..},1,0\rangle$ algebras of type $\langle 2,2,1,0,0\rangle$ .

Interpreting one of 0 and 1 as True and the other as False yields classical bivalent logic in equational form. In this case, '+' is read as OR, '.' as AND, and complementation as NOT.

[edit] Some basic identities

2 can be seen as grounded in the following trivial "Boolean" arithmetic:

1+1 = 1+0 = 0+1 = 1
0+0 = 0
0.0 = 0.1 = 1.0 = 0
1.1 = 1
$\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 the duality pervading all Boolean algebras.

This Boolean arithmetic suffices to verify any equation of 2, including any axiom, by examining every possible assignment of 0s and 1s to each variable (see decision procedure).

A little known but powerful axiom set (basis) for 2 is:

A.B.C = B.C.A.
$\overline{A}.A=0$
$A.\overline{A.B}=A.\overline{B}$

This basis, plus the identity A.0=0 below, make for an easy approach to proof, called calculation in the entry laws of form.

The following equations may now be verified:

$A . A = A$
$A + A = A$
$A + 0 = A$
$A + 1 = 1$
$A .0 = 0$
$A .1 = A$
$\overline{\overline{A}}=A$
$A.B=\overline{\overline{A}+\overline{B}}$
$A+B=\overline{\overline{A}.\overline{B}}$

Each of '+' and '.' distributes over the other. That is, A.(B+C) = A.B + A.C and A+B.C = (A+B).(A+C). That '.' distributes over '+' is in accord with real-valued algebra, but not '+' over '.'. For this and other reasons, a sum of products (which leads to a NAND synthesis) is more commonly employed than a product of sums (which leads to a NOR synthesis).

Note that each of '+' and '.' can be defined in terms of the other and complementation. Moreover, concatenation suffices for product. Hence concatenation and overbar suffice to notate 2 and Quine's Boolean term schemata. Letting (X) denote the complement of X and "()" denote either 0 or 1 yields the primary algebra, described in laws of form.

[edit] A bit of metatheory

De Morgan's theorem states that if you do the following, in the given order, to any Boolean 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 a decision procedure. Logicians refer to this fact as "2 is decidable". In practice, the number of steps required to verify an equation via a decision procedure increases exponentially along with the number of its variables.

[edit] 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: