Boolean Algebra - CS 61C Course Notes

1Learning Outcomes¶

Identify the AND, OR, and NOT operations in Boolean Algebra.
Simplify Boolean Algebra expressions using laws of Boolean Algebra.

🎥 Lecture Video

In the previous section we explained how to generate a truth-table from a given circuit (we simply need to evaluate it for input combinations). The big question is: How do we go the other way? How do we derive a circuit of logic gates from a truth-table?

History: George Boole and Claude Shannon

In the 19th Century, the mathematician George Boole (1815-1864), developed a mathematical system (algebra) involving logic, later becoming known as Boolean algebra. His variables took on the values of TRUE and FALSE. Later, Claude Shannon (the father of information theory, 1916–2001) wrote his Master’s thesis on how to map Boolean algebra to digital circuits.

2Boolean Algebra Operations¶

Table 1:Boolean algebra basic operations: AND, OR, and NOT. See the logic gate section for truth tables.

Operation	Boolean Algebra Notation	Notes
AND(a, b)	$a \cdot b$ , $ab$	Basic operation. The $\cdot$ is often dropped, as in the second notation.
OR(a, b)	$a + b$	Basic operation.
NOT(a)	$\overline{a}$	Basic operation.

We can also define operations for NAND, NOR, and XOR (though these are not considered basic operations).

Table 2:Boolean algebra NAND, NOR, XOR.

Operation	Boolean Algebra Notation	Notes
NAND(a, b)	$\overline{a \cdot b}$ $\overline{ab}$	“Not AND”
NOR(a, b)	$\overline{a + b}$	“Not OR”
XOR(a, b)	$a \oplus b$	Not a basic operation, but common enough to have its own symbol.^[1]

3Why use Boolean Algebra¶

The value of Boolean algebra for circuit design comes from the fact that Boolean expressions can be manipulated mathematically. In general, it is much easier to manipulate equations than it is to directly manipulate circuits.

Simplify Circuits. A Boolean algebra expression can be simplified. This simplification will lead directly to a circuit simplification. Using fewer gates means using fewer transistors—cheaper and more energy-efficient!
Verify circuits. Another use for Boolean algebra is in circuit verification. Given a circuit and a Boolean equation, we can ask the question, “Do the two different representations represent the same function?” The first step would be to derive a new Boolean expression based on the circuit. Then through algebraic manipulation we could manipulate the expressions until they match, thereby “proving” the eqivalence of the two.

3.1Example¶

We can use Boolean algebra to verify the below simplification. The first circuit ( $y = ab + a + c$ ), which uses three gates, is equivalent to the second circuit ( $y = a + c$ ), which uses just one OR gate. We describe this approach at the end of this section.

"TODO" — Figure 1:First circuit: $y = ab + a + c$ .

We will revisit this example.

4Laws of Boolean Algebra¶

Along with Boolean algebra comes a collection of laws that apply to Boolean expressions. These are simple algebraic equalities that are known to be true. We can manipulate other Boolean expressions through successive application of these laws.

Table 3 lists the most important of the common Boolean laws.

Table 3:Laws of Boolean Algebra.

AND Form	OR Form
$x \cdot y = y \cdot x$	$x + y = y + x$	Commutativity
$(xy)z = x(yz)$	$(x + y) + z = x + (y + z)$	Associativity
$x \cdot 1 = x$	$x + 0 = x$	Identity
$x \cdot 0 = 0$	$x + 1 = 1$	Laws of 0’s and 1’s
$xy + x = x$	$(x + y)x = x$	Uniting Theorem
$x(y + z) = xy + xz$	$x + yz = (x + y)(x + z)$	Distributivity
$x \cdot x = x$	$x + x = x$	Idempotence
$x \cdot \overline{x} = 0$	$x + \overline{x} = 1$	Inverse (Complement)
$\overline{xy} = \overline{x} + \overline{y}$	$\overline{x + y} = \overline{x} \cdot \overline{y}$	DeMorgan’s Laws

Some laws are similar to ordinary (non-Boolean) algebra, but many are specific to Boolean algebra and rely on variables taking on precisely two truth values: 1 (true) and 0(false).

Because of the symmetry of Boolean algebra all these laws come in two versions (the two columns above), one being called the dual version of the other. Practically speaking, this means you only need to remember one version of the law, and the other one can be naturally derived.

4.1Proofs¶

Analyze the proofs below, which fall into two categories:

Exhaustive proof, i.e., making truth tables (where again, truth tables enumerate the input/output relationship for all possible input values) then identifying the columns that represent the left-hand and/or right-hand sides of the equation.
Algebraic manipulation by using other laws.

Law of 0’s, Law of 1’s

$x \cdot 0 = 0$

$x$	$x \cdot 0$
0	0
1	0

$x + 1 = 1$

$x$	$x + 1$
0	1
1	1

Distributivity

$x(y + z) = xy + xz$

Coming soon...

$x + yz = (x + y)(x + z)$

\begin{aligned} (x + y)(x + z) &= x \cdot x + xz + xy + yz && \text{Distributivity} \\ &= x + xy + xz + yz && \text{Idempotence (AND)} \\ &= x + x(y + z) + yz && \text{Distributivity (Prop. 1)} \\ &= x + yz && \text{Uniting Theorem (AND)} \end{aligned}

Idempotence

$x \cdot x = x$

$x$	$x \cdot x$
0	0
1	1

$x + x = x$

$x$	$x + x$
0	0
1	1

DeMorgan’s Laws

At a high-level: “distribute” the inversion (e.g., dual) over x, y and operator.

$\overline{xy} = \overline{x} + \overline{y}$

$x$	$y$	$xy$	$\overline{xy}$	$\overline{x}$	$\overline{y}$	$\overline{x} + \overline{y}$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

$\overline{x + y} = \overline{x} \cdot \overline{y}$

$x$	$y$	$x + y$	$\overline{x + y}$	$\overline{x}$	$\overline{y}$	$\overline{x} \cdot \overline{y}$
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

4.2Example, revisited¶

Let us return to the example described above and prove that the first circuit is equivalent to the second circuit.

\begin{aligned} y &= ab + a + c && \text{Equation derived from original circuit} \\ &= a(b + 1) + c && \text{Distributivity} \\ &= a(1) + c && \text{Law of 1's} \\ &= a + c && \text{Identity (AND)} \end{aligned}

Footnotes¶

$a \oplus b = (a + b)\overline{ab} = a\overline{b}+\overline{a}b$
↩