20 min read

De Morgan's Theorems

Break the bar and change the sign — how to remove a NOT from over a whole AND or OR.

The Two Theorems

Augustus De Morgan, a British mathematician, described two rules for a NOT bar that covers a whole expression: 1 A \cdot B = A + B — a NAND is the same as OR-ing the inverted inputs. 2 A + B = A \cdot B — a NOR is the same as AND-ing the inverted inputs. A memory phrase: "Break the bar, change the sign." When you split a long bar into short bars, AND becomes OR and OR becomes AND.

The two output columns are identical, so the theorem holds.

Worked example

Simplify X = NOT((A + B) · C̅)

Step Expression Law used 1 (A + B) \cdot C Start 2 A + B + C De Morgan on the outer bar (\cdot becomes +) 3 A \cdot B + C De Morgan on A + B, and double negation Answer: X = A \cdot B + C

X = 1

Try it:

Compare the X column with a NAND gate's truth table (1, 1, 1, 0). They are the same — De Morgan in action.

NOT A OR NOT B behaves exactly like one NAND gate.

Assignment questions often give a circuit with three inputs and NOT gates, and ask you to simplify it and check with a truth table. You need three skills together: circuit to expression, the laws, and De Morgan . Here is the complete method on a circuit of our own.

X = 1

Try it:

Compare the X column with the simplified answer below — they match in every row.

Label every gate output first: P, R, S and X.

Worked example

Step 2 — simplify, naming each law

Step Expression Law used 1 A + B + (A + B) \cdot C Start 2 A + B + C Redundancy: Y + Y \cdot C = Y + C, with Y = A + B 3 A \cdot B + C De Morgan: A + B = A \cdot B Answer: X = A \cdot B + C (or A + B + C — three gates instead of four).

The redundancy rule is very useful: Y + Y \cdot C = Y + C, and the same with the bar swapped, Y + Y \cdot C = Y + C . Proof with the second distributive law: Y + Y \cdot C = (Y + Y) \cdot (Y + C) = 1 \cdot (Y + C) = Y + C . The trick in step 2: look for a group that appears twice — once with a bar and once without. Here A + B appears in both terms, so treat it as one letter Y. Then finish with De Morgan to remove the long bar.

Worked example

Step 3 — check with a truth table

A B C A + B (A + B) \cdot C Original X A \cdot B + C 00010110011011010000001101111000000101011111000001110111 The last two columns are identical in all 8 rows, so the simplification is correct ✓.

Practice

Which expression equals NOT(A + B)?

The Two Theorems

Augustus De Morgan, a British mathematician, described two rules for a NOT bar that covers a whole expression: 1 A \cdot B = A + B — a NAND is the same as OR-ing the inverted inputs. 2 A + B = A \cdot B — a NOR is the same as AND-ing the inverted inputs. A memory phrase: "Break the bar, change the sign." When you split a long bar into short bars, AND becomes OR and OR becomes AND.

Proof by Truth Table

The two output columns are identical, so the theorem holds.

Using De Morgan to Simplify

Worked example

Simplify X = NOT((A + B) · C̅)

Step Expression Law used 1 (A + B) \cdot C Start 2 A + B + C De Morgan on the outer bar (\cdot becomes +) 3 A \cdot B + C De Morgan on A + B, and double negation Answer: X = A \cdot B + C

X = 1

Try it:

Compare the X column with a NAND gate's truth table (1, 1, 1, 0). They are the same — De Morgan in action.

NOT A OR NOT B behaves exactly like one NAND gate.

Putting It All Together: a Three-Input Circuit

Assignment questions often give a circuit with three inputs and NOT gates, and ask you to simplify it and check with a truth table. You need three skills together: circuit to expression, the laws, and De Morgan . Here is the complete method on a circuit of our own.

X = 1

Try it:

Compare the X column with the simplified answer below — they match in every row.

Label every gate output first: P, R, S and X.

Worked example

Step 2 — simplify, naming each law

Step Expression Law used 1 A + B + (A + B) \cdot C Start 2 A + B + C Redundancy: Y + Y \cdot C = Y + C, with Y = A + B 3 A \cdot B + C De Morgan: A + B = A \cdot B Answer: X = A \cdot B + C (or A + B + C — three gates instead of four).

The redundancy rule is very useful: Y + Y \cdot C = Y + C, and the same with the bar swapped, Y + Y \cdot C = Y + C . Proof with the second distributive law: Y + Y \cdot C = (Y + Y) \cdot (Y + C) = 1 \cdot (Y + C) = Y + C . The trick in step 2: look for a group that appears twice — once with a bar and once without. Here A + B appears in both terms, so treat it as one letter Y. Then finish with De Morgan to remove the long bar.

Worked example

Step 3 — check with a truth table

A B C A + B (A + B) \cdot C Original X A \cdot B + C 00010110011011010000001101111000000101011111000001110111 The last two columns are identical in all 8 rows, so the simplification is correct ✓.

Practice

Which expression equals NOT(A + B)?

Step	Expression	Law used
1	$A + B$	Start
2	$A \cdot B$	De Morgan: break the bar, + becomes ·
3	$A \cdot B$	Double negation

Step	Expression	Law used
1	$(A + B) \cdot C$	Start
2	$A + B + C$	De Morgan on the outer bar (· becomes +)
3	$A \cdot B + C$	De Morgan on $A + B$ , and double negation

Step	Expression	Law used
1	$A + B + (A + B) \cdot C$	Start
2	$A + B + C$	Redundancy: $Y + Y \cdot C = Y + C$ , with $Y = A + B$
3	$A \cdot B + C$	De Morgan: $A + B = A \cdot B$

A	B	C	$A + B$	$(A + B) \cdot C$	Original X	$A \cdot B + C$
0	0	0	1	0	1	1
0	0	1	1	0	1	1
0	1	0	0	0	0	0
0	1	1	0	1	1	1
1	0	0	0	0	0	0
1	0	1	0	1	1	1
1	1	0	0	0	0	0
1	1	1	0	1	1	1

Step	Expression	Law used
1	$A + B$	Start
2	$A \cdot B$	De Morgan: break the bar, + becomes ·
3	$A \cdot B$	Double negation