Digital Design · Boolean Algebra and De Morgan Identities

#04 Preserve the truth table while simplifying a gate network to its input A

Apply Boolean identities and De Morgan rules, simplify a two-term expression and verify the equivalent circuit with all four input combinations.

Question

Whole existing English final frame showing Boolean identities, De Morgan gate equivalence, the worked simplification or the original and simplified circuits with their truth table. — Boolean plus denotes inclusive OR, a dot denotes AND and a prime denotes complement. Factoring the two terms and applying the complement and identity rules gives F equal to A for every binary input pair.

Work in two-valued Boolean algebra. Variables take values in {0,1}. The plus sign denotes inclusive OR, a multiplication dot denotes AND, and a prime denotes logical complement. A prime on a parenthesized expression complements the entire expression; it is not a derivative. Boolean 1+1 is 1. Do not evaluate these expressions using ordinary real-number addition. For n independent binary inputs, a complete uncompressed truth table contains 2^n input assignments: four for two inputs and thirty-two for five. Explain the identity rules A+0=A and A·1=A, the idempotent rules A+A=A and A·A=A, and the complement rules A+A'=1 and A·A'=0. Then derive both De Morgan identities: (A·B)'=A'+B' and (A+B)'=A'·B'. Moving complement through a group inverts both inputs and exchanges AND with OR. Verify both identities on all four binary input pairs. Their gate realizations have the same steady logical truth table. Simplify F=A·B+A·B'. Factor A to obtain F=A·(B+B'), use B+B'=1, then use A·1=A. In input order (A,B)=00,01,10,11, the two product terms are respectively 0,0,0,1 and 0,0,1,0. Their inclusive OR gives 0,0,1,1, exactly the A column. The source diagram has distinct A and B signal buses; bridge crossings are not connections, while junction dots mark connections. The original network has one NOT, two AND and one OR. The simplified Boolean function carries A to the output and is independent of B. Keep functional equivalence distinct from physical timing. The identities describe valid binary logical values. A simplified implementation may reduce gates or wiring, but actual speed, area, loading, buffering and drive strength depend on the chosen technology and circuit constraints. A direct logical connection does not imply zero physical propagation delay or that all electrical interface requirements disappear. Equal steady-state truth tables do not establish equal transient waveforms: the original reconvergent B and NOT B paths can momentarily disagree during a transition. No universal delay optimum or glitch-free guarantee follows from algebra alone. These qualifications scope the implementation discussion without changing the worked identity or narration. Conclude by relating Boolean expressions to circuit functions and identities to function-preserving rewrites. Introduce the next topics, sum of products, product of sums, minterms and maxterms, without treating the brief preview as a complete derivation.

Written solution and narration transcript(shows the full solution)

Below are all the lines written in the notebook together with the full narration transcript.

