|
Combinational Logic
A digital logic system is concerned with just two voltage states. The signal processed by the system
is either: high or low; on or off; logic 1 or logic 0. In the early days of
digital systems, circuits were built from discrete components such as resistors
and transistors. Today most
digital systems are built primarily from integrated circuits. At the heart of
all digital systems are small switching circuits called logic gates. There are a
number of different logic gates that open and give a high output
signal, depending on the combination of signals present at their inputs. Logic
gates are decision making circuits. Combinational logic is about
combining logic gates to process two or more signals to produce at least one
output according to a set of rules for each logic gate.
| The set of rules which
govern the behaviour of logic gates are written in the form of a truth table. A
truth table shows the value of the output for each of the possible input
combinations. Those for a two input AND gate are shown on the right. |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
|
| They can also be drawn in the form of a
Venn diagram. A Venn diagram is a useful way of illustrating the
function of a logic gate. The shaded portion of the diagram shows where
the output will be high. The Venn diagram for the two input AND gate is
shown on the right. You should see that there is only one portion of the
diagram shaded. That portion is where A and B overlap. This signifies
that the output is high where both A AND B are 1. |
|
Compare this with the truth table and Venn diagram for the NAND
gate below. You will see from these that the shaded portion is everything except
the section where A and B overlap. This is the complement (opposite) or inverse
of A and B. We say it is NOT (A AND B).
This method of describing logic functions becomes difficult
and confusing if a large number of gates are used in a logic system. To make
things neater and more simple to understand we make use of Boolean algebra.
Boolean algebra was developed in 1847 but it was nearly 100 years later before
it was used in digital electronics to analyse and predict the logical behaviour
of switching systems.
Boolean algebra is a form of mathematical shorthand which
describes how a logic gate (or system) functions. It uses certain conventions
which must be learnt
 | In Boolean algebra a plus sign (+) represents an OR
statement, and a dot (.) represents an AND statement. |
| A bar above the top of a symbol (A
for instance) means that the value of the symbol is inverted or
complemented. In Boolean terms 1
= 0 and 0 = 1. |
| A double bar ( ) is a
double inversion and cancels out to give the original symbol. In Boolean
terms
 = B.
|
Back to
Contents
Not gate or inverter [Q = A]
| This gate has only one input
and one output. The transistor switch circuit shown below acts as a Not
gate. It produces a 'high' output if the input is low and a 'low' output
if the input is high. As you can see from the Truth Table no matter what
the input state the gate 'inverts' it at the output. |
 |
 |
| NOT
gate truth table |
| Input |
Output |
| 0 |
1 |
| 1 |
0 |
|
|
A NOT GATE |
NOR gate [Q=A + B]
| A NOR gate is
essentially a NOT gate with two or more inputs, The symbol
for a NOR gate along
with its truth table and corresponding Venn diagram are shown below. If
either A or B or both are high the output is low. The Nor gate can
be represented by the Boolean expression A
. B [Q is 1 when A AND
B are 0 (look at the truth table)].
Using De-Morgans
theorem we can see this is the same as saying A
+ B [Q is 0 when A OR
B or both are 1]
|
|
|
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
1 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
0 |
|
 |
Back to
Contents
OR gate [Q=A + B]
| An OR gate is a NOR
gate followed by a not gate. The
symbol
for
a two input
OR gate, along
with its truth table and corresponding Venn diagram is
shown below. |
|
|
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 |
|
 |
Back to
Contents
NAND gate [Q=A
. B]
| A two input NAND
gate is shown below along with its truth table and corresponding Venn
diagram. When both A and B are 'high' the output is ' not high' (i.e. it
is 'low'). Its name is derived from the NOT AND (shortened to NAND). If
any of the inputs are 'low'
the output is 'high'.
The NAND gate can be represented by the Boolean
expression A + B
[Q = 1 when A OR B OR
both are 0] Using De-Morgans we can see
this is the same as saying A . B
[Q is 0 when A AND B are both
1 (look at the truth table)]
|
|
|
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
1 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
|
 |
Back to
Contents
AND gate [Q=A . B]
| An AND gate is a
NAND gate follwed by a NOT gate. A two input AND gate is shown below along
with its truth table and corresponding Venn diagram. Its truth table can
be found by inverting the 1's and 0's at the output of the NAND gate truth
table. The output of an AND gate is 'high' only when A and B are 'high'.
If any of the inputs are low the output is 'low'. |
|
|
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
|
|
Back to
Contents
Exclusive-OR (X-OR gate) [Q=A .
B + A . B]
| This is a special
case OR gate which allows a 'high' output when A or B is 'high' but
excludes the case where both inputs being 'high' give rise to a 'high'
output. It is often called the difference gate because the output is
'high' only when the inputs are different. A two input X-OR gate is shown
below along with its truth table and corresponding Venn diagram. |
|
|
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
|
 |
