UNIVERSITY OF SAINT LOUIS

Tuguegarao City

SCHOOL OF ENGINEERING, ARCHITECTURE, AND INFORMATION TECHONOLOGY EDUCATION

First Semester
S.Y. 2020-2021

CORRESPONDENCE LEARNING MODULE

Logic Circuit and Switching Theory

Prepared by:

JAY M. VENTURA, MIT

Instructor

Reviewed by:

JAY M. VENTURA, MIT

Program Chair/Department Head

Recommended by:

RONALD M. VILLAVERDE, ME-ECE, PECE

Academic Dean

Approved by:

EMMANUEL JAMES P. PATTAGUAN, Ph.D.

VP for Academics
 CLO1 Correctly Boolean Modular Week Digital Logic-
identify logic Algebra and learning 2, 3 design: Circuit
gates to use Logic gates with an Design
in different introductio
designs; Definitions n to the
Functions Verilog Laborator
Convert HDL -
Boolean y
Canonical and Chapter 2
function to its Experime
Standard forms page 38- nt-1
equivalent 58
logic circuit.

For this week, August 31 – September 4, 2020 of this grading period, the following shall be your guide for the
different lessons and tasks that you need to accomplish. Be patient, read it carefully before proceeding to the
tasks expected of you.
GOOD LUCK!

Content
Chapter 1: BOOLEAN ALGEBRA
• Canonical and Standard Forms
Learning Outcomes
•
I. LEARNING CONTENT

A. Minterms and Maxterms

Canonical Form – In Boolean algebra, function can be expressed as Canonical Disjunctive Normal Form known as
minterm and some are expressed as Canonical Conjunctive Normal Form known as maxterm.

Minterm – is the product of n literals in which each variable appears exactly once either in T or F form, but not in
both. (Also known as a standard product term). Each minterm has value 1 for exactly one combination of values of
variables.

Maxterm – is the sum of n literals in which each variable appears exactly once in T or F from, but not in both. Each
maxterm has a value of 0 for exactly one combination of values of variables.

In other words:

Minterm, we look for the functions where the output results in “1”.
Maxterm we look for function where the output results in “0”.

Table 1: Minterms and Maxterm for Three Binary Variables

Minterms maxterms

x y z Term Designation Term 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

Explanation:

1. Since Minterms only consider 1 as an output, let’s take a look at 𝑚0 or minterm 0,

𝑥′𝑦’𝑧’ is equal to 1, the value of 𝑥 = 0, 𝑦 = 0, 𝑎𝑛𝑑 𝑧 = 0 taking the complement we have 𝑥’ = 1, 𝑦’ =

1, 𝑎𝑛𝑑 𝑧’ = 1 , the operation used in minterms is AND operation, we then get the function 𝑥’𝑦’𝑧’ or
1 𝐴𝑁𝐷𝑒𝑑 1 𝐴𝑁𝐷𝑒𝑑 1 = 1; Take note that the output of AND operation is equal to 1 if all the inputs is equal
to 1 otherwise the output is equal to 0.

2. Maxterm only consider 0 as an output, let’s take a look at 𝑀0 or Maxterm 0

 𝑥 + 𝑦 + 𝑧 is equal to 0, the value of 𝑥 = 0, 𝑦 = 0, 𝑎𝑛𝑑 𝑧 = 0, the operation used in maxterms is OR operation.
Take note that the output of OR operation is equal to 0 if all the inputs is equal to 0 otherwise the output is equal
to 1.

A Boolean function can be represented using minterms. For example, the function in the table 2 is determined by
expressing the combinations 001 , 1000 , and 111 as 𝑥’𝑦’𝑧 , 𝑥𝑦’𝑧’, and 𝑥𝑦𝑧 , respectively. Since each one of these
minterms results in 𝑓1 = 1, we should have

𝑓1 = 𝑥 ′ 𝑦 ′ 𝑧 + 𝑥𝑦 ′ 𝑧 ′ + 𝑥𝑦𝑧 = 𝑚1 + 𝑚4 + 𝑚7

Similarly, it may be easily verified that

𝑓2 = 𝑥 ′ 𝑦𝑧 + 𝑥𝑦 ′ 𝑧 + 𝑥𝑦𝑧 ′ + 𝑥𝑦𝑧 = 𝑚3 + 𝑚5 + 𝑚6 + 𝑚7

