2.4 DeMorgan's law and bubble pushing

Why this matters

NAND and NOR are the cheapest two-input gates (Section 2.3), so circuits are often built from them, but expressions are easier to think about as AND and OR. DeMorgan's law is the bridge: it says how an inversion moves through a gate, and so how to turn any AND-OR design into one that uses only NAND or only NOR gates. It is also the law students get wrong most often, because everything depends on where the bar sits.

Learning goals

• Apply DeMorgan's laws to an expression, keeping the scope of every bar right.
• Redraw a NAND gate as an OR gate with inverted inputs, and a NOR gate as an AND gate with inverted inputs.
• Read the exact function of a circuit with input bubbles, counting every inversion once.
• Convert an AND-OR or OR-AND circuit into a NAND-NAND or NOR-NOR circuit by bubble pushing.
• Implement a circuit with NAND gates only or NOR gates only, and say how many gates it takes.

Intuition first

Say it in words. "It is not the case that both doors are open" means "at least one door is closed". "It is not the case that either door is open" means "both doors are closed". The first sentence turns a not-and into an or of nots, and the second turns a not-or into an and of nots. That is the whole law. An inversion applied to a group, and then passed to the members of the group, flips the group's operator.

For a programmer this is the familiar rewrite of !(a && b) into !a || !b. The analogy breaks in one way that matters here: in code the two forms can differ in evaluation order and side effects, but in a circuit they are two drawings of the same gate, and which drawing is more convenient depends on which gates you have.

DeMorgan's laws