Back to
Contents
Exclusive-NOR (X-NOR gate) [Q=A .
B + A . B]
| This is a special
case NOR gate which allows a 'high' output when A and B are both the same
(either high or low) but excludes the cases where they are different. It
is often called the parity or equivalence gate because the output is
'high' only when the inputs are the same. A two input X-NOR gate is shown
below along with its truth table and corresponding Venn diagram. |
|
|
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
1 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
|
 |
It is not good practice to mix different logic IC's on the the same circuit
because this often leads to overpopulation of the board (if you only require one
AND gate from a four x two input chip the remaining three are wasted). It is
much better and more economical to build all your gates from similar chips.
All the logic gates mentioned above can be built by combining NAND gates or
NOR gates. This often leads to a simplification in size and complexity. The NAND
gate equivalents for different gates are shown below.
You can check that each one gives the correct output by constructing a stage
by stage truth table for each gate.
|
|
| INPUTS |
STAGE |
OUTPUT |
| A |
B |
X |
Y |
Z |
Q |
| 0 |
0 |
1 |
1 |
0 |
1 |
| 0 |
1 |
1 |
0 |
1 |
0 |
| 1 |
0 |
0 |
1 |
1 |
0 |
| 1 |
1 |
0 |
0 |
1 |
0 |
|
Back to
Contents
Changing AND to OR (and Vice-Versa) [ De-Morgans Theorems]
De-Morgan, a contemporary of Boole devised two theorems which
enable conversions from AND to Or and Or to AND. This allows us to design
circuits mathematically from combinations of NAND and NOR gates as we saw above.
The first theorem states that :
A + B
= A . B
What this means in reality is that a NOR gate can be built by
inverting the inputs of and AND gate. If we want to design an OR gate
mathematically then we need to the following:
 = 
so that......
A + B =
In other words an OR gate can be built by inverting the inputs
to a NAND gate
Algebraically an AND gate is an inverted NAND statement:
 = A . B
So this is built by inverting the output of a NAND gate.
Look again at the NAND gate
equivalent circuits above can you see how the mathematical descriptions are
realised in practice ?
The second theorem is very similar. It states that:
A . B
= A + B
What this means in reality is that a NAND gate can be built by
inverting the inputs to a OR gate. If we want to design an AND gate
mathematically then we need to do the following:
so that......
A . B = 
In other words an AND gate can be built by inverting the
inputs to a NOR gate.
Algebraically an OR gate is an inverted NOR statement:
= A + B
So an OR gate can be built by inverting the output of a NOR
gate. Look at the NOR gate equivalent circuits below can you see how each is
described by its mathematical statement ?
Back to
Contents
Boolean Identities
Boolean Identities are statements which are arrived at from
studying the AND and OR statements and are used to simplify Boolean expressions
or logic systems. The tables below show the Boolean identities for the OR and
AND operations.
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 |
|
A + 0 = A |
If we look at
the truth table you will see that wherever A is 'OR'd' with
0
(B = 0) the output is the same as A. |
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 |
|
A + 1 = 1 |
If we look at
the truth table you will see that wherever A is 'OR'd' with
1
(B = 1) the output is |
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 |
|
A + A
= 1 |
If we look at
the truth table you will see that wherever A is 'OR'd' with A
(B = A) the output is |
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 |
|
A + A = A |
If we look at
the truth table you will see that wherever A is 'OR'd' with
A (B = A) the output is |
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
|
A . 0 = 0 |
If we look at
the truth table you will see that wherever A is 'AND'd' with
0 (B = 0) the output is |
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
|
A . 1 = A |
If we look at
the truth table you will see that wherever A is 'AND'd' with
1 (B = 1) the output is |
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
|
A . A
= 0 |
If we look at
the truth table you will see that wherever A is 'AND'd' with A
(B = A) the output is |
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
|
A . A = A |
If we look at
the truth table you will see that wherever A is 'AND'd' with
A (B = A) the output is |
Back to
Contents
Other Boolean Laws
Commutative
Law:
A . B = B .
A
A + B = B + A
Associative
Law:
(A . B) . C = A . (B . C) = A . B .
C
(A + B) + C = A + (B + C) = A + B + C
Distributive Law:
(A . B) + (C
. B) = B . (A + C)
(A + B) . (C
+ B) = B + (A . C)
Absorption or Redundancy Law:
A + A . B = A
Back to
Contents
Logic Circuit Design
Logic circuits can be built from dedicated or programmable
components. Programmable Logic Controllers or PLC's can be programmed to perform
a variety of tasks and will be discussed later. Dedicated circuits built from
logic gates can only perform the single task for which they were designed.
There are two ways to design and build dedicated logic
circuits one is to draw up a logic table for the operation of the logic system
and use this as the basis for building and simplifying the system. The other is
to use Boolean algebra to design and simplify the logic system. In this section
we will be looking at and comparing the two methods, based on what we have
learnt to date.
| The first circuit we are going
to look at is the Exclusive OR gate. Its truth table is shown on the
right. Lines 2 and three of the truth table show that the output is only
logic 1 when A is 0 and B is 1 or
A is 1 and B is 0. |
If we write A (or B) is 0 as A
(or B) and A (or B is 1)
as A (or B) we can re-write it in simplified form as the boolean
equation:
Q = A
. B + A . B
This equation is a sum (+) of two products (.)
and is ideal for building with NAND gates.
|
| INPUTS |
OUTPUT |
| A |
B |
Q |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
|
| Using logic gates this means the circuit
consists of two two-input AND gates (one with a NOT gate on input A and
one with a NOT gate on input B) feeding into a two input OR gate. |
Logic System to simulate X-OR gate
|
Back to
Contents
Construction Method for solving the
NAND gate equivalent of an X-OR system
| If we build the simulated X-OR system shown above from
its NAND gate equivalents
we produce the circuit shown. The Not gates feeding from the AND gates
into the OR gate are redundant because a NOT followed by a NOT cancel
out. |
 |
