Week 4
Boolean Functions and their Forms
Week 4: Boolean Functions and their Forms
Learning Outcomes
1. Express Boolean functions into Canonical and Standard forms
2. Obtain the Boolean function from reading the truth tables
3. Construct two-level implementation circuit diagrams of Boolean functions
Week 4: Boolean Functions and their Forms
The Canonical Forms
• Each term has all the variables (primed or unprimed) present.
• Product or implicant – a Boolean term of one or more literals joined by the AND
operation.
• Sum - a Boolean term of one or more literals joined by the OR operation
• Minterm – a product term involving all inputs
• E.g., 𝑥𝑦 ′ 𝑧 (a three-variable minterm)
• Maxterm - a sum term involving all inputs
• E.g., 𝐴 + B′ (a two-variable maxterm)
Week 4: Boolean Functions and their Forms
Minterms and Maxterms
𝒙 𝒚 𝒛 Minterm Designation Maxterm Designation
0 0 0 𝑥 ′𝑦′𝑧′ 𝑚0 𝑥+𝑦+𝑧 𝑀0
0 0 1 𝑥 ′𝑦′𝑧 𝑚1 𝑥 + 𝑦 + 𝑧′ 𝑀1
0 1 0 𝑥 ′ 𝑦𝑧 ′ 𝑚2 𝑥 + 𝑦′ + 𝑧 𝑀2
0 1 1 𝑥 ′ 𝑦𝑧 𝑚3 𝑥 + 𝑦 ′ + 𝑧′ 𝑀3
1 0 0 𝑥𝑦 ′ 𝑧 ′ 𝑚4 𝑥′ + 𝑦 + 𝑧 𝑀4
1 0 1 𝑥𝑦 ′ 𝑧 𝑚5 𝑥 ′ + 𝑦 + 𝑧′ 𝑀5
1 1 0 𝑥𝑦𝑧 ′ 𝑚6 𝑥 ′ + 𝑦′ + 𝑧 𝑀6
1 1 1 𝑥𝑦𝑧 𝑚7 𝑥 ′ + 𝑦 ′ + 𝑧′ 𝑀7
Week 4: Boolean Functions and their Forms
Sum of Minterms, Product of Maxterms
• Sum of Minterms – a Boolean function of minterms joined by OR operations
• E.g., 𝑓 = 𝑥𝑦𝑧 ′ + 𝑥 ′ 𝑦 ′ 𝑧 + 𝑥𝑦 ′ 𝑧
• Product of Maxterms – a Boolean function of maxterms joined by AND operations
• E.g., 𝑓 = (𝑥 + 𝑦)(𝑥 + 𝑦 ′ )(𝑥 ′ + 𝑦 ′ )
• Functions can be expressed in canonical form:
• By manipulating the Boolean expression
• By using the truth table.
Something to think about:
Find out how to express a function in sum-of-minterms form to an equivalent sum-of-
maxterms form.
Week 4: Boolean Functions and their Forms
Sum of Minterms, Product of Maxterms
Express the Boolean function 𝐹 = 𝐴′ 𝐵 + b) Truth table of 𝐹 = 𝐴′ 𝐵 + 𝐵 ′ 𝐶
𝐵 ′ 𝐶 in Sum of Minterms form (a) by
Algebraic manipulation, (b) by using the 𝑨 𝑩 𝑪 𝑭 Minterm
truth table. 0 0 0 0
0 0 1 1 𝑚1
a) 𝐹 = 𝐴′ 𝐵 + 𝐵 ′ 𝐶 0 1 0 1 𝑚2
= 𝐴′ 𝐵 𝐶 + 𝐶 ′ + 𝐵 ′ 𝐶 𝐴 + 𝐴′ 0 1 1 1 𝑚3
1 0 0 0
= 𝐴′ 𝐵𝐶 + 𝐴′ 𝐵𝐶 ′ + 𝐴𝐵 ′ 𝐶 + 𝐴′ 𝐵 ′ 𝐶 1 0 1 1 𝑚5
= 𝐴′ 𝐵 ′ 𝐶 + 𝐴′ 𝐵𝐶 ′ + 𝐴′ 𝐵𝐶 + 𝐴𝐵 ′ 𝐶 1 1 0 0
1 1 1 0
= 𝑚1 + 𝑚2 + 𝑚3 + 𝑚5
𝐹 𝐴, 𝐵, 𝐶 = ∑ 1,2,3,5
Week 4: Boolean Functions and their Forms
Sum of Minterms, Product of Maxterms
b) Truth table of
Express the Boolean function 𝐹 = 𝐴′ 𝐵 + 𝐵 ′ 𝐶 in 𝐹 = (𝐴′ + 𝐵 ′ )(𝐴′ + 𝐶)(𝐵 + 𝐶)
Product of Maxterms form (a) by Algebraic 𝑨 𝑩 𝑪 𝑭 Maxterm
manipulation, (b) by using the truth table. 0 0 0 0 𝑀0
a) 𝐹 = 𝐴′ 𝐵 + 𝐵 ′ 𝐶 0 0 1 1
0 1 0 1
= 𝐴′ 𝐵 + 𝐵 ′ 𝐴′ 𝐵 + 𝐶 0 1 1 1
𝐹 = (𝐴′ + 𝐵 ′ )(𝐵 + 𝐵 ′ )(𝐴′ + 𝐶)(𝐵 + 𝐶) 1 0 0 0 𝑀4
1 0 1 1
= 𝐴′ + 𝐵′ 𝐴′ + 𝐶 𝐵 + 𝐶 1 1 0 0 𝑀6
1 1 1 0 𝑀7
= 𝐴′ + 𝐵′ + 𝐶𝐶 ′ 𝐴′ + 𝐶 + 𝐵𝐵 ′ 𝐵 + 𝐶 + 𝐴𝐴′
= 𝐴′ + 𝐵′ + 𝐶 𝐴′ + 𝐵′ + 𝐶 ′ 𝐴′ + 𝐵 + 𝐶 𝐴′ + 𝐵 ′ + 𝐶 𝐴 + 𝐵 + 𝐶 𝐴′ + 𝐵 + 𝐶
= 𝐴′ + 𝐵 ′ + 𝐶 ′ 𝐴′ + 𝐵 ′ + 𝐶 𝐴′ + 𝐵 + 𝐶 𝐴 + 𝐵 + 𝐶
= 𝑀0 ⋅ 𝑀4 ⋅ 𝑀6 ⋅ 𝑀7
Week 4: Boolean Functions and their Forms
The Standard Forms
• Provides Boolean functions with any number of variables composing the sum or
product terms.
• Sum of Products – product terms joined by the OR operation
• E.g., 𝑥 + 𝑦 ′ 𝑧
• Product of Sums – sum terms joined by the AND operation
• E.g., 𝑥(𝑦 + 𝑧)(𝑥 ′ + 𝑦 ′ )
Something to think about:
You’ve probably noticed that we can convert a Boolean function in standard form to its
equivalent canonical form. How about the other way around?
Week 4: Boolean Functions and their Forms
The Standard Forms
• Provides Boolean functions with any number of variables composing the sum or
product terms.
• Sum of Products – product terms joined by the OR operation
• E.g., 𝑦 ′ + 𝑥 + 𝑦𝑧
• Product of Sums – sum terms joined by the AND operation
• E.g., 𝑥(𝑦 + 𝑧)(𝑥 ′ + 𝑦 ′ )
• Results in a two-level logic diagram implementation of AND and OR gates; Inverters
are not considered, but are assumed that complements are readily available.
Week 4: Boolean Functions and their Forms
Examples of Two-level Implementations
• Two-level implementation of a function in sum-of-products form
• Two-level implementation of a function in product-of-sums form
Week 4: Boolean Functions and their Forms
Boolean Functions of 𝒏 Variables
• No variables; results in either of two constant functions,
• 𝑓 = 0 or 𝑓 = 1
• One Variable, four Boolean functions
• 𝑓=0
• 𝑓=𝑥
• 𝑓 = 𝑥′
• 𝑓=1
• Two Variables, 16 Boolean Functions
𝑛
• In general, for 𝑛 number of variables, we can construct 22 Boolean functions
Thank You!
