Boolean Algebra

Digital Electronics 
2.1 Introduction to AOI Logic
Boolean Algebra
What is Boolean Algebra ?
Boolean Algebra is a mathematical technique that provides
the ability to algebraically simplify logic expressions. These
simplified expressions will result in a logic circuit that is
equivalent to the original circuit, yet requires fewer gates.
Boolean Algebra
Digital Electronics
Simplification
With Boolean
Algebra
Z  BC  AB  AC
Z  A  BC
2
George Boole
Boolean Theorems (1 of 7)
Single Variable - AND Function
My name is George Boole and I lived in
England in the 19th century. My work
on mathematical logic, algebra, and the
binary number system has had a
unique influence upon the
development of computers. Boolean
Algebra is named after me.
Theorem #2
Theorem #3
Theorem #4
X0  0
X 1 X
XX  X
XX0
X
0
3
Project Lead The Way, Inc.
Copyright 2009
Theorem #1
0
X
1
X
X
X
X
X
0
X
X Y
Z
X Y
Z
X Y
Z
X Y
Z
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
4
1
Digital Electronics 
2.1 Introduction to AOI Logic
Boolean Algebra
Boolean Theorems (2 of 7)
Boolean Theorems (3 of 7)
Single Variable - OR Function
Single Variable - Invert Function
Theorem #5
Theorem #6
Theorem #7
Theorem #8
X0 X
X  1 1
XXX
X  X 1
X
0
X
X
1
1
X
X
X
X
Theorem #9
1
X
XX
X
X
X
X Y
Z
X Y
Z
X Y
Z
X Y
Z
0
0
0
0
0
0
0
0
0
0
0
0
X X X
0
1
1
0
1
1
0
1
1
0
1
1
0
1
0
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
5
6
Example #1: Boolean Algebra
Example #1: Boolean Algebra
Example
Example
Simplify the following Boolean expression and note the
Boolean theorem used at each step. Put the answer in
SOP form.
Simplify the following Boolean expression and note the
Boolean theorem used at each step. Put the answer in
SOP form.
F1  A A B  C C D
F1  A A B  C C D
Solution
F1  A A B  C C D
7
Project Lead The Way, Inc.
Copyright 2009
F1  A B  C C D
; Theorem #3
F1  A B  0 D
; Theorem #4
F1  A B  0
; Theorem #1
F1  A B
; Theorem #5
F1  A B
8
2
Digital Electronics 
2.1 Introduction to AOI Logic
Boolean Algebra
Example #2: Boolean Algebra
Example #2: Boolean Algebra
Example
Example
Simplify the following Boolean expression and note the Boolean
theorem used at each step. Put the answer in SOP form.
Simplify the following Boolean expression and note the
Boolean theorem used at each step. Put the answer in
SOP form.
F2  B B C  B C C  A B 1  A B 0
F2  B B C  B C C  A B 1  A B 0
Solution
F2  B B C  B C C  A B 1  A B 0
F2  B C  B C  A B 1  A B 0 ; Theorem #3 (twice)
9
Boolean Theorems (4 of 7)
BC
 A B 1  A B 0 ; Theorem #7
F2 
BC
 A B  A B 0 ; Theorem #2
F2 
BC
AB 
F2 
BC
AB
0
; Theorem #1
; Theorem #5
10
F2  B C  A B
Boolean Theorems (5 of 7)
Commutative Law
Associative Law
Theorem #10A – AND Function
Theorem #11A – AND Function
X (Y Z)  (X Y) Z
X Y  Y  X
Theorem #10B – OR Function
Theorem #11B – OR Function
X  (Y  Z)  (X  Y)  Z
XY Y  X
11
Project Lead The Way, Inc.
Copyright 2009
F2 
12
3
Digital Electronics 
2.1 Introduction to AOI Logic
Boolean Algebra
Boolean Theorems (6 of 7)
Example #3: Boolean Algebra
Example
Distributive Law
Simplify the following Boolean expression and note the
Boolean theorem used at each step. Put the answer in
SOP form.
Theorem #12A – AND Function
X (Y  Z)  X Y  X Z
F3  R T  (R  S)(R  T)
Theorem #12B – OR Function
( X  Y)(W  Z)  XW  XZ  YW YZ
13
14
Boolean Theorems (7 of 7)
Example #3: Boolean Algebra
Example
Consensus Theorem
Simplify the following Boolean expression and note the Boolean
theorem used at each step. Put the answer in SOP form.
Theorem #13A
F3  R T  (R  S)(R  T)
Solution
F3  R T  R  S R  T


X XY  XY

Theorem #13C
X XYXY
F3  R T  R R  R T  S R  S T ; Theorem #12B
F3  R T  0  R T  S R  S T
; Theorem #4
F3  R T  R T  S R  S T
; Theorem #5
F3  T R  R  S  S R
; Theorem #12A
F3
; Theorem #8


 T 1  S   S R
F3  T1  S R
; Theorem #6
F3  T  S R
; Theorem #2
Project Lead The Way, Inc.
Copyright 2009
Theorem #13B
X XY  XY
15
Theorem #13D
X XYXY
16
4
Digital Electronics 
2.1 Introduction to AOI Logic
Boolean Algebra
Example #4: Boolean Algebra
Example #4: Boolean Algebra
Example
Example
Simplify the following Boolean expression and note the Boolean
theorem used at each step. Put the answer in SOP form.
Simplify the following Boolean expression and note the
Boolean theorem used at each step. Put the answer in
SOP form.
F4  P S  P Q S  P Q S
Solution
F4  P S  P Q S  P Q S
F4  P S  P Q S  P Q S



F4  P S  Q S  P Q S ; Theorem #12A
17

F4  P S  Q  P Q S
; Theorem #13C
F4  P S  PQ  P Q S
; Theorem #12A
F4  PS 1  Q   P Q
; Theorem #12A
F4  PS 1   P Q
; Theorem #6
F4  PS  P Q
; Theorem #2
18
Summary
Boolean Theorems
1)
X 0  0
10A)
XY  Y  X
2)
X 1 X
10B)
XY Y  X
3)
XX X
11A)
XYZ   XYZ
4)
XX0
11B)
X  Y  Z    X  Y   Z
5)
X0 X
12A)
6)
X  1 1
12B)
XY  Z   XY  XZ
X  Y W  Z   XW  XZ  YW  YZ
7)
XXX
13A)
X  XY  X  Y
8)
X  X 1
13B)
X  XY  X  Y
9)
XX
13C)
X  XY  X  Y
13D)
X  XY  X  Y
Commutative
Law
Associative
Law
Distributive
Law
Consensus
Theorem
19
Project Lead The Way, Inc.
Copyright 2009
5

Download Report