| This then becomes simplified to: |
|
Back to
Contents
Proving the NAND gate equivalent of an X-OR system using Boolean
Algebra
Remember: Q = A
. B + A . B
If we analyse the logic system we arrive at the expression:
Using De-Morgans theorem
And a double inversion cancels itself out so that
we get:
Q = A
. B + A . B
Back to
Contents
Solving Logic Problems Solving
a logic problem involves designing a logic system which performs a particular
task. This is where Boolean algebra can be extremely useful. Problem
One - A Traffic Light System
| A |
B |
R |
Y |
G |
| 0 |
0 |
1 |
0 |
0 |
| 0 |
1 |
1 |
1 |
0 |
| 1 |
0 |
0 |
0 |
1 |
| 1 |
1 |
0 |
1 |
0 |
|
This problem requires a system
which lights 3 lamps red (R), yellow
(Y) and green (G) in the correct
sequence to drive a traffic light. A simple inspection of the way a
traffic light works will show that this is a four state cycle which can
be built from two input logic gates. |
 |
If we look at the truth table
above, we see that
| Red has to be lit when A is 0 and B is 0 (A
. B) or A is
0 and B is 1 (A
. B) |
| Yellow has to be lit when A is 0 and B is
1 (A . B) or A is
1 and B is 1 (A . B) |
| Green is lit when A is 1 and B is 0 (A .B) |
|
Re-writing these
in Boolean notation allows us to simplify these expressions:
R = A
. B + A
. B
R = A
(B + B)
R = A
[Since (B + B) = 1]
Similarly
Y = A
. B + A . B
Y = B (A
. A)
Y = B
[since (A . A = 0)]
G = A .B
|
|
| The logic circuit can be
built by feeding R from A via an inverter, Y from B directly and G
from the output of an AND gate with A and B inverted as its inputs.
Its NAND gate equivalent is shown below |
|
|
Problem Two - A Simple Multiplexer
| A simple multiplexer is shown on the right. Its
operation should be self evident. Two signals A and B are fed into it
from the left. The state of the address pin (C) controls which of these
two signals appear on the output Q.
When C = 0, Q = A and when C = 1, Q = B
This is basically a digital equivalent of a double
throw switch. |
 |
| As this system requires 3 inputs its truth table will
have 8 (23) possible states. We can write the Boolean equation from lines
1,3,6 and 7 of the truth table so that:
Q = A . B
. C + A . B
. C + A
. B . C + A . B . C
This can be simplified as shown below. |
| State |
A |
B |
C |
Q |
| 0 |
0 |
0 |
0 |
0 |
| 1 |
1 |
0 |
0 |
1 |
| 2 |
0 |
1 |
0 |
0 |
| 3 |
1 |
1 |
0 |
1 |
| 4 |
0 |
0 |
1 |
0 |
| 5 |
1 |
0 |
1 |
0 |
| 6 |
0 |
1 |
1 |
1 |
| 7 |
1 |
1 |
1 |
1 |
|
 |
