Learning Objectives
design a logic system from a truth table, written description or Boolean algebra expression using combinations of gates;
simplify a logic system using either Boolean algebra or Karnaugh maps;
convert logic systems comprising mixed gates into either NOR or NAND gates only;
describe and explain the operation of combinational logic systems.
Designing a Logic System
In Tutorial 9 we saw the principles of simple logic design. We saw how we could produce a truth table from a combination of different logic gates. The diagram shows another combination of logic gates:
Complete the truth table.

In drawing up the truth table, we notice that:
C is A inverted, so that when A is a 1, C is a 0 and vice versa.
D is a 1 when both C AND D are a 1.
Q is a 1 when B is a 1.
Now let us do the reverse. We are going to design a circuit having been given a description.
Design a circuit with two inputs A and B that will give an output that is high only when B is high and A is low. 



We can solve a problem if we are given a truth table rather than a written description. Here is another truth table:
A 
B 
Q 
0 
0 
1 
0 
1 
0 
1 
0 
1 
1 
1 
1 


Simplifying Logic Circuits with Boolean Algebra
The methods we have looked at above are OK for very simple systems, but with a more complex system we would find the truth tables very cumbersome, if not impossible. So we can use Boolean algebra, which we first met in Tutorial 9. Let us look at a few of the rules:
A, B, and Q represent the variables which can only be 1 or 0.
A (“Abar”) is NOT A. If A = 0, A = 1 and vice versa. A is said to be complementary to A.
Important Note: It is impossible using this web editor to place the bar above the A, so I have written the Abar as a white letter on a black background, A. In Word, I have put the bars above the letters using the line drawing function. However it does not copy across at all well. In some questions I have written "Abar". If you can do it any better, then please tell me, and then come and do the edits for me! The double compliment "A barbar" I will write as A¯ ¯.
Go back to Tutorial 9 to revise the basic rules of Boolean Algebra.
A useful property of logic gates is that there is often more than one solution to a problem, and Boolean algebra helps to simplify the expressions required. This allows us to use the minimum number of gates, desirable as that reduces the effort in design and wiring. Here are some laws that will simplify matters:
Name 
What it says 
De Morgan’s First Law 

De Morgan’s Second Law 

Double inversion 

Commutative Laws 
A + B = B + A 
Associative Laws 
A + (B + C) = (A + B) + C

A.(B.C) = (A.B).C 

Distributive Laws 
A .(B + C) = (A.B) + (A.C) 
A + (B.C) = (A + B).(A + C) 

Product of Sums 
(A + B).(A + B) = A.A + A.B + B.A + B.B 
Redundancy 
A.B + A.B.C + A.B.D = A.B 
De Morgan's laws were worked out by the British mathematician, Augustus de Morgan (1806  1871).
There are a lot of laws here, which we will use to simplify the circuit as shown in the example below:
Simplify the Boolean expression for this circuit.

The Boolean expression for this circuit is:
The associative law says:
See where the brackets have moved. Well so what? Look at De Morgan I:
Then De Morgan II gives us:
The double bar gives us a double inversion, so we get:
We can’t get much simpler than this. 
Simplifying Circuits with Karnaugh Maps
Another way of finding the simplest solution to a logic gate problem is the use of the Karnaugh map (named after the American Physicist, Maurice Karnaugh (1924  )). Here is a truth table for an output with four different inputs, or a fourbit word. You may wonder what this last term means:
A word is a set of binary digits. Computers use sixteen or thirtytwo bit words, which means that they process groups of 16 or 32 binary digits. 8 binary digits is called a byte. Here we have a group of four digits, not a very good medium for a computer.
A bit is a binary digit, 1 or 0 (ON or OFF)
Look at this truth table:
DCBA 
Q

0000 
0 
0001 
1 
0010 
0 
0011 
1 
0100 
0 
0101 
1 
0110 
0 
0111 
1 
1000 
0 
1001 
0 
1010 
1 
1011 
1 
1100 
1 
1101 
0 
1110 
0 
1111 
0 
There are seven rows in this truth table where the output is 1. So we can write the Boolean expression:
This is a
pretty ghastly expression. Of course we can simplify it using the methods
we saw above, but Karnaugh maps are much more helpful in this case.
Notice the order of the letters. D is the most significant bit, and A is the least.
In the Karnaugh map we split up the truth table into a 4 x 4 matrix, with the rows identified by DC, and the columns identified with BA. Notice the order of the two bit words. One bit is the same as the neighbours. The sum of adjacent bits has to be different.
If you can’t remember these, just learn the order, 00, 01, 11, 10.
We need to fill the table from the truth table above. For example 00, 01 (Black arrows) gives a 1 and 01, 10 (Blue arrows) gives a 0.
So we fill the table:
We can identify clusters of 1s:
These clusters have been marked P, R, S. Let us look at group P. We get a 1 in both cells when DC is 10. We get a 1 in one of the cells when BA = 11, or when BA = 10. So we can write the Boolean expression for cluster P as:
We can rewrite this as:

Now let's do the same for R.
What is the Boolean expression for R? 
Explain why we can write R = D.A. 
Now look at S.
What is the Boolean expression for S? 
Now we can put P, R, and S together:
Can we simplify this any further? No.
To design the circuit, we need to think of the three inputs to OR gates:
D AND NOT C AND B
NOT D AND A
D AND C AND NOT A AND NOT B
We will build this up bit by bit, starting with Q. Q = P + R + S. Q is equal to P OR R OR S.
This is the output end of the circuit. Now we will draw P = D.C.B
Now we will draw R = D.A
Then we can draw out S = D.C.B.A
Finally we can put the whole thing together:
In this last example, we have designed a rather complex system from a Karnaugh map. We could test it out with a giant truth table, but it would get rapidly rather tedious. For a more complex circuit it would be impossible.
Using NAND or NOR gates to make up Circuits
How do we get a NOT gate from a NAND gate? Draw up a truth table to back up your answer. 

Show how an AND gate can be made from two NAND gates. Draw up a truth table to back up your answer. 
Question 11 
Answer the interactive question. 

Use a truth table to prove that the circuit above is an OR gate. 
How would you make a NOT gate from a NOR gate? 
How would you make an OR gate from a NOR gate? 
The Operation of Combinational Logic Systems
Show how this circuit can be made with NAND gates. 
Links 

Interactive logic gates simulator 

Electronics tutorials 

Video tutorial on Karnaugh Maps 

NAND gates 