Implementing Minimized Boolean Functions with Basic, NAND, and NOR Gates

Recommended resources

The freely available resources this lesson will direct you to.

Hello! In the last lesson, you reduced a truth table to a shorter Boolean expression using a K-map. Now you’ll turn that expression into a circuit. We’ll use the same function throughout, first with NOT, AND, and OR gates, then with NAND gates only and NOR gates only. The important skill is not merely choosing gate symbols; it is tracking every inversion so that all three circuits implement the original truth table.

Start with the expression, then identify the signals

Your K-map produced

Y = A B + B C .

The notation tells you what each part of a basic-gate circuit must do. NOT gates produce $A$ and $B$ . One AND gate produces $A B$ ; another produces $B C$ . An OR gate combines those two products to produce $Y$ . The wires carrying $B$ and $B$ are different signals, so be careful to connect each to the intended AND gate.

This is a sum-of-products circuit: AND gates form the product terms, and an OR gate forms their sum. It is a direct way to translate the minimized expression, but it is not the only way to build it. NAND and NOR are called universal gates because either gate type, used in sufficient numbers, can implement any Boolean function.

Read the short gate-construction portions of Gate Universality from All About Circuits before making those substitutions. Focus on what happens when an inversion is placed at a gate’s inputs or output.

Gate Universality

All About Circuits shows how NAND and NOR gates can supply the inversions needed to reproduce basic gate functions. Read the indicated subsections as a toolkit for the two implementations below.

In “Constructing the NOT function,” begin with the paragraph that opens “As you can see, there are two ways to use a NAND gate as an inverter.” Read the inverter discussion through its note on practical loading. For this lesson, focus on the logical result of connecting both inputs of a NAND or NOR gate to the same signal. Then read the AND construction in “Constructing the AND function,” from the opening explanation to the end of that subsection. Finally, in “Constructing the OR function,” read the OR construction, ending with its comparison of inverted NAND inputs and inverted NOR inputs.

For the circuits in this lesson, treat a two-input gate with its inputs connected to the same signal as an inverter:

NAND (X, X) = X, NOR (X, X) = X .

That connection makes a NAND-only or NOR-only schematic possible without quietly leaving a separate NOT gate in it.

Build the sum of products with NAND gates only

A NAND gate outputs the complement of a product. At first, that seems unhelpful: the expression needs $A B$ and $B C$ , not their complements. But De Morgan’s law gives those complemented products exactly the role we need:

Y = A B + B C = A B \cdot B C .

The inner complements are NAND outputs. The outer complement of their AND is another NAND output. We have changed the form of the expression, not its value.

Here is the complete connection plan using two-input NAND gates only. Name the intermediate wires so you can check what each gate actually produces:

a_{n} b_{n} p_{n} q_{n} Y = NAND (A, A) = A, = NAND (B, B) = B, = NAND (a_{n}, b_{n}) = A B, = NAND (B, C) = B C, = NAND (p_{n}, q_{n}) = p_{n} q_{n} = A B + B C .

That is five NAND gates when only $A$ , $B$ , and $C$ are supplied as inputs. If complemented inputs were already available from elsewhere, the circuit would not need to generate them again. Notice also that $p_{n}$ is not the first product term—it is its complement. Mistaking an intermediate wire’s polarity is a common way to produce a circuit that looks plausible but fails its truth table.

The following video shows the same double-inversion technique on a different minimized sum of products. You do not need to repeat its K-map work; concentrate on the conversion from expression to gate connections.

Simplification 6: NAND implementation example

Watch “Simplification 6: NAND implementation example” from Down to the Wires for a visual account of why NAND outputs can feed a final NAND gate in place of an AND-OR network.

In the worked example, start at the algebra, where the minimized sum is double-complemented and De Morgan’s law exposes the NAND stages. Then watch the gate conversion, where the circuit is redrawn with NAND gates. Track the inversions on the connections between stages; the example has more product terms than our two-term function.

Choose a useful form for NOR gates

A NOR gate outputs the complement of a sum. Consequently, a product of sums is especially convenient for a two-level NOR-only circuit: first NOR each sum, then NOR those results. The minimized sum-of-products expression remains correct, but we can rewrite it to expose that structure.

For our function, an equivalent product of sums is

Y = (A + B) (B + C) .

You can check the equivalence by expanding the right-hand side:

(A + B) (B + C) = A B + A C + B C .

The middle term adds no new output-1 cases. Whenever $A C = 1$ , either $B = 0$ , making $A B = 1$ , or $B = 1$ , making $B C = 1$ . Thus the expression has exactly the same behavior as $A B + B C$ .

Apply De Morgan’s law to the product of sums:

Y = (A + B) + (B + C) .

Each inner complement is a NOR output; the outer complement of their OR is a final NOR output. The complete two-input NOR-only connection plan is

a_{n} b_{n} s_{n} t_{n} Y = NOR (A, A) = A, = NOR (B, B) = B, = NOR (a_{n}, B) = A + B, = NOR (b_{n}, C) = B + C, = NOR (s_{n}, t_{n}) = (A + B) (B + C) .

Again, this uses five gates when the complemented inputs must be generated within the circuit. NAND naturally fits a sum of products; NOR naturally fits a product of sums. This is a design pattern, not a restriction: universality means either gate type can implement either expression, though a different form may make the connections simpler.

In the next video, the instructor constructs a NOR-only circuit for a different expression. Compare its final polarity check with the named intermediate signals above.

Implementing Boolean Expressions Using NOR Gates | Logic GATEs

“Implementing Boolean Expressions Using NOR Gates | Logic GATEs” from Engineering Funda demonstrates how inverters and De Morgan’s law lead to a NOR-only circuit, then checks the resulting expression.

Watch the basic circuit to identify the original NOT, AND, and OR operations. Skip the intervening bubble-drawing steps, then watch the NOR redraw, focusing on tied-input NOR inverters and the replacement of an AND gate with inverted inputs. Finish with the output check, where the gate outputs are translated back into a Boolean expression.

Check the circuit you actually connected

A correct algebraic transformation is useful only if the wires match it. After drawing a gate circuit, label every intermediate output with its Boolean expression, as we did for $p_{n}$ , $q_{n}$ , $s_{n}$ , and $t_{n}$ . Then simplify the expression at the final output. This catches a missing inversion more reliably than counting gate symbols.

For this example, the previous lesson’s K-map specifies output 1 at $000$ , $001$ , $011$ , and $111$ , with inputs ordered $A B C$ . Both the NAND and NOR implementations must reproduce those four 1s and produce 0 for the other four combinations. For instance, at $A = 0$ , $B = 1$ , $C = 0$ , the function is 0: neither $A B$ nor $B C$ is true. If a proposed circuit gives 1 there, inspect the polarity of its intermediate signals before changing the original expression.

A minimized Boolean expression is a starting point for implementation, not a guarantee that every gate arrangement has the same gate count or physical characteristics. For now, the decisive requirement is logical equivalence for every specified input combination.

Key takeaways

A minimized sum of products translates directly into NOT, AND, and OR gates. To use NAND gates only, form complemented product terms and combine them with a final NAND. To use NOR gates only, an equivalent product of sums lets you form complemented sum terms and combine them with a final NOR. In either case, generate any required complemented inputs with gates of the allowed type, and verify the finished circuit against the function’s truth table.

Next, you’ll implement a Boolean function with a multiplexer—another way to realize the same input-output behavior with a different circuit structure.