De Morgan's theorems: Exercises — Hardware deep dive

Before we start, one reminder of the only two facts we will use over and over — the two theorems from the parent note. A bar (the horizontal line, e.g. $\overline{A}$ ) means "NOT": it flips a $0$ to a $1$ and a $1$ to a $0$ . A dot ( $\cdot$ ) means AND (output $1$ only when both inputs are $1$ ). A plus ( $+$ ) means OR (output $1$ when at least one input is $1$ ).

Level 1 — Recognition

Here we only recognise which theorem applies and read a bar's scope. No heavy algebra yet.

Exercise 1.1

State the result of $\overline{A \cdot B}$ .

Recall Solution 1.1

The long bar sits over an AND. Break the bar, change the sign: the AND becomes OR and each variable gets its own bar. $\overline{A \cdot B} = \overline{A} + \overline{B}$

Exercise 1.2

State the result of $\overline{A + B}$ .

Recall Solution 1.2

The long bar sits over an OR. Break it: OR becomes AND, each variable negated. $\overline{A + B} = \overline{A} \cdot \overline{B}$

Exercise 1.3

Which of the two theorems is being used in $\overline{X + Y} = \overline{X} \cdot \overline{Y}$ ?

Recall Solution 1.3

The bar covers a sum ( $X + Y$ , an OR), and it turned into a product (AND). That is Theorem 2 (break the OR). Renaming $A \to X$ , $B \to Y$ changes nothing — the theorem holds for any variables.

Exercise 1.4

True or false: $\overline{A} \cdot \overline{B}$ means the same as $\overline{A \cdot B}$ .

Recall Solution 1.4

False. Look at the length of the bar. In $\overline{A} \cdot \overline{B}$ there are two short bars — each variable is negated first, then ANDed. In $\overline{A \cdot B}$ there is one long bar covering the whole AND. Different scope → different meaning. Concretely, $\overline{A \cdot B} = \overline{A} + \overline{B}$ (an OR), which is not $\overline{A} \cdot \overline{B}$ .

Level 2 — Application

Now we apply the recipe once or twice, including double-negation ( $\overline{\overline{A}} = A$ : negating twice returns the original).

Exercise 2.1

Simplify $\overline{\overline{A} \cdot B}$ .

Recall Solution 2.1

Step 1 — WHAT: the outer bar sits over an AND, so apply Theorem 1. WHY: the top-level operator under the long bar is $\cdot$ . Break it: $\overline{\overline{A} \cdot B} = \overline{\overline{A}} + \overline{B}$ Step 2 — WHAT: simplify $\overline{\overline{A}}$ . WHY: double negation cancels. $= A + \overline{B}$

Exercise 2.2

Simplify $\overline{A + \overline{B}}$ .

Recall Solution 2.2

Step 1: top-level operator under the bar is OR → Theorem 2: $\overline{A + \overline{B}} = \overline{A} \cdot \overline{\overline{B}}$ Step 2: double negation $\overline{\overline{B}} = B$ : $= \overline{A} \cdot B$

Exercise 2.3

Express the NAND function $\overline{A \cdot B}$ using an OR gate and NOT gates only.

Recall Solution 2.3

Theorem 1 gives $\overline{A \cdot B} = \overline{A} + \overline{B}$ . In words: invert each input, then OR them. So a NAND gate = two NOT gates feeding an OR gate. This is the bubble-pushing view: a NAND drawn as an OR with bubbles on its inputs. See the figure — the bubble on the AND's output "slides" onto the OR's inputs.

Exercise 2.4

Negate $F = A + B + C$ (three-variable OR).

Recall Solution 2.4

Generalised Theorem 2: break the OR into an AND, negate each term. $\overline{F} = \overline{A + B + C} = \overline{A} \cdot \overline{B} \cdot \overline{C}$

Level 3 — Analysis

Here we handle nested bars, mixed operators, and verify by truth table.

Exercise 3.1

Simplify $\overline{A \cdot B + C}$ .

Recall Solution 3.1

Step 1 — WHAT: the top-level operator under the long bar is the $+$ (AND binds tighter than OR, so the expression is $(A \cdot B) + C$ ). Apply Theorem 2. WHY: we always break the outermost operator first. $\overline{A \cdot B + C} = \overline{A \cdot B} \cdot \overline{C}$ Step 2 — WHAT: the leftover long bar $\overline{A \cdot B}$ is over an AND → Theorem 1. $= (\overline{A} + \overline{B}) \cdot \overline{C}$ Result: $\overline{A \cdot B + C} = (\overline{A} + \overline{B}) \cdot \overline{C}$ .

