Introduction to Karnaugh Maps - Combinational Logic Circuits, Functions, & Truth Tables
Summary
TLDRThis video script offers a comprehensive guide on utilizing Karnaugh maps (K-maps) to simplify the process of writing Boolean functions and creating corresponding circuit diagrams. It demonstrates how to translate truth tables into K-maps for two, three, and four variables, emphasizing the importance of grouping ones in powers of two. The script also illustrates the process of deriving functions from K-maps and testing their accuracy, followed by constructing logic circuits based on the simplified functions. The tutorial encourages viewers to practice by pausing and attempting examples themselves, highlighting the efficiency of K-maps in digital logic design.
Takeaways
- đ The script discusses the process of using a Karnaugh map (K-map) to simplify and represent Boolean functions based on a truth table.
- đ It explains how to create a three-variable K-map with eight squares, corresponding to the eight possible input combinations of variables a, b, and c.
- đ The importance of correctly placing the function values within the K-map squares is highlighted, which aligns with the truth table's output for each combination of inputs.
- đ The concept of circling groups of ones in the K-map is introduced, emphasizing that the number of ones circled must be a power of two (1, 2, 4, 8, etc.).
- đ€ The script illustrates how to derive Boolean expressions from the K-map by identifying variables that do not change within each group of circled ones.
- đ ïž It demonstrates the conversion of a K-map into a circuit diagram, showing the use of AND and OR gates to represent the simplified Boolean function.
- đ The video provides examples of both horizontal and vertical orientations for a three-variable K-map, as well as a four-variable K-map for more complex functions.
- đ The process of filling out a K-map with function values for different variable combinations is detailed, including how to handle the complements of variables.
- đ The script explains how to test the derived Boolean function by substituting variable values and verifying the output against the truth table.
- đ It also covers the reverse process of creating a K-map from a given Boolean function, showing how to place ones and zeros in the appropriate squares.
- đĄ Finally, the video encourages viewers to practice by pausing and attempting to create K-maps and circuit diagrams from provided truth tables or functions.
Q & A
What is a Karnaugh map and how is it used in logic design?
-A Karnaugh map, often abbreviated as K-map, is a visual tool used to simplify Boolean algebra expressions and to minimize logic circuits. It is used to represent the truth table of a Boolean function in a more compact form, making it easier to identify patterns and simplify the function into its simplest form.
How many squares are needed for a three-variable Karnaugh map?
-A three-variable Karnaugh map requires 2^3, which equals 8 squares, to represent all possible combinations of the three binary variables.
What is the significance of the arrangement of rows and columns in a three-variable Karnaugh map?
-In a three-variable Karnaugh map, the arrangement of rows and columns corresponds to the binary values of the variables. For instance, if the variables are A, B, and C, the rows might represent A and B, while the columns represent C, allowing for a systematic representation of all possible input combinations.
How do you determine the function values to be placed in a Karnaugh map?
-The function values are determined from the truth table of the Boolean function. Each cell in the Karnaugh map corresponds to a specific combination of input variables, and the value placed in that cell is the output of the function for that combination.
What is the rule for circling groups of ones in a Karnaugh map?
-When simplifying a Karnaugh map, you circle groups of ones (representing TRUE or 1 in the function) together. The number of ones in a group must be a power of two, such as 1, 2, 4, or 8, because this allows for the simplest representation of the function in terms of AND and OR operations.
How do you interpret the groups of ones in a Karnaugh map to write the simplified Boolean function?
-Each group of ones in a Karnaugh map corresponds to a term in the simplified Boolean function. You write down the variables that do not change within the group, and if a variable changes, you use its complement. The terms for all groups are then combined using OR operations.
What is the purpose of a circuit diagram in the context of Karnaugh maps?
-A circuit diagram is used to visually represent the physical implementation of a Boolean function. After simplifying a Boolean function using a Karnaugh map, the circuit diagram shows how to connect logic gates (AND, OR, NOT) to achieve the desired output.
Can you provide an example of how to convert a simplified Boolean function into a Karnaugh map?
-Certainly. If you have a simplified Boolean function like 'A BC + AB', you would create a Karnaugh map and fill in the cells where A is 1 and C is 1 for the term 'AC', and where A is 1, B is 0 for the term 'AB'. The filled cells represent the TRUE outputs of the function for the respective variable combinations.
What is the difference between a horizontal and a vertical orientation of a three-variable Karnaugh map?
-The difference lies in how the variables are assigned to the rows and columns. In a horizontal orientation, one pair of variables is assigned to the rows, and the third variable to the columns. In a vertical orientation, it's the opposite, with one variable assigned to the columns and the pair of variables to the rows. The choice of orientation can affect the ease of simplifying the function.
How do you handle a four-variable Karnaugh map?
-A four-variable Karnaugh map requires 2^4, or 16 squares, arranged in a 4x4 grid. Two variables are assigned to the rows and the other two to the columns. You fill in the map based on the function's truth table and then circle groups of ones to simplify the function, similar to the process with three-variable maps.
Can you explain the process of creating a circuit diagram from a simplified Boolean function?
-To create a circuit diagram from a simplified Boolean function, you identify each term in the function that requires an AND operation and represents it with an AND gate. Then, you use OR gates to combine the outputs of these AND gates to represent the OR operations in the function. NOT gates may be used if any term involves a variable's complement.
Outlines
đ Introduction to Karnaugh Maps and Truth Tables
This paragraph introduces the concept of Karnaugh maps (K-maps) as a tool for simplifying the process of writing functions based on truth tables. It explains the structure of a three-variable K-map with eight squares, each representing different input possibilities. The paragraph details how to fill in the K-map with function values from the truth table and emphasizes the importance of circling groups of ones in powers of two to simplify the function. It also provides an example of deriving a function from the K-map by identifying variables that do not change within these groups.
đ Testing the Function and Circuit Diagram Creation
The second paragraph continues the discussion by testing the derived function against specific variable values to ensure its correctness. It then proceeds to convert the function into a circuit diagram, explaining the use of AND and OR gates to represent the logical operations of the function. The paragraph also encourages viewers to pause and attempt the problem themselves, introducing a new example with a different K-map orientation and explaining how to fill it out based on the given truth table.
đ Vertical Orientation K-Map and Function Derivation
This paragraph focuses on creating a K-map with a vertical orientation, explaining the process of filling it out based on the given function values. It demonstrates how to identify pairs of ones and derive the function by considering variables that remain constant within these pairs. The paragraph also includes testing the derived function with different variable combinations to validate its accuracy and concludes with the conversion of the function into a logic circuit diagram.
đ Four-Variable K-Map Analysis and Function Construction
The fourth paragraph extends the concept to four-variable K-maps, guiding the viewer through the analysis of pairs of ones and the construction of a function based on constant variables within these pairs. It illustrates the process of selecting terms and building the function step by step, emphasizing the independence of certain variables for each selection. The paragraph also encourages practice by inviting the viewer to try another example with a four-variable K-map.
đ Converting Functions into K-Maps for Different Variable Combinations
This paragraph demonstrates how to create K-maps from given functions for both three-variable and four-variable scenarios. It explains the process of identifying where variables are constant or complementary within the function terms and placing ones accordingly in the K-map. The paragraph provides examples of functions with different variable combinations and guides the viewer through the process of filling out the corresponding K-maps.
đš Advanced K-Map Filling with Color Coding
The final paragraph presents a more complex example of filling out a four-variable K-map based on a given function. It introduces color coding to distinguish between different terms in the function and explains the significance of the number of ones corresponding to the number of variables in each term. The paragraph concludes by summarizing the method for turning a function into a K-map and thanks the viewer for watching.
Mindmap
Keywords
đĄTruth Table
đĄKarnaugh Map (K-Map)
đĄVariables
đĄFunction Value
đĄBoolean Algebra
đĄComplement
đĄCircuit Diagram
đĄAND Gate
đĄOR Gate
đĄSimplification
Highlights
Introduction to using a Karnaugh map (K-map) to simplify and write a function based on a truth table.
Explanation of a three-variable K-map with eight squares representing all input possibilities.
Method to fill a K-map with function values from a truth table.
Technique for grouping ones in a K-map to simplify the function.
Rule of grouping ones in powers of two (1, 2, 4, 8, etc.) for K-map simplification.
Deriving a function from a K-map by identifying variables that do not change within a group of ones.
Example of testing the derived function against the truth table for accuracy.
Conversion of the simplified function into a circuit diagram using AND and OR gates.
Demonstration of creating a K-map with a vertical orientation for a three-variable function.
Process of filling a vertical K-map by analyzing the function values for different variable combinations.
Strategy for selecting groups of ones in a vertical K-map to form a simplified function.
Application of the derived function to create a logic circuit diagram.
Introduction to a four-variable K-map and its analysis for function simplification.
Method for identifying constant variables within groups of ones in a four-variable K-map.
Example of converting a given function into a K-map for educational purposes.
Step-by-step guide to creating a three-variable K-map from a function with terms.
Complex example of creating a four-variable K-map from a function with multiple terms.
Final example demonstrating the coloring and selection process in a four-variable K-map.
Conclusion summarizing the process of turning functions into K-maps and circuit diagrams.
Transcripts
consider the truth table shown on the
screen
how can we take the data in its truth
table and write a function using the
variables a b and c
enter carnot maps
the karnaugh map will be very helpful
for us to
write a function that describes this
truth table
so we have three variables so we need a
three variable karnaugh map with eight
squares
now the eight squares will match the
eight different input possibilities that
we have here
so this is just one of the two ways in
which we can draw a three variable
cardinal map
so we're going to have two rows
and four columns
so on top i'm going to put
for the inputs a b on the bottom c
so now the inputs a b
it could be 0 0
0 1
1 1
and 1 0. now the input for c
is only 0 or 1.
now the values that we're going to put
inside the square are the function
values that we see here
so for this first square a b is 0 and c
is 0
which corresponds to a function value of
0.
now for the next one
a b is still zero which means we're
dealing with this column
and c is one so we're dealing with this
particular square
the function value for that
is still zero
now for the third row
we can see that a b
is 0 1
and
c
is 0
and the function value is 1 so we're
going to put a 1
for that square
now for the next one a b is still 0 1
and c is 1.
so here's where a b is 0 1 and c is 1
giving us this square which the function
value is 0.
next a b is 1 0 so we're dealing with
the last column and c is zero so the
function value
is one
now for this one a b is
one zero still
c is one
and the function value is one
next we have a b is one one
so that's the third column
c is zero and the function value is one
and for the last one
the function value is zero
where a b and c is one
so that's how we can take the data in a
truth table
and put it on a karnaugh map or
for short we could say k map
now
how can we take this data and turn it
into a function
what we need to do is basically circle
groups of ones together
we can circle
one one or we could circle two ones
but we cannot circle three once
the number of ones that you can circle
could be one
two four eight
and so forth it has to be a power of two
so you can't circle three ones
five ones six ones not gonna work
so the best thing we can do is circle
two groups or two pairs of ones
let me use a different color so you can
see it
so let's start with this one
now what type of
what information can we derive from that
group of ones
those two ones highlighted do they
depend on the input a
notice that the input a varies between 0
and 1 yet the output is the same
so the output for those two
ones does it depend on a
notice that it depends on b
when b is one
the output is one so we're looking for
the variable
that doesn't change
b doesn't change
so should we write b
or not b
because b is one and the output is one
we're gonna write b
now
these two or this pair of ones also
corresponds to a c value of zero
notice that c is always zero
for
that pair of ones
so because z c is zero
and the output is one we need to write
not c
now let's move on to the next pair of
ones
so let's put an or symbol represented by
the plus sign
so
for the second pair of ones
what variables
do not change
so notice that c
changes
so for this pair of ones it is
independent of c
but notice that a b
is the same a is one b is
zero so which one is going to be not a
is it air b
so because a is one and it matches the
output function one
we're going to leave it as a but because
b is zero
we need to put
not b
because
not zero is one
so this
is the function
that explains this truth table
now we could test it out
so let's see if
a is zero and if b is one and if c is
one
if we get a function value of zero
so b is one
c is one a is zero
and b is one
so if we put
if we write the complement of one that's
going to be zero
so we have zero times one which is zero
and zero times zero is zero so we get an
output of zero
so that worked
let's try another one
let's try this one
let's see if the function will give us
the correct output
so b is zero
c is one
a is one
and b is zero
now the complement of one is zero
and the complement of zero is one
zero times zero is zero one times one is
one
zero plus one is one
so we get the right output
now for the sake of practice
let's make sure that we have the right
function let's try the last one
so b is one c is one
a is one
and b is one as well so the complement
of one is zero
and one times zero is zero zero plus
zero is zero and we can see that we have
the correct output
so we have the correct function
so that's how you could use a karnaugh
map
to quickly
write a function that corresponds to a
truth table
now let's take the function that we have
and turn it into a circuit diagram
so the function that we have was b
times the complement of c
plus a
times the complement of b
so we can write that as
b c prime plus
a
b prime
so we need an and gate to connect b and
c prime
so let's start with that
and we need another and gate
to connect
a
and b prime
so this is going to be b
and c prime and here we have a
and b prime
now notice that we have
a plus symbol between
these two terms
so we need to use an or gate
the plus symbol is associated
with the or operation
so the output of this and gate
is going to be b c prime
and the output of this and gate is going
to be
a b prime
and the output of the or gate
is going to give us the function f
which is what we have here
so that's the circuit diagram that
corresponds to this function
let's try another example
let's use this truth table
to create a k-map
and then use that to write a function
which will then use that to turn it into
a circuit diagram
if you want to pause the video and try
this problem feel free
now
the type of k-met that i'm going to draw
is going to be a little bit different
than the last one
the last one was a three variable k-map
drawn in the horizontal direction
but i'm going to draw one with
a vertical
orientation
so instead of having two rows four
columns
i'm going to have two columns
and four rows
so i'm going to put one variable above
the diagonal line
two variables below it
so a has two possibilities zero or one
bc can be zero zero
zero one one one
or one zero
so that's how you can draw a three
variable k map
with
vertical orientation
now let's fill in a table
so for this first column a is zero which
we can see it for the first four inputs
so here when b is when b and c is zero
the function is going to be zero
and when bc is 0 1
the function is going to be 1.
when bc is 1 0
the function is 0
and when bc is 1
the function is 1.
now for the second column
a is always one which will correspond to
these four
so when bc is zero
the function is one
and when bc is zero one the function is
also one
when bc is one zero the function is one
and when bc is one one the function is
zero
so that's how we can quickly fill out
this k-map
now how can we use it to write a
function for the truth table
so let's start with
this pair of ones
notice that a is always zero
so we need to write the complement of a
because the complement of zero will give
us an output of one
now for those pair of ones
notice that
b
changes
so
the output is independent of b so we're
not going to include b but notice that c
is one
so we're just going to write c
now let's draw the next pair of ones
so notice that a is always one for that
group
and this time c changes so it's
independent of c
but b is consistent b is always zero
so we're going to write b prime
now there's only one
last one that we need to consider
and that's here
so a is one we're just gonna write a
b is one we're gonna write b
and because c is zero we're gonna write
c prime
so this is the function
that corresponds to this truth table
now let's test the function to make sure
that we do indeed have the right one
so let's start with what we have here
so a is zero
c
is a zero
a is still zero b prime b is one
and then we have a b c prime so a is
zero
b is one
c is zero
the complement of zero is one
the complement of one is zero
and the complement of zero is one one
times zero is zero zero times zero is
zero
and zero times one is also zero
so this adds up to zero
which we can see that's the case
now let's try one more
let's try
this one
where a b and c is a one so we have
the complement of one times one
plus one times the complement of one
plus one times one times the complement
of one
the complement of one is a zero
so automatically zero times one is zero
one times zero is still zero
and the last one is going to be zero so
the output is once again zero
okay let's try one that's gonna give us
a value of one let's try this one
so a is one
c
is one
b is zero
and a is one
b is zero
c is one
so the complement of one is zero
the complement of zero
is one
and the complement of one is zero
zero times one is zero one times one is
one
one times zero times zero is zero
zero plus one plus zero is one
so this function works
so now you know how to write a function
using
the k-map
but now let's turn this function
into a circuit diagram
let's draw the logic circuit that
corresponds this function
so let's start with the first term that
we have
so we need an and gate
so it's going to be a prime c
and the output will be
a prime c
now for the second
and gate the input will be a
and the second input is going to be b
prime
giving us the output a
b prime
now for the last one i'm going to use a
three input and gate
so the three inputs will be a
b and c prime
now we need a three input
or gate
so then this will give us the output
function f
and so that's how you can draw
the logic circuit
for this particular function
consider the four variable k map that we
have
on the screen
go ahead and
write a function for this k-map
feel free to pause the video
so first let's begin by analyzing those
two pair of ones
so notice that a and b
is always one
for that selection
so we have a and b
and for that selection
notice that c
is always zero
but d
changes
so it depends on
c but not d
so we have a b
and since c is zero we're gonna have c
prime
now let's select another pair of ones
so let's go with that
now notice that a is always zero
so we're gonna have a prime
b changes so it's gonna be independent
of b
now c
is always one and d is always zero so
we're going to write d prime
now let's select this pair of ones that
we have there
so a is always one
and b is always zero so let's write b
prime for
for that part
now
notice that c
changes with the numbers zero and one
but d remains the same d is always one
so this is going to be a b prime d
so this is the function that corresponds
to this particular four variable k map
let's try another example
go ahead and try this one
so instead of selecting two ones we can
select a group of four ones
so for that particular group
which variables remain the same
notice that a is always 0 and b
is always 0. so we're going to have a
prime and b prime
now c
can be 0 or 1 so it's independent of c
and d can also be zero or one
so it's only going to depend on a and b
for that first selection
now the next selection
we can basically take a square of ones
so which variables are constant
notice that a is always one
so we're going to write a
b
changes between one and zero so it's
independent of b
on this side
notice that d
is always one
so it's going to depend on d
c
changes so it's independent of c
so this particular function
is represented by this equation it's a
prime b prime plus a d
so now you know how to take the
information from a four variable k map
and turn it into a function
now let's say that we're given a
function
ac
plus
a b prime
so how can we take this function
and create a three variable k map
and let's create it in the horizontal
direction
so we're gonna need two rows
and four columns
so we're gonna put a b above the
diagonal line and c below it
so a b can be 0 0
0 1
1 1 or 1 0
and c could be 0 or 1.
now let's focus on the ac term
notice that we don't have any
compliments here
so we're looking for when a is one
and when c is one
c
is one anywhere in this row
a
is one here
so what we're going to do is we're going
to put a 1
in those boxes
now let's focus on the next term
a b prime
so we just have a we're going to put one
we have the complement of b so we're
going to write zero
so let's identify
where a is one and b is zero
so this is when a is one and b is zero
so anywhere in this region
so we need to fill this row with a one
and we have an overlapping one there
now every other box
we're going to put a 0 in it
so that's how we can take a function
and draw a k map from it
now let's try another example
so let's say the function
is a
b prime
plus ac
plus a prime
bc prime
so let's create another three variable k
map
but in the vertical orientation
so we're going to have two columns
and four rows
so we're going to put the letter a on
top
bc below the diagonal line
so a can be 0 or 1
bc can be 0 0 0 1
1 1 or 1 0.
now let's start with this term a b prime
so a is going to be 1 b is going to be
0.
a is 1 in this column
so let me just highlight that in red
and b is 0
here
so that means we're going to put a 1
in those first two boxes on the right
now let's move on to the next term ac
so that's when a is one
and when c
is one
so we need to put a one here
and here
now for the next one we have a prime b c
prime
i forgot to put 1 1 for that
now for a prime we're going to write 0
for b we're going to put 1
for c prime we're going to write 0.
so a is 0
in the first column
and
b
is 1
here
and c is 0 here
so we want a
to be 0 and b to be 1 and c to be 0.
so that only corresponds to this last
square
so we're going to put
a 1 there
so every other box we're going to put a
0
and so that is the k-map
that corresponds
to that function
here's another harder example
let's say the function is a b prime
plus a prime c d
plus a
b c prime
go ahead and draw a k map for that
function
now what type of k map do we need would
you say it's a three variable k map or a
four-variable k-map
notice that we have four variables a b c
and d
so this time
we're going to need
four columns
and four rows
let's put the letters a b
on top
and c d on the bottom
so a b could be 0 0
0 1
1 1 and 1 0
and the same is true for cd
now
let's focus on
a b prime
so we have a
which we're going to put a 1 for that
and for the complement of b let's put a
zero
so one is a one and one is b zero
a is one
and b is zero
anywhere in this column
so we're gonna put a one
everywhere in that column
now let's move on to the next term
a prime c d
so let's put the zero for the complement
of a and a one for c and d
so notice that c and d is one in this
region and a
is zero
in the first two columns
so therefore we have to put a one
at the intersecting squares
now for the last term
a b c prime
we're going to put a 1 for a and b and a
0 for the complement of c
so
a and b are 1 in this region
c
is 0
in the first two
rows
so we're going to put a 1 here
everywhere else we're going to fill it
in with a zero
and so now we've completed the four
variable k map
let's work on one more example
so this one i'm going to color code
differently
so let's say the function is c
a d prime
plus
a prime b c prime d
plus a
b prime c
so go ahead and fill out the four
variable k map
given this function
so let's start with the lettuce c
so since we have c and not the
complement of c it's just going to be
one
c
is one in this region
so that's anywhere in the last two rows
so we're gonna have to put a one in
all of those rows i mean in the in those
two rows
so i'm gonna
color code this
group of eight ones
notice that when we have
just a term with one variable
we're going to get eight ones
for a term with two variables we're
going to get four ones
for a term with three variables
we're going to get two ones
and four a term with four variables
we're only going to get
one one
so let's move on to the next one
a d prime
so for a i'm gonna put one
and for d prime is zero
so a is one
in
the last two columns on the right
and d is zero
here
so we're going to have
a 1
and these as well
so now i'm going to circle those ones
with a red color
so as we can see
for a term with two variables
we have a total
of four ones highlighted in red
now let's move on to the next term
which has four variables
so we should only get
one one
in the k map
so for a prime we're gonna write zero
for b one c prime 0 d1
so
when a is 0 and b is 1 here
c
is 0 and d is 1 here
we're just going to put a 1 in this
region
and i'm going to highlight it
in green
now for the last one
a b prime c
so we're going to have a 1 for a
0 for b prime and a 1 for c
so first let's identify where
a b is 1 0
so that's going to be
in this region
and now let's identify where c
is one
c is one
in the second and the third row from the
top
so we're gonna need a one here and the
one that we already have here
so as you can see for a term with three
variables
we get a pair of ones or two ones
everything else
let's put a zero
and so now you know how to turn a
function into a k-map
so that's it for this video thanks for
watching
Voir Plus de Vidéos Connexes
Logic implementation using Programmable Logic Array (PLA)
#11 Gerbang Logika | LOGIKA INFORMATIKA
DeMorgan simplification
ServiceNow Transform Maps & Field Maps
AQA AâLevel Define problems using Boolean logic
Belajar Bersama, Bab 2 Dasar-dasar Pemetaan, Penginderaan Jauh dan Sistem Informasi Geografi Kelas X
5.0 / 5 (0 votes)