Definition 2.4.1(DeMorgan's laws).

The complement of a sum is the product of the complements, and the complement of a product is the sum of the complements: $\overline{X + Y} = \overline{X}\,\overline{Y}$ and $\overline{XY} = \overline{X} + \overline{Y}$. Each side is equal to the other for every value of X and Y.

The memory rule is "break the bar, change the sign": cut the bar over the group, put a bar on each member, and switch AND to OR or OR to AND. The laws hold for any number of members. For three variables, $\overline{A + B + C} = \overline{A}\,\overline{B}\,\overline{C}$ and $\overline{ABC} = \overline{A} + \overline{B} + \overline{C}$.

The bar over the group and the bars over the members are different things, which is where mistakes start. The expression $\overline{AB}$ is a NAND of A and B. The expression $\overline{A}\,\overline{B}$ is an AND of two inverted signals, which is a NOR of A and B. They are different functions: when A is 1 and B is 0 the first is 1 and the second is 0. Written with the wrong bars, a correct law becomes a wrong answer.

The laws were already in use in the previous sections. They are the reason a sum of products turns into a product of sums when you complement it, and the reason NAND and NOR gates can stand in for AND and OR.

Gates with bubbles

A bubble on a gate means one inversion. DeMorgan's law says a NAND gate, which is an AND with a bubble on its output, does the same job as an OR gate with a bubble on each input. Likewise a NOR gate does the same job as an AND gate with a bubble on each input.

A logic schematic with inputs nand_a, nand_b, orb_a, orb_b, nor_a, nor_b, andb_a and andb_b and outputs nand_y, orb_y, nor_y and andb_y.

NAND gate g_nand: inputs nand_a and nand_b; output nand_y.

NOR gate g_nor: inputs nor_a and nor_b; output nor_y.

OR gate g_orb: inputs inverted orb_a and inverted orb_b; output orb_y.

AND gate g_andb: inputs inverted andb_a and inverted andb_b; output andb_y.

It computes nand_y = not (nand_a and nand_b).

It computes orb_y = not orb_a or not orb_b.

It computes nor_y = not (nor_a or nor_b).

It computes andb_y = not andb_a and not andb_b.

Description: Four gates, each with two inputs and one output. The top left gate is a NAND and the top right gate is an OR with a bubble on each input. The bottom left gate is a NOR and the bottom right gate is an AND with a bubble on each input.

Figure 2.4.1. Top row: a NAND gate and an OR gate with a bubble on each input. Bottom row: a NOR gate and an AND gate with a bubble on each input. In each row the two gates compute the same function.

The drawing is checked: the program that drew Figure 2.4.1 evaluated each gate, bubbles included, against its expression. The two gates in a row also match the two sides of DeMorgan's law above.

Definition 2.4.2(bubble pushing).

Bubble pushing is redrawing a gate by flipping every bubble on it and switching its shape between AND and OR. Every input and the output are flipped: a bubble appears where there was none and disappears where there was one. The result computes the same function.

Check it on a gate with a bubble on one input only. An OR gate with a bubble on its first input computes $\overline{A} + B$. Flipping gives an AND gate with a bubble on its second input and on its output, which is $\overline{A\overline{B}}$, and $\overline{A} + B = \overline{A\overline{B}}$ confirms they agree.

Two bubbles on the two ends of one wire, one at the output of a gate and one at the input of the next, cancel each other, because inverting twice changes nothing. Bubble pushing moves bubbles across gates and cancels them in pairs until the drawing uses the gates you have.

Reading bubbles without miscounting

Every bubble you see is one inversion, and every inversion is a bubble. A NOT gate is a triangle with a bubble at its tip, and that bubble is the inversion. The gate that the NOT feeds has no extra inversion unless a bubble is drawn on its own input. When you read a circuit, write down each bubble you see before you write the expression: the ones on inputs, the ones on outputs, and the one inside each NOT symbol. A bubble that you count twice, or one that you miss, changes the function.

AND-OR into NAND-NAND

A two-level AND-OR circuit has bubbles nowhere. Put two bubbles on each wire between the levels, one at the end of the AND gate and one at the start of the OR gate: they cancel, so the function is unchanged. An AND gate with a bubble on its output is a NAND gate, and an OR gate with a bubble on each input is another NAND by DeMorgan. The three stages are below.

A logic schematic with inputs A, B, C and D and output Y.

AND gate g1: inputs A and B; output n1.

AND gate g2: inputs C and D; output n2.

OR gate g3: inputs n1 and n2; output Y.

It computes Y = A and B or C and D.

A logic schematic with inputs A, B, C and D and output Y.

NAND gate g1: inputs A and B; output n1.

NAND gate g2: inputs C and D; output n2.

OR gate g3: inputs inverted n1 and inverted n2; output Y.

It computes Y = A and B or C and D.

A logic schematic with inputs A, B, C and D and output Y.

NAND gate g1: inputs A and B; output n1.

NAND gate g2: inputs C and D; output n2.

NAND gate g3: inputs n1 and n2; output Y.

It computes Y = A and B or C and D.

Description: Three circuits with inputs A, B, C and D and output Y. The top circuit has two AND gates feeding an OR gate. The middle circuit has two NAND gates feeding an OR gate with a bubble on each input. The bottom circuit has two NAND gates feeding a third NAND gate.

Figure 2.4.2. Three stages of one circuit. Top: AND-OR. Middle: a bubble pair on each wire between the levels. Bottom: two levels of NAND gates.

In algebra this is double negation followed by DeMorgan: $AB + CD = \overline{\overline{AB} \cdot \overline{CD}}$. The dual transformation takes an OR-AND circuit to NOR-NOR: $(A + B) \cdot (C + D)$ $= \overline{\overline{A + B} + \overline{C + D}}$. In a NOR-NOR circuit the first level is two NOR gates and the second level is one NOR gate.

Only NOR gates (3 NOR).

A logic schematic with inputs A, B, C and D and output Y.

NOR gate g1: inputs A and B; output n1.

NOR gate g2: inputs C and D; output n2.

NOR gate g3: inputs n1 and n2; output Y.

It computes Y = (A or B) and (C or D).

Description: A circuit with inputs A, B, C and D and output Y: two NOR gates, one on A and B and one on C and D, feed a third NOR gate.

Figure 2.4.3. An OR-AND function, (A + B)(C + D), as two levels of NOR gates.

If the original expression has inverted literals, such as $\overline{A}B$, the inverters stay, and in a NAND-only design they become NANDs with tied inputs.

A worked conversion

Example 2.4.1(a circuit with bubbles, in NOR gates only).

The circuit in Figure 2.4.4 has four inputs and four gates. Go gate by gate and list every bubble. The upper AND gate has a bubble on its A input, and its other input comes from a NOT gate on B, whose own bubble is the one inversion of B. The lower AND gate has a bubble on its C input, and D comes straight in. The OR gate has no bubbles. So the upper AND gate computes $\overline{A}\,\overline{B}$ and the lower one $\overline{C}D$, and the output is $\overline{A}\,\overline{B} + \overline{C}D$.

A logic schematic with inputs A, B, C and D and output F.

NOT gate n1: input B; output n1.

AND gate g1: inputs inverted A and n1; output n2.

AND gate g2: inputs inverted C and D; output n3.

OR gate g3: inputs n2 and n3; output F.

It agrees with the function logic:ch02/demorgan-practice#F.

Description: A circuit with inputs A, B, C and D and output F. The upper AND gate has a bubble on its first input, which is A, and its second input comes from a NOT gate on B. The lower AND gate has a bubble on its first input, which is C, and D on its second input. An OR gate combines the two AND gates.

Figure 2.4.4. Two AND gates with bubbles, one fed through a NOT gate, and an OR gate.

We want the same function with NOR gates only. Take the pieces in turn.

The product $\overline{A}\,\overline{B}$ is already one NOR gate on A and B, because $\overline{A}\,\overline{B} = \overline{A + B}$.

The product $\overline{C}D$ has one inverted input and one plain one. A NOR gate gives the AND of two inverted signals, so we need D inverted as well, and then $\overline{C}D = \overline{C + \overline{D}}$. The inverted D is a NOR gate with both inputs tied, so this product takes two NOR gates.

The last step is the OR gate. An OR is a NOR followed by a NOT, and the NOT is another NOR with tied inputs, so the OR takes two NOR gates. Altogether the circuit has five NOR gates, and Figure 2.4.5 checks it against the function above.

Only NOR gates (5 NOR). 5 gates in all.

A logic schematic with inputs A, B, C and D and output F.

NOR gate g_ab: inputs A and B; output n1.

NOR gate n_d: inputs D and D; output n2.

NOR gate g_cd: inputs C and n2; output n3.

NOR gate g_or: inputs n1 and n3; output n4.

NOR gate g_inv: inputs n4 and n4; output F.

It agrees with the function logic:ch02/demorgan-practice#F.

Description: A circuit with inputs A, B, C and D and output F made of five NOR gates: one on A and B, one with both inputs connected to D, one on C and the inverted D, a NOR gate on the outputs of the first and third of these, and a final NOR gate with both inputs connected to the previous gate's output.

Figure 2.4.5. The same function in five NOR gates.

Example 2.4.2(one inverted input, in NAND gates only).

Draw $\overline{A} + B$ as a circuit and convert it. The most direct drawing is one OR gate with a bubble on the input that carries A. Convert it in four stages, shown in order in Figure 2.4.6.

First, the OR gate with a bubble on A. Second, add a bubble to the B input, and cancel it with a NOT gate on B so the function does not change: A is inverted once, by its bubble, and B twice, by the NOT and by the bubble, which is the same as not at all. Third, the OR gate with two input bubbles is a NAND gate, so the drawing is a NAND with a NOT on one input. Fourth, the NOT is a NAND with tied inputs, and the circuit has two NAND gates.

A logic schematic with inputs A and B and output P.

OR gate g1: inputs inverted A and B; output P.

It agrees with the function logic:ch02/practice-2-1#P.

A logic schematic with inputs A and B and output P.

NOT gate nb: input B; output n1.

OR gate g1: inputs inverted A and inverted n1; output P.

It agrees with the function logic:ch02/practice-2-1#P.

A logic schematic with inputs A and B and output P.

NOT gate nb: input B; output n1.

NAND gate g1: inputs A and n1; output P.

It agrees with the function logic:ch02/practice-2-1#P.

Only NAND gates (2 NAND). 2 gates in all.

A logic schematic with inputs A and B and output P.

NAND gate nb: inputs B and B; output n1.

NAND gate g1: inputs A and n1; output P.

It agrees with the function logic:ch02/practice-2-1#P.

Description: Four circuits with inputs A and B and output P. The first is one OR gate with a bubble on its A input. The second is an OR gate with a bubble on each input and a NOT gate on B. The third is a NAND gate with a NOT gate on B. The fourth is two NAND gates, one with both inputs connected to B, feeding the second NAND gate along with A.

Figure 2.4.6. Four stages of the conversion, from top to bottom: the OR gate with one bubble, the OR gate with two bubbles and a NOT, a NAND gate and a NOT, and two NAND gates.

When pushing bubbles is not enough

Bubble pushing converts a circuit mechanically, one gate at a time, and the result is correct but not always small. Simplifying the expression first can do better.

Example 2.4.3(five NOR gates, or three).

Consider $\overline{(A + B) \cdot (B + \overline{C})}$. As a circuit, two OR gates feed a NAND gate, and the second OR gate has a bubble on the input that carries C.

A logic schematic with inputs A, B and C and output Q.

OR gate g1: inputs A and B; output n1.

OR gate g2: inputs B and inverted C; output n2.

NAND gate g3: inputs n1 and n2; output Q.

It agrees with the function logic:ch02/practice-2-2#Q.

Description: A circuit with inputs A, B and C and output Q. An OR gate takes A and B. A second OR gate takes B and C, with a bubble on its C input. A NAND gate combines the two OR gates.

Figure 2.4.7. Two OR gates, one with an inverted C input, feeding a NAND gate.

To use NOR gates only by bubble pushing, make each OR a NOR followed by a NOT, invert C with a tied NOR, and note that the AND of two inverted signals is a NOR. The result has five NOR gates:

Only NOR gates (5 NOR). 5 gates in all.

A logic schematic with inputs A, B and C and output Q.

NOR gate g_x: inputs A and B; output n1.

NOR gate n_c: inputs C and C; output n2.

NOR gate g_y: inputs B and n2; output n3.

NOR gate g_or: inputs n1 and n3; output n4.

NOR gate g_inv: inputs n4 and n4; output Q.

It agrees with the function logic:ch02/practice-2-2#Q.

Description: A circuit with inputs A, B and C and output Q made of five NOR gates: one on A and B, one with both inputs connected to C, one on B and that inverted C, a NOR gate on the first and third outputs, and a final NOR gate with both inputs connected to the previous output.

Figure 2.4.8. Q from bubble pushing: five NOR gates.

The algebra gives a smaller circuit. The sums share B, so the OR-over-AND distributive law pulls it out. A product with a plain A and an inverted C is a NOR of an inverted A and C, by DeMorgan. Each line follows from the one above by the law beside it.

Step-by-step simplification; each line names the law used to get from the line above

Expression	Law used
$\overline{(A + B) \cdot (B + \overline{C})}$
$= \overline{(B + A) \cdot (B + \overline{C})}$	Commutative
$= \overline{B + A\overline{C}}$	Distributive
$= \overline{B + \overline{\overline{A}} \cdot \overline{C}}$	Double negation
$= \overline{B + \overline{\overline{A} + C}}$	DeMorgan

The last line is a NOR of B and a NOR of $\overline{A}$ and C, and the inverted A is one more NOR with tied inputs. That is three NOR gates:

Only NOR gates (3 NOR). 3 gates in all.

A logic schematic with inputs A, C and B and output Q.

NOR gate n_a: inputs A and A; output n1.

NOR gate g1: inputs n1 and C; output n2.

NOR gate g2: inputs n2 and B; output Q.

It agrees with the function logic:ch02/practice-2-2#Q.

Description: A circuit with inputs A, C and B and output Q made of three NOR gates: one with both inputs connected to A, one on that inverted A and C, and a third on that output and B.

Figure 2.4.9. The same Q in three NOR gates.

Course conventions

How CSE 369 writes this

Bubbles may sit on gate inputs as well as outputs. NOT is an overbar in every expression: a bar over a whole sum or product is one inversion of the group, and bars over letters are inversions of the letters. A drawing that uses a constrained gate set (NAND only, NOR only) has no NOT gates and no bubbles on inputs: every inversion is made by a gate of the allowed kind.

Pitfalls

Common pitfall

• Breaking a bar over a product but keeping the AND, so that $\overline{AB}$ becomes $\overline{A}\,\overline{B}$. The operator must change when the bar breaks: the right answer is $\overline{A}+\overline{B}$.
• Flipping only some of a gate's bubbles. Bubble pushing flips every input and the output, and switches AND and OR.
• Miscounting inversions when reading a circuit. A NOT symbol's own bubble is its inversion, and counting it a second time as an input bubble turns $\overline{B}$ back into plain B.
• Leaving a double inversion in the drawing, such as a NOT feeding a bubble, a pair of tied NAND gates in series, or two bubbles on one wire. They cancel, so remove both and save the gates.
• Putting a bubble on one end of a wire without the matching bubble on the other. A lone bubble inverts a signal, and the function changes.

Check your understanding

Take the quiz (5 questions)

Which of these is equal to $\overline{A+B+C}$?

$\overline{A}\,\overline{B}\,\overline{C}$$\overline{A} + \overline{B} + \overline{C}$$\overline{ABC}$

Which of these is the function of the circuit with two AND gates and an OR gate that has a bubble on A, an inverter on B, a bubble on C and a plain D?

$\overline{A}\,\overline{B} + \overline{C}D$$\overline{A}B + \overline{C}D$$\overline{A}\,\overline{B} + CD$

How many NOR gates does the five-gate circuit for the practice function use?

543

How many NAND gates does the final stage of the conversion of the one-bubble OR gate use?

231

How many NOR gates does the simplified circuit for Q use?

354

Exercises

Exercise 2.4.1

Use DeMorgan's law to write the complement of $A\overline{B} + C$ without any bar over more than one letter. Name the law at each step.

Hint

Break the outer bar first, then the bar over the product, then remove double bars.

Solution

Each line follows from the one above by the law beside it.

Step-by-step simplification; each line names the law used to get from the line above

Expression	Law used
$\overline{A\overline{B} + C}$
$= \overline{A\overline{B}} \cdot \overline{C}$	DeMorgan
$= (\overline{A} + \overline{\overline{B}}) \cdot \overline{C}$	DeMorgan
$= (\overline{A} + B) \cdot \overline{C}$	Double negation

The answer is $(\overline{A} + B) \cdot \overline{C}$. The sum of products turned into a product of sums, as it always does.

Tags: Warm-upBoolean algebra

Exercise 2.4.2

Write the output Y of Figure 2.4.10 as an expression, listing each bubble first. Then use DeMorgan's law to remove every bar that covers more than one letter.

A logic schematic with inputs A, B, C and D and output Y.

OR gate g1: inputs A and inverted B; output n1.

AND gate g2: inputs inverted C and D; output n2.

NOR gate g3: inputs n1 and n2; output Y.

It agrees with the function logic:ch02/s04-read#Y.

Description: A circuit with inputs A, B, C and D and output Y. An OR gate takes A and B with a bubble on its B input. An AND gate takes C and D with a bubble on its C input. A NOR gate takes the two outputs.

Figure 2.4.10. An OR gate and an AND gate, each with one bubble on an input, feeding a NOR gate.

Hint

There are three bubbles in the picture: one on the B input of the OR gate, one on the C input of the AND gate, and one on the output of the NOR gate.

Solution

The OR gate computes $A + \overline{B}$ and the AND gate computes $\overline{C}D$. The NOR gate inverts their OR, so Y is $\overline{A + \overline{B} + \overline{C}D}$. Break the bar:

Step-by-step simplification; each line names the law used to get from the line above

Expression	Law used
$\overline{A + \overline{B} + \overline{C}D}$
$= \overline{A} \cdot \overline{\overline{B}} \cdot \overline{\overline{C}D}$	DeMorgan
$= \overline{A} \cdot B \cdot \overline{\overline{C}D}$	Double negation
$= \overline{A} \cdot B \cdot (\overline{\overline{C}} + \overline{D})$	DeMorgan
$= \overline{A} \cdot B \cdot (C + \overline{D})$	Double negation

The answer is $\overline{A} \cdot B \cdot (C + \overline{D})$.

Tags: StandardGates and schematicsBoolean algebra

Exercise 2.4.3

Implement $A\overline{B} + C$ with NAND gates only. How many gates does it take?

Hint

Start from the AND-OR circuit. Put a bubble pair on the wire between the levels, then make the two inverted inputs from tied NAND gates.

Solution

The AND-OR circuit has an AND gate on A and an inverted B, and an OR gate that combines it with C. The NAND-NAND form has a NAND on A and an inverted B in the first level, and a second-level NAND that takes that output and an inverted C: an OR of two signals is a NAND of their complements. The wire C goes straight to the second level, so no first-level gate is there to supply the bubble, and the inverted C needs a gate of its own. Each inverted input is a NAND with tied inputs. There are two inverters, one for B and one for C, and two NAND gates for the two levels: four gates in all.

Only NAND gates (4 NAND).

A logic schematic with inputs A, B and C and output Y.

NAND gate n_b: inputs B and B; output n1.

NAND gate n_c: inputs C and C; output n2.

NAND gate g1: inputs A and n1; output n3.

NAND gate g2: inputs n3 and n2; output Y.

It agrees with the function logic:ch02/s04-nand-ex#Y.

Description: A circuit with inputs A, B and C and output Y made of four NAND gates: one with both inputs connected to B, one with both inputs connected to C, a NAND on A and the inverted B, and a final NAND on that output and the inverted C.

Figure 2.4.11. Four NAND gates for A times not B, plus C.

Tags: StandardGates and schematics

Exercise 2.4.4

Implement $\overline{(\overline{A} + B) \cdot (C + B)}$ with NOR gates only. First convert it by bubble pushing and count the gates. Then rewrite it with algebra and find a circuit with fewer gates.

Hint

The two sums share B, so pull it out with the OR-over-AND distributive law, then turn the product that remains into a NOR.

Solution

Bubble pushing converts each gate in turn: a NOR to invert A, a NOR for each of the two sums, a NOR for the AND of their complements, and a tied NOR to undo it. That is five gates.

Only NOR gates (5 NOR). 5 gates in all.

A logic schematic with inputs A, C and B and output R.

NOR gate n_a: inputs A and A; output n1.

NOR gate g_x: inputs n1 and B; output n2.

NOR gate g_y: inputs C and B; output n3.

NOR gate g_z: inputs n2 and n3; output n4.

NOR gate g_inv: inputs n4 and n4; output R.

It agrees with the function logic:ch02/s04-nor-ex#R.

Description: A circuit with inputs A, C and B and output R made of five NOR gates: one with both inputs connected to A, one on that inverted A and B, one on C and B, a NOR gate on the second and third outputs, and a final NOR gate with both inputs connected to the previous gate's output.

Figure 2.4.12. R by bubble pushing: five NOR gates.

The algebra gives a better answer. Each line follows from the one above by the law beside it.

Step-by-step simplification; each line names the law used to get from the line above

Expression	Law used
$\overline{(\overline{A} + B) \cdot (C + B)}$
$= \overline{(B + \overline{A}) \cdot (B + C)}$	Commutative
$= \overline{B + \overline{A}C}$	Distributive
$= \overline{B + \overline{A} \cdot \overline{\overline{C}}}$	Double negation
$= \overline{B + \overline{A + \overline{C}}}$	DeMorgan

The last line is a NOR of B and a NOR of A and an inverted C, and the inverted C is a NOR with tied inputs. That is three NOR gates.

Only NOR gates (3 NOR). 3 gates in all.

A logic schematic with inputs A, C and B and output R.

NOR gate n_c: inputs C and C; output n1.

NOR gate g1: inputs A and n1; output n2.

NOR gate g2: inputs n2 and B; output R.

It agrees with the function logic:ch02/s04-nor-ex#R.

Description: A circuit with inputs C, A and B and output R made of three NOR gates: one with both inputs connected to C, one on A and that inverted C, and a third on that output and B.

Figure 2.4.13. R in three NOR gates.

Tags: ChallengeGates and schematicsBoolean algebra