Example: Interpretation of a Digital Circuit

Here is a sample problem, taken from the textbook The Essentials of Computer Organization and Architecture by Linda Null and Julia Lobur.

The task is to represent this circuit by both a Boolean expression and a
Truth Table. Admittedly, this will prove to be a silly circuit.

Interpreting a Digital Circuit: Step 1

Label the circuit elements (I have chosen to use numbers) and label the output
of each element. Note that we are slowly building a Boolean expression.

The outputs of each gate are as follows:
The output of gate 1 is (X + Y),
The output of gate 2 is (Y Å Z),
The output of gate 3 is X’,
The output of gate 4 is X’ + (Y Å Z), and
The output of gate 5 is (X + Y) Å [X’ + (Y Å Z)]

Interpreting a Digital Circuit: Step 2

For a circuit of this complexity, the best next step is to make a Truth Table.

X	Y	Z	X + Y	(Y Å Z)	X’	X’ + (Y Å Z)	(X + Y) Å [X’+(Y Å Z)]
0	0	0	0	0	1	1	1
0	0	1	0	1	1	1	1
0	1	0	1	1	1	1	0
0	1	1	1	0	1	1	0
1	0	0	1	0	0	0	1
1	0	1	1	1	0	1	0
1	1	0	1	1	0	1	0
1	1	1	1	0	0	0	1

We have now solved the problem. I want to continue and produce a simpler expression.
(At least I think that it is simpler).

Interpreting a Digital Circuit: Step 3

Present the truth table without the intermediate expressions. Use the standard rules to convert the truth table to either Canonical SOP or Canonical POS.
We do both.

X	Y	Z	F(X, Y, Z)
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

SOP: F(X, Y, Z) = X’·Y’·Z’ + X’·Y’·Z + X·Y’·Z’ + X·Y·Z
0 0 0 0 0 1 1 0 0 1 1 1

POS: F(X, Y, Z) = (X + Y’ + Z) · (X + Y’ + Z’) · (X’ + Y + Z’) · (X’ + Y’ + Z)
0 1 0 0 1 1 1 0 1 1 1 0

Interpreting a Digital Circuit: Step 4

SOP:

F(X, Y, Z) = X’·Y’·Z’ + X’·Y’·Z + X’·Y’·Z’ + X·Y’·Z’ + X·Y·Z
= X’·Y’·(Z’ + Z) + (X + X’)·Y’·Z’ + X·Y·Z
= X’·Y’ + Y’·Z’ + X·Y·Z

POS:

F(X, Y, Z) = (X + Y’ + Z) · (X + Y’ + Z’) · (X’ + Y + Z’)
· (X’ + Y’ + Z) · (X + Y’ + Z)
= (X + Y’) · (X’ + Y + Z’)· (Y’ + Z)

One can also write

F(X, Y, Z) = S(0, 1, 4, 7)

F(X, Y, Z) = P(2, 3, 5, 6)

This is about as simple as I can make these expressions.

Building a Digital Circuit for a Boolean Expression

We take as examples two representations of the same Boolean expression.

Sum of Products

SOP One OR gate connecting the output of a number of AND gates.

Building a Digital Circuit (Part 2)

Product of Sums

POS One AND gate connecting the output of a number of OR gates.

There are simpler Boolean expressions that are equivalent to both F2 and G2,
which are equivalent to each other. We study simplification later.

Stylistics

There are very few issues involved in drawing a digital implementation of
a Boolean circuit. The basic issue is DRAWING NEATLY.

My style of having the inputs at the top, with each input immediately feeding a NOT gate, if necessary, is only a convention. It helps me minimize the clutter in a drawing. The student may adopt any style that is easy to understand.

Big Gates

This style will ask for gates with a large number of inputs.
Here is an 8–input AND fabricated from three 4–input AND gates.

The AND gate on the right could also be a 2–input or 3–input gate.