Logic Gate Design | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Logic Gate Design

Discrete Mathematics · Chapter 13: Boolean Algebra and Logic CircuitsSection 13.6 · lesson 86 of 878 min · free with a free account

← The Arithmetic Logic Unit (ALU)Next lesson: Simplifying Logic Circuits →

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

Six building blocks, and one is all a fabrication line needs.

  • Read all six gate symbols and truth tables
  • Prove NAND and NOR are universal
  • Build a circuit from an expression and count its levels
  • Construct a half-adder from two gates

Transcript

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

Boolean Algebra and Logic Circuits

Logic Gate Design

This section introduces all six standard logic gates, and shows how they build real circuits. Along the way, it proves a surprising fact. One gate type, on its own, is enough to build anything. We'll finish by building a half-adder, a genuinely useful piece of computer arithmetic, from just two gates.

The Opening Problem

One Shelf of Parts

A chip manufacturer doesn't stock six different shelves of parts, labeled AND, OR, NOT, NAND, NOR and XOR. Many standard-cell libraries used in real fabrication are built almost entirely from one gate type, repeated by the millions. Manufacturing one uniform shape over and over is cheaper and more reliable than switching between six. That's only possible because of a fact this section proves. Certain gates are universal. They can build every other gate, and therefore any circuit at all, using only copies of themselves. How to shrink a circuit to fewer gates is section thirteen point seven. Every circuit here is left exactly as built.

Figure 1

The Six Gate Symbols

A logic gate is a small circuit component that computes one Boolean operation on its inputs. Each has a standard schematic symbol. AND and OR keep their familiar shapes, and NOT is a triangle. NAND and NOR add a small circle, called a bubble, to the output of AND and OR. The bubble means, and then complement. And XOR adds a second curved line on the input side of the OR shape.

Table 1

Six Gates, Defined by Their Tables

Each gate's truth table defines it completely. AND is one only when both inputs are one. OR is one when at least one input is one. NAND is the opposite of AND: it's zero only when both inputs are one. NOR is the opposite of OR: it's one only when both inputs are zero. XOR is one exactly when the two inputs differ. And NOT, with a single input, just swaps zero and one. Real gates aren't limited to two inputs. A three-input AND outputs one only when all three inputs are one, and a three-input OR outputs one when at least one is.

13.6.2

What Makes a Gate Universal

A gate, or a set of gates, is universal, or functionally complete, if every Boolean function can be built from copies of it alone. Proving that sounds daunting. But section thirteen point three already did most of the work. Every Boolean function has a sum-of-products expression, built from nothing but AND, OR and NOT. So a single gate is universal the moment it can reproduce AND, OR and NOT by itself. Any sum-of-products expression, and so any function, then follows by substitution.

Worked Example

NOT, AND and OR From NAND Alone

Let's do it with NAND. Tie both inputs of a NAND gate to the same signal, A. The output is A times A, complemented. Since A times A is A, that's just A prime. So one NAND gate makes NOT. For AND, take A NAND B, and feed it into a second NAND, with both inputs tied together. The second gate undoes the complement, leaving A B. That's two NAND gates. For OR, first make A prime and B prime, each with its own NAND. Then NAND those together. By De Morgan's law, the complement of A prime B prime is A plus B. That's three gates in total. So NOT, AND and OR are all reachable with NAND alone. And since any function can be written with NOT, AND and OR, NAND alone is universal.

Not Every Gate

Useful Isn't the Same as Universal

The identical argument, with NOR in place of NAND, shows that NOR alone is universal too. But universality isn't automatic. Take XOR. Any circuit made only of XOR gates, fed by A and B, with no constant signal, can only ever compute zero, A, B, or A XOR B. None of those four matches AND's truth table. So being useful and being universal are different properties. NAND and NOR happen to have both. That's the fact behind the fabrication line. A process built around one universal gate gives up no capability. Any circuit could be rebuilt from nothing but NAND gates, or nothing but NOR gates. It costs more gates and more levels, but never anything the circuit can compute.

