Truth Tables and Computer Circuits

Date: 01/17/2000 at 15:33:40
From: Melissa Van Etten
Subject: Truth Tables and Computer Circuits

Can you please explain how to read and draw computer circuit diagrams, 
how to form truth tables from reading the diagrams, and the logical 
arguments behind this?

Date: 01/17/2000 at 17:33:50
From: Doctor TWE
Subject: Re: Truth Tables and Computer Circuits

Hi Melissa - thanks for writing to Dr. Math.

There's a lot to that question. I'll try to cover the basics.

Logic circuits are composed of gates. Each gate has one or more inputs 
and one output. Unlike in analog circuits, where the output could be 
any value (usually some quantity of volts or amps), logic circuits are 
digital, which means that the inputs and output are either "high" or 
"low." There is no in-between. A "high" input or output is usually 
written as a 1 and a "low" is written as a 0. Physically, these 1's 
and 0's are usually represented by voltage. A popular scheme called 
"TTL logic levels" assigns logic 1 +3V to +5V and logic 0 +.5V to 0V. 
The physical representation of the levels can vary, but the logic 
remains the same.

There are three basic gates, plus a host of "supplemental" gates that 
could be made from the basic three. The three basic gates are:

Inverter (sometimes called a "NOT gate"):
-----------------------------------------
An inverter has one input and one output. The schematic symbol for it 
looks like a triangle pointing to the right with a circle on the end 
of it. A is the input and X is the output.

  

The logic level of the output is always the opposite of the input, so 
if the input is 1, the output is 0 and vice-versa. We can represent 
this on a truth table. A truth table is simply a chart of all possible 
input values and the output associated with them. Here is the truth 
table for the inverter:

     A | X
     -----
     0 | 1
     1 | 0

There are two rows because one input has two possible combinations; 
high (1) or low (0). For each combination, the output is given. We can 
see that in each row, the output (X) is the opposite of the input (A).

AND gate:
---------
The AND gate has two (or more) inputs and one output. The schematic 
symbol for it looks kind of like an elongated capitol D. A and B are 
the inputs and X is the output.

  

The output is high only if both inputs, A AND B are high. (Do you see 
where it got its name?) Here is the truth table for the AND gate:

     A B | X
     -------
     0 0 | 0
     0 1 | 0
     1 0 | 0
     1 1 | 1

There are four rows because two inputs have four possible 
combinations. Notice that we list 0 1 and 1 0 separately. Even though 
in an AND gate the order of the inputs doesn't matter, in other 
circuits it could. For each combination, the output is given. We can 
see that the only time the output (X) is high is when BOTH inputs (A 
and B) are high.

For AND gates with 3 or more inputs, the same rule holds true; the 
output is high only when ALL inputs are high.


OR gate:
---------
The OR gate has two (or more) inputs and one output. The schematic 
symbol for it has a curved left side ad a pointed right side. A and B 
are the inputs and X is the output.

  

The output is high when either input, A OR B are high. (Do you see 
where it got its name?) Here is the truth table for the OR gate:

     A B | X
     -------
     0 0 | 0
     0 1 | 1
     1 0 | 1
     1 1 | 1

Again, there are four rows. For each combination, the output is given. 
We can see that the output (X) is high is when EITHER input (A or B) 
is high.

For OR gates with 3 or more inputs, the same rule holds true; the 
output is high when AT LEAST ONE of its inputs is high.

Combining Gates:
----------------
Gates are usually connected output-to-input. To determine the final 
output of the circuit, work your way from left to right. For a truth 
table, you'll have to do this for EVERY input combination. For 
example:

  

                 Output
       Inputs|  of gate # |
       A B C | 1  2  3  4 | X
       -----------------------
       0 0 0 | 0  1  1  0 | 0
       0 0 1 | 0  0  0  1 | 1
       0 1 0 | 0  1  1  0 | 0 
       0 1 1 | 0  0  0  1 | 1
       1 0 0 | 0  1  1  0 | 0
       1 0 1 | 0  0  0  1 | 1
       1 1 0 | 1  1  1  0 | 0
     +-------+------------+---+
     | 1 1 1 | 1  0  1  0 | 0 | <- example row
     +-------+------------+---+

From the example row in the truth table we can see that when A=1, B=1 
and C=1; the output of gate 1 (the AND gate) is 1 (because both A and 
B are 1), the output of gate 2 (the first inverter) is 0 (because C is 
1), the output of gate 3 (the OR gate) is 1 (because one of the two 
inputs -- which are the outputs from gates 1 and 2 -- is 1), and that 
the output of gate 4 (the last inverter) is 0 (because the input -- 
which is the output of gate 3) is 1. The final output (X) is 0. We 
normally don't have a separate column for this, since the final output 
is the output of gate 4.


This should get you started on logic circuits and truth tables. If you 
have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/