1. Rewrite a Boolean function without changing its table
Boolean plus denotes inclusive OR, a dot denotes AND and a prime denotes complement. Factoring the two terms and applying the complement and identity rules gives F equal to A for every binary input pair.
Truth tables specify a function exactly, but their row count grows exponentially.
Two independent binary inputs:
$\displaystyle N = 2^{2} = 4$
Five independent binary inputs:
$\displaystyle N = 2^{5} = 32$
Boolean algebra provides another way to describe the same function.
A valid identity rewrites an expression while preserving every logical output.
The aim includes simpler implementations as well as simpler notation.
Fewer gates and simpler wiring can help, while actual delay depends on the implementation.
Preserve the truth table when simplifying the logic.
Narration transcript
Truth tables are exact, but they grow very quickly. With two inputs we had four rows. With five inputs, we already have thirty two rows. Boolean algebra gives us another tool. It lets us rewrite a logic expression without changing its behavior. The goal is not just nicer math on the page. A simpler expression usually means fewer gates, shorter wires, less delay, and a circuit that is easier to check. So in digital design, algebra is a way to keep the same contract while making the implementation cleaner.
2. Apply identity, idempotence and complement rules
Boolean plus denotes inclusive OR, a dot denotes AND and a prime denotes complement. Factoring the two terms and applying the complement and identity rules gives F equal to A for every binary input pair.
Use Boolean plus for inclusive OR, a dot for AND, and a prime for complement.
OR identity:
$\displaystyle A+0 = A$
AND identity:
$\displaystyle A\cdot 1 = A$
Idempotence:
$\displaystyle A+A = A\cdot A = A$
Complementing a binary input exchanges zero and one.
OR complement:
$\displaystyle A+A' = 1$
AND complement:
$\displaystyle A\cdot A' = 0$
Apply these identities within larger Boolean expressions.
Narration transcript
Start with a small set of identities. A OR zero is A, because zero adds no new way to make the output one. A AND one is A, because one does not block the signal. A OR A is still A, and A AND A is still A; repeating the same condition does not change it. The complement rules are also essential. A OR NOT A is always one. A AND NOT A is always zero. These identities are the basic moves we use to simplify larger expressions.
3. Move inversion through a Boolean group
Boolean plus denotes inclusive OR, a dot denotes AND and a prime denotes complement. Factoring the two terms and applying the complement and identity rules gives F equal to A for every binary input pair.
De Morgan identities move an inversion through a Boolean group.
Complement of AND:
$\displaystyle \left(A\cdot B\right)' = A'+B'$
Complement of OR:
$\displaystyle \left(A+B\right)' = A'\cdot B'$
Invert every input and exchange AND with OR when moving NOT through the group.
The transformation also describes equivalent gate arrangements.
Both arrangements give the same complete truth table.
Narration transcript
De Morgan's laws are the most important rewrite rules for moving a NOT through a group. NOT of A AND B becomes NOT A OR NOT B. NOT of A OR B becomes NOT A AND NOT B. Notice the pattern: the NOT crosses the parentheses, each input is inverted, and AND changes to OR, or OR changes to AND. This is not a trick for symbols only. It tells us that two different gate structures can have exactly the same truth table.
4. Factor and simplify a two-term expression
Boolean plus denotes inclusive OR, a dot denotes AND and a prime denotes complement. Factoring the two terms and applying the complement and identity rules gives F equal to A for every binary input pair.
Simplify the worked expression using Boolean identities.
Original expression:
$\displaystyle F = A\cdot B+A\cdot B'$
Factor the common input:
$\displaystyle F = A\cdot \left(B+B'\right)$
The parenthesized factor combines B with its complement through OR.
Complement identity:
$\displaystyle B+B' = 1$
Apply the AND identity:
$\displaystyle F = A\cdot 1 = A$
The ideal Boolean function can be implemented by carrying A to the output.
Algebra proves the result without first enumerating the table.
Every binary input assignment retains its original logical output.
Narration transcript
Now simplify one expression. F equals A AND B, OR A AND NOT B. Both terms contain A, so factor A out. What remains is B OR NOT B. But B OR NOT B is always one. Then A AND one is just A. The whole circuit reduces to a wire carrying A. This is the power of Boolean algebra: we did not test every row first. We used rules to prove that a larger logic expression behaves exactly like a smaller one.
5. Verify the original and simplified circuits
Boolean plus denotes inclusive OR, a dot denotes AND and a prime denotes complement. Factoring the two terms and applying the complement and identity rules gives F equal to A for every binary input pair.
Compare the original gate network with the simplified connection.
The original circuit contains one inverter, two AND gates and one OR gate.
Simplified logical output:
$\displaystyle F = A$
Verify the equivalence with a complete two-input truth table.
For input rows zero-zero, zero-one, one-zero and one-one, both outputs are zero, zero, one and one.
The algebraic proof and the complete table confirm the same function.
Narration transcript
Look at the circuit view of the same result. The original design has an inverter, two AND gates, and one OR gate. The simplified design is only A going to the output. That sounds almost too simple, so we verify it with the truth table. For every combination of A and B, the original expression gives the same output as A. Algebra gave the shortcut, and the table confirms the contract.
6. Connect identities to circuit equivalence
Boolean plus denotes inclusive OR, a dot denotes AND and a prime denotes complement. Factoring the two terms and applying the complement and identity rules gives F equal to A for every binary input pair.
Use algebra as a way to reason about circuit behavior.
A Boolean expression specifies a logic function that a circuit can implement.
A Boolean identity preserves the function under the stated binary model.
De Morgan identities move inversion through a group while exchanging AND and OR.
Simplify the logical expression before choosing a physical circuit implementation.
Next, organize expressions as sums of products, products of sums, minterms and maxterms.
Narration transcript
Here is the fourth mental model. A Boolean expression is a circuit description. An identity is a safe rewrite rule. De Morgan's laws let us push inversion through a group by flipping AND and OR. A good designer uses these rules before drawing a final circuit. In the next lesson, we will organize expressions more systematically with sum of products, product of sums, minterms, and maxterms.