13.6.3

From Expression to Circuit

Now, building a circuit from an expression. Draw one gate per operation, and wire each gate's output to every input that uses it, working outward from the innermost operations. Take the door lock from section thirteen point three. Y equals A, times B plus C, times D prime. An OR gate takes B and C, and computes B plus C. A NOT gate takes D, and computes D prime. The first AND gate combines A with the OR gate's output. And the second AND gate combines that result with D prime, producing Y. That's four gates in all.

Tracing the Circuit

Checking the Circuit, and Counting Levels

Tracing specific inputs confirms the circuit matches the expression. Try A equals one, B zero, C one, and D zero. The OR gate outputs one, since C is one. The NOT gate outputs one, since D is zero. The first AND gate outputs one times one, which is one. And the second AND gate outputs one times one, so Y is one. That matches the expression directly: one, times zero plus one, times one, is one. This circuit has three levels. The OR and NOT gates are level one, since their inputs come straight from the circuit's inputs. The first AND is level two, and the second AND is level three. Level count is a genuine measure of complexity, separate from gate count. Each gate adds a little delay, so more levels means a signal takes longer to cross.

13.6.4

The Half-Adder

Here's a complete, useful example. Adding two one-bit numbers needs two outputs, a sum bit and a carry bit. Since one plus one is one zero in binary, the sum bit is one exactly when A and B differ. That's precisely XOR's truth table. And the carry is one exactly when both are one. That's precisely AND's truth table. So a half-adder is just those two gates, side by side, sharing the same two inputs. Check all four cases. Zero plus zero is zero zero. Zero plus one and one plus zero are zero one. And one plus one is one zero. Exactly XOR and AND, side by side. A full adder also accepts a carry-in, and extends this same pair of gates. Chained bit by bit, full adders form the addition circuitry inside a processor's ALU.

Takeaways

Small Gates, Any Circuit

To summarize. Each of the six gates has a standard symbol and a defining truth table. A bubble on AND or OR gives NAND or NOR, and an extra curve on OR gives XOR. NAND alone is universal, because it can build NOT, AND and OR, and every function has a sum-of-products form. The same holds for NOR. But universality isn't automatic. XOR alone can't build AND. Building a circuit means one gate per operation, wired from the innermost operations outward. And a couple of basic gates can do real work, like the half-adder. Here's something to think about. Using only XOR gates, fed by A and B, with no constant zero or one, is there any way to wire a circuit that computes AND? And what does your answer suggest about what makes NAND and NOR special, rather than a property every gate shares?

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 Logic Gate Design

How do you build NOT, AND, and OR using only NAND gates?
Tie both NAND inputs together to get NOT, since \overline{A\cdot A}=\overline{A}. For AND, feed \overline{AB} into a second NAND with its inputs tied, giving AB with two gates. For OR, NAND \overline{A} with \overline{B} and use De Morgan's law to get A+B, which takes three gates. Every function has a sum-of-products form, so NAND alone is universal.
Why is XOR not a universal gate even though it is useful?
XOR alone cannot build every Boolean function, so it is not universal. A circuit of only XOR gates fed by A and B, with no constant signals, can compute only 0, A, B, or A\oplus B. None of these matches the truth table of AND, so AND cannot be built. Being useful and being universal are different properties.
How do you draw a logic circuit from a Boolean expression and count its levels?
Draw one gate per operation, working from the innermost operations outward, and wire each gate's output to every input that uses it. Levels count the gates along the longest path: gates fed directly by the inputs are level one. For Y=A(B+C)D', the OR and NOT gates are level one, the first AND is level two, and the last AND is level three.
How do you make a half-adder from two logic gates?
A half-adder is an XOR gate and an AND gate that share the same two inputs A and B. XOR gives the sum bit, which is 1 exactly when the inputs differ. AND gives the carry bit, which is 1 only when both inputs are 1. For 1+1, the sum is 0 and the carry is 1, which is binary 10.

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 →