Boolean Logic
A usefule website for more information is How
Stuff Works
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.
Basic gates
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
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, and the
output is a boolean value.) Sum-of-products is a method you can
use create these gate systems. 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.)
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. (See lecture
notes for examples.)
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 for fewer
gates.
Switches
You can think these switches 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.
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 whatever the input
was. In the diagram above, we have power coming in (on) which is
equivalent to a logical 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.
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). C 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 x has the value 0 (off), the output x' will have the value
1. Thus, this switch '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, we can
say that its output is false (0) only if both the inputs are 0.
Three switches are used for its implementation. Power (1) is
applied to the system at the top of the wire. If either x or y
is 1, the output from that left part 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 (1) 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
switch on the right. So, if the output value of the x-y wire is
1, the final result is 0. Otherwise, the final result is 1.
Thus, if either x or y is 1, the switch 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:
Power is applied to the main input of the first
switch. The x input controls this switch. So the output of this
switch will be x'. This value is used to control the second
switch. Here, notice that we use y as the main input to the
switch instead of power (1). So, the switch value x' is
controlling whether the value of y is expressed. If x' is 0,
we'll get the value of y as the output. Otherwise, we'll just
get 0 as an output. So, if x is 1, the output is completely
dependent on y. That's exactly what we want to have for an AND
gate. (Consult the truth table to verify.)
For practice, you can try implementing some of the other basic
boolean functions, such as NOR (true when both inputs are 0, false
otherwise) and NAND (false when both inputs are 1, true
otherwise).
Decoders
See lecture notes for an introduction. 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.' You don't need to see the implementation as long
as you understand what it does. 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.)
Multiplexers
You can think of multiplexers as 'selectors', since
that's really what they do. Given a set of inputs (each of which
could be 0 or 1), the control line(s) select which one of those
values should be returned as an output. The inputs together form a
binary number which indexes the output lines. For example, if you
wanted a multiplexer to select one of 4 inputs, you would number
those lines in binary as 00,01,10,11. Notice that exactly 2 bits
were needed. For our multiplexer, we'll need two control lines:
one for each of the bits in our 2-bit binary numbers. Then, if we
for example, set the first control line to 0 and the second to 1,
we'll output the value of the 2nd input, since 01 is our second
'address' value.
Adders
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.
Notice that 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. There are more efficient
ways to implement adders.