TEJ3M Boolean Algebra and Simplification: Notes and Practice

Key things to remember

A + A = A

and

A \cdot A = A

— there is no 2 in Boolean algebra.

A + 1 = 1

A \cdot 0 = 0

A + A^{'} = 1

A \cdot A^{'} = 0

3Absorption:

A + A \cdot B = A

4De Morgan:

(A \cdot B)^{'} = A^{'} + B^{'}

and

(A + B)^{'} = A^{'} \cdot B^{'}

5Inverting an expression inverts each variable AND swaps the operator.

6AND binds more tightly than OR, exactly as × binds more tightly than +.

7Always verify a simplification with a truth table.

Boolean algebra is ordinary algebra's stranger cousin: the variables can only be 0 or 1, and there are only three operations. It matters because a circuit and an expression are the same object written two ways. Simplify the expression and you have simplified the circuit — fewer gates, less power, less heat, lower cost, and fewer things to go wrong. On a chip produced a million times, removing one gate is a real saving.

The laws

Law	OR form	AND form
Identity	A + 0 = A	A · 1 = A
Null / Annulment	A + 1 = 1	A · 0 = 0
Idempotent	A + A = A	A · A = A
Complement	A + A′ = 1	A · A′ = 0
Commutative	A + B = B + A	A · B = B · A
Associative	(A+B)+C = A+(B+C)	(A·B)·C = A·(B·C)
Distributive	A + (B·C) = (A+B)·(A+C)	A · (B+C) = A·B + A·C
Absorption	A + A·B = A	A · (A+B) = A
Double negation	(A′)′ = A	—

The one law that is not like ordinary algebra

A + A = A

, not

2 A

. And

A + 1 = 1

, not

A + 1

. There is no number 2 in Boolean algebra — + means OR, so "A or A" is just A, and "A or true" is always true. The AND-side rules (

A \cdot A = A

A \cdot 0 = 0

) feel more familiar, which is exactly why the OR-side ones get missed.

De Morgan's theorems

Fig 1Break the bar, change the sign.

(A \cdot B)^{'} = A^{'} + B^{'} (A + B)^{'} = A^{'} \cdot B^{'}

Inverting a whole expression inverts each variable AND swaps AND for OR.

De Morgan's theorems are the most-used rules in the whole topic, and the most-misapplied. The error is inverting the variables but leaving the operator alone — writing $(A \cdot B)^{'} = A^{'} \cdot B^{'}$ , which is simply false. Test it: with A = 1, B = 0, the left side is $(0)^{'} = 1$ while the wrong right side is $0 \cdot 1 = 0$ . One counterexample is enough to disprove it, and checking one row takes ten seconds.

The plain-English version

"It is not true that both happened" means "at least one of them did not happen". "It is not true that either happened" means "neither happened". Read your expression out loud in words and De Morgan becomes obvious rather than mechanical.

Simplification in practice

Expand any brackets using the distributive law, to get a sum of AND terms.
Look for a variable that appears in two terms, and factor it out.
Apply the complement law: any bracket containing $X + X^{'}$ becomes 1.
Apply identity and absorption to remove what is left.
Verify with a truth table. If the original and simplified expressions do not match on every row, you made an error.

Always verify

A simplified expression that does not match the original is worse than no simplification at all, because it looks finished. Building the truth table for both takes two minutes and is the only proof that the two circuits behave identically.

Why this earns its place

Consider $Y = A \cdot B + A \cdot B^{'}$ . As written, that is two AND gates, one inverter and one OR gate — four gates. Factor out A to get $A \cdot (B + B^{'})$ , then apply the complement law to get $A \cdot 1$ , and the identity law to get simply $Y = A$ . Four gates become a wire. The output never depended on B at all, which the original expression hid completely.

ABefore simplification

$Y = A \cdot B + A \cdot B^{'}$
4 gates, 2 chips
Propagation delay through three levels
More power, more board area, more to fail

BAfter simplification

$Y = A$
A single wire
No delay
Nothing to fail

Where marks get lost

Writing

(A \cdot B)^{'} = A^{'} \cdot B^{'}

. De Morgan requires swapping the operator too.

Writing

A + A = 2 A

. There is no 2 — OR of a value with itself is the value.

Forgetting

A + 1 = 1

and treating it like arithmetic addition.

Ignoring precedence:

A + B \cdot C

means

A + (B \cdot C)

, not

(A + B) \cdot C

Applying De Morgan to only part of an expression while a bar still spans the rest.

Declaring a simplification finished without verifying it against a truth table.

Boolean Algebra and Simplification

Key things to remember

The laws

De Morgan's theorems

Simplification in practice

Why this earns its place

Worked examples

Where marks get lost

Flashcards 10

Practice