Exercise 3.2

Simplify $\overline{(\overline{A} + B) \cdot (A + \overline{B})}$ .

Recall Solution 3.2

Step 1: outer bar over an AND → Theorem 1: $= \overline{(\overline{A} + B)} + \overline{(A + \overline{B})}$ Step 2: each piece is a bar over an OR → Theorem 2 on both: $= (\overline{\overline{A}} \cdot \overline{B}) + (\overline{A} \cdot \overline{\overline{B}})$ Step 3: double negation ( $\overline{\overline{A}} = A$ , $\overline{\overline{B}} = B$ ): $= (A \cdot \overline{B}) + (\overline{A} \cdot B)$ This is the XOR function — output $1$ exactly when $A$ and $B$ differ.

Exercise 3.3

Verify $\overline{A + B} = \overline{A} \cdot \overline{B}$ by building the full truth table, and confirm the two columns match on all four rows.

Recall Solution 3.3

Two Boolean expressions are equal iff they give the same output on every input row.

$A$	$B$	$A + B$	$\overline{A + B}$	$\overline{A}$	$\overline{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

The two bold columns are identical on all $4$ rows → the theorem holds. ∎

Exercise 3.4

A student claims $\overline{A + B} = \overline{A} + B$ . Find the input row that disproves it.

Recall Solution 3.4

The student negated only the first term and forgot to flip the operator. Test $A = 0, B = 1$ :

True LHS: $\overline{0 + 1} = \overline{1} = 0$ .
Wrong RHS: $\overline{0} + 1 = 1 + 1 = 1$ .

$0 \neq = 1$ → the claim is false. (The correct answer is $\overline{A} \cdot \overline{B}$ , which at $A = 0, B = 1$ gives $1 \cdot 0 = 0$ , matching the LHS.)

Level 4 — Synthesis

Now we combine De Morgan with other laws to fully simplify or convert expressions.

Exercise 4.1

Negate the sum-of-products $F = A \cdot B + \overline{C}$ and simplify.

Recall Solution 4.1

Step 1: top-level operator is $+$ → Theorem 2: $\overline{F} = \overline{(A \cdot B)} \cdot \overline{(\overline{C})}$ Step 2: $\overline{(\overline{C})} = C$ ; and $\overline{A \cdot B} = \overline{A} + \overline{B}$ (Theorem 1): $\overline{F} = (\overline{A} + \overline{B}) \cdot C$

Exercise 4.2

Convert $F = A \cdot B \cdot C$ (a 3-input AND) into NAND-only form.

Recall Solution 4.2

Idea: a NAND gives $\overline{X}$ of an AND, so double-negate to recover the AND. Step 1 — double negation (put two bars on, which changes nothing): $F = \overline{\overline{A \cdot B \cdot C}}$ Step 2: the inner bar $\overline{A \cdot B \cdot C}$ is exactly a 3-input NAND. The outer bar is a NOT, and a NOT built from a NAND is a NAND with its two inputs tied together (since $\overline{X \cdot X} = \overline{X}$ ). So: feed $A, B, C$ into one 3-input NAND, then feed its output into a second NAND used as an inverter. See NAND and NOR Universal Gates. This is exactly why NAND is universal — De Morgan lets us rebuild any AND/OR/NOT from it.

Exercise 4.3

Simplify $\overline{\overline{A} \cdot \overline{B}} + \overline{\overline{A} + \overline{B}}$ .

Recall Solution 4.3

First term: $\overline{\overline{A} \cdot \overline{B}}$ — bar over an AND → Theorem 1: $\overline{\overline{A}} + \overline{\overline{B}} = A + B$ Second term: $\overline{\overline{A} + \overline{B}}$ — bar over an OR → Theorem 2: $\overline{\overline{A}} \cdot \overline{\overline{B}} = A \cdot B$ Combine: $(A + B) + (A \cdot B)$ . By the absorption law (Boolean Algebra Laws), $A + B$ already covers $A \cdot B$ (whenever $A \cdot B = 1$ , both $A$ and $B$ are $1$ , so $A + B = 1$ too). Therefore: $= A + B$

Exercise 4.4

Show that a NOR gate ( $\overline{A + B}$ ) equals an AND gate fed by two inverted inputs.

Recall Solution 4.4

Theorem 2 directly: $\overline{A + B} = \overline{A} \cdot \overline{B}$ — "invert both inputs, then AND." So a NOR = two NOT gates feeding an AND gate. This is the mirror of Exercise 2.3 and again a Bubble Pushing move: push the output bubble of the OR back onto its inputs, and the OR becomes an AND.

Level 5 — Mastery

Full multi-step problems with mixed laws and general- $n$ reasoning.

Exercise 5.1

Fully simplify $F = \overline{\overline{(A + B)} \cdot \overline{C}}$ .

Recall Solution 5.1

Step 1: outer bar over an AND → Theorem 1: $F = \overline{\overline{(A + B)}} + \overline{\overline{C}}$ Step 2: double negation on both pieces: $= (A + B) + C = A + B + C$ Result: $F = A + B + C$ .

Exercise 5.2

Negate $F = (A + B) \cdot (C + D)$ and express the answer as a sum of products.

Recall Solution 5.2

Step 1: top-level operator under the bar is AND → Theorem 1: $\overline{F} = \overline{(A + B)} + \overline{(C + D)}$ Step 2: each piece is a bar over an OR → Theorem 2 twice: $= (\overline{A} \cdot \overline{B}) + (\overline{C} \cdot \overline{D})$ Already a sum of products. Result: $\overline{F} = \overline{A} \overline{B} + \overline{C} \overline{D}$ .

Exercise 5.3

Prove the generalised Theorem 1 for three variables, $\overline{A \cdot B \cdot C} = \overline{A} + \overline{B} + \overline{C}$ , by applying the two-variable theorem twice (associativity, not a new truth table).

Recall Solution 5.3

Step 1: group the AND: $A \cdot B \cdot C = (A \cdot B) \cdot C$ . Treat $(A \cdot B)$ as one block $X$ . Apply two-variable Theorem 1: $\overline{(A \cdot B) \cdot C} = \overline{(A \cdot B)} + \overline{C}$ Step 2: now $\overline{A \cdot B}$ is again a bar over an AND → Theorem 1 once more: $= (\overline{A} + \overline{B}) + \overline{C} = \overline{A} + \overline{B} + \overline{C}$ ∎ The same nesting extends to $n$ variables: each application peels one more variable.

Exercise 5.4

The exclusive-OR is $A \oplus B = A \overline{B} + \overline{A} B$ . Find its complement $\overline{A \oplus B}$ (the XNOR) using De Morgan, and simplify.

Recall Solution 5.4

Step 1: $A \oplus B = A \overline{B} + \overline{A} B$ ; top-level operator is $+$ → Theorem 2: $\overline{A \oplus B} = \overline{(A \overline{B})} \cdot \overline{(\overline{A} B)}$ Step 2: break each inner AND with Theorem 1 (and double-negate): $\overline{A \overline{B}} = \overline{A} + \overline{\overline{B}} = \overline{A} + B$ $\overline{\overline{A} B} = \overline{\overline{A}} + \overline{B} = A + \overline{B}$ Step 3: multiply out $(\overline{A} + B) (A + \overline{B})$ : $= \overline{A} A + \overline{A} \overline{B} + B A + B \overline{B}$ Now $\overline{A} A = 0$ and $B \overline{B} = 0$ (a variable AND its own complement is always $0$ ): $= \overline{A} \overline{B} + A B$ Result: $\overline{A \oplus B} = A B + \overline{A} \overline{B}$ — this is exactly XNOR (" $1$ when $A$ and $B$ are equal"), as expected. See Karnaugh Maps if you want to visualise this grouping.

Wrap-up recall

Recall One-line answers to the whole page

Theorem 1 ::: $\overline{A \cdot B} = \overline{A} + \overline{B}$
Theorem 2 ::: $\overline{A + B} = \overline{A} \cdot \overline{B}$
Peel which operator first? ::: the outermost one under the bar
$\overline{A \oplus B}$ equals ::: $A B + \overline{A} \overline{B}$ (XNOR)
$\overline{A \cdot B + \overline{C}}$ equals ::: $(\overline{A} + \overline{B}) \cdot C$

Connections

De Morgan's theorems — the parent note these exercises drill.
Boolean Algebra Laws — absorption & complement laws used in L4–L5.
Complement of a Function — De Morgan is the general complement recipe.
NAND and NOR Universal Gates — L4.2 and L4.4 build gates from De Morgan.
Bubble Pushing — graphical version used in Ex 2.3 and 4.4.
Logic Gates - AND OR NOT — the physical gates behind every symbol.
Karnaugh Maps — visual grouping to justify simplifications.