De Morgan's theorems: Question bank — Hardware deep dive

Before the traps, three words we'll lean on constantly:

bar / negation / NOT — the line drawn over an expression, meaning "flip 0↔1". A bar over one letter negates one letter; a bar over a whole group negates the group's result.
scope of a bar — how far the line reaches. $\overline{A} \cdot \overline{B}$ has two short bars (each over one letter); $\overline{A \cdot B}$ has one long bar (over the whole product). These are different expressions, and telling them apart is the single most important skill here.
top-level operator — the operation that gets done last under the bar. That is the operator De Morgan flips first.

True or false — justify

TF:

\overline{A \cdot B}

and

\overline{A} \cdot \overline{B}

are the same expression.

False. You changed the bar's scope but forgot to flip AND→OR. At

A = 1, B = 0

: LHS

= \overline{0} = 1

but

\overline{1} \cdot \overline{0} = 0 \cdot 1 = 0

. They disagree, so they are not equal.

TF:

\overline{A + B} = \overline{A} \cdot \overline{B}

is a valid instance of De Morgan.

True. The bar sits over a top-level OR, so OR→AND and each term is negated. This is Theorem 2 exactly.

TF: De Morgan's theorems are definitions, so no proof is needed.

False. They are theorems proved by truth tables — both sides give identical output on all input rows. A definition is assumed; a theorem is earned.

TF: De Morgan only works for exactly two variables.

False. It generalises:

\overline{A \cdot B \cdot C} = \overline{A} + \overline{B} + \overline{C}

, and likewise for OR. One long bar over any-length group splits into individual bars with the operator flipped.

TF: Applying De Morgan changes what the circuit computes.

False. It's an identity — the output truth table is unchanged. It only rewrites the form (e.g. into NAND-only), which is why designers use it freely.

TF:

\overline{\overline{A}} = A

is a separate rule you sometimes need alongside De Morgan.

True. De Morgan produces double bars (e.g.

\overline{\overline{A}}

after breaking

\overline{\overline{A} \cdot B}

); you then collapse them with double negation, which is a distinct law from Boolean Algebra Laws.

TF: In

\overline{A + B \cdot C}

the top-level operator under the bar is the AND.

False. AND binds tighter than OR, so

B \cdot C

is computed first and the last operation is the OR. De Morgan flips that OR first:

\overline{A} \cdot \overline{(B \cdot C)}

TF: A NAND gate is literally an OR gate fed by two inverters.

True.

\overline{A \cdot B} = \overline{A} + \overline{B}

means "invert both inputs, then OR" — the graphical form of this is Bubble Pushing.

Spot the error

Error: "

\overline{A + B} = \overline{A} + \overline{B}

The operator was not flipped. A bar over OR must become AND:

\overline{A + B} = \overline{A} \cdot \overline{B}

. Test

A = 1, B = 1

: LHS

\overline{1} = 0

, but the wrong RHS

0 + 0 = 0

agrees by luck — try

A = 0, B = 1

: LHS

\overline{1} = 0

, wrong RHS

1 + 0 = 1

. Mismatch.

Error: "

\overline{A + B} = \overline{A} + B

The bar covers the whole group, so every term inside gets negated — you stopped after the first. Correct:

\overline{A} \cdot \overline{B}

(also flip the operator).

Error: "

\overline{A \cdot B \cdot C} = \overline{A} \cdot \overline{B} \cdot \overline{C}

All bars distributed correctly, but the operator was left as AND. Breaking a bar over AND gives OR:

\overline{A} + \overline{B} + \overline{C}

Error: "

\overline{\overline{A} \cdot B} = \overline{A} + \overline{B}

The double bar over

A

was dropped. Break the outer bar →

\overline{\overline{A}} + \overline{B}

, then

\overline{\overline{A}} = A

, giving

A + \overline{B}

Error: "To negate

A \cdot B + \overline{C}

, flip signs to get

\overline{A} + \overline{B} \cdot C

The top-level operator is

+

, so it must become

\cdot

\overline{F} = \overline{(A \cdot B)} \cdot \overline{(\overline{C})} = (\overline{A} + \overline{B}) \cdot C

