Transcript Boolean Algebra

Boolean Algebra
Summary
•
•
•
•
•
Digital Circuits (Chips/ICs/Transistors)
Basic Logic gates
Boolean Algebra, Basic Rules and Identities
Logic Simplification using Boolean Algebra
De Morgan’s Theorem and its Application in
Logic Simplification
• Karnaugh Maps – Logic simplification using
K’Maps
• Implicants
Chips/ICs
• Our world is full of integrated circuits (ICs)
• We can found ICs starting from Microprocessor
in our computer to almost every modern
electrical device such as Car, TV, CD Player,
Cell Phone, Electric oven, washing machine etc.
• Made from different electrical components such
as transistors, resistors, capacitors and diodes
Gordon E. Moores’s Laws
• Transistors per an IC: Doubling of the number of
transistors on integrated circuits every two years (at
least for 1 more decade)
• Cost per transistor: As the size of transistors has
decreased, the cost per transistor has decreased as
well
• Computing performance per unit cost: As the size of
transistors shrinks, the speed at which they operate
increases
Transistor count is the most common measure of chip complexity.
Processor
Transistor count
Date of introduction
Manufacturer
Intel 4004
2300
1971
Intel
Intel 8008
2500
1972
Intel
Intel 8080
4500
1974
Intel
Intel 8088
29 000
1979
Intel
Intel 80286
134 000
1982
Intel
Intel 80386
275 000
1985
Intel
Intel 80486
1 200 000
1989
Intel
Pentium
3 100 000
1993
Intel
AMD K5
4 300 000
1996
AMD
Pentium II
7 500 000
1997
Intel
AMD K6
8 800 000
1997
AMD
Pentium III
9 500 000
1999
Intel
AMD K6-III
21 300 000
1999
AMD
AMD K7
22 000 000
1999
AMD
Pentium 4
42 000 000
2000
Intel
Barton
54 300 000
2003
AMD
AMD K8
105 900 000
2003
AMD
Itanium 2
220 000 000
2003
Intel
Itanium 2 with 9MB cache
592 000 000
2004
Intel
Cell
241 000 000
2006
Sony/IBM/Toshiba
Core 2 Duo
291 000 000
2006
Intel
Core 2 Quad
582 000 000
2006
Intel
G80
681 000 000
2006
NVIDIA
POWER6
789 000 000
2007
IBM
Dual-Core Itanium 2
1 700 000 000
2006
Intel
Quad-Core Itanium
Tukwila[1]
2 000 000 000
2008
Intel
Boolean algebra
• There are only two possible values for any quantity and
for any arithmetic operation 1 or 0
• It does not matter how many or few terms we add
together, either.
Addition in Boolean Algebra
• Is not same as real-number algebra
Multiplication in Boolean Algebra
• Is same as in real-number algebra. Anything multiplied
by 0 is 0, and anything multiplied by 1 remains
unchanged
Logic Gates
• A logic gate is an elementary building block of a digital
circuit.
• There are AND, OR, NOT, NAND, NOR, EXOR and
EXNOR gates.
• Most logic gates have two inputs and one output.
• At any given moment, every terminal is in one of the two
binary conditions low (0) or high (1), represented by
different voltage levels.
• The logic state of a terminal can, and generally does,
change often, as the circuit processes data.
• In most logic gates, the low state is approximately zero
volts (0 V), while the high state is approximately five volts
positive (+5 V).
Boolean Addition corresponds to the logical
function of an "OR" gate
Boolean addition corresponds to the logical
function of an “AND" gate
Boolean compliment corresponds to the
logical function of a “NOT" gate
Boolean Identities
• The sum of anything and zero is the same as the
original "anything."
• This identity is no different from its real-number
algebraic equivalent
Boolean Identities
• The sum of anything and one is one
• Different from normal algebra
Boolean Identities
• Adding A and A together
• Is same as connecting both inputs of an OR gate to each other and
activating them with the same signal
Boolean Identities
• The sum of a variable and its complement is 1
Boolean Identities
• Just as there are four Boolean additive identities (A+0, A+1, A+A,
and A+A'), so there are also four multiplicative identities: Ax0, Ax1,
AxA, and AxA'. Of these, the first two are no different from their
equivalent expressions in regular algebra:
Boolean Identities
• The third multiplicative identity: The product of a
Boolean quantity and itself is the original quantity,
since 0 x 0 = 0 and 1 x 1 = 1
Boolean Identities
• The fourth multiplicative identity: The product of a
variable and its complement is 0
Boolean Identities (Summary)
Boolean Identities
• Double complement: a variable inverted twice.
Complementing a variable twice (or any even number of
times) results in the original Boolean value.
Laws of Boolean Algebra
• The commutative law/property tells that, we can reverse the order
of variables that are either added together or multiplied together
without changing the truth of the expression
Laws of Boolean Algebra
•
Associative law tells that, we can associate groups of added or multiplied
variables together with parentheses without altering the truth of the
equations
Laws of Boolean Algebra
•
Distributive property: The Boolean expression formed by the product of a
sum, and in reverse shows how terms may be factored out of Boolean
sums-of-products
Basic Boolean Algebraic properties
• Commutative, Associative, and Distributive
Boolean Rules
• Boolean algebra finds its most practical use in the
simplification of logic circuits.
• If we translate a logic circuit's function into symbolic
(Boolean) form, and apply certain algebraic rules to the
resulting equation to reduce the number of terms and/or
arithmetic operations, the simplified equation may be
translated back into circuit form for a logic circuit
performing the same function with fewer components.
• If a equivalent function may be achieved with fewer
components, the result will be increased reliability and
decreased cost of manufacture.
Boolean Rules
• This rule may be proven symbolically by factoring an "A" out of the
two terms, then applying the rules of A + 1 = 1 and 1A = A to achieve
the final result:
Boolean Rules
Boolean Rules
• Proving using truth table
Boolean Rules
• Simplification of a product-of-sums expression
Boolean Rules (Summary)
DeMorgan's Theorems
DeMorgan's Theorems
•
Reducing the expression (A + (BC)')' to A’BC using DeMorgan's Theorems
DeMorgan's Theorems
•
Reducing the expression (A + (BC)')' to A’BC using DeMorgan's Theorems
DeMorgan's Theorems
• Maintaining the grouping implied by the complementation bars for the
expression is crucial to obtaining the correct answer
DeMorgan's Theorems
•
•
•
Applying the principles of DeMorgan's theorems to the simplification of a gate circuit
Label the outputs of the first NOR gate and the NAND gate
Finally, write an expression (or pair of expressions) for the last NOR gate
DeMorgan's Theorems
•
Reduce the expression using the identities, properties, rules, and theorems
(DeMorgan's) of Boolean algebra
DeMorgan's Theorems (Review)
• DeMorgan's Theorems describe the equivalence between gates with
inverted inputs and gates with inverted outputs. Simply put, a NAND
gate is equivalent to a Negative-OR gate, and a NOR gate is
equivalent to a Negative-AND gate.
• When "breaking" a complementation bar in a Boolean expression,
the operation directly underneath the break (addition or
multiplication) reverses, and the broken bar pieces remain over the
respective terms.
• It is often easier to approach a problem by breaking the longest
(uppermost) bar before breaking any bars under it. You must never
attempt to break two bars in one step!
• Complementation bars function as grouping symbols. Therefore,
when a bar is broken, the terms underneath it must remain grouped.
Parentheses may be placed around these grouped terms as a help
to avoid changing precedence.
Karnaugh Maps
• Applying Boolean algebra can be awkward in order to simplify
expressions
• It is laborious and requires remembering all the laws
• The Karnaugh map provides a simple and straight-forward method
of minimizing Boolean expressions
• With the Karnaugh map Boolean expressions having up to four and
even six variables can be simplified.
• Karnaugh map provides a pictorial method of grouping together
expressions with common factors and therefore eliminating
unwanted variables.
• Karnaugh map can also be described as a truth table.
Karnaugh Maps
• Minterm: (Standard product or canonic product term) such as AB’CD
or A’BCD’ etc. where each variable used once and once only.
• Maxterm: (Standard sum or canonical sum term) such as
(A+B’+C+D) or (A’+B+C+D’) where each variable used once and
once only
• Sum of products: (Minterm canonic form or canonic sum function
f(A,B,C,D)=AB’CD+A’BCD’+A’BC’D
• Product of sums: (Maxterm canonic form or canonic product function
f(A,B,C,D)=(A+B’+C+D) (A’+B+C+D’)(A’+B+C’+D)
• Adjacent Cells: If two occupied cells of a Karnaugh are adjacent,
horizontally, vertically (but not diagonally) then one variable is
redundant. Adjacent cells differ in the value of only one variable.
(Rule of adjacency - can knock off one variable as A+A’=1)
Karnaugh Maps
• Combining all adjacent 1’s more than once doesn’t matter unless no
1 is left out, as A + A = A and A.A = A
• Physical, Logical adjacency
Karnaugh Maps
•
The correspondence between the Karnaugh map and the truth table
•
(two variable)
The values inside the squares are copied from the output column of the truth
table, therefore there is one square in the map for every row in the truth table
Karnaugh Maps
•
•
Consider the following map. The function plotted is:
Z = f(A,B) = A B’+ AB
Referring to the map the two 1’s are grouped together. The variable B has
its true and false form within the group. Eliminate B leaving only A which
only has its true form
•
Using algebric simplication:
Z = A + AB
Z = A( + B)
Z=A
Karnaugh Maps
• Consider the expression z = f(A,B) = A’B’+AB’+A’B plotted on
Karnaugh map:
• The first group labeled I, consists of two 1s which correspond to A =
0, B = 0 and A = 1, B = 0. Put in another way, all squares in this
example that correspond to the area of the map where B = 0
contains 1s, independent of the value of A. So when B = 0 the
output is 1. The expression of the output will contain the term
•
For group labeled II corresponds to the area of the map where A = 0. The
group can therefore be defined as . This implies that when A = 0 the output
is 1. The output is therefore 1 whenever B = 0 and A = 0
Hence the simplified answer is Z = A’ + B’
Karnaugh Maps
•
Given the truth table
The Boolean algebraic expression is
m = a'bc + ab'c + abc' + abc.
Minimization is done as follows.
m = a'bc + abc + ab'c + abc + abc' + abc
= (a' + a)bc + a(b' + b)c + ab(c' + c)
= bc + ac + ab
bc + ac + ab
Karnaugh Maps
•
The Karnaugh map for 4 variables
q = a'bc'd + a'bcd + abc'd' + abc'd + abcd + abcd' + ab'cd + ab'cd'
q = bd + ac + ab
This expression requires 3 2-input
and gates and 1 3-input or gate.
RULE: Minimization is achieved by drawing the smallest possible
number of circles, each containing the largest possible number of 1s.
Karnaugh Maps
• Imlpicant:
Each of the terms i.e product terms that are combined to become sum of products
later on are called implicants
• Prime Imlpicant:
Largest possible group of values. For that group we can not find larger group
An implicant can get submerged in to a prime implicant.
• Essential Prime Imlpicant:
At least one 1 or cell, which not been covered in any other group should be covered
• Non Essential Prime Imlpicant:
One way of combining 1s which is not covered otherwise as a an essential prime
implicant
Gordon E. Moore
• Each year computer chips become more
powerful yet cheaper than the year before.
Gordon Moore, one of the early integrated circuit
pioneers and founders of Intel once said,
• "If the auto industry advanced as rapidly as the
semiconductor industry, a Rolls Royce would get
a half a million miles per gallon, and it would be
cheaper to throw it away than to park it.”