COS 126 Lecture 11: Boolean Logic
I've chosen to talk about the slides in a different order: I hope this
doesn't cause any confusion.
Levels of abstraction - slide 1
Recently, we've been working with higher levels of abstraction: data
structures like stacks, queues, lists, trees, Rational numbers, etc. They
have been built upon more primitive data types like pointers and ints.
Now we're going to look at low levels of the computer architecture and
look at how computers are built up in successive levels of abstraction.
At the lowest level, there are switches, wires, and electrical current.
Values are either on or off - corresponding directly to whether a switch
is on or off and to whether a wire is connected to a power source or not.
These low levels are the domain of electrical or computer engineers. Computer
scientists don't usually worry about details at this primitive level. However,
it is important that computer scientists understand the limitations of
the hardware. This is analagous to the situation we encountered in the
Rational Arithmetic program. In theory, the client program (e.c) didn't
need to know how the functions in the interface (RAT.h) were implemented.
However, as we saw, the implementation did affect the results generated
by e.c.
Switches, transistors (controlled switches) - slide 6
Switches are the fundamental building block of computers, much
like atoms are the fundamental building block of matter.
You can think of transistors as acting like switches on a train track.
Or, more appropriately, like valves on a water pipe. Switches control whether
the flow of electricity (instead of water) is cut off.
The speed of a computer is directly related to how fast the
switches work.
power
input
output
If the input switch is on (1), the output will be 0. If the input switch
is off (0), the output will be 1. In general, this is how you can think
about a system of transistors: there is an initial power source. Once that
power is 'switched' away from the output line, the output will be 0
(regardless of the input switch).
Primitive gates are implemented with transistors. The primitive gates
are AND, OR, NOT, XOR, NAND, and NOR.
Here's how you can interpret the diagrams in the lecture notes:
NOT gate:
At the top of the diagram, power is applied to the wire (value =1).
Y is the input: if its value is 1, the switch is activated. Like a train
switch, you can think of the direction of power as being diverted from
the main route. So, the power won't get to the output x: x will have the
value 0. If y has the value 0 (off), the output x will have the value 1.
Thus, this transistor switches the input value - 0 to 1 or 1 to 0. This
is exactly what a NOT gate should do. The concept of NOT is really an abstraction
of what this transistor is actually doing.
OR gate:
OR takes two values as input. Its result is true (1) if at least one
of the inputs is 1. Or, equivalently, its output is false (0) only if both
the inputs are 0. Three transistors are used for its implementation. Power
is applied to the system at the top of the wire. If either x or y is 1,
the output from that left wire will be 0 (the power will be 'switched'
away from the central line, like a train switch or a water pipe.) Think
of water flowing from the top to the bottom. If at any point that water
is diverted away from the central pipe, water will not reach the bottom.
The flow of power works the same way. In this system, power is also applied
at the top of the wire on the right of the diagram. The output from the
left wire serves as the input controlling the transistor on the right value.
So, if the output value of the x-y wire is 1, the final result is 0. Otherwise,
the final result is 1. Now, if either x or y is 1, the transistor on the
right will have input value 0 and the final result will be 1 (power will
reach the output line.) Try all the possible input values for x and y yourself,
and you'll see that OR is correctly implemented.
AND gate:
This diagram is more complicated. Power is applied to the top of both
the left and right wires. The x and y inputs control the switches on each
of those wires. So, their values will be switched as inputs into the third
wire. Power is applied to the top of this (horizontal) wire, too. (The
power will enter at the left of the horizontal wire.) If the outputs of
both the left and right wires is 0, the final result will be 1. Otherwise,
power will not reach the final output, and its value will be 0. So, if
either x or y is 0, the output of its corresponding wire will be 1. That
value of 1 will activate a switch on the horizontal wire, causing the final
output to be 0. This is the correct implementation of AND.
For practice, you can try implementing some of the other basic boolean
functions, such as NOR and NAND.
Basic gates - slide 5
Recall that we learned about boolean functions when we were looking
at TOY commands.
The simplest gate (because it takes only one input) is the not gate
(also called an 'inverter.') It simply reverses (or negates, or inverts)
the input. If the input is 0, the output is 1. If the input is 1, the output
is 0. The NOT gate is represented by a triangle with a circle at its rightmost
tip. 
In a complicated system, you can just draw the circle
part (the bubble) on the wire.
Before we get any further, let me introduce the concept of a 'truth
table.' It's important that you learn how to interpret truth tables and
understand how to use them to describe boolean functions. A truth table
is a table that shows all the possible combinations of input values. The
size of the truth table will depend on the number of inputs. A function
of one variable (like NOT) has two possible inputs: 0 and 1. So, it has
two rows. A function of two variables will have 4 rows. A function of 3
variables will have 8 rows. In general, a function of n variables will
have 2^n rows. Here's the truth table for NOT:
input | output
--------------
0 | 1
1 | 0
The AND gate is represented by a half circle:
Its truth table
is:
x y | output
------------
0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1
AND corresponds to the product of the input terms: (xy). Zero times
anything is zero. Zero AND anything is zero. By adding an inversion bubble
to the output of the AND gate, a NAND gate is formed. Its output is exactly
the opposite of the output of an AND gate.
The OR gate is represented by a crescent: 
Its truth table
is:
x y | output
------------
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1
OR corresponds to the sum of the input terms (if we consider 2 to be
true: 1 + 1 -> true (1)). By adding an inversion bubble to the output
of the OR gate, a NOR gate is formed. Its output is exactly the opposite
of the output of an OR gate.
The XOR gate is an OR gate with an added curved line to the left of
the crescent: 
Its truth table is:
x y | output
------------
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0
Recall that XOR is 'exclusive or.' It is true only if exactly one of
the inputs is true. All of these gates: AND, NAND, OR, NOR, and XOR can
take more than 2 inputs. An AND of n inputs is true only if all n inputs
are true (1). OR is true if one of its inputs is true. etc.
Sum-of-products - slides 4 and 5
A system of gates (connected together by wires) can be constructed to
implement Boolean functions. (A Boolean function is just one in which all
the inputs are boolean values (0,1), and the output is a boolean value.)
Sum-of-products is a systematic method you can use create these gate systems,
using only AND, OR, and NOT gates.
Here's how it works:
First, you'll be given a description of the function you need to implement.
It may be descriptive, like "implement the function of three variables
which is true if an even number of inputs is true and false otherwise.
Or, it may be given as an equation, like "m = x'yz + xy + z"
The first thing to do is construct the corresponding truth table. (This
isn't entirely necessary, but it's good practice anyway.) To construct
the truth table, you first need to list all the possible inputs. Then,
for each row in the truth table, determine the corresponding output. For
example, for the equation above, the truth table entry 101 will have output
1, (since the third input: z is true.)
In general, if there are n inputs, then there will be 2^n truth
table entries.
Next, for each row in the truth table with output equal to one, draw
the corresponding AND gate. For each input in that truth table row with
value 1, just draw a wire from that input to the AND gate. For each input
in that truth table row with value 0, draw a wire from that input to a
NOT gate and then another wire from the output of the NOT gate to the AND
gate. (Look at the picture on slide 5 to see what I'm talking about.)
Finally, draw a wire from the output of each of the AND gates into an
OR gate. The output of the OR gate is the output of the function. Trace
through the gates for a few of the input combinations to convince yourself
that this method produces the correct results.
Now, a twist: in the case in which more of the outputs (in the truth
table) are ones instead of zeros, you don't want to have to draw that many
AND gates. So, instead, you can draw an AND gate for each of the zero outputs
(doing the same thing for the inputs), wire their outputs to the input
of the OR gate, and then add a NOT gate at the end.
Notice that these gate circuits are not unique. It is often possible
to simplify them and create equivalent systems with fewer gates.
(For this course, you should not be concerned with minimizing the number
of gates.)
Charts of Boolean functions - slides 2 and 3
These slides just demonstrate the power of Boolean functions. The
representations
of x and y (and z) are given at the top of each table. Then, beside each
row a corresponding function is listed, if applicable.
Don't worry about these two slides too much. It's more important that
you understand the overall concepts.
Decoders - slide 7
This slide shows the implementation of a decoder. Notice that for any
combination of inputs (x,y,z), exactly one of the output lines will be
true(1). The rest will be false (0). A decoder is a circuit that you'll
often see drawn as a rectangle, with n input lines and 2^n output lines.
The implemention is 'hidden' inside this 'black box.'
Once you understand how it is implemented, you can work at a higher
level of abstraction, and treat the decoder as a primitive circuit.
Given any
binary number, it produces a value of one on the corresponding output line.
For example, given the input 110, the 6th output line will have the value
1. (Remember that counting will start at 0.)
Adders - slide 8
This slide makes the fundamental leap from Boolean functions to
arithmetic. We see how to implement an adder (addition) circuit
using only AND, OR, and NOT gates.
It's difficult to read the circuitry of the adder in the
course packet.
Again, we have the idea of abstracting the low level implementation
into a higher-level circuit. In this case, given three inputs, we output
their sum (which is one digit) and a carry bit (if any). The carry bit
is necessary in the case where more than 1 input has value equal to one.
The circuit for the sum part of
the output is an odd parity circuit. An odd parity circuit is one which
has output one if the number of inputs that are one is odd. The circuit
for the carry output is a majority circuit. A majority circuit has output
equal to one if the majority of the inputs have value one.
To add multiple digit numbers, you can use multiple adders. The x and
y inputs of each adder will be two corresponding digits of the two numbers
you are adding. The z input will be the carry from the previous adder.
This is a slow way to add: you can't add any pair of numbers until you
compute the carry from the previous two. Also, as mentioned in the slide,
we need to ensure the correct timing. We shouldn't add any pair of digits
until we have the correct result from the previous adder.