CS61C

Boolean Algebra

Learning Outcomes

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

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?

Boolean Algebra Operations

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).

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.¹

Why 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.

Example

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.

Cascade of an AND on b and a into an OR with a, and then an OR with c to output y, equivalent to y equals a OR c after simplification.

Equivalent single two-input OR gate with inputs a and c and output y.

We will revisit this example.

Laws 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.

#tab-boolean-laws lists the most important of the common Boolean laws.

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.

Proofs

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.

::::::{note} Law of 0’s, Law of 1’s :class: dropdown

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

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

::::::{note} Idempotence :class: dropdown

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

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

::::::{note} DeMorgan’s Laws :class: dropdown

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

$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

$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

Example, 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}

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