Karnaugh Maps | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 13.4 Free with a free account

Karnaugh Maps

Discrete Mathematics · Chapter 13: Boolean Algebra and Logic CircuitsSection 13.4 · lesson 84 of 8710 min · free with a free account

← Boolean Expressions and Logical OperatorsNext lesson: The Arithmetic Logic Unit (ALU) →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Simplification as visual pattern-matching.

  • Explain why K-maps use Gray code order
  • Build 2-, 3- and 4-variable maps
  • Find prime and essential prime implicants
  • Use don't-care cells to shrink expressions

Transcript

Everything said in the video, section by section (1,421 words). Read along, or search it.

Boolean Algebra and Logic Circuits

Karnaugh Maps

This section gives a visual route to simplifying Boolean expressions, the Karnaugh map. Instead of hunting for the next algebraic law, we'll arrange the truth table as a grid and look for rectangles. We'll build maps for two, three and four variables, state the grouping rules precisely, and see how don't-care inputs shrink circuits further.

The Opening Problem

Fewer Gates on a Sensor Board

An embedded-systems engineer is designing the control logic for a small industrial sensor board. The goal is the simplest Boolean expression for each output signal, because every extra gate on the chip costs silicon area, power and propagation delay. The algebraic route works, but it requires spotting which law applies next, amid a page of symbols. The Karnaugh map, or K-map, takes a different route. It's a grid that turns simplification into a visual pattern-matching task. Nothing about the laws changes. The K-map just reaches equivalent results another way.

13.4.1

Why Gray Code Order

A K-map gives every minterm its own cell. And it arranges the grid so that any two cells sharing an edge differ in exactly one variable. That property isn't automatic. It has to be built into how the rows and columns are labeled. Try ordinary counting order: zero zero, zero one, one zero, one one. The middle step, zero one to one zero, flips two bits at once. So neighboring cells would differ in two variables. Reorder them as zero zero, zero one, one one, one zero. Now every step flips exactly one bit. And since the sequence is used cyclically, even the wraparound from one zero back to zero zero flips just one bit. That ordering is called a Gray code. So a Karnaugh map is a grid with one cell per minterm, holding the function's value, with its rows and columns labeled in Gray code order.

Figure 1

A 2-Variable Map

With two variables, one labels the rows and the other the columns. Each has only two values, so the adjacency property holds automatically. Let F of A and B have minterms zero, one and three. So F is one everywhere except at A equals one, B equals zero. The top row, A equals zero, is all ones. Across that row, B takes both values, and only A equals zero stays fixed. So it gives the term A prime. The right column, B equals one, is also all ones. Only B equals one stays fixed there, giving the term B. Together, F equals A prime plus B. We got there without applying a single named law, just by reading what stays fixed across each block.

13.4.2

A 3-Variable Map: Go Big

With three variables, A labels the two rows, and B C labels four columns, in the Gray order zero zero, zero one, one one, one zero. Let F have minterms zero, one, two, three, five and seven. The top row is entirely ones, giving the term A prime and covering minterms zero through three. That leaves minterms five and seven. You could group them as an isolated pair. But that misses something bigger. The columns zero one and one one are all ones in both rows. That's a group of four, where A and B both vary, and only C stays fixed at one. So that group gives the single-literal term C, and F equals A prime plus C. That's the central rule. Always look for the largest valid rectangle before settling for a smaller one, because a bigger group always gives a shorter term.

Four Variables

Wraparound in Both Directions

With four variables, A B labels four rows and C D labels four columns, both in Gray code order. That's a four by four grid of sixteen cells. Wraparound adjacency now works in both directions. The leftmost and rightmost columns are adjacent, and so are the top and bottom rows. So all four corner cells are mutually adjacent. Each pair of corners differs in exactly one variable, through one of the two wraparounds. Here's an example with ten minterms: zero, two, and eight through fifteen.

Figure 3

Reading a 4-Variable Map

Here's the map. The bottom two rows, A B equals one one and one zero, are entirely ones. In both rows, A is one, and B varies. That's a group of eight, giving the single term A. That leaves minterms zero and two, both in the top row, still uncovered. They're corner cells. And the bottom row supplies the two other corners. All four corners are mutually adjacent by wraparound. All four share B equals zero and D equals zero, with A and C free. So they give the term B prime D prime. So F equals A plus B prime D prime. And that corner group is essential, because nothing else covers minterms zero and two.

13.4.3

Valid Groups and Prime Implicants

