Noesis
3.1.8Boolean Algebra & Logic Gates

De Morgan's theorems

1,791 words8 min readdifficulty · medium6 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHAT are they?

They generalise to any number of variables: A⋅B⋅C⋯‾=A‾+B‾+C‾+⋯\overline{A\cdot B\cdot C\cdots} = \overline{A}+\overline{B}+\overline{C}+\cdots A+B+C+⋯‾=A‾⋅B‾⋅C‾⋯\overline{A+ B+ C+\cdots} = \overline{A}\cdot\overline{B}\cdot\overline{C}\cdots

WHY are they true? (Derive from scratch — truth tables)

We don't accept these on faith. Two Boolean expressions are equal iff they produce the same output for every input combination. So we build the truth table.

Theorem 1: prove A⋅B‾=A‾+B‾\overline{A\cdot B} = \overline{A} + \overline{B}

AA BB A⋅BA\cdot B A⋅B‾\overline{A\cdot B} A‾\overline{A} B‾\overline{B} A‾+B‾\overline{A}+\overline{B}
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

Why this step? The two bold columns (A⋅B‾\overline{A\cdot B} and A‾+B‾\overline{A}+\overline{B}) match on every row → the expressions are provably equal. ∎

Theorem 2: prove A+B‾=A‾⋅B‾\overline{A+B} = \overline{A}\cdot\overline{B}

AA BB A+BA+B A+B‾\overline{A+B} A‾\overline{A} B‾\overline{B} A‾⋅B‾\overline{A}\cdot\overline{B}
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Why this step? Again both bold columns match on all four rows → equal. ∎

Figure — De Morgan's theorems

HOW to apply it (the mechanical recipe)

To negate any expression:

  1. Change every AND (⋅\cdot) to OR (++) and every OR to AND.
  2. Negate each individual variable/term.
  3. Keep 0↔1 swapped if constants appear.

This is exactly the complement procedure — De Morgan is the engine behind "dualise and complement."

Common mistakes (Steel-manned)

Active recall

Recall Cover the answers and test yourself
  • Q: What are the two theorems? → A⋅B‾=A‾+B‾\overline{A\cdot B}=\overline A+\overline B and A+B‾=A‾⋅B‾\overline{A+B}=\overline A\cdot\overline B.
  • Q: State the 4-word slogan → "Break the bar, change the sign."
  • Q: How do you prove them rigorously? → identical truth-table columns.
  • Q: Why do designers care? → convert circuits to NAND-only / NOR-only (bubble pushing).
  • Q: A+B‾\overline{A+B} equals? → A‾⋅B‾\overline A\cdot\overline B.
Recall Feynman: explain to a 12-year-old

Imagine a rule: "You may go outside only if it's not (raining AND cold)." That's the same as saying "You may go outside if it's not raining OR not cold." One "no" spread over two conditions turns the "and" into an "or." That flip is exactly what De Morgan's theorem does — it's just common sense written with symbols.

Connections

  • Boolean Algebra Laws — De Morgan sits beside distributive, commutative, absorption laws.
  • Logic Gates - AND OR NOT — the physical gates being negated.
  • NAND and NOR Universal Gates — De Morgan is why they are universal.
  • Karnaugh Maps — used to justify grouping/complement steps.
  • Complement of a Function — De Morgan is the general recipe for taking a complement.
  • Bubble Pushing — graphical form of De Morgan on circuit diagrams.
