CKV
Digital Design
CS/EEE/ECE/INSTR F215
Lecture 4: Boolean algebra
8/27/2020 1
CKV
Boolean Algebra
Postulates of Boolean Algebra
Duality Principle
8/27/2020 2
CKV
Boolean Algebra
Applying Duality
8/27/2020 3
CKV
Boolean Algebra
Some important Theorems
DeMorgan’s Th.
8/27/2020 4
CKV
Boolean Algebra
Theorems can be proved in two ways
-using Postulates
8/27/2020 5
CKV
Boolean Algebra
Theorems can be proved in two ways
-using Truth tables
x y xy x+xy x
0 0 0 0 0
0 1 0 0 0
1 0 0 1 1
1 1 1 1 1
8/27/2020 6
CKV
Boolean Functions
Consists of binary variables, constants and Logic symbols
Single variable in normal or complemented form - literal
Can be transformed into circuit
8/27/2020 7
CKV
Boolean Functions
Boolean function can be represented by truth table in
only one way
x y z F1 F2
0 0 0 0 1
0 0 1 0 1
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 1 0
1 1 0 1 0
1 1 1 1 0
8/27/2020 8
CKV
Boolean Functions
Boolean function can be represented in many ways in
algebraic form
Both represent same function ?
Implementation of both same ? Try it out
Need for simplification
8/27/2020 9
CKV
Boolean Functions
Ways of simplification
-Algebraic manipulation
-K Maps
-QM(Quine-McCluskey) Method
8/27/2020 10
CKV
Boolean Functions
Algebraic manipulation done using postulates and
theorems
For example: 1 Not, 1 OR, 1 AND
1 AND
8/27/2020 11
CKV
Boolean Functions
Canonical Forms-Type1
x y F1 x y F2
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 1 1 0
x y F3
0 0 1
0 1 0
1 0 0
1 1 1
8/27/2020 12
CKV
Boolean Functions
Each input entry will be represented by a term
x y
Designation
F3
0 0 1
0 1 0
1 0 1
1 1 1
Minterms
Standard Product
Sum of Products
(Canonical form-Type1)
8/27/2020 13
CKV
Boolean Functions
Canonical Forms-Type2
x y F1 x y F2
0 0 0 0 0 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
x y F3
0 0 0
0 1 1
1 0 1
1 1 0
8/27/2020 14
CKV
Boolean Functions
Each input entry will be represented by a term
x y
Designation
F3
0 0 0
0 1 1
1 0 0
1 1 0
Maxterms
Standard Sums
Product of Sums
(Canonical form-Type2)
8/27/2020 15
CKV
Boolean Algebra
Some important Theorems
DeMorgan’s Th.
8/27/2020 16
CKV
Boolean Algebra
Theorems can be proved in two ways
-using Truth tables
x y xy x+xy x
0 0 0 0 0
0 1 0 0 0
1 0 0 1 1
1 1 1 1 1
8/27/2020 17
CKV
Boolean Functions
Consists of binary variables, constants and Logic symbols
Single variable in normal or complemented form - literal
Can be transformed into circuit
8/27/2020 18
CKV
Boolean Functions
Boolean function can be represented by truth table in
only one way
x y z F1 F2
0 0 0 0 1
0 0 1 0 1
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 1 0
1 1 0 1 0
1 1 1 1 0
8/27/2020 19
CKV
Boolean Functions
Boolean function can be represented in many ways in
algebraic form
Both represent same function
Implementation of both same? Try it out
Need for simplification
8/27/2020 20
CKV
Boolean Functions
Algebraic manipulation done using postulates and
theorems
For example: 1 Not, 1 OR, 1 AND
1 AND
8/27/2020 21
CKV
Boolean Functions
Before learning
-K Maps
-QM(Quine-McCluskey) Method
Canonical and standard forms of Boolean functions
8/27/2020 22
CKV
Boolean Functions
Canonical Forms-Type1
x y F1 x y F2
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 1 1 0
x y F3
0 0 1
0 1 0
1 0 0
1 1 1
8/27/2020 23
CKV
Boolean Functions
Each input entry will be represented by a term
x y
Designation
F3
0 0 1
0 1 0
1 0 1
1 1 1
Minterms
Standard Product
Sum of Products
(Canonical form-Type1)
8/27/2020 24
CKV
Boolean Functions
Canonical Forms-Type2
x y F1 x y F2
0 0 0 0 0 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
x y F3
0 0 0
0 1 1
1 0 1
1 1 0
8/27/2020 25
CKV
Boolean Functions
Each input entry will be represented by a term
x y
Designation
F3
0 0 0
0 1 1
1 0 0
1 1 0
Maxterms
Standard Sums
Product of Sums
(Canonical form-Type2)
8/27/2020 26
CKV
Boolean Functions
Canonical forms from Truth table
Sum of Products Representation ?
x y z F
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
Product of Sums Representation ?
1 0 1 0
1 1 0 0
1 1 1 1
8/27/2020 27
CKV
Boolean Functions
Can we convert from one canonical form to another ?
x y z F Using Truth Table
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
Minterm and Maxterm are Complementary to each other
8/27/2020 28
CKV
Boolean Functions
x y z F F’
0 0 0 0 1
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 0
8/27/2020 29
CKV
Boolean Functions
Express in minterms:
Simplify
F= m7 + m6 + m3 + m2
8/27/2020 30
CKV
Boolean Functions
Express in minterms:
x y z x’yz’ F
0 0 0 0 0
0 0 1 0 0
F= m2 + m3 + m6 + m7
0 1 0 1 1
0 1 1 0 1
1 0 0 0 0
1 0 1 0 0
F= M0.M1. .M4.M5
1 1 0 0 1
1 1 1 0 1
8/27/2020 31
CKV
Boolean Functions
Standard Form – Terms that form the function may contain one,
two or many literals
Sum of Products
Product of Sums
How is it different from canonical form ??
8/27/2020 32
CKV
Boolean Functions
Some times standard forms result in better implementation
What form ??
Standard Form
SPOT THE DIFF ??
8/27/2020 33
CKV
Thank You
8/27/2020 34
