Simplifying Logic Circuits | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Simplifying Logic Circuits

Discrete Mathematics · Chapter 13: Boolean Algebra and Logic CircuitsSection 13.7 · lesson 87 of 879 min · free with a free account

← Logic Gate Design

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

Algebra and Karnaugh maps together, with gate count as the payoff.

  • Choose between algebraic laws and K-maps
  • Minimize a function both ways and compare
  • Simplify a safety-interlock circuit from 12 gates to 3
  • Cross-check a minimal form by expanding it

Transcript

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

Boolean Algebra and Logic Circuits

Simplifying Logic Circuits

This final section of the course pulls two toolkits together, algebraic laws and Karnaugh maps, aimed at one practical number: the gate count. We'll minimize a function both ways and compare, then take a safety-interlock circuit from twelve gates down to three. Finally, we'll see how to check any minimal form, without redrawing a map.

The Opening Problem

One Number That Matters

Picture a designer laying out a safety-interlock chip. Once the logic is correct, one number matters: how many gates it takes to build. Every extra gate costs silicon area, draws power, and adds propagation delay. Two toolkits from this chapter attack that number directly. Neither is new here. This section's job is integration, using both together, with gate-count reduction as the payoff. Modern designers rarely do this by hand past a handful of variables. Logic-synthesis software performs the same reductions automatically, across millions of gates. Working through it by hand, on problems small enough to check both ways, is what makes it possible to trust that software, and to sanity-check what it produces.

Table 13.7.1

Two Toolkits, One Goal

Here's how the two toolkits compare. Algebraic laws are best for short expressions, for spotting a known pattern, and for factoring shared pieces. Karnaugh maps are best for building a minimal form straight from a truth table. Does each guarantee the global minimum? Algebra does only if you spot the right law at every step. A K-map does, up to five or six variables, if the prime implicants are grouped correctly. Algebra scales to many variables, but it's easy to overlook a step. K-maps become hard to draw or read past five or six variables. So in practice, algebra tends to verify, factor or finish a simplification, while a K-map tends to start one from scratch.

Worked Example

F(x, y, z), by Algebra

Take F of x, y and z, equal to x y z, plus x y z prime, plus x prime y z, straight from a truth table. Algebraically, group the first two terms, which share x y. They factor to x y, times z plus z prime. By the complement law, that's just x y. So F equals x y plus x prime y z. Factor out y, giving y times the quantity x plus x prime z. And x plus x prime z equals x plus z, an identity available from section thirteen point three. So F equals y times x plus z, which is x y plus y z.

K-Map Route

F(x, y, z), by K-Map

Now the K-map route, placing the same three minterms on a three-variable map. The ones sit in column y z equals one one, in both rows, and in row x equals one, column one zero. The horizontal pair, in row x equals one, combines to x y. The vertical pair, in column one one, combines to y z. So F equals x y plus y z, identical to the algebra. Now count gates. The raw expression needed three three-input AND gates, one three-input OR gate, and two NOT gates, for z prime and x prime. That's six gates. The minimized form needs two two-input AND gates and one two-input OR gate. That's three gates, a fifty percent reduction.

13.7.2

Capstone: A Safety Interlock

Here's the capstone example. A factory machine's motor should run whenever the safety guard is closed and the operator's switch is engaged, regardless of anything else. It should also run whenever the machine is in inspector override mode, and the emergency stop hasn't been triggered, regardless of the guard or switch. Let A mean the guard is closed, and B that the switch is engaged. Let C mean the emergency stop has not been triggered, and D that override mode is active. A truth table built from this specification has exactly seven on-minterms. Written out, the canonical sum-of-products has seven four-literal terms. It's deliberately unwieldy, to make the payoff of simplifying it concrete.

Algebraic Route

From 7 Terms to 2

The algebraic route. First, group the four terms that share A B. They're all four combinations of C and D, with A B fixed. So they factor to A B, times C prime plus C, times D prime plus D. By the complement law, twice, that's just A B. That leaves A B, plus three terms ending in C D. Now a clever move. By the absorption law, A B plus A B C D is still A B. So adding the redundant term A B C D changes nothing. But now there are four C D terms, covering every combination of A and B. By the same pattern, they collapse to just C D. So M equals A B plus C D. Two terms, and no complemented literals at all.