De Morgan Theorem 1
A⋅B‾=A‾+B‾\overline{A\cdot B} = \overline{A} + \overline{B}
De Morgan Theorem 2
A+B‾=A‾⋅B‾\overline{A+B} = \overline{A}\cdot\overline{B}
The 4-word slogan for De Morgan
Break the bar, change the sign
How are De Morgan's theorems rigorously proved
By truth table — both sides give identical outputs for all input rows
A‾⋅B‾\overline{\overline A \cdot B} simplifies to
A+B‾A + \overline B
Why do De Morgan's theorems matter in hardware
They let circuits be rebuilt using only NAND or only NOR gates (bubble pushing)
Common wrong answer for A⋅B‾\overline{A\cdot B}
A‾⋅B‾\overline A\cdot\overline B (forgot to flip AND to OR)
Negate A⋅B+C‾A\cdot B + \overline C
(A‾+B‾)⋅C(\overline A + \overline B)\cdot C
Generalised Theorem 1 for n variables
A⋅B⋅C⋯‾=A‾+B‾+C‾+⋯\overline{A\cdot B\cdot C\cdots} = \overline A + \overline B + \overline C + \cdots

Concept Map

gives

gives

shares rule

shares rule

verify via

proves

proves

extends to

extends to

is engine of

enables

enables

NOT distributes over group

Theorem 1: bar A.B = barA + barB

Theorem 2: bar A+B = barA . barB

Break the bar, change the sign

Truth tables

Equal iff same output all rows

Generalises to N variables

Complement / dualise procedure

NAND-only or NOR-only circuits

Boolean simplification

Hinglish (regional understanding)

Intuition Hinglish mein samjho

De Morgan ke do simple rules hain jo batate hain ki jab ek bade group ke upar NOT (bar) lagta hai to kya hota hai. Rule seedha yaad rakho: "bar todo, sign badlo". Matlab agar bar ek AND ke upar hai, to use OR bana do, aur andar ke har variable ke upar apna alag bar laga do. Isliye A⋅B‾=A‾+B‾\overline{A\cdot B} = \overline{A} + \overline{B}, aur ulta A+B‾=A‾⋅B‾\overline{A + B} = \overline{A}\cdot\overline{B}.

Yeh true kyun hai? Truth table bana ke check karo — dono side ke output har input combination par bilkul same aate hain, isliye woh equal hain. Feynman style se socho: A⋅BA\cdot B sirf tab 1 hota hai jab dono 1 hon, to uska NOT tab 1 hoga jab kam se kam ek 0 ho — yani "A zero OR B zero", jo A‾+B‾\overline A + \overline B hai. Bas itni si baat hai.

Sabse common galti: log A⋅B‾\overline{A\cdot B} ko A‾⋅B‾\overline A\cdot\overline B likh dete hain — operator flip karna bhool jaate hain. Yeh galat hai, check karo A=1,B=0A=1, B=0 par. Isliye hamesha operator (AND/OR) ko bhi badalna zaroori hai, sirf bar lagana kaafi nahi.

Yeh theorem hardware mein bahut important hai kyunki isse aap poore circuit ko sirf NAND gates ya sirf NOR gates se bana sakte ho (ise "bubble pushing" bolte hain). Factories ko ek hi type ka gate banana sasta padta hai, isliye De Morgan real designs mein rozana use hota hai.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 1,697 wordsD2Visual walkthroughThe derivation in pictures · 1,591 wordsD3Worked examplesEvery scenario covered · 2,128 wordsD4ExercisesGraded, full solutions · 2,426 wordsD5Question bankConcept traps, quick reveals · 1,324 words

Test yourself — Boolean Algebra & Logic Gates

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Boolean algebra — AND, OR, NOT, XOR, NAND, NOR operationsCoding · 1.1.3Logic gates — physical gate symbols, transistor implementation ideaCoding · 1.1.5Universal gates (NAND - NOR completeness)Hardware · 3.1.14Boolean algebra — AND, OR, NOT, XOR, NAND, NOR operationsCoding · 1.1.3Truth tables — all 16 binary operationsCoding · 1.1.4Logical operators — and, or, not, short-circuit evaluationCoding · 1.2.8Regular languages — closed under union, intersection, complement, concatenation, Kleene starCoding · 4.6.6Boolean variables and operations (AND, OR, NOT)Hardware · 3.1.4Boolean algebra laws (commutative, associative, distributive)Hardware · 3.1.7