The circuit can be built from NOT, AND, OR
gates or it can be built from NAND gates only. We said above that:
Q = A . B
. C + A . B .
C + A
. B . C + A . B . C
If we look at the first two terms we can
see that A . C is
common to both. These two terms can be factorized using the Distributive
law, to give A . C
(B + B). You will remember
from the Boolean identities discussed
above that B + B = 1 Similarly
in the second two terms B . C is common to both terms. Factorizing
we get B . C (A +
A). As before A + A = 1.
You should be able to see from this that: Q
= A . C + B . C It
should also be clear how and why the circuits on the left are constructed
in the way they are. |
 |
Back to
Contents
Karnaugh Mapping
When logic systems contain 3 or more inputs, the
simplest method for simplifying Boolean expressions is to use a Karnaugh
map.
|
Inputs |
C |
C |
| A |
B |
A
. B . C |
A
. B . C |
| B |
A
. B . C |
A
. B . C |
| A |
A
. B . C |
A
. B . C |
| B |
A
. B . C |
A
. B . C |
|
A Karnaugh map is essentially a different
way of representing information from a truth table graphically. Each field
(cell) in the Karnaugh map represents a row in the truth table (and
consequently an AND function). As a result the number of fields or
cells in a Karnaugh map is equal to the number of rows in the truth table.
If there are three inputs A, B, and C then the number of rows in the truth
table (and hence the number of cells in the Karnaugh map) is 23 or
8.
The Karnaugh map is best thought of as an
unrolled cylinder with the join at the top and bottom so that B
would meet B when rolled
up. |
As an example of how to use a Karnuagh map we
will look at the data switch problem from above: You will remember that:
Q = A . B
. C + A . B .
C + A
. B . C + A . B . C
| Inputs |
C |
C |
| A |
B |
1 |
|
| B |
1 |
1 |
| A |
|
1 |
| B |
|
|
|
Compare the truth table on the
right with the Karnaugh map on the left.
You will see that for each row of the truth table
where Q is 1. A 1 is placed in the corresponding cell of the Karnaugh
map.
Simplification involves Grouping together those cells
that contain a 1. Cells can be looped horizontally or vertically but
must always be Grouped in powers of 2 i.e. 2, 4, 8, 16 etc. A group of
six for example would not work. It is permissible to use some cells in
more than one group as long as these rules are adhered to. In this case
it is:
Q = A . C + B . C |
| A |
B |
C |
Q |
| 0 |
0 |
0 |
0 |
| 1 |
0 |
0 |
1 |
| 0 |
1 |
0 |
0 |
| 1 |
1 |
0 |
1 |
| 0 |
0 |
1 |
0 |
| 1 |
0 |
1 |
0 |
| 0 |
1 |
1 |
1 |
| 1 |
1 |
1 |
1 |
|
|
We could group the two cells containing A .
B . C and A
. B . C but these are both redundant with respect to A . C
and B . C respectively (see Redundancy law)
and it would serve little purpose. |
Back to
Contents
|
Logic Families
Logic circuits can be built using transistors
based on bipolar semiconductors or FET's.
Those based around bipolar transistors belong to a family known as TTL
(meaning transistor-transistor logic). Those based around FET's belong
to a family of IC's called CMOS (meaning complimentary metal oxide
semiconductor). CMOS is pronounced "see-moss".
TTL IC's are known as "74"
series because all IC's have identification numbers beginning with the
number 74.
CMOS IC's are identified as
"4000B" series the B indicates that the inputs are buffered to
help protect the IC's from damage due to static charges.
Both types use predominantly 14 or 16 pin
d.i.l. (meaning dual in line) packages. To make maximum use of the pin
connections several circuits may appear on one chip.
|
|
For example a quad two-input NAND gate IC
contains four identical NAND gates, with two inputs and one output per
gate. Each IC also needs a +ve and -ve power supply connection.
The 'pin outs' for the 74 series and
4000B series are different so care is needed not to confuse them. |
|
|
|
| CMOS and TTL Compared |
Back to
Contents |
| Property |
TTL |
CMOS |
| Power Supply |
5V +/- 0.25V d.c. |
3V to 15V d.c. |
| Current needed |
Milliamperes |
Microamperes |
| Input Impedance |
Low |
Very High |
| Switching Speed |
Fast |
Slow |
| Fan-out |
Ten |
Fifty |
|
| 
