Problem#1 (solve the problem a.
use Boolean Algebra)
Figure 1.
a. Simplify the logic circuit figure 1
b. Determine the truth table
c. Determine timing diagram of the output signal X
Combinational Logic
Circuit
Introduction
Boolean algebra
to describe and analyze circuits that were made up of combinations of
logic gates
Combinational logic circuits
• at any time, the logic level at the output depends on the combination
of logic levels present at the inputs.
• A combinational circuit has no memory characteristic, so its output
depends only on the current value of its inputs.
Boolean expression Form
• form of a sum-of-products (SOP) expression.(MINTERM function)
Example
ABC BCD CDE X
A B ABC AC X
• form of a product-of-sums (POS) expression. (MAXTERM function)
Example
( A B )( A B C ) X
( B C D)(C D)(C D E F ) X
Problem #2
1. Which of the following expressions is in SOP form?
(a) AB + CD + E
(b) AB (C + D)
(c) (A + B) (C + D + F)
(d) + PQ
2. Repeat question 1 for the POS form.
Sum of Product (SOP) form
When two or more product terms are summed by boolean addition
Example
ABD+CD+ABC
AD+C+C
Single overbar cannot extend over more than one variable; however more than
one variable in a term can have an over bar
Example
is OK
is not OK
Standard Vs non standard SOP
form
• Standard sum of product (SOP) form
One in which all the variable in the domain appear in each product
term in the expression
Example
ABD+CD+ABC
• nonstandard sum of products (SOP) forms
Example
AD+C+C
Conversion of a non standard
SOP expression to Standard
SOP expression
Conversion of a SOP expression to Standard SOP expression
• Step 1: multiply to each nonstandard product term by 1.
• Step 2: Replace 1 by a sum of a missing variable and its complement. (
A + = 1)
• Step 3: Apply rule : B(A + )=(AB)(B)
Conversion of a non standard
SOP expression to Standard SOP expression
Example
AC++AB
1st term
A BC A BC (D D) A BCD A BCD
2nd term
Standard Vs non standard POS
form
Standard Product of Sum (POS) form
One in which all the variables in the domain appear in each sum term in
the expression
example
(A++C)(++C)(A+B+C)
Non Standard Product of Sum (POS) form
Example
(A+B)(A++C)(A+C)
Conversion of a non standard
POS expression to Standard POS expression
Conversion of a POS expression to Standard POS expression
• Step 1: Add to each nonstandard product term by 0.
• Step 2: Replace 0 by a product of a missing variable and its
complement. ( A. = 0)
• Step 3: Apply rule 12: A+BC=(A+B)(A+C)
Conversion of a non standard
POS expression to Standard POS expression
Example
Boolean Expression and Truth
Tables
• All standard Boolean Expression can be converted into truth table
using binary values for each term in expression
• SOP or PAS expression can be determined from truth table
Converting SOP Expression to
truth table
• SOP expression is equal to 1 only if at least one of product term is equal
to 1
• How to convert from SOP expression to truth table
Step 1 :
List of possible combination of binary value of the variable in the
expression
Step 2 :
Convert the SOP expression to standard form
Step 3:
Place a 1 in the output column (X) for each binary value that make the
SOP expression standard a 1 and place 0 for all remaining binary values
Converting SOP Expression to
Truth Table
Example
A BC A BC ABC X
Converting POS Expression to
Truth Table
• A POS Expression is equal to 0 only if at least one of the product term is
equal to 0
• How to covert from POS expression to truth table
Step 1:
Lis of possible combination of binary values of the variables in the
expression
Step 2:
Convert the POS expression to standard form if it is not already
Step 3:
Place a 0 in the output column (X) for each binary value that make the
standard POS expression a 0 and Place 1 for all the remaining binary values
Converting POS Expression to
Truth Table
Example ( A B C )( A B C )( A B C )( A B C )( A B C ) X
Problem #3
A B C X
a. Determine the Boolean Expression as a
0 0 0 1 Minterm function
0 0 1 0 b. Contruct the logic circuit based on the
0 1 0 0 minterm function
0 1 1 1 c. Determine the Boolean Expression as a
1 0 0 0 Maxterm function
1 0 1 1 d. Construct the logic circuit based on the
1 1 0 0
Maxterm function
1 1 1 0
Maxterm and Minterm for 3
variables
Minterm Maxterm
X Y Z
Term Designation Term Designation
0 0 0 m0 +Y+Z M0
0 0 1 Z m1 +Y+ M1
0 1 0 m2 ++Z
M2
0 1 1 m3 ++
1 0 0 +Y+Z M3
m4
1 0 1 +Y+ M4
1 1 0 m5 ++Z
XY M5
1 1 1 m6 ++
m7 M6
M7
Example
Known the Boolean Expression
X=A+C
Determine in Minterm function !
Solution
1st term A = A(B+) (C+)
= ABC+AB+AC+A
2nd term C =C (A+)
= AC + C
Min term function for X=A+C Is
X= ABC+AB+AC+A+C
X = m7 + m6 + m5 + m4 + m1
In Minterm function Can be written as
f (ABC) = (1,4,5,6,7) or
In Maxterm function can be written as X= M0.M2.M3 or F(ABC)= (0,2,3)
Example
• The truth table for X = m7 + m6 + m5 + m4 + m1
A B C X
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
Example
• The truth table for X= M0.M2.M3
A B C X
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
Karnaugh Map Method
• The Karnaugh map (K map) is a graphical tool used to simplify a logic
equation or to convert a truth table to its corresponding logic circuit
in a simple
• K map can be used for problems involving any number of input
variables, its practical usefulness is limited to five or six variables.
• five- and six-input are best done by a computer program.
K Map
• Karnaugh maps and truth tables for 2 variables
• Karnaugh maps and truth tables for 3 variables
K Map
Karnaugh maps and truth tables for 4 variables
Looping
• The expression for output X can be simplified by properly combining
those squares in the K map that contain 1s. The process for combining
these 1s is called looping.
looping groups of Two (Pairs)
Example
Looping
looping groups of Two (Pairs)..
• Example
Looping
• looping groups of Four (Quads)
Looping
• looping groups of Four (Quads)..
Looping
• looping groups of Four (Quads)..
Looping
• looping groups of eight (Octets)
Example
Simplify the Boolean expression use K Map
X= +D+D+ABCD+CD
The Result
Example
Example
• The same K map with two equally good solutions.
Example
Example
Don’t-Care Conditions
• Some logic circuits can be designed so that there are certain input
conditions for which there are no specified output levels,
• usually because these input conditions will never occur. In other
words, there will be certain combinations of input levels where we
“don’t care” whether the output is 1 or 0.
Don’t-Care Conditions
• “Don’t care” conditions should be changed to 0 or 1 to produce K-
map looping that yields the simplest expression.
Example
• Let’s design a logic circuit that controls an elevator door in a three-
story building. The circuit has four inputs. M is a logic signal that
indicates when the elevator is moving (M = 1) or stopped (M = 0).
• F1, F2, and F3 are floor indicator signals that are normally LOW, and
they go HIGH only when the elevator is positioned at the level of that
particular
Example
Ans.
Home Work
Make a summary in ppt. format
Subchapter 6.8 – 6.10
Must be submitted Next Week