Transcript 1*a - Department of Computer and Information Science

Department of Computer and Information Science,
School of Science, IUPUI
CSCI 240
Boolean Algebra
Dale Roberts, Lecturer
Computer Science, IUPUI
E-mail: [email protected]
Dale Roberts
Boolean Algebra
We observed in our introduction that early in the
development of computer hardware, a decision
was made to use binary circuits because it greatly
simplified the electronic circuit design.
In order to work with binary circuits, it is helpful to
have a conceptual framework to manipulate the
circuits algebraically, building only the final “most
simple” result.
George Boole (1813-1864) developed a
mathematical structure to deal with binary
operations with just two values. Today, we call
these structures Boolean Algebras.
Dale Roberts
Boolean Algebra Defined
A Boolean Algebra B is defined as a 5-tuple
{B, +, *, ’, 0, 1}
+ and * are binary operators; they have two
operands
’ is a unary operator; it has one operand
The following five axioms must hold for any
elements a, b, c  {0,1}
Dale Roberts
Axioms
Law
Form 1
Form 2
Commutative
a+b=b+a
a*b=b*a
Distributive
a + (b * c) = (a + b)*(a + c)
a * (b + c) = (a * b)+(a * c)
Identity
a+0=a
a*1=a
Complement
a + a’ = 1
a * a’ = 0
Dale Roberts
Boolean Algebra is not regular algebra!
We recognize Form 2 of distributive law:
a * (b + c) = (a * b)+(a * c)
(Multiplication is distributive over addition)
Is Form 1 of distributive law is true?
a + (b * c) = (a + b)*(a + c)
4 + (3 * 2) =? (4 + 3)(4 + 2)
4 + 6 =? 7 * 6
10 ≠ 42
Dale Roberts
Terminology
Element 0 is called the zero element. In computer
science, we’ll call the 0 element “FALSE”.
Element 1 is called the unit element. In computer
science, we’ll call the 1 element “TRUE”.
In computer science, we’ll call the + operation “OR”.
The result of + is called sum.
In computer science, we’ll call the * operation “AND”.
The result of * is called product.
In computer science, we’ll call the ’ operation “NOT”.
The result of ’ is called complement.
Juxtaposition implies * operation: ab = a * b
Operator order of precedence is: (), ’, *, +.
a+bc = a+(b*c) ≠ (a+b)*c
ab’ = a(b’) ≠ (a*b)’
Dale Roberts
Single Bit Boolean Algebra
Define a Boolean Algebra where 0
and 1 are bits.
1’ = 0 and 0’ = 1
+
0
1
*
0
1
0
0
1
0
0
0
1
1
1
1
0
1
Dale Roberts
Proof by Truth Table
Consider Form 1 of the distributive theorem: a + (b * c) = (a
+ b)*(a + c). Is it true for a two bit Boolean Algebra?
Can prove using a truth table. How many possible combinations of
a, b, and c are there?
Three variables, each with two values:
2*2*2 = 23 = 8
a
b
c
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
b*c
a+(b*c)
a+b
a+c
(a+b)*(a+c)
Dale Roberts
Proof by Truth Table (cont)
Consider Form 1 of the distributive theorem: a + (b * c) =
(a + b)*(a + c). Is it true for a two bit Boolean Algebra?
Can prove using a truth table. How many possible
combinations of a, b, and c are there?
Three variables, each with two values: 2*2*2 = 23 = 8
a
b
c
b*c
a+(b*c)
a+b
a+c
(a+b)*(a+c)
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Dale Roberts
n-bit Boolean Algebra
Single bit Boolean Algebra can be extended
to n-bit Boolean Algebra by define sum,
product and complement as bit-wise
operations
Let a = 1101010, b = 1011011
a + b = 1101010 + 1011011 = 1111011
a * b = 1101010 * 1011011 = 1001010
a’ = 1101010’ = 0010101
Dale Roberts
Principle Duality
The dual of a statement S is obtained by
interchanging * and +; 0 and 1.
Write the dual of (a*1)*(0+a’) = 0.
(a+0)+(1*a’) = 1
Did you notice that all the original axioms
are duals of each other?
Thus, the dual of any theorem in a Boolean
Algebra is also a theorem.
This is called the Principle of Duality.
Dale Roberts
Named Theorems
All of the following theorems can be proven based on the
axioms. They are used so often that they have names.
Idempotent
a+a=a
a*a=a
Boundedness
a+1=1
a*0=0
Absorption
a + (a*b) = a
a*(a+b) = a
Associative
(a+b)+c=a+(b+c)
(a*b)*c=a*(b*c)
The theorems can be proven for a two-bit Boolean Algebra
using a truth table, but you must use the axioms to
prove it in general for all Boolean Algebras.
Dale Roberts
More Named Theorems
Involution
(a’)’ = a
DeMorgan’s
(a+b)’ = a’ * b’
(a*b)’=a’ + b’
DeMorgan’s Laws are particularly important in circuit
design. It says that you can get rid of a complemented
output by complementing all the inputs and changing
ANDs to ORs. (More about circuits coming up…)
Dale Roberts
Proof using Theorems
Use the properties of Boolean Algebra to reduce
(x + y)(x + x) to x. Warning, make sure you use
the laws precisely.
(x + y)(x + x)
Given
(x + y)x
Idempotent
x(x + y)
Commutative
x
Absorption
Unlike truth tables, proofs using Theorems are valid for any
boolean algebra, but just bits.
Dale Roberts
Standard Form
Like regular algebra, Boolean equations can be
expressed as a sum of products. Each product
is a term of the equation.
Consider the term xyx’z. We define a term to be
a Fundamental Product (FP) if it does not repeat
any literal. Since our term repeats x, is it not FP.
You call always minimize a term to make it FP.
xyx’z = xx’yz = 0yz (which law) = 0 (which law?)
An expression E is sum-of-products form if it is
the sum of one ore more FPs, none of which is
included in another.
Dale Roberts
Sum-of-Products Form
1. Consider E=xz’ + y’z + xyz’.
This is a sum of products, but is not sum-of-products form
because xz’ is contained within xyz’. i.e. it can be
reduced. (which law?)
2. Consider E=xz’ + x’yz’ + xy’z.
This is already sum-of-products form.
Any non-zero Boolean expression can be changed to sumof-products form. (By duality, there is also a product-ofsums form, but it is used less often.)
Dale Roberts
Converting to Sum-of-Products Form
1. Use DeMorgan’s Laws and Involution to
move complements inside parenthesis
until only variables are complemented.
2. Use distributive law to transform in to
sum of products
3. Use commutative, idempotent, and
complement laws to transform each
term into 0 or FP.
4. Use absorption law to make sum-ofproducts form.
Dale Roberts
Example of conversion to sum-of-products form
Consider E=((ab)’c)’((a’+c)(b’+c’))’
E=((ab)’’+c’)((a’+c)’+(b’+c’)’) – DeMorgan’s Law
E=(ab+c’)(ac’+bc) – DeMorgan’s and Involution Laws
E=abac’ + abbc +ac’c’ + bcc’ – Distributive Law
E=abc’ + abc + ac’ + 0 – Idempotent and Complement
E=ac’ + abc – Absorption Law
Dale Roberts
Complete Sum-of-Products Form
A complete sum-of-products form is a sum-ofproducts form where each term involves all the
variables. (Each term will have the same
number of literals.
You can add missing variables by multiplying by
1, where 1 is of the form x + x’.
Theorem: Every non-zero Boolean expression
can be placed in complete sum-of-products
form, and it is unique.
Dale Roberts
Complete Sum-of-Products Example
Express E(x,y,z) = (x’ + y)’ + x’y in complete sumof-products form.
E = xy’ + x’y – DeMorgan’s Law.
If we didn’t know z was involved, we’d think we
were done.
E=xy’(z + z’) + x’y(z + z’)
E=xy’z + xy’z’ + x’yz + x’yz’ – Distributive Law
(Don’t simplify using Absorption, or you’ll take it
back out of Complete S-O-P form)
Dale Roberts
Sources
Lipschutz, Discrete Mathematics
Mowle, A Systematic Approach to Digital Logic
Design
Dale Roberts