. The proposed answer never flipped the outer OR.

Error: "

\overline{A \cdot (B + C)} = \overline{A} \cdot (\overline{B} + \overline{C})

Only the inner group was touched. Flip the outer AND first:

\overline{A} + \overline{(B + C)} = \overline{A} + \overline{B} \cdot \overline{C}

Error: "Since

\overline{A} \cdot \overline{B}

has two bars and

\overline{A + B}

has one, De Morgan can't relate them."

Bar count is irrelevant; bar scope and operator are what matter. De Morgan is precisely the theorem that these two differently-drawn expressions are equal.

Why questions

Why does breaking a bar over AND produce an OR (not another AND)?

A \cdot B

is 1 only when both are 1, so its NOT is 1 whenever at least one is 0 — "A is 0 or B is 0". "At least one" is exactly OR, so the operator must flip to OR.

Why is a truth table considered a complete proof, not just evidence?

Boolean variables take only finitely many value combinations (

2^{n}

rows). Checking all of them checks every possible input, so identical output columns prove exact equality — nothing is left untested.

Why do hardware designers care about De Morgan at all?

It lets any circuit be rebuilt from a single gate type (NAND-only or NOR-only), which is cheaper and more uniform to fabricate — see NAND and NOR Universal Gates.

Why must you identify the top-level operator before applying De Morgan?

De Morgan flips the operator done last under the bar. Flip the wrong (inner) operator and you negate the wrong grouping, producing a non-equivalent expression.

Why is De Morgan called the "engine" of taking a complement?

Complementing a whole function means pushing one big bar all the way down to the variables; De Morgan is the rule that legally moves the bar inward one operator at a time — see Complement of a Function.

Why does the double-negation law keep showing up right after De Morgan?

Breaking a bar over an already-negated term (like

\overline{A}

) stacks a second bar, giving

\overline{\overline{A}}

; double negation collapses it back to

A

, finishing the simplification.

Edge cases

Edge: what does De Morgan give for a single variable

\overline{A}

(no operator)?

Nothing to break — there is no top-level AND/OR, so the theorem doesn't apply. It fires only when a bar sits over a group of two or more terms joined by an operator.

Edge: apply Theorem 1 with a constant:

\overline{A \cdot 1}

Break the AND:

\overline{A} + \overline{1} = \overline{A} + 0 = \overline{A}

. This matches the shortcut

A \cdot 1 = A

, so

\overline{A \cdot 1} = \overline{A}

— consistent.

Edge: apply Theorem 2 with a constant:

\overline{A + 1}

Break the OR:

\overline{A} \cdot \overline{1} = \overline{A} \cdot 0 = 0

. Sanity check:

A + 1 = 1

always, and

\overline{1} = 0

— matches.

Edge: does De Morgan hold if

A = B

(same variable twice), e.g.

\overline{A \cdot A}

Yes.

\overline{A \cdot A} = \overline{A} + \overline{A} = \overline{A}

. It also equals

\overline{A}

directly since

A \cdot A = A

. Repeated variables are fine.

Edge: is

\overline{A \cdot B \cdot C}

ambiguous about grouping, and does that break De Morgan?

No ambiguity: AND is associative, so all groupings agree. De Morgan gives

\overline{A} + \overline{B} + \overline{C}

regardless of how you pair the ANDs.

Edge: apply De Morgan twice to

\overline{\overline{A + B}}

First bar:

\overline{A + B} = \overline{A} \cdot \overline{B}

, so the whole thing is

\overline{\overline{A} \cdot \overline{B}}

; break again →

\overline{\overline{A}} + \overline{\overline{B}} = A + B

. Two negations return the original, as expected.

Connections

De Morgan's theorems — the parent note these traps drill.
Boolean Algebra Laws — double negation and associativity used in the edge cases.
Complement of a Function — De Morgan as the bar-pushing engine.
Bubble Pushing — the graphical form tested in the NAND item.
NAND and NOR Universal Gates — why designers care.
Logic Gates - AND OR NOT — the gates being negated.
Karnaugh Maps — alternative justification tool.