In his pivotal 1937 master's thesis "A Symbolic Analysis of Relay and Switching
Circuits", Claude E. Shannon provides the essential link between boolean
algebra and electronic
hardware.
Shannon was the first to toy with the idea of using symbolic logic to represent,
develop and simplify circuits providing electronics engineers with the
mathematical tool
they need to
build digital electronic circuits and eventually design the digital computer.
The paper starts by relating the two fields. It then states theorems
from the field of symbolic logic, applies these theorems to simplifying
general series/parallel circuits, proves
some properties
of series/parallel circuits using symbolic analysis, and discusses properties
and theorems relating to other specific circuit types. It ends with
a couple examples of
"practical"
applications of the tools Shannon develop in the paper.
Postulates and Theorems of Boolean Algebra
Shannon begins by defining the formalism that he will adapt throughout
the paper. The circuits discussed in the paper only contain relay
contacts and switches. If the circuit
between two
terminals (say terminal a and terminal b) is open (ie the gate is open)
then the hindrance function (resistance), Xab
or just X if the terminals it connects are
unambiguous, is equal to 1. If the circuit between the terminals
is closed (ie the gate is closed) then the hindrance function (resistance)
Xab, is equal to 0. A + sign represents a
series circuit, and a * represents a parallel circuit.
Shannon then states postulates and theorems from boolean algebra relates
them to the behavior of circuitry.
The postulates are as follows:
1a. 0*0 = 0 A closed circuit in parallel with a
closed circuit is a closed circuit.
b. 1 + 1 = 1 An open circuit in series with an open circuit
is an open circuit is an open circuit.
2a. 1 + 0 = 0 + 1 = 1 An open circuit in series with a closed circuit in
either order (i.e., whether the open circuit is to the right or left of
the closed circuit) is an open
circuits.
b. 0 * 1 = 1 * 0 = 0 A closed circuit in parallel with an open
circuit in either order is a closed circuit.
3a. 0 + 0 = 0 A closed circuit in series with a closed circuit
is a closed circuit is a closed circuit.
b. 1 * 1 = 1 An open circuit in parallel with an open circuit is
an open circuit.
4. At any given time either time either X = 0 or X = 1.
Theorems of boolean algebra are as follows:
Let X, Y, and Z be hindrance functions, the " ' " be the notation
for negation (ie X' = negation of X ~ if X = 1, X' = 0 and vice versa),
and f be a function of boolean
variables
1a. X + Y = Y + X
1b. X*Y = Y*X
2a. X + (Y + Z) = (X + Y) + Z
2b. X(YZ) = (XY) Z
3a. X(Y + Z) = X*Y + X*Z
3b. X + Y*Z = (X + Y)(X + Z)
4a. 1*X = X
4b. 0 + X = X
5a. 1 + X = 1
5b. 0*X = 0
6a. X + X' = 1
6b. X*X' = 0
7a. 0' = 1
7b. 1' = 0
8. (X')' = X
9a. (X + Y + Z ...)' = X'*Y'*Z'*...
9b. (X*Y*Z*...)' = X' + Y' + Z' + ...
10a f(X1,X2,...Xn) = X1*f(1,X2...Xn)
+ X1'*f(0,X2...Xn)
10b f(X1,...,Xn) = [f(0,X2...Xn)
+ X1]*[f(1,X2...Xn) + X1']
11a f(X1...Xn) = X1X2f(1,1,X3...Xn)
+ X1X2'f(1,0,X3...Xn) + X1'X2f(0,1,X3...Xn)
+ X1'X2'f(0,0,X3...Xn)
11b f(X1...Xn) = [X1 + X2 +
F(0,0,X3...Xn)]*[X1 + X2' +
f(0,1,X3...Xn)]*[X1' + X2 +
f(1,0,X3...Xn)]*[X1' + X2'
+ f(1,1,X3...Xn)]
12a f(X1...Xn) = f(1,1,1...1)X1X2...Xn
+ f(0,1,1...1)X1'X2...Xn + ... + f(0,0,0...0)X1'X2'...Xn'
12b f(X1...Xn) = [X1 + X2 +
...Xn + f(0,0,0...0)]* ... *[X1' + X2'
... + Xn' + f(1,1...1)]
13 f(X1,X2...Xn,+,*)' = f(X1',X2'...Xn',*,+)
14a X = X + X = X + X + X = etc.
14b X = X*X = X*X*X = etc.
15a X + XY = X
15b X(X+Y) = X
16a XY + X'Z = XY + X'Z + YZ
16b (X + Y)(X' + Z) = (X + Y)(X' + Z)(Y + Z)
17a X f(X,Y,X,...) = X f(1,Y,Z,...)
17b X + f(X,Y,Z,...) = X + f(1,Y,Z,...)
18a X' f(X,Y,Z,...) = X' f(0,Y,Z,...)
18b X' + f(X,Y,Z,...) = X' + f(1,Y,Z,...)
From these fundamental postulates and theorems, Shannon develops his own
theorems relating to circuitry analysis. He also demonstrates how
his theorems
and these theorems
can be used.
Let all the letters represent hindrance functions, where are bar above the letter represents the negation of that letter's hindrance. Given this as the initial circuit:
To simplify this circuit we do the following:
1. write the circuit as an algebraic expression:
(v'z + sv)x's + (x' + y + sx + sy'w)swxy + x'y + (xy + wsv + vz)vz' + vz'
2. apply boolean algebra rules to simplify circuit:
(v'z
+ sv)x's + (x' + y + sx + sy'w)swxy + x'y + (xy + wsv + vz)vz' + vz'
= (v'z + sv)x's + swxy + x'y + vz'
= v'x'sz + svx' + (swx + x')y + vz'
= sx'(v'z + v) + y(sw + x') + vz'
= sx'(z + v) + ysw + yx' + vz'
= sx'z + ysw + yx' + vz' ==== since vz' + sx'z + vsx' = vz' + sx'z
= s(x'z + yw) + yx' + vz'
3. draw resulting circuit:
___ y ___ ___ v ___
___ s _____
|
| |
| |
|
a -|
|----|
|----| _x' _ _ w'_ |----b
|__ x' ___| |___ z' ___|
|_| |_|
|_ |
|_z _| |_ y_|
Some
unexpected difficulties arose while I was working through some of the proofs.
For example, in Shannon's proof of XOR being the most complex in terms
of elements
required for a series/parallel implementation, I did not understand his
argument for explaining why there is no other way of expanding an XOR that
will reduce the number
of elements in the function. I will resolve these difficulties by
trying to talk to others and get help in understanding.
My milestones have not changed much since the proposal stage. The references were easier to obtain than I had expected. However, most of these references are purely mathematical texts that were summarized The proofs are harder to work out though.