Summary

1And in Conclusion $\dots$ ¶

Our goal this lecture was to build combinational logic blocks. We can summarize this approach with the following diagram:

"Diagram with three bubbles describing three representations of combinational logic: Truth Table, Boolean Expression, and Gate Diagram. The representations are connected with curved arrows showing conversions between them." — Figure 1 in previous section.

We discussed how to convert among these three representations, as represented by the arcs in the diagram. Here is a summary:

Truth table to Boolean Expression. Write the canonical form (Sum-of-Products) and follow with algebraic simplification if desired.
Boolean Expression to Truth table. Evaluate expression for all input combinations and record output values.
Boolean Expression to Gates. Use AND gates for the AND operators, OR gates for the OR operators, and inverters for the NOT operator. Wire up the gates the match the structure of the expression.
Gates to Boolean Expression. Reverse the above process.
Gates to Truth table. Pass through all input combination and evaluate output.
Truth table to Gates. Map to Boolean expression then to gates.

In digital electronics, it is often important to get certain outputs based on your inputs, as laid out by a truth table. Truth tables map directly to Boolean expressions, and Boolean expressions map directly to logic gates. However, in order to minimize the number of logic gates needed to implement a circuit, it is often useful to simplify long Boolean expressions.

We can simplify expressions using the nine key 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

Laws of Boolean Algebra (reprint of Table 3 from this section).

Additionally, we have many boolean functions which take boolean signals (0 or 1) as input and output a boolean result (0 or 1). When designing digital systems, boolean functions are represented as logic gates. Common logic gates can be found in this section

There are two basic types of circuits: combinational logic circuits and state elements. Combinational logic circuits simply change based on their inputs after whatever propagation delay is associated with them. For example, if an AND gate (pictured below) has an associated propagation delay of 2ps, its output will change based on its input as follows:

"The left diagram depicts a two-input AND gate with inputs INPUT_A and INPUT_B and low output; the right diagram shows the associated timing waveforms for a, b, and output showing AND behavior with visible propagation delay after input edges."

You should notice that the output of this AND gate always changes 2ps after its inputs change. State elements, on the other hand, can remember their inputs even after the inputs change. State elements change value based on a clock signal. A rising edge-triggered register, for example, samples its input at the rising edge of the clock (when the clock signal goes from 0 to 1).

2Textbook Readings¶

P&H A.3-A.6

3Additional References¶

These notes would not be possible without Professor John Wawrzynek’s CS 61C handouts:

Boolean Handout

4Exercises¶

Check your knowledge!

4.1Conceptual Review¶

4.2Short Exercises¶

Solution to Exercise 6 #

NOT, AND, OR, XOR, NAND, NOR, XNOR

Here are the outputs for each boolean function combined into a single truth table. All possible combinations of the inputs ${x}$ and ${y}$ are shown on the left, and the output of the boolean function based on the current inputs is shown on the right

Input(s)	NOT	AND	OR	XOR	NAND	NOR	XNOR
${x}$ ${y}$	$\bar{x}$	${x}\cdot{y}$	${x}+{y}$	${x}\oplus{y}$	$\overline{{x}\cdot{y}}$	$\overline{{x}+{y}}$	$\overline{{x}\oplus{y}}$
0 0	1	0	0	0	1	1	1
0 1	1	0	1	1	1	0	0
1 0	0	0	1	1	1	0	0
1 1	0	1	1	0	0	0	1