Combinational vs.

Sequential Circuits
A combinational circuit
has inputs, outputs and
an internal logic circuit
Constitutes a mapping
from the inputs to the
outputs
A sequential circuit has
inputs, outputs, an
internal logic circuit and
binary cells as memory
A binary cell is a memory
device with two possible states.
Boolean Algebra
Variables in a Boolean
algebra take on values
that are not numbers
but logical values:
TRUE or FALSE
x = TRUE, y = FALSE
George Boole
1815 - 1864

It is not of the essence of mathematics to be conversant with
the ideas of number and quantity.
~ An Investigation into the Laws of Thought, on Which are
Founded the Mathematical Theories of Logic and Probabilities
Boolean Algebra
Provides the basis for digital
logic a logic based on
processing discrete (rather
than analog) signals
Can be used to describe the
states of switching circuits
Led to the development of
digital computers
Claude Shannon
1916 - 2001
It just happened that no one else was
familiar with both fields at the same time.
LOW
HIGH
Logical Variables
Logical variables take
only two values:
1.0
3.0
0.4
0.2
V
o
l
t
a
g
e

L
e
v
e
l

[
V
]

In actual computers,
these are represented
by voltage levels




TRUE 1 HIGH
FALSE 0 LOW
Logical Operators
Logical operators
mathematically
associate one or more
(logical) input values
with a single (logical)
output value
Logic gates are the
physical devices that
perform logical
operations (for
instance, in circuits)
Basic Logical Operators
One Input
Two (or More) Inputs
NOT
(negation)
OR
(disjunction)
AND
(conjunction)
Switching Circuits
Boolean algebra was first
applied to switching circuits
OR gate
AND gate
Light
Bulb
Battery
Light
Bulb
Battery
x
y
x
y
x y
y
x
In the input, use a '1' to represent a closed switch, a
'0' for an open switch; in the output, use a '1' for a lit
bulb, a '0' for an unlit bulb
Truth Tables
Since there are only two possible values (0 or 1) for
any logical variable, we can define each of the
logical operations by the output they produce given
all of the possible inputs
x
0 1
1 0
NOT
x
x
NOT gate
(inverter)
'
x
or
(Logic) x
or
x
F T
T F
x
Truth Tables
x y xy
0 0 0
0 1 0
1 0 0
1 1 1
AND
x
y
* x y
AND gate
xy
or
. x y (Logic)
or
Truth Tables
x y x + y
0 0 0
0 1 1
1 0 1
1 1 1
OR
x
y
x + y
OR gate
v x y (Logic)
or
Order of Operations
The logical operators
have an order of
precedence:
1. NOT
2. AND
3. OR
'
F = x + yz
( )
G
'
= x + y z
( )
'
H = x + yz
( )
J
'
= x + yz
As usual brackets can
always be used to
change the order of
precedence
Boolean
Expressions
Boolean Postulates
The truth tables for each of the basic logical
operations can also be stated as postulates for a
new kind of algebra a Boolean algebra
0 0 0 0*0 0 = + = P2a P2b
1 1 1 1*1 1 = + = P3a P3b
0 1 1 1*0 0 = + = P4a P4b
1 0 0 1
' '
= = P5a P5b
1 if 0 0 if 1 x x x x = = = = P1a P1b
Boolean
algebra is
closed over
the values
{0, 1}
Boolean Algebra
This new algebra of logical operators has several
properties in common with the more familiar
algebra of addition and multiplication
Commutative Property
Associative Property
The order in which Boolean
variables are ANDed or ORed
doesnt matter to the result
The manner in which ANDed
or ORed Boolean variables
are grouped doesnt matter to
the result
* *
x y
x y y x
y x + = +
=
( ) ( )
( ) ( )
* * * *
x y
x
z x
y z
y
z
z
x y
+ + = + +
=
Boolean Algebra
Boolean algebra has one more property that is not
familiar from the algebra of addition and multiplication
Distributive Property I
( )
* * * x y z x y x z + = +
Distributive Property II
( ) ( ) ( )
* * x y z x y x z + = + +
Relation to Set Theory
The logical operators are related to set theory
NOT
OR
AND
'
x
x + y
* x y
complement
union
intersection
'
x
x y
x y
'
x
x y
x y
x
y
Relation to Set Theory
In terms of set theory, this corresponds to:
0 0 0 0*0 0 = + = P2a P2b
There is no intersection between one
empty set and another empty set.
The union of one empty set and
another empty set is still empty.
CC=C
CC=C
Note: Since a 0 indicates a Boolean value FALSE,
the set of TRUE values with which it is associated is
empty. Hence, a 0 corresponds to the empty set.
Relation to Set Theory
In terms of set theory, this corresponds to:
0 1 1 1*0 0 = + = P4a P4b
There is no intersection between the
entire universe and an empty set.
The union of the entire universe and
an empty set is still the universe.
U U C=
UC=C
Note: Since a 1 indicates TRUE, the set of TRUE
values with which it is associated is the entire universe
of possibilities. Hence, a 1 corresponds to the universe.
Boolean Theorems
In terms of set theory, this corresponds to:
*0 0 x = T9a
There is no intersection between a
set x and an empty set.
x C=C
In terms of truth tables, this corresponds to:
x x * 0
0 0 by P2a
1 0 by P4a
Boolean Theorems
0 x x + = T9b
The union of a set x and an empty
set is still the set x.
x x C=
In terms of truth tables, this corresponds to:
In terms of set theory, this corresponds to:
x x + 0
0 0 by P2b
1 1 by P4b
0 is the identity
element with
respect to OR
Boolean Theorems
In terms of set theory, this corresponds to:
*1 x x = T10a
The intersection between a set x and
the universe is the set x.
x U x =
In terms of truth tables, this corresponds to:
x x * 1
0 0 by P4a
1 1 by P3a
1 is the identity
element with
respect to AND
Boolean Theorems
1 1 x + = T10b
The union of a set x and the universe
is still the universe.
x U U =
In terms of truth tables, this corresponds to:
In terms of set theory, this corresponds to:
x x + 1
0 1 by P4b
1 1 by P3b
Boolean Theorems
* x x x x x x = + = T11a T11b
0 1 * x x x x
'
=
'
+ = T12a T12b
Idempotency Theorems
Inverse Elements
x x x x
''
=
''
= T13a T13b
Double Negation
Both AND and OR are idempotent, meaning that ANDing or
ORing a Boolean variable with itself once has the same effect
as ANDing or ORing the variable with itself many times.
Every Boolean variable has an inverse element given in terms
of the NOT operator.
Absorption Theorems
Absorption theorems
allow the simplification of
circuits by reducing the
number of gates.
x xy x + = T14a
Prove
x
y
x
xy x xy +
(identity element for ) *1 * x xy x x y + = + by T10a AND
( )
(distribution) * 1 x y = + by P8a
*1 x = by T10b
(identity element for ) x = by T10a AND
Proof Using Truth Tables
Boolean proofs may be completed using the theorems
or, equivalently, using truth tables
x
0
0
1
1
y
0
1
0
1
xy
0
1
0
0
x + xy
0
1
1
1
x + y
0
1
1
1
x x y x y
'
+ = + T14d
Prove
x
1
1
0
0
Permutations
are listed in
the order of
the binary
numbers
from 0 to 3
F0
0
0
0
0
0
0
0
0
F1
1
0
0
0
0
0
0
0
F2
0
1
0
0
0
0
0
0
Proof Using Truth Tables
For N variables, there are 2
N

permutations of 0 and 1
There are therefore
possible Boolean functions
for N variables

y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
For instance, for three variables, N = 3:
There are 2
3
= 8 permutations.
Permutations are listed in the order of the
binary numbers from 0 to 7.
There are 2
8
= 256 Boolean functions.
x
0
0
0
0
1
1
1
1
2
2
N
F3
0
0
1
0
0
0
0
0
F4
0
0
0
1
0
0
0
0
F5
0
0
0
0
1
0
0
0
Derived Boolean Operators -
NAND
x y xy (xy)
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
NAND
x
y
NAND gate
( )
'
xy
or
NAND x y
or
| x y
Derived Boolean Operators -
NOR
x y x + y (x + y)
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
NOR
x
y
NOR gate
( )
'
x + y
or
NOR x y
or
+ x y
Derived Boolean Operators
XOR (Exclusive OR)
x y
0 0 0
0 1 1
1 0 1
1 1 0
XOR
x
y
XOR gate
x y
or
XOR x y
x y
Derived Boolean Operators
XNOR (Exclusive NOR or Equivalence)
x y
0 0 0 1
0 1 1 0
1 0 1 0
1 1 0 1
XNOR
x
y
XNOR gate
or
XNOR x y
x y
x y
( )
'
x y
x y
or