Digital Logic Basics

Below are some important small scale scale integrated circuits and Boolean logic.  These basic gates are essential to design an understanding how they are formed can help you understand how to build larger and more complex Boolean networks.  The gates shown here are -- and, or, nand, nor, xor, and not.

AND Gate a b c 0 0 0 0 1 0 1 0 0 1 1 1
OR Gate a b c 0 0 0 0 1 1 1 0 1 1 1 1	View propagation  Clear propagation
NAND Gate a b c 0 0 1 0 1 1 1 0 1 1 1 0
NOR Gate a b c 0 0 1 0 1 0 1 0 0 1 1 0	View propagation  Clear propagation
XOR Gate a b c 0 0 0 0 1 1 1 0 1 1 1 0
Inverter a c 0 1 1 0	View propagation  Clear propagation

Above shows common basic gates used.  The table on the left is called a truth table.  If the zeros were replaced with false and the ones were replaced with a true, well this is where the name comes from.  In all the tables a and b are inputs and c is the output.  The symbols located to the right of the tables are the symbols used when drawing a circuit using these gates.

The structure of a truth table is as follows.  Only binary values are used in the table.  The first input 'b' alternates 0 -> 1, all the way down the truth table until the end.  The the next input uses double the amount of zeros and one and alternates 0 -> 0 -> 1 -> 1, until the end of the table.  If there were another input then it would get double the last amount of ones and zeros.  This continues until all inputs are in the table.  As you may gather the table can get big quickly, that is why this method is usually only used on basic gates.

Equation Symbols

Circuits are not just drawn strait from truth tables the are first written by hand using other symbols

and	a * b = c	The multiply symbol is the 'and' function
or	a + b =c	The add symbol is the 'or' function
nand	/a * /b = c	Notice that 'nand' is a combination of an inverter and an 'and' gate
nor	/a + /b = c	Notice that 'nor' is a combination of an inverter and an 'or' gate
xor	a b = c	This new symbol is used for an 'xor' function
invert	/a = c	A slash before the 'a' or slash over the 'a' both mean to invert the logical value

Sum Of Products (SOP)

In order to put a truth table into an equation we need a method to covert the table to this form.  It turns out there is a method called Sum of products, that does just this.  The method will be shown and then discussed.

Using sum of products we get --> d = ( /a * /b * c) + ( /a * b * /c ) + ( a * b * /c ) + ( a * b * c )

Every line that has an output of one is put into the SOP equation.  All of the inputs on that line are 'anded' together, if the value if the input on that line is zero then the inverted value is 'anded' together.  Then all of the lines are 'ored' together forming the final equation.

Reducing and K-maps

Now that we have this equation how do we know if it is reduced, do we have extra gates that do not need to be there?  To answer these questions we can put the data into a Karnaugh map or K-map.  Again the method will be shown and then discussed.

Final equation -->  d = ( /a * /b * c) + ( a * b ) + ( b * /c )

Notice that our equation has less gates.  This is important because less gates means less money.

Now to explain how to build and use a k-map.  First the k-map outline is constructed.  If you have two inputs one goes on top and one on the left.  IF you have three, one on top two on the left.  If you have four, two on top and two on the left.  This patter n continue as more inputs are added.  The number of boxes depend on the number of inputs to display.  notice the order of the binary on the left side, 00 -> 01 --> 11 --> 10.  This is due to the fact that only one bit can change each time you go to a new row.  From 00 the right zero changes to a 1, then 01 the left zero changes to a 1, and finally 11 the right one changes to a zero.  If we would have gone from 01 to 10 two digits would have changed.  

When filling out the k-map use the corresponding truth table.  a=0 b=0 c=0 gets a zero according to the truth table, a=0, b=0, c=1 gets a one, etc.  Once the k-map is filled out group ones together with circles that shares the same borders.  Diagonal borders do not count and each circle has to hold a power of two number of digits in it, 1, 2, 4, 8, etc.  Grouping around the world is acceptable and all ones must be in a circle.

Once all the ones are circled, use the SOP method to write the new equation.  Notice that two of the new pieces of the equation only have two terms not three.  If an input in a circle changes between ones then it can be left out of the equation.  Notice that in the vertical circle with two ones circled the input 'c' changes from 1 to 0 in the same circle.  This input 'c' can be left out of the equation because it is a don't care, simple meaning we do not care about c because it does not affect this part of the equation.

Final Circuit Diagram

This is the final circuit diagram of the equation produced from the k-map.

Boolean Identities (Demorgan's Laws)

When doing operations do the operations in the order that you would do them in arithmetic terms, i.e. multiply first add second.