De Morgan's Laws in Practice: NAND-Only Circuit Design

TL;DR: De Morgan’s two identities — $\overline{A \cdot B} = \overline{A} + \overline{B}$ and $\overline{A + B} = \overline{A} \cdot \overline{B}$ — let you swap AND for OR (and vice versa) by distributing inversion. The practical payoff: any logic function can be implemented in NAND-only or NOR-only form, which is exactly what CMOS chip designers and FPGA synthesizers do.

The two De Morgan identities — $\overline{A \cdot B} = \overline{A} + \overline{B}$ and $\overline{A + B} = \overline{A} \cdot \overline{B}$ — are easy to memorize. The harder question is how working engineers actually use them. The answer spans CMOS transistor-level design, FPGA synthesis, NAND-only and NOR-only implementations, and multi-level circuit optimization.

This article focuses on putting De Morgan’s Laws to work in real design scenarios — how they shrink gate counts in actual circuits, how they let you implement any logic in NAND-only or NOR-only form, and how the simulator makes the equivalences obvious.

Quick Recap: The Two Laws

For reference, De Morgan’s two identities:

These generalize to $n$ variables:

Explore NAND Gate Behavior

Application 1: Converting to NAND-Only Implementation

In static CMOS, a two-input NAND uses four transistors, while a noninverting AND can be implemented as a NAND followed by an inverter. That makes NAND a useful primitive, but it does not mean a whole design should use only NAND gates. ASIC synthesis maps logic into the cells available in a characterized library, and FPGA synthesis maps primarily into lookup tables and dedicated resources.

The Conversion Process

Any Sum-of-Products (SOP) expression can be converted to NAND-NAND form in two steps:

1. Start with the SOP: $Y = AB + CD$
2. Apply double negation: $Y = \overline{\overline{AB + CD}}$
3. Apply De Morgan’s to the outer bar: $Y = \overline{\overline{AB} \cdot \overline{CD}}$

The result is a two-level NAND-NAND circuit: the first level NANDs compute $\overline{AB}$ and $\overline{CD}$, and the second level NAND combines them.

Worked Example: 3-Variable Function

Convert $Y = A\overline{B}C + \overline{A}BC$ to NAND-only:

Step 1: Double-negate: $Y = \overline{\overline{A\overline{B}C + \overline{A}BC}}$

Step 2: Apply De Morgan’s to the outer bar:

Implementation:

• Gate 1 (NAND): Inputs $A$, $\overline{B}$, $C$ — outputs $\overline{A\overline{B}C}$
• Gate 2 (NAND): Inputs $\overline{A}$, $B$, $C$ — outputs $\overline{\overline{A}BC}$
• Gate 3 (NAND): Inputs are outputs of Gate 1 and Gate 2 — outputs $Y$

The NOT gates for $\overline{A}$ and $\overline{B}$ are implemented by tying together the two inputs of a NAND gate.

Gate count in this schematic: 3 NAND gates + 2 NAND-based inverters = 5 NAND gates. The direct AND-OR drawing also uses five gates but three gate types. A single-type construction is convenient for a restricted package inventory; a silicon implementation should be judged using the target library’s area, delay, and power data.

Try NAND Universal Logic Template

Application 2: Converting to NOR-Only Implementation

The dual of the NAND-NAND conversion works for Product-of-Sums (POS) expressions, yielding NOR-NOR circuits.

The Conversion Process

1. Start with a POS: $Y = (A + B)(C + D)$
2. Double-negate: $Y = \overline{\overline{(A+B)(C+D)}}$
3. Apply De Morgan’s to the outer bar: $Y = \overline{\overline{(A+B)} + \overline{(C+D)}}$

The result is a two-level NOR-NOR circuit: the first level NORs compute $\overline{A+B}$ and $\overline{C+D}$, and the second NOR combines them.

NOR gates can be the natural match for product-of-sums logic or for a library that provides a suitable compound cell. The choice between NAND, NOR, and mixed-gate forms depends on fan-in, drive, loading, placement, and the target technology rather than a universal preference.

Application 3: Multi-Level Circuit Optimization

Real circuits are rarely limited to two levels. When you encounter multi-level logic with inversions scattered throughout, De Morgan’s Laws let you “push bubbles” through the circuit to cancel redundant inversions and reduce gate count.

Worked Example: Simplifying a 4-Gate Expression

Simplify: $Y = \overline{\overline{A \cdot B} + \overline{C \cdot D}}$

Step 1 — Apply De Morgan’s to the outer bar (the expression inside is a sum of two terms):

Step 2 — Cancel the double negations:

We started with what appeared to be a complex expression requiring 2 NAND gates, 1 NOR gate, and an output inverter. After applying De Morgan’s Laws twice, it reduces to a single 4-input AND gate.

Worked Example: Bubble Pushing in a Three-Level Circuit

Given: $Y = \overline{\overline{(A + B)} \cdot \overline{(C + D)} \cdot E}$

Step 1 — Apply De Morgan’s to the outer NAND:

Step 2 — Cancel double negations:

At the Boolean-symbol level, the expression collapses to one 5-input OR with one complemented input. Whether that is smaller, faster, or lower power in hardware depends on the available cells or LUTs, their fan-in, routing, and load.

Application 4: FPGA Synthesis and Technology Mapping

When you write Verilog or VHDL, the synthesis tool does not directly translate your code into AND and OR gates. Instead, it performs technology mapping — converting your logic into the specific primitives available on the target FPGA or ASIC library. De Morgan’s Laws are a core transformation in this process.

How Synthesis Tools Use De Morgan’s Laws

1. LUT mapping: An FPGA lookup table can implement any Boolean function up to its input capacity. Synthesis simplifies and factors the logic before packing functions into LUTs; De Morgan transformations are among the equivalent rewrites it may use.

2. Polarity optimization: Many library gates naturally provide inverted outputs or inputs. Bubble pushing can preserve a useful complemented signal and avoid adding a separate inverter.

3. Critical-path optimization: A tool may choose an equivalent NAND, NOR, or compound-cell form when the characterized library and placement predict a better timing result. The winning form is technology-dependent.

A Concrete Verilog Example

Consider this RTL code:

assign y = ~(a & b) | ~(c & d);

The synthesis tool recognizes $\overline{AB} + \overline{CD}=\overline{ABCD}$. It may use separate gates, a compound library cell, or a single FPGA LUT if the input capacity permits. The RTL specifies behavior; reports from the selected target establish the implemented area and timing.

Application 5: Legacy Hardware and Gate Substitution

If you are working with vintage hardware or constrained parts inventories, De Morgan’s Laws are your primary tool for gate substitution.

The Universal Gate Constructions

Using only NAND gates, you can build every other gate:

The OR construction follows directly from De Morgan’s: $A + B = \overline{\overline{A} \cdot \overline{B}}$, which is NAND(NOT A, NOT B).

This is also useful with a constrained parts inventory. If only sections of a 74LS00 are available, three NAND sections can implement one OR function, provided the replacement meets the original circuit’s voltage, fan-out, timing, power, and unused-input requirements.

Verification with the Oscilloscope

When building De Morgan transformations in DigiSim, compare the original and transformed outputs. An OSCILLOSCOPE_8CH can display both outputs alongside their inputs.

Exhaustively checking the stable input combinations verifies the truth table. Exercising input transitions can also reveal differences represented by the simulator’s propagation-delay model, but it does not establish timing for a particular physical implementation.

Logically equivalent circuits are not necessarily timing-equivalent. A NAND-NAND and an AND-OR drawing may both have two logical levels, yet cell delays, input slew, fan-out, loading, and routing can differ. Additional inversion levels can lengthen a path, but only a target-specific timing analysis supports a physical speed claim.

Common Pitfalls in Applied De Morgan’s

The Partial Flip

Students often remember to invert each term but forget to flip the operator. This produces $\overline{A \cdot B} = \overline{A} \cdot \overline{B}$, which is incorrect. Always change AND to OR or OR to AND.

Floating Inputs in NAND/NOR Circuits

When building NAND-only circuits in DigiSim, give every relevant input a defined source. A real CMOS input left floating can acquire an unpredictable voltage, switch in response to coupled noise, and increase supply current. Tie unused physical inputs to the appropriate valid logic level according to the device data sheet; in a schematic exercise, use the corresponding CONSTANT source.

Confusing Logical Equivalence with Timing Equivalence

Two circuits with the same truth table may have very different propagation delays. When converting a circuit using De Morgan’s Laws, always check whether the transformation adds or removes gate levels.

Challenge: Multi-Level Optimization

Take this expression and reduce it to the minimum number of gates:

Hint: Apply De Morgan’s to the outer NAND, cancel double negations, and see what remains. (Solution: $Y = (A + \overline{B}) + (\overline{A} + B) = A + \overline{A} + B + \overline{B} = 1$. The entire expression is always true — no gates needed at all.)

This is a powerful demonstration: De Morgan’s Laws combined with the Complement Law can sometimes eliminate entire circuits.

Continue with Karnaugh maps for a visual approach to the same simplifications, or revisit Boolean algebra fundamentals. Open the NAND component reference to wire one of these conversions yourself.