Figure 13.7.2

K-Map Route

The K-map route places the same seven minterms on a four-variable map, with rows A B and columns C D, both in Gray code. The row A B equals one one is entirely filled, giving the group A B. The column C D equals one one is entirely filled too, giving the group C D. The two groups overlap at the cell A B C D. That's perfectly normal. K-map groups are allowed to share cells. Both methods agree. M equals A B plus C D.

Table 13.7.2

Gate Count, Before and After

Here are the gate counts for both examples. F went from six gates to three, a fifty percent reduction. And M went from twelve gates, seven four-input ANDs, an OR, and four NOTs, down to three. That's a seventy-five percent reduction. The final circuit is the deliverable a designer would actually fabricate: two two-input AND gates, for A B and C D, feeding one two-input OR gate. And this is exactly what an ALU's designer does to every internal circuit. Each candidate operation, the adder, the AND array, the OR array, starts as a truth table. Fewer gates in any of those paths means a shorter critical path through the whole unit, and a lower power budget for the finished chip.

13.7.3

Cross-Check by Expanding

A K-map grouping and an algebraic simplification should always agree, since both describe the same function. Algebra gives a direct way to confirm a K-map's answer. Suppose a K-map for some function G groups to x prime y, plus x z. Expand each term back to minterms. X prime y equals x prime y times z plus z prime, which is x prime y z plus x prime y z prime. And x z equals x z times y plus y prime, which is x y z plus x y prime z. Those are minterms zero one one, zero one zero, one one one and one zero one. In decimal, that's two, three, five and seven. If the original truth table has G equal to one at exactly those rows, the result is confirmed, without redrawing the map. If not, there's an error in the grouping or the table, worth finding before any gate gets built.

Takeaways

Fewer Gates, Checked Twice

To summarize, and to close the course. Simplification has a concrete payoff. Fewer gates mean less silicon area, lower power, and shorter propagation delay. Algebraic laws and Karnaugh maps are complementary, not competing. Algebra excels at factoring, verifying and finishing. K-maps excel at building a minimal form directly from a truth table. Introducing a redundant term, justified by absorption, is a legitimate move that can unlock further combination, as it did in going from seven terms to two. And any minimized expression can be checked, by expanding it back to minterms, and comparing with the truth table. Here's something to think about. Suppose a K-map and an algebraic simplification of the same expression produce two different-looking answers, each with the same number of gates. Does that disagreement mean one method made an error? What would you check first, and how does the cross-checking technique help you decide?

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 Simplifying Logic Circuits

When should I use algebraic laws instead of a Karnaugh map to simplify a logic circuit?
Use a K-map to build a minimal form straight from a truth table, and use algebraic laws for short expressions, known patterns, factoring, and finishing or verifying a result. K-maps become hard to draw or read past about five or six variables. Algebra scales further, but it can miss a step and leave the expression non-minimal.
How do you simplify F = xyz + xyz' + x'yz by algebra and by K-map?
Both methods give F = xy + yz. Algebraically, xyz + xyz' = xy(z+z') = xy, so F = xy + x'yz = y(x + x'z) = y(x+z). On a K-map, the pair in row x=1 gives xy and the pair in column yz=11 gives yz. The gate count drops from six to three.
How do you simplify a seven-minterm safety-interlock function to M = AB + CD?
Factor the four minterms containing AB: they cover every C,D combination, so AB(C'+C)(D'+D) = AB. Then absorption lets you add the redundant term ABCD, since AB + ABCD = AB. That gives four CD terms covering every A,B combination, which collapse to CD. The result is M = AB + CD, cutting 12 gates to 3.
How can I check that a K-map's minimal expression is correct without redrawing the map?
Expand each product term back into minterms and compare them with the rows where the truth table has output 1. For G = x'y + xz, x'y = x'yz + x'yz' and xz = xyz + xy'z. These are minterms 3, 2, 7, and 5. If G=1 at exactly rows 2, 3, 5, and 7, the form is confirmed.

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 →