Two-element Boolean algebra

The simplest Boolean algebra, one having just two elements, named 1 and 0 by convention. Interpreting 1 as True and 0 as False yields classical bivalent logic in equational form. An infix "+" is the usual notation for OR. An infix "." (or concatenation) denotes AND. These operators are derived by analogy from addition and multiplication of numbers. To see this, equate any nonzero number to 1. By convention, A.B+C is interpreted as (A.B)+C not A.(B+C). This too parallels addition and multiplication in (real valued) algebra. Boolean complementation, read as NOT, is generally represented by an overbar.

Paul Halmos's minimalist name for this algebra, 2 , appears to have some following. For an elegant alternative notation for 2, see Laws of Form.

Basic identities

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

1+0 = 0+1 = 1. 0+0 = 0. As in numerical arithmetic.
1+1 = 1.
${\overline {1}}=0.{\overline {0}}=1.$

This arithmetic suffices to verify any axiom set (basis) for 2, including the following little-known one, by examining every possible assignment of 0s and 1s to each variable:

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

This arithmetic also suffices to verify the following basic identities:

$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}}}}$

The + and . operators are distributive, that is A.(B+C) = A.B + B.B and A+B.C = (A+B).(A+C). That product distributes over sum conforms to standard algebra, but not sum over product. Consequently people tend to find the first more comfortable to do than the second. For this and other reasons a sum of products (which leads to an easy NAND synthesis) is more commonly used than a product of sums (which leads to an easy NOR synthesis).

Other

De Morgan's theorem states that if you do the following in 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);
then 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.