Lecture 6-
7
Boolean Expressions forms and
simplification
Forms of Boolean Expressions
• Sum-of-products form (SOP)
– first the product (AND) terms are formed then these are summed (OR)
– Ex: ABC + DEF + GHI
• Product-of-sum form (POS)
– first the sum (OR) terms are formed then the products are taken (AND)
– Ex: (A+B+C) (D+E+F) (G+H+I)
• Both forms are dual of each other.
Forms of Boolean Expressions
▪ Canonical Form
▪ Canonical form is not efficient but sometimes
useful in analysis and design
▪ In an expression in canonical form, every variable
appears in every term. Ex.
f(A,B,C, D) = ABC’D + AB’CD + AB’CD’ Canonical SOP
f(A,B,C,D) =(A+B+C’+D) (A+B’+C+D) (A+B’+C+D’) Canonical POS
▪ Note that the dot (meaning AND) is often omitted.
Forms of Boolean Expressions
• An SOP expression can be forced into canonical form by ANDing the
incomplete terms with terms of the form (X + X’) where X is the name of
the missing variable.
Ex.-
f( A,B,C) = (A+B) (B+C)
= (A+B+C.C’) (A.A’+B+C)
= (A+B+C) (A+B+C’) (A+B+C)
(A’+B+C)
= (A+B+C) (A+B+C’) (A’+B+C)
• The product term (Logical AND term) in a canonical SOP expression is
called a ‘min-term’.
• The sum term (Logical OR term) in a canonical POS expression is called a
‘max-term’.
• Both canonical SOP and canonical POS forms are Dual to each other.
Example: A Notation using Canonical Form
▪ Each output variable can be expressed in following two ways.
▪ Canonical SOP form (Sum of Min-terms for which output is 1)
▪ Canonical POS form (Product of Max-terms for which output is 0)
Canonical SOP form (Sum of Min-terms)
f(p, q, r)= p’qr + pq’r + pqr’+ pqr
f(p, q, r) = m3 + m5 + m6 + m7
f(p, q, r)= ∑ (3,5,6,7)
Canonical POS form (Product of Max-terms)
f(p, q, r) = (p+q+r). (p+q+r’)
.(′p+q’+r).(p’+q′+r)
f(p, q, r) = M0 . M1. M2 . M4
f(p, q, r)= ∏ (0,1,2,4)
Example
▪ Consider the following Boolean expression:
F = x y + x’ z
F(x, y, z) = ∑(1, 3, 6, 7)
Or
F(x, y, z) = ∏(0, 2, 4, 5)
Example
Convert the following expression into Canonical SOP
expression.
f(A,B,C)= A’B+C’+ABC
Sol.: f(A,B,C)= A’B (C+C’)+ (A+A’)(B+B’)C’ +ABC
=A’BC+A’BC’+ABC’+AB’C’+A’BC’+A’B’C’+ABC
= A’BC+ A’BC’+ ABC’+AB’C’+A’B’C’+ABC
Example
Convert the following expression into Canonical
SOP expression.
f(x, y, z)= x + y’z
Sol.: f(x, y, z)= x(y + y’) (z + z’) +(x+x’) y’z
= xyz + xyz’+ xy’z+ xy’z’+ xy’z + x’y’z
= xyz + xyz’+ xy’z + xy’z’+ x’y’z
Example
▪ Consider the function F(A, B, C) = ∑(1,4,5,6,7). Find
the Complement of it.
Solution: F = ∑(1,4,5,6,7) = m0+m4+m5+m6+m7
F’ = ∑ (0, 2, 3) = m0+m2+m3
OR SOP
F= ∏ (0,2,3)= M0.M2.M3
F’= ∏(1,4,5,6,7)= M1.M4.M5.M6.M7
POS
Simplification of Logic Circuits
• First obtain one expression for the circuit, then try to
simplify.
• Example: Two methods for simplifying
– Algebraic method (use Boolean algebra theorems)
– Karnaugh mapping method (systematic, step-by-step approach)
Example
• Simplification of logic circuits using Algebraic method (use
Boolean algebra theorems)
For the given logic circuit: a) Write the Boolean expression for the original
circuit . b) Simplify the Boolean expression. c) Draw the simplified circuit .
Example
Example
Example
Comparative Analysis of Boolean Forms
NAND AND NOR IMPLEMENTATION
Example
▪ Express the Boolean function F = x y + x’ z as a
product of max-terms.
• F = xy + x’z = (xy + x’)(xy + z) Distributive law
= (x + x’)(y + x)(x + z)(y + z)
= (x + y)(x + z)(y + z)
Problem and Discussion
Q.1. Express the following function in sum of min-terms and
product of max-terms:
F(A,B,C,D)= B’D+A’D+BD
Sol.
SOP/POS Conversion