Transcript Boolean Logic - Texas State University

EE2420 – Digital Logic
Summer II 2013
Set 2: Boolean Logic
Hassan Salamy
Ingram School of Engineering
Texas State University
Boolean Algebra
2




The basis for much of what we will do in this class is
grounded in Boolean algebra, named for George Boole.
In the early chapters of the textbook we will study the
Theorems and Laws of Boolean Algebra and techniques for
implementing Boolean functions using electronic circuits.
In later chapters we will study how Boolean functions can be
used to implement arithmetic and other useful functions.
Later still we will adapt these techniques to create
components critical to modern computing such as memory
elements and sequence logic.
Electrical Circuits (Over)simplified
3




For those of you who have had no experience with electrical
circuits, the following is a vastly oversimplified primer.
The simple model of matter is that it is made up of atoms which
have positively-charged nuclei orbited by negatively-charged
electrons. Given sufficient energy, an electron can be dislodged
from its atom.
Think of electricity as the flow of energy carried by the movement
of electrons dislodged from atoms.
An electrical circuit is formed when there is a closed path around
which the electrons flow.
Circuits Primer part 2
4







In electrical circuits, we are interested in the movement of energy
from one location to another.
Some elements in a circuit provide energy. These are sources.
Some elements in a circuit expend energy. These are sinks.
The total energy sourced must equal the total energy expended.
We typically measure energy somewhat indirectly. Energy is
measured in Joules (J). Power is energy per unit time. Power is
measured in Watts (W). A Watt is one Joule per second.
1W = 1J/s
A 100W light bulb expends 100 Joules each second.
Circuits Primer part 3
5





We said a 100W light bulb expends 100 Joules each second.
We also said to think of electricity as the flow of energy carried
by the movement of electrons dislodged from atoms.
To get energy to the light bulb, we make a circuit from the power
producing plant to the light bulb.
In that circuit each moving electron is charged with energy at the
source. When an electron passes through the sink (light) that
energy is expended.
The amount of power that can be supplied depends on two
factors:


The number of electrons that can move through the wires
The amount of energy carried with each electron
Circuits Primer part 4
6



The number of electrons flowing in a circuit is called current. Current is
measured in Amperes (A). An Ampere is one Coulomb of electrons per second.
A Coulomb is 6,241,507,648,655,549,400 (approx 6.24 x 1018) electrons.
The amount of energy per electron is called voltage. Voltage is measured in
Volts (V). One Volt is one Joule per Coulomb.
So to determine power we take the product of the number of electrons flowing
(current) and the energy per electron (voltage) and we should get a measure of
power (wattage)

Voltage * Current = Power

In units V*A=W or (J/C)*(C/s) = (J/s)
Circuits Primer part 5
7





Most of the devices that we will be dealing with in this class will operate using
relatively low power circuits.
However, this does not make them 100% safe. It also does not make it
impossible to damage the equipment if used incorrectly.
Electricity flows very easily through most metals, including jewelry. It would be
wise when you are dealing with any circuitry to remove any jewelry from your
hands (rings, watches, etc. ) or long necklaces that could contact the circuitry.
Be careful how you wire the power supply to your circuits. If you reverse the
polarity and try to drive current “backward” through the circuit, you are likely
to cause damage.
Ask your lab monitor if you are not sure.
The Scope of Boolean Algebra
8




In common arithmetic, we are often concerned with the range of values that a
variable may take. This is generally determined by the nature of the problem:
 The integers 1-12 – the month of the year
 A 7-digit decimal integer – local telephone number
 A real number in the interval from 0 to 100 – a test grade
 Imaginary numbers.
For Boolean algebra, every variable is constrained to one of two values: True
or False
Any convenient two-valued pair can be used to represent the True/False pair:
on/off, high/low, clockwise/counter-clockwise, closed/open, loud/soft, 1/0
We will commonly use the 1/0 notation with 1=True and 0=False
Switches
9

A very early electronic implementation of Boolean algebra
recognized that the state of a switch (open or closed) could be
used to represent a Boolean variable (True or False) and that
switches could be wired in combination to represent complex
Boolean algebra equations.
Open Switch
Closed Switch
Electrically-controlled Switches
10




A simple mechanical switch (like a light switch on a wall)
requires physical effort to manually open or close the
contact.
An electrically-controlled switch is opened or closed based
on the state of an input.
For a normally-open switch, when the input is inactive, the
switch is open and when the input is active, the switch closes.
For a normally-closed switch, when the input is inactive, the
switch is closed and when the input is active, the switch opens.
Normally-open
Normally-closed
Types of Switches
11





The earliest devices used for electrically-controlled switching
for Boolean algebra purposes were relays.
A relay uses an input to generate an electromagnetic field
that physically moves the switch contacts into position.
Because relays depend on physical movement of the
contacts, they are too slow for modern digital computing
purposes.
Modern systems use transistors to perform the function of
switches without requiring mechanical movement.
While transistors are complex devices capable of much more
than digital switching, when used for switching they may be
modeled as very simple electrically-controlled switches.
Active-high Input Switching Devices
12

