Boolean Algebra

Boolean algebra provides a set of rules for manipulating logical expressions. Just as ordinary algebra lets you simplify $2x+2y=2(x+y)$, Boolean algebra lets you simplify logic circuits — fewer gates, cheaper hardware, faster operation.

Notation:

Operation	Symbol	Meaning
AND	$A\cdot B$ or $AB$	both true
OR	$A+B$	at least one true
NOT	$\bar{A}$ or $\neg A$	inverse
XOR	$A\oplus B$	exactly one true

In Boolean algebra, variables take only two values: 0 (false) and 1 (true).

These laws hold for any Boolean expression and can be applied in any order.

Identity laws (neutral elements)

$A\cdot 1=AA+0=A$

Multiplying by 1 (AND with 1) leaves the variable unchanged. Adding 0 (OR with 0) leaves it unchanged.

Null/Domination laws

$A\cdot 0=0A+1=1$

AND with 0 always gives 0. OR with 1 always gives 1.

Idempotent laws

$A\cdot A=AA+A=A$

AND-ing or OR-ing a variable with itself returns the same variable.

Complement laws

$A\cdot \bar{A}=0A+\bar{A}=1$

A variable AND its inverse is always 0. A variable OR its inverse is always 1.

Double negation

$\overline{\stackrel{ˉ}{A}}=A$

Inverting twice returns the original value.

Commutative laws

$A\cdot B=B\cdot AA+B=B+A$

Associative laws

$(A\cdot B)\cdot C=A\cdot (B\cdot C)(A+B)+C=A+(B+C)$

Distributive laws

$A\cdot (B+C)=(A\cdot B)+(A\cdot C)$ $A+(B\cdot C)=(A+B)\cdot (A+C)$

Absorption laws

$A\cdot (A+B)=AA+(A\cdot B)=A$

The second term is absorbed because $A$ already determines the result.

De Morgan's laws relate AND to OR through negation. They are among the most useful laws for simplifying complex Boolean expressions.

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

In words:

• The NOT of an AND = the OR of the NOTs
• The NOT of an OR = the AND of the NOTs

Verification by truth table for $\overline{A\cdot B}=\bar{A}+\bar{B}$:

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

Application: NAND is $\overline{A\cdot B}$, which equals $\bar{A}+\bar{B}$ by De Morgan's first law. So a NAND gate can be replaced by OR gate with inverted inputs — useful when designing with limited gate types.

The goal is to reduce the number of terms and operations in an expression, which corresponds to using fewer gates in a circuit.

Strategy:

1. Identify terms that match a known identity
2. Apply the identity to simplify
3. Repeat until no further simplification is possible

Worked example 1

Simplify $A\cdot A+B$:

$A\cdot A+B=A+B(\text{idempotent: }A\cdot A=A)$

Worked example 2

Simplify $A\cdot (A+B)$:

$A\cdot (A+B)=A(\text{absorption law})$

Worked example 3

Simplify $\overline{A+\bar{A}}$:

$\overline{A+\bar{A}}=\overline{1}=0(\text{complement: }A+\bar{A}=1;\text{ then }\overline{1}=0)$

Worked example 4

Simplify $(A\cdot B)+(A\cdot \bar{B})$:

$(A\cdot B)+(A\cdot \bar{B})=A\cdot (B+\bar{B})(\text{factor out }A)$ $=A\cdot 1(\text{complement: }B+\bar{B}=1)$ $=A(\text{identity: }A\cdot 1=A)$

This simplification means that a circuit computing $(A\cdot B)+(A\cdot \bar{B})$ can be replaced with just the single variable $A$ — a significant reduction.

Worked example 5 — using De Morgan's law

Simplify $\overline{\bar{A}+\bar{B}}$:

Apply De Morgan's second law to the outer NOT: $\overline{\bar{A}+\bar{B}}=\overline{\bar{A}}\cdot \overline{\bar{B}}=A\cdot B(\text{double negation on each term})$

Boolean simplification directly reduces hardware. Each term saved removes one logic gate.

Worked example — simplify and draw:

Original expression: $X=(A\cdot B)+(A\cdot \bar{B})+(\bar{A}\cdot B)$

Step 1 — factor the first two terms: $(A\cdot B)+(A\cdot \bar{B})=A\cdot (B+\bar{B})=A\cdot 1=A$

Expression is now: $X=A+(\bar{A}\cdot B)$

Step 2 — apply distributive law: $A+(\bar{A}\cdot B)=(A+\bar{A})\cdot (A+B)=1\cdot (A+B)=A+B$

Simplified: $X=A+B$

Original: 7 gates (3 ANDs, 2 NOTs, 2 ORs). Simplified: 1 gate (one OR).

Confirming by truth table:

A	B	$\bar{A}$	$\bar{B}$	AB	A$\bar{B}$	$\bar{A}$B	$(AB)+(A\bar{B})+(\bar{A}B)$	A+B
0	0	1	1	0	0	0	0	0 ✓
0	1	1	0	0	0	1	1	1 ✓
1	0	0	1	0	1	0	1	1 ✓
1	1	0	0	1	0	0	1	1 ✓

Truth table matches — simplification is correct.

1. Applying De Morgan's law incorrectly to three or more variables

De Morgan's laws apply to two terms at a time: $\overline{A\cdot B\cdot C}=\bar{A}+\bar{B}+\bar{C}$ (extended form). Changing only some terms — or failing to flip the operator — is a common error. Every term is negated AND the operator flips.

2. Forgetting to flip the operator

$\overline{A\cdot B}=\bar{A}+\bar{B}$ — the AND becomes OR. $\overline{A+B}=\bar{A}\cdot \bar{B}$ — the OR becomes AND. A very common mistake is writing $\overline{A\cdot B}=\bar{A}\cdot \bar{B}$ (negating terms but keeping the AND). This is wrong.

3. Applying absorption without verifying the form

Absorption ($A+AB=A$) applies when one term is a subset of another. It does not apply to $A+BC$ (no common factor). Check that the simpler term appears as a factor before applying absorption.

4. Confusing simplification steps

Show each step with the law used. In exam answers, each line should reference one law. Jumping multiple steps in one line causes marks to be lost if the intermediate result is wrong.