Now the grouping rule, stated precisely. A valid group is a rectangular block of cells, wraparound allowed, where every cell contains a one, or a don't-care being used as a one. Its size must be a power of two: one, two, four, eight or sixteen. And it must be as large as possible, not contained inside some larger valid block. A group meeting all three conditions is called a prime implicant. And if some one-cell is covered by only one prime implicant, that implicant is essential. It must appear in every minimal sum-of-products expression.

Table 1

Bigger Groups, Shorter Terms

Here's why bigger is better. In a group of two to the k cells, exactly k variables take both values somewhere in the group, so they drop out of the term. The other variables stay fixed throughout, so they survive in the term. A single cell eliminates nothing. A pair eliminates one variable, a group of four eliminates two, eight eliminates three, and sixteen eliminates four. It's the same principle the algebraic combining law captures with symbols. The K-map just lets you read it off the grid. And both worked examples had only essential prime implicants. In the three-variable map, minterm zero needs A prime, and minterm five needs C. In the four-variable map, minterms nine, eleven, thirteen and fifteen need A, and minterms zero and two need B prime D prime.

13.4.4

Don't-Care Conditions

Some input combinations never arise in practice, or don't affect what the circuit has to do. These are don't-care conditions, marked X on the map. When grouping, an X can be treated as zero or one, whichever allows a bigger group. And it never has to be covered. Here's an example. A binary-coded decimal digit uses four bits, W, X, Y and Z. But only the values zero through nine ever occur. So the six codes from ten to fifteen never appear. They're don't-cares. Suppose the output F must be one exactly when the digit is five through nine. That gives this map, with the X cells in the third row, and in the right half of the bottom row.

Figure 4

Using the Don't-Cares

Without the don't-cares, treating codes ten to fifteen as zero, the biggest groups are pairs. That gives W prime X Y, plus W prime X Z, plus W X prime Y prime. Three terms, and nine literals in total. Now use the don't-cares favorably. Treating fourteen and fifteen as one extends the pair six, seven into a group of four, giving just X Y. Treating thirteen and fifteen as one turns the pair five, seven into X Z. And treating ten and eleven as one turns eight, nine into W X prime. So F equals X Y plus X Z plus W X prime. Still three terms, but only six literals. Every required one, five through nine, is covered, and no code from zero to four is ever set to one. The saving comes purely from choosing among the don't-cares. Don't-cares like these are common wherever the surrounding system restricts the inputs: display decoders, impossible sensor combinations, and unused states in state machines.

Takeaways

Find the Biggest Rectangles

To summarize. A Karnaugh map puts one truth-table row in each cell, with Gray code labels, so that adjacent cells, including wraparound pairs, differ in exactly one variable. Two-variable maps are two by two, three-variable maps two by four, and four-variable maps four by four, where even the four corners are adjacent. A prime implicant is a maximal, power-of-two rectangle of ones. An essential one is the only cover for some cell, and must appear in the minimal expression. Bigger groups eliminate more variables. And don't-cares, used favorably, can shrink the result, like the drop from nine literals to six. Here's something to think about. A five-variable function has thirty-two cells, and a six-variable function has sixty-four. As the grid grows, does looking for the biggest rectangle by eye still guarantee a truly minimal expression? Or does it depend on the map staying small enough to check every grouping?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Karnaugh Maps

Why do Karnaugh maps label rows and columns in Gray code order?
Gray code order makes any two cells that share an edge differ in exactly one variable, which is what lets you merge neighbors. Ordinary counting 00, 01, 10, 11 flips two bits going from 01 to 10. The order 00, 01, 11, 10 flips one bit per step, including the wraparound from 10 back to 00.
How do you find prime and essential prime implicants on a K-map?
Circle rectangular groups of 1s, wraparound allowed, with sizes that are powers of two, and make each group as large as possible. A group meeting those conditions is a prime implicant. It is essential if it is the only one covering some 1. For F with minterms 0,1,2,3,5,7, both A' and C are essential.
How do you read a product term from a group on a 4-variable K-map?
Keep the variables that stay constant across the group and drop the ones that take both values. A group of 2^k cells eliminates k variables. For example, the four corner cells (minterms 0, 2, 8, 10) are adjacent by wraparound. Only B=0 and D=0 stay fixed, so the term is B'D'.
How do don't-care cells make a K-map expression simpler?
A don't-care cell can be treated as a 1 when that makes a group larger, and it never has to be covered. In the BCD example where F=1 for digits 5 through 9, codes 10 through 15 are don't-cares. Using them turns W'XY + W'XZ + WX'Y' (nine literals) into XY + XZ + WX' (six literals).

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →