1.1: The Boolean Bit

As we have seen, information can be communicated by sequences of 0 and 1 values. By using only 0 and 1, we can deal with data from many different types of sources, and not be concerned with what the data means. We are thereby using abstract, not specific, values. This approach lets us ignore many messy details associated with specific information processing and transmission systems.

Bits are simple, having only two possible values. The mathematics used to denote and manipulate single bits is not difficult. It is known as Boolean algebra, after the mathematician George Boole (1815–1864). In some ways Boolean algebra is similar to the algebra of integers or real numbers which is taught in high school, but in other ways it is different.

Algebra is a branch of mathematics that deals with variables that have certain possible values, and with functions which, when presented with one or more variables, return a result which again has certain possible values. In the case of Boolean algebra, the possible values are 0 and 1.

First consider Boolean functions of a single variable that return a single value. There are exactly four of them. One, called the identity, simply returns its argument. Another, called not (or negation, inversion, or complement) changes 0 into 1 and vice versa. The other two simply return either 0 or 1 regardless of the argument. Here is a table showing these four functions:

Table 1.1: Boolean functions of a single variable

\(x\)	\(f(x)\)
Argument	IDENTITY	NOT	ZERO	ONE
0	0	1	0	1
1	1	0	0	1

Note that Boolean algebra is simpler than algebra dealing with integers or real numbers, each of which has infinitely many functions of a single variable.

Next, consider Boolean functions with two input variables A and B and one output value C. How many are there? Each of the two arguments can take on either of two values, so there are four possible input patterns (00, 01, 10, and 11). Think of each Boolean function of two variables as a string of Boolean values 0 and 1 of length equal to the number of possible input patterns, i.e., 4. There are exactly 16 (24) different ways of composing such strings, and hence exactly 16 different Boolean functions of two variables. Of these 16, two simply ignore the input, four assign the output to be either A or B or their complement, and the other ten depend on both arguments. The most often used are \(AND\), \(OR\), \(XOR\) (exclusive or), \(NAND\) (not and), and \(NOR\) (not or), shown in Table 1.2. (In a similar way, because there are 8 possible input patterns for three-input Boolean functions, there are \(2^8\) or 256 different Boolean functions of three variables.)

Table 1.2: Five of the 16 possible Boolean functions of two variables

\(x\)	\(f(x)\)
Argument	AND	NAND	OR	NOR	XOR
00	0	1	0	1	0
01	0	1	1	0	1
10	0	1	1	0	1
11	1	0	1	0	0

It is tempting to think of the Boolean values 0 and 1 as the integers 0 and 1. Then \(AND\) would correspond to multiplication and \(OR\) to addition, sort of. However, familiar results from ordinary algebra simply do not hold for Boolean algebra, so such analogies are dangerous. It is important to distinguish the integers 0 and 1 from the Boolean values 0 and 1; they are not the same.

There is a standard notation used in Boolean algebra. (This notation is sometimes confusing, but other notations that are less confusing are awkward in practice.) The \(AND\) function is represented the same way as multiplication, by writing two Boolean values next to each other or with a dot in between: \(A\, AND\, B\) is written \(AB\) or \(A•B\). The \(OR\) function is written using the plus sign: \(A\, +\, B\) means \(A\, OR\, B\). Negation, or the \(NOT\) function, is denoted by a bar over the symbol or expression, so \(NOT\, A\) is \(\overline{A}\). Finally, the exclusive-or function \(XOR\) is represented by a circle with a plus sign inside, \(A\, ⊕\, B\).

\begin{equation} \nonumber
\begin{aligned}
&\begin{array}{rl}
N O T & \bar{A} \\
A N D & A \cdot B \\
N A N D & \overline{A \cdot B}
\end{array}\\
&\begin{array}{cc}
O R & A+B \\
N O R & \overline{A+B} \\
X O R & A ⊕ B \end{array}
\end{aligned}
\end{equation}

Table 1.3: Boolean logic symbols

There are other possible notations for Boolean algebra. The one used here is the most common. Sometimes \(AND\), \(OR\), and \(NOT\) are represented in the form \(AND(A, B)\), \(OR(A, B)\), and \(NOT(A)\). Sometimes infix notation is used where \(A\, ∧\, B\) denotes \(A\, ·\, B\), \(A\, ∨\, B\) denotes \(A\, +\, B\), and \(∼A\) denotes \(A\). Boolean algebra is also useful in mathematical logic, where the notation \(A\, ∧\, B\) for \(A\, ·\, B\), \(A\, ∨\, B\) for \(A\, +\, B\), and \(¬A\) for \(A\) is commonly used.

Several general properties of Boolean functions are useful. These can be proven by simply demonstrating that they hold for all possible input values. For example, a function is said to be reversible if, knowing the output, the input can be determined. Two of the four functions of a single variable are reversible in this sense (and in fact are self-inverse). Clearly none of the functions of two (or more) inputs can by themselves be reversible, since there are more input variables than output variables. However, some combinations of two or more such functions can be reversible if the resulting combination has the name number of outputs as inputs; for example it is easily demonstrated that the exclusive-or function \(A\, ⊕\, B\) is reversible when augmented by the function that returns the first argument—that is to say, more precisely, the function of two variables that has two outputs, one \(A\, ⊕\, B\) and the other \(A\), is reversible.

For functions of two variables, there are many properties to consider. For example, a function of two variables \(A\) and \(B\) is said to be commutative if its value is unchanged when \(A\) and \(B\) are interchanged, i.e., if \(f(A, B)\) = \(f(B, A)\). Thus the function \(AND\) is commutative because \(A\, ·\, B\) = \(B\, ·\, A\). Some of the other 15 functions are also commutative. Some other properties of Boolean functions are illustrated in the identities in Table 1.4.

\begin{array}{rrrr} \nonumber
\text { Idempotent: } & A \cdot A=A & \text { Absorption: } & A \cdot(A+B)=A \\
& A+A=A & & A+(A \cdot B)=A \\
\text { Complementary: } & A \cdot \overline{A}=0 & \text { Associative: } & A \cdot(B \cdot C)=(A \cdot B) \cdot C \\
& A+\overline{A}=1 & & A+(B+C)=(A+B)+C \\
& A \oplus A =0 & & A \oplus(B \oplus C)=(A \oplus B) \oplus C \\
& A \oplus \overline{A}=1 & & \\
\text { Minimum: } & A \cdot 1=A & \text { Unnamed Theorem: } & A \cdot(\overline{A}+B)=A \cdot B \\
& A \cdot 0=0 & & A+(\overline{A} \cdot B)=A+B \\
\text { Maximum: } & A+0 =A & \text { De Morgan: }& \overline{A} \cdot \overline{B}=\overline{A+B} \\
& A+1=1 & & \overline{A}+\overline{B} =\overline{A \cdot B} \\
\text { Commutative: } & A \cdot B=B \cdot A & \text { Distributive: } & A \cdot(B+C)=(A \cdot B)+(A \cdot C) \\
& A+B=B+A & & A+(B \cdot C)=(A+B) \cdot(A+C) \\
& A \oplus B=B \oplus A \\
& \overline{A \cdot B} =\overline{B \cdot A} \\
& \overline{A+B} = \overline{B+A} \end{array}

Table 1.4: Properties of Boolean Algebra. These formulas are valid for all values of \(A\), \(B\), and \(C\).

The Boolean bit has the property that it can be copied (and also that it can be discarded). In Boolean algebra copying is done by assigning a name to the bit and then using that name more than once. Because of this property the Boolean bit is not a good model for quantum-mechanical systems. A different model, the quantum bit, is described below.