These examples demonstrate an important property of Boolean algebra: any Boolean function can e expressed as
sum of minterms (by “sum” is meant the ORing of terms)
x y z Function 𝒇𝟏 Function 𝒇𝟐

0 0 0 0 0

0 0 1 1 0

0 1 0 0 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 1

Now consider the complement of a Boolean function, if we are going to consider those combination have 0 as
output and then we are going to use OR operations we will have the function:

𝑓1′ = 𝑥 ′ 𝑦 ′ 𝑧 ′ + 𝑥𝑦 ′ 𝑧 + 𝑥 ′ 𝑦𝑧 ′ + 𝑥 ′ 𝑦𝑧 + 𝑥𝑦 ′ 𝑧 + 𝑥𝑦𝑧′

If we take the complement of 𝑓1′ , we obtain the function 𝑓1 :

𝑓1 = (𝑥 + 𝑦 + 𝑧)(𝑥 + 𝑦 ′ + 𝑧 ′ )(𝑥 ′ + 𝑦 + 𝑧′(𝑥 ′ + 𝑦 ′ + 𝑧)

𝑓1 = 𝑀0 • 𝑀2 • 𝑀3 • 𝑀5 • 𝑀6

Similarly, it is possible to read the expression for 𝑓2 from the table:

 𝑓2 = (𝑥 + 𝑦 + 𝑧)(𝑥 + 𝑦 + 𝑧 ′ )(𝑥 + 𝑦 ′ + 𝑧)(𝑥 ′ + 𝑦 + 𝑧)

𝑓2 = 𝑀0 𝑀1 𝑀2 𝑀4

These examples demonstrate a second important property of Boolean algebra: any Boolean function can be
expressed as a product of maxterm (by “product” is meant the ANDing of terms). The procedure for obtaining the
product of maxterms directly from the truth table is as follows. Form a maxterm for each combination of the
variables that produces 0 in the function, and then form the AND of all those maxterms. Boolean functions
expressed as a sum of minterms or product of maxterms are said to be in canonical form.

Sum of Minterms

It was previously stated that for n binary variables, one can obtain 2𝑛 distinct minterms, and that any Boolean
function can be expresses as sum of minterms. The minterms whose sum defines the Boolean functions are those
that give the 1’s of the function in a truth table.

Note that if one or more variables is missing in a given function, just AND the term by the expression such as 𝑥 +
𝑥’ by postulate 5, since this will give you 1. To clarify this statement/procedure lets take a look at the example
below.

Example: Express the Boolean function 𝐹 = 𝐴 + 𝐵′𝐶 in sum of minterms.

Solution: Note that the function F has three variables, the first term is missing two variables; therefore:

𝐴 = 𝐴(𝐵 + 𝐵′ ) = 𝐴𝐵 + 𝐴𝐵"

This is still missing one variable; therefore:

𝐴 = 𝐴𝐵(𝐶 + 𝐶 ′ ) + 𝐴𝐵′(𝐶 + 𝐶 ′ )

= 𝐴𝐵𝐶 + 𝐴𝐵𝐶 ′ + 𝐴𝐵′ 𝐶 + 𝐴𝐵′𝐶′

The second term 𝐵′𝐶 is missing one variable; therefore

𝐵′ 𝐶 = 𝐵′ 𝐶(𝐴 + 𝐴′ ) = 𝐴𝐵′ 𝐶 + 𝐴′𝐵′𝐶

Combining all terms, we have

𝐹 = 𝐴 + 𝐵′𝐶

= 𝐴𝐵𝐶 + 𝐴𝐵𝐶 ′ + 𝐴𝐵′ 𝐶 + 𝐴𝐵′ 𝐶 ′ + 𝐴𝐵′ 𝐶 + 𝐴′𝐵′𝐶

But 𝐴𝐵′𝐶 appear twice, and according to theorem 1 (𝑥 + 𝑥 = 𝑥), it is possible to remove one of them. Rearranging
the minterms in ascending order, we finally obtain

𝐹 = 𝐴′ 𝐵′ 𝐶 + 𝐴𝐵′ 𝐶 ′ + 𝐴𝐵′ 𝐶 + 𝐴𝐵𝐶 ′ + 𝐴𝐵𝐶

= 𝑚1 + 𝑚4 + 𝑚5 + 𝑚6 + 𝑚7

It is sometimes convenient to express the Boolean function, when its sum of minterms, in the following short
notation:

𝐹(𝐴, 𝐵, 𝐶) = ∑(1,4,5,6,7)
 The summation symbol ∑ stands for ORing of terms; the numbers following it are the minterms of the function.

The alternative procedure for deriving the minterms of a Boolean function is to obtain the truth table of the
function directly form the algebraic expression and then read the minters from the truth table. Let’s consider again
the first example:

𝐹 = 𝐴 + 𝐵′𝐶

A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
Note: To do your truth table faster just understand the function, in our example, it means that the function is equal
to 1 when A=1 or BC=01.

Product of Maxterm

To express Boolean function as product of maxterm, it must be first be converted to a form or OR terms.
You can do this by applying the distributive law which is 𝑥 + 𝑦𝑧 = (𝑥 + 𝑦)(𝑥 + 𝑧). Then any missing variable 𝑥 in
each OR terms is ORed it with 𝑥𝑥’.

Example: Express the Boolean function 𝐹 = 𝑥𝑦 + 𝑥′𝑧 in a product of Maxterm

Solution:

1. Convert the function into OR terms using distributive law.

𝐹 = 𝑥𝑦 + 𝑥 ′ 𝑧 if we assume that 𝑥𝑦 = 𝐴 then we will have the function
= 𝐴 + 𝑥′𝑧 Using distributive law, we will have the expression
= (𝐴 + 𝑥 ′ )(𝐴 + 𝑧) Substituting the value of 𝐴 = 𝑥𝑦, we will have the resulting function equal
to:
This is term = (𝑥𝑦 + 𝑥 ′ )(𝑥𝑦 + 𝑧) This expression can be further expanded using distributive law, by doing
equal to 1 that, we will have the resulting expression equal to:
= (𝑥 + 𝑥 ′ )(𝑥 ′ + 𝑦)(𝑥 + 𝑧)(𝑦 + 𝑧) Looking at this expression, we can see that we have term equal to 𝑥 + 𝑥 ′ ,
if we recall, the expression 𝑥 + 𝑥′ is equal to 1 by the postulate 5(a). Since
any variable ANDed to 1 is equal to the variable itself, we will have the
resulting expression equal to:
= (𝒙′ + 𝒚)(𝒙 + 𝒛)(𝒚 + 𝒛)
2. From the output of the first step, we then look for the missing variable in each OR term. Analyzing the
output, we can see that each OR term is missing one variable, so taking it term by term we will have:
For the first term:
This is term We let 𝐴 = 𝑥 ′ + 𝑦, since 𝑧 is missing in this term, we will OR 𝑧𝑧′ to 𝐴 so we have the
𝑥′ + 𝑦
equal to 0 expression
Next is we apply again the distributive law to this expression so that we will have the
𝐴 + 𝑧𝑧 ′
expression:
(𝐴 + 𝑧)(𝐴 + 𝑧 ′ ) Substituting 𝐴 = 𝑥 ′ + 𝑦, we will have the resulting expression equal to:
(𝑥 ′ + 𝑦 + 𝑧)(𝑥 ′ + 𝑦 + 𝑧 ′ ) This is for the first term.
 For the second term, we also apply the same steps we did on the first term.
We let 𝐴 = 𝑥 + 𝑧, since 𝑦 is missing in this term, we will OR 𝑦𝑦′ to 𝐴 so we have the
𝑥+𝑧
expression
Next is we apply again the distributive law to this expression so that we will have the
𝐴 + 𝑦𝑦′
expression:
(𝐴 + 𝑦)(𝐴 + 𝑦′) Substituting 𝐴 = 𝑥 + 𝑧, we will have the resulting expression equal to:
(𝑥 + 𝑦 + 𝑧)(𝑥 + 𝑦′ + 𝑧) This is for the second term.

For the third term, we also apply the same steps we did on the first and second term.
We let 𝐴 = 𝑦 + 𝑧, since 𝑥 is missing in this term, we will OR 𝑥𝑥′ to 𝐴 so we have the
𝑦+𝑧
expression
Next is we apply again the distributive law to this expression so that we will have the
𝐴 + 𝑥𝑥′
expression:
(𝐴 + 𝑥 )(𝐴 + 𝑥′) Substituting 𝐴 = 𝑦 + 𝑧, we will have the resulting expression equal to:
(𝑥 + 𝑦 + 𝑧)(𝑥′ + 𝑦 + 𝑧) This is for the third term.

Combining all the resulting expression from each term we will have the expression:

(𝑥′ + 𝑦 + 𝑧)(𝑥′ + 𝑦 + 𝑧′ )(𝑥 + 𝑦 + 𝑧)(𝑥 + 𝑦′ + 𝑧)(𝑥 + 𝑦 + 𝑧)(𝑥′ + 𝑦 + 𝑧)

Removing the duplicate terms and rearranging them, we will have the final expression:

𝐹 = (𝑥 + 𝑦 + 𝑧)(𝑥 + 𝑦′ + 𝑧)(𝑥′ + 𝑦 + 𝑧)(𝑥′ + 𝑦 + 𝑧′ )

= 𝑀0 𝑀2 𝑀4 𝑀5

Using the short notation of sum of Maxterm, we have:

𝐹(𝑥, 𝑦, 𝑧) = ∏(0,2,4,5)

Standard Forms

The two canonical forms of Boolean algebra are basic forms that one obtains from reading a function from truth
table. These forms are very seldom with the least number of literals because of the fact that all variables must be
present either complemented or uncomplemented.

Another way to present Boolean function is standard form, this is a simplified version of the canonical forms.

The sum of product is a Boolean expression containing AND terms, called product terms, of one or more literals
each. The sum denotes the ORing of these terms. Example of sum of product is

𝐹1 = 𝑦 ′ + 𝑥𝑦 + 𝑥′𝑦𝑧′

A product of sums is a Boolean expression containing OR terms, called sum terms. Each term may have any number
of literals. The product denotes the ANDing of these terms. Example of product of sum is:

𝐹2 = 𝑥(𝑦 ′ + 𝑧)(𝑥 ′ + 𝑦 + 𝑧 ′ )

Figure 1 show the implementation of the functions 𝐹1 and 𝐹2 .

(a): Sums of Product (SOP) (b): Product of Sums (POS)
Figure 1: Two Level Implementation

(a): 𝐴𝐵 + 𝐶(𝐷 + 𝐸) (b): 𝐴𝐵 + 𝐶𝐷 + 𝐶𝐸

Figure 2: Three and Two Level Implementation
II. ASSESSMENT
1. Using a truth table below, prove that (𝑋𝑌) (𝑋′ + 𝑍′) = 𝑋𝑌𝑍′
x y z (𝑋𝑌) (𝑋′ + 𝑍′) 𝑋𝑌𝑍′
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

2. Simplify each of the following expressions

a. (𝐴′𝐶 + 𝐵′ + 𝐷𝐹′ )[𝐴 + 𝐶′ + 𝐵′ + 𝐷𝐹′ ]
b. (𝐴𝐶 + 𝐵′ )(𝐺 + 𝐹 + 𝐷𝐸) (𝐴𝐶 + 𝐵′ )′
c. (𝑋′ + 𝑌′𝑍′ + 1) (𝑋 + 𝑌) (𝑋 + 𝑍 )

3. Determine the complement of the following function

a. (𝐴 + 𝐵′𝐶 + 1) (𝐵′ + 𝐶′ + 𝐵𝐶𝐹 )
b. 𝑃𝑄 (𝑀′𝑁′𝑃′ + 𝑁𝑅 + 𝑅′𝑆′ ) 𝑅′

III. REFENCES

Textbook:
Hwang, E.O. (2018). Digital logic and microprocessor design with interfacing, 2nd edition; Calif., U.S.A.:
Cengage Learning

Other References:
Charles H. Roth Jr, Lizy Kurian John, Byeong Kil Lee (2016). Digital systems design using Verilog, International
edition; Australia: Cengage Learning

Online references:
AspenCore, Inc. (2020). Laws of Boolean Algebra. Retrieved from https://www.electronics-
tutorials.ws/boolean/bool_6.html in August 2020

tutorialspoint.com, (2020). Boolean Algebra. Retrieved from

https://www.tutorialspoint.com/computer_logical_organization/boolean_algebra.htm in August 2020

EETech Media, LLC (2020). Introduction to Boolean Algebra. Retrieved from

https://www.allaboutcircuits.com/textbook/digital/chpt-7/introduction-boolean-algebra/ in August 2020

Wolfram Research, Inc. (2020) Boolean Algebra. Retrieved from

http://mathworld.wolfram.com/BooleanAlgebra.html in August 2020