Truth tables
For the five basic logic gates, a textual description of the operations
(what output state results from various combinations of input states) is
sufficient to give you an understanding of the function.
But as logic gates are combined to make more complex functions, describing
the behavior in English begins to get confusing.
What is needed is a precise way to show the relationships between inputs
and outputs.
We do this by means of a "truth table."
This is simply a table of states, where we make a column for each input or
output and a row for each combination of input states.
From the table you can quickly see that given certain states at the inputs,
a specific output state is to be expected.
Here are the truth tables for the gates we covered so far:
AND
in  out 
A  B  Y 
0  0  0 
0  1  0 
1  0  0 
1  1  1 


OR
in  out 
A  B  Y 
0  0  0 
0  1  1 
1  0  1 
1  1  1 


XOR
in  out 
A  B  Y 
0  0  0 
0  1  1 
1  0  1 
1  1  0 

Check these tables against your understanding of the logic gates to make sure
you agree with all the output results.
Of course, the basic logic gates are fairly simple.
But if we want to represent something a little more complicated, a truth table
helps clarify things.
For example, suppose we have a circuit (made up of several logic gates) which
functions as a single bit addition function.
Such a function has three inputs (the two values being added, plus a carry
input) and two outputs (the result for that digit, and the overflow carry).
Now the truth table becomes a bit more complicated, like this:
in  out 
A  B  CY_{1}  Y  CY 
0  0  0  0  0 
0  1  0  1  0 
1  0  0  1  0 
1  1  0  0  1 
0  0  1  1  0 
0  1  1  0  1 
1  0  1  0  1 
1  1  1  1  1 
The input combinations don't have to be in a particular order, as long as all
the cases (or all the cases you care about) are represented.
Notice also our use of names for the signals: A and B for the values being
added, CY_{1} for the carry from the previous bit, Y for the digit
output and CY for the carry to the next digit.
The use of "A," "B," "C"... for input data and
"Y" for output data are common name choices.
The "1" subscript on the carry input indicates that the carry is
from the digit whose place value is one less.
These are some naming conventions you may encounter, but the simple rule is,
somewhere the meanings of these names need to be described.
A truth table may have entries besides one and zero.
One example we'll offer for now is that "X" as an input state means
"don't care;" that is, the state really doesn't matter.
For example, we could express the AND gate truth table like this:
This truth table tells us that if A is 0, Y is zero no matter what B is, and
also that if B is 0, Y is zero no matter what A is.
There are other notations that may occur in a truth table which we will
not encounter until later in this course.
Logic gate symbols
When we start to use basic logic gates together to perform more complex
functions, we need a way to diagram the way the function works.
One way to do this is to write more complex logic expressions; several
hardware description languages such as VHDL, Verilog and PALASM work this way.
But a more standardized approach is to draw diagrams.
Each logic operation has a particular symbol used for these diagrams.
The symbols for our five basic logic gates are:
Buffer 
AND 
OR 
XOR 
Inverter 





The straight lines on either side of the symbols are inputs or outputs.
The inputs are all shown on the left; it is a convenient convention for logic
diagrams to have signals "flow" from left to right, although in
fact the direction is indicated by which way the symbol points.
Note also that for the AND and OR gates, there could be more than two inputs;
these would be indicated by additional lines connected to the left side of the
symbol.
Using these symbols, and connecting input and output lines, you have a way
of representing functions made up of several gates.
For example, consider this function:
The drawing represents this expression:
Y = (A AND B) OR (C AND D AND E)
We use straight lines to connect the gates.
The "flow" of the information is from left to right because that
is the way the gates are pointing, not because of their placement on
the page.
Inverted levels
We saw earlier that the symbol for an inverter is a combination of the symbol
for the buffer and an open dot.
Actually it is the dot that indicates the inverter.
This dot can be combined with the other logic gate symbols, at either an
input or output, to indicate that an inversion happens at that point.
For example, if the inverter dot is placed at the output of the AND gate,
it means that after the AND operation, the result is inverted.
(This particular example means the output is "0" when all
inputs are "1;" this "notAND" function is known as a
"NAND gate."
Placing an inverter at the output of an OR gate is called a "NOR
gate.")
When you see a dot at any signal on a logic gate, it means that the signal
state is inverted at that point.
Here are some examples of gates with inverters:
NAND 
NOR 






Y=NOT(A AND B) 
Y=NOT(A OR B) 
Y=A AND NOT(B) 
Y=NOT(A) OR NOT(B) 
It shouldn't be hard to figure out the truth tables for these combined gates.
And actually, if you did, you might notice something interesting: the last
example has the same truth table as the NAND gate, even though they look
nothing alike.
There is a principle called DeMorgan's Theorem which says simply that
a logical binary expression remains unchanged if you invert the inputs and
outputs and swap ANDs and ORs.
That is, for any gate, if you invert a signal which wasn't inverted, and take
away the inverters that were there, and also change any AND into an OR
and any OR into an AND... the truth table comes out the same.
If this doesn't seem intuitive to you, try a few more truth tables until you
believe that it always works.
Think about our description of the AND gate.
"For the output to be '1,' you need a '1' at both input A
and input B."
But we would be just as correct to say:
"For the output to be '0', you need a '0' at input A or input
B."
That's consistent with DeMorgan's theorem.
And really, we may not always think of our logic in terms of "1"
being the "active" state.
When we do so we are using "positive logic," but there can be other
times when we are more interested in the 0s than in the 1s.
We will encounter signals in computer electronics which are called
"active low," which means that "0" represents a state we
care most about.
Next: Registers
Previous: Binary
Copyright ©20032006, Mark Bereit. All rights reserved.
