Combinatorial Devices

A digital circuit can be in one of two states 0 or 1.

0-1 volts -> logic 0

2-5 volts -> logic 1

A gate is a simple electronic device that can be used to compute various combinations of logic states.

A transistor can be thought of as a simple switch either closed or open.

Gates are made from transistors:

Invertor or NOT gate

NAND gate

NOR gate

Logic symbols used for these combinations are:

A X

0 1

1 0

A B X

0 0 1

0 1 1

1 0 1

1 1 0

A B X

0 0 1

0 1 0

1 0 0

1 1 0

A B X

0 0 0

0 1 0

1 0 0

1 1 1

A B X

0 0 0

0 1 1

1 0 1

1 1 1

A NAND or a NOR gate can be built from just two transistors

AND or OR require three, so most logic is built from NAND’s and NOR’s

All logic circuits can be built just from NAND gates (or NOR)

eg an invertor:

Boolean Algebra

Another way to describe circuits is by using Boolean Algebra.

Variables (normally capital letters) can be either 0 or 1 and can be combined by :

AB -> A and B (sometimes written A.B)

A + B -> A or B

-> not A

From an arbitrary truth table, we can generate a Boolean expression:

A B C

0 0 1

0 1 0

1 0 1

1 1 1

Look at each row that produces a 1 in the C column. Form the expression using AND and NOT that generates a 1. OR all the rows that produce a 1 together:

C = + A + AB

To implement the function as a circuit:

Use standard ANDs and ORs to start with. Use more than two inputs if necessary.

Convert to NANDs and NORs when finished.

Inverting circles can be added to/removed from either end of a line.

3 input devices can be formed from 2 input devices with the output combined with the third input

is the same as:

The following equivalence’s also allow us to simplify our circuits:

which are a result of De Morgan’s Law = +