BJT – Bipolar Junction Transistor

MOSFET – Metal-Oxide Semiconductor Field Effect Transistor
Switch
NMOS:
input
NPN BJT
+V=On
Conducting path
Normally-open
Conducting path
Conducting path
input
input
N-channel
MOSFET
0V=Off
Lecture 2: Boolean Logic
12/28
Active-low Input Switching Devices
13

BJT – Bipolar Junction Transistor

MOSFET – Metal-Oxide Semiconductor Field Effect Transistor
Switch
input
PNP BJT
Conducting path
Normally-closed
Conducting path
Conducting path
input
input
P-channel
MOSFET
PMOS:
+V=Off
0V =On
13/28
Switch Logic
14


In the following circuit, the battery is connected to the lamp if
switch A is closed and switch B is closed. If either switch is open,
there is not a complete circuit.
This is the Boolean function AND
Switch A
Battery
Switch B
Lamp
Switch Logic
15


In the following circuit, the battery is connected to the lamp if
switch A is closed or switch B is closed. If either switch is closed,
there is a complete circuit.
This is the Boolean function OR
Switch A
Switch B
Battery
Lamp
Switch Logic
16


In the following circuit, the battery is connected to the lamp and the
output voltage is high if the input to the normally-closed switch is low.
Conversely, when the input is high, the lamp is disconnected and the
output drops to 0.

Therefore, the output is the opposite of the input.

This is the Boolean function NOT
Input
Output
Battery
Lamp
Logic Gates
17

Special circuit symbols are used for the Boolean logic
functions regardless of the type of switches used to
implement the functions.
AND
OR
NOT
Logic circuits
18





Logic circuits perform operations on digital
signals
 Implemented as electronic circuits where
signal values are restricted to a few
discrete values
In binary logic circuits there are only two
values, 0 and 1
Switching
Network
The general form of a logic circuit is a
switching network
In the figure to the right, the inputs are
labeled Xn and the outputs are labeled Yn
Not shown in the figure are the required
connections for providing power to the
circuit.
Y1
Y2
Y3
X1
X2
X3
Yn
Xm
discrete values
Boolean algebra
19

Direct application to switching networks
Work with 2-state devices  2-valued Boolean algebra
(switching algebra)
 Use a Boolean variable (X, Y, etc.) to represent an input or
output of a switching network
 Boolean variable may take on only two values (True, False)
 We will use a notation of 0 for False and 1 for True
 So the possibilities for a variable are: X=0, X=1
 These symbols are not binary numbers, they simply
represent the 2 states of a Boolean variable
 They are not voltage levels, although they commonly refer to
the low or high voltage input/output of some circuit element

Notation Conventions
20



Boolean AND

The raised dot “· ”  x· y

The intersection symbol “”  x  y

No symbol  xy
Boolean OR

Plus sign “+”  x + y

The union symbol “”  x y
Boolean NOT

Single quotation “ ’ ” following  x’

Bar over letter  x

Exclamation point preceding  !x

Tilde preceding  ~x
Inversion of a function
21

If a function is defined as
 f(x1,

Then the complement of f is
 f(x1,

x2)= x1+ x2 = (x1+ x2)’
Similarly, if
 f(x1,

x2)= x1+ x2
x2)= x1 · x2
Then the complement of f is
 f(x1,
x2)= x1 · x2= (x1 · x2)’
Truth tables
22

Tabular listing that fully describes a logic function
 Output
x1
x2
0
0
0
value for all input combinations (valuations)
x1· x2
x1
x2
0
0
0
0
0
1
1
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
1
1
AND
x1 + x2
OR
x1
x1’
NOT
Truth tables
23

Truth table for AND and OR functions of three
variables
Truth tables of functions
24

If L(x,y,z)=x+yz, then the truth table for L is:
+
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
yz
0
0
0
1
0
0
0
1
x+yz
0
0
0
1
1
1
1
1
Logic gates and networks
25

A larger circuit is implemented by a network of
gates
 Called
x
x
x
a logic network or logic circuit
1
2
3
f = (x + x )  x
1
2
3
Logic gates and networks
26

Draw the truth table and the logic circuit for the
following function
 F(a,b,c)
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
ac
0
0
0
0
0
1
0
1
= ac+bc’
bc'
0
0
1
0
0
0
1
0
ac+bc'
0
0
1
0
0
1
1
1
a
c
b
Analysis of a logic network
27

To determine the functional behavior of a logic
network, we can apply all possible input signals to
it
x
x
0 01 1
1 10 0
1
A
0 10 1
0 00 1
11 0 1
B
2
Network that implements f = x1 + x1  x2
f
Analysis of a logic network
28

The function of a logic network can also be
described by a timing diagram (gives dynamic
behavior of the network)
1
x
1 0
x 1
2 0
A
1
0
B
1
0
f
1
0
Time
Timing diagram