Boolean Algebra

The algebra of two-valued logic — the mathematical engine behind every digital circuit's behavior.

Digital LogicElectrical Engineering Year 2Free preview
⏱️ About 18 min

A single transistor can't do arithmetic — but wire enough of them together with the right logic, and you get a processor. The rules governing that logic were written down in 1854, long before the first computer existed.

💡
The big idea: Boolean algebra is a two-valued algebra (0 and 1) with three operations — AND, OR, and NOT — that obey a set of laws remarkably similar to ordinary algebra, but with crucial differences. These laws let you simplify complex logic expressions into minimal forms, which directly translates to simpler, faster, and cheaper digital circuits.
🎯 By the end, you'll be able to
  • Define the AND, OR, and NOT operations and their standard algebraic symbols
  • Apply the commutative, associative, and distributive laws of Boolean algebra
  • Use identity, complement, idempotent, and absorption laws to simplify expressions
  • State and apply De Morgan's theorems to transform expressions between AND/OR and NOT forms
  • Algebraically simplify a multi-term Boolean expression to its minimal form
📎 Helpful to know first

The three operations

Boolean algebra, introduced by George Boole in 1854, operates on a two-element set: {0, 1}. There are exactly three fundamental operations:

AND (multiplication): written A·B or simply AB. The result is 1 only if both inputs are 1. Think of switches in series — current flows only when all switches are closed.

OR (addition): written A+B. The result is 1 if at least one input is 1. Think of switches in parallel — current flows if any switch is closed.

NOT (complement / inversion): written as A with an overbar (Ā) or A' (prime). It flips the value: NOT 0 = 1, NOT 1 = 0.

These three operations are sufficient to express any logical relationship in digital systems. Every logic gate and every digital circuit — no matter how complex — is built from combinations of these primitives.

\[ A \cdot B = 1 \text{ iff } A = 1 \text{ and } B = 1 \qquad A + B = 1 \text{ iff } A = 1 \text{ or } B = 1 \qquad \overline{A} = 1 - A \]
The three fundamental Boolean operations: AND (·), OR (+), and NOT (overbar or prime). Each operates on two-valued variables where 0 = false and 1 = true.

Fundamental laws

Boolean algebra obeys a set of laws that look familiar from ordinary algebra — but with important differences. Here are the ones you need to know by heart:

\[ A + B = B + A \qquad A \cdot B = B \cdot A \]
Commutative laws: the order of operands does not affect the result for both OR and AND.
\[ (A + B) + C = A + (B + C) \qquad (A \cdot B) \cdot C = A \cdot (B \cdot C) \]
Associative laws: grouping of operands does not affect the result.
\[ A \cdot (B + C) = A \cdot B + A \cdot C \qquad A + (B \cdot C) = (A + B) \cdot (A + C) \]
Distributive laws: AND distributes over OR (left, familiar from ordinary algebra), and crucially, OR also distributes over AND (right, which does NOT hold in ordinary algebra).

Identity, complement, idempotent, and absorption

Beyond the three structural laws above, several single-variable identities are essential for simplification:

\[ A + 0 = A \qquad A \cdot 1 = A \]
Identity laws: OR with 0 and AND with 1 leave the variable unchanged (0 is the additive identity, 1 is the multiplicative identity).
\[ A + A = A \qquad A \cdot A = A \]
Idempotent laws: ORing or ANDing a variable with itself yields the same variable. This is unique to Boolean algebra — in ordinary algebra, A + A = 2A.
\[ A + \overline{A} = 1 \qquad A \cdot \overline{A} = 0 \]
Complement laws: a variable ORed with its complement is always 1 (tautology); a variable ANDed with its complement is always 0 (contradiction).
\[ A + A \cdot B = A \]
Absorption law: A ORed with (A AND B) equals just A. Intuitively, if A is true, the whole expression is true regardless of B; if A is false, both terms are false anyway.

De Morgan's theorems

De Morgan's theorems are two of the most powerful tools in Boolean algebra. They describe how to push a NOT through a parenthesized group, swapping AND for OR (or vice versa) and complementing each variable:

\[ \overline{A + B} = \overline{A} \cdot \overline{B} \qquad \overline{A \cdot B} = \overline{A} + \overline{B} \]
De Morgan's theorems: the complement of an OR equals the AND of the complements (left); the complement of an AND equals the OR of the complements (right). The bar 'breaks' and the operator flips.

Worked example: algebraic simplification

Let's put these laws to work. Consider the Boolean function:

\[ F = AB + A\overline{B} + \overline{A}B \]
The expression we want to simplify. It has three product terms, each of two variables.
📝 Worked example: Simplify F = AB + AB' + A'B to its minimal form using Boolean algebra laws.
  1. Group the first two terms and factor out A: AB + AB' = A(B + B').
  2. Apply the complement law (B + B' = 1): A(B + B') = A · 1.
  3. Apply the identity law (A · 1 = A): A · 1 = A. So AB + AB' simplifies to just A.
  4. Substitute back: F = A + A'B.
  5. Apply the distributive law in the OR-over-AND form: X + YZ = (X + Y)(X + Z). Here X = A, Y = A', Z = B, so A + A'B = (A + A')(A + B).
  6. Apply the complement law (A + A' = 1): (A + A')(A + B) = 1 · (A + B).
  7. Apply the identity law (1 · X = X): 1 · (A + B) = A + B.
  8. The simplified result is F = A + B.
✓ F = A + B

Why simplification matters

The original expression F = AB + AB' + A'B required three AND gates, one OR gate (with three inputs), and one NOT gate. The simplified form F = A + B needs just a single OR gate. Fewer gates means less silicon area, lower power consumption, shorter propagation delay, and lower cost — which is exactly why Boolean algebraic simplification is a core skill in digital design.

In practice, engineers use systematic methods like Karnaugh maps and the Quine-McCluskey algorithm to minimize expressions with many variables, but the algebraic approach shown here builds the intuition those methods rely on.

✏️ Practice: If A = 1, B = 0, and C = 1, evaluate the Boolean expression F = AB + AC' + B'C.
Solution
  1. Evaluate each term: AB = 1·0 = 0.
  2. AC' = 1·(NOT 1) = 1·0 = 0, since C = 1 means C' = 0.
  3. B'C = (NOT 0)·1 = 1·1 = 1, since B = 0 means B' = 1.
  4. Sum the terms: F = 0 + 0 + 1 = 1.
✏️ Practice: Using De Morgan's theorem, if A = 1 and B = 1, what is the value of (A · B)'? (Enter 0 or 1.)
Solution
  1. By De Morgan's theorem: (A·B)' = A' + B'.
  2. A' = NOT 1 = 0, and B' = NOT 1 = 0.
  3. A' + B' = 0 + 0 = 0.
  4. Verify directly: A·B = 1·1 = 1, so (A·B)' = NOT 1 = 0.

Check your understanding

1. Which of the following is NOT a valid Boolean algebra law?
A + B = A · B is not a law of Boolean algebra. OR and AND are distinct operations; they are not interchangeable. The idempotent, distributive (AND over OR), and distributive (OR over AND) laws are all valid.
2. According to De Morgan's theorem, what is the complement of (A + B)?
De Morgan's theorem states that the complement of an OR is the AND of the complements: (A + B)' = A' · B'. The complement bar 'breaks' over the group, and the OR becomes an AND.
3. In the simplification of F = AB + AB' + A'B = A + B, which law was used to turn A + A'B into (A + A')(A + B)?
The step uses the distributive law in its OR-over-AND form: X + YZ = (X + Y)(X + Z). This is unique to Boolean algebra — in ordinary algebra, X + YZ cannot be factored this way. Here X = A, Y = A', Z = B.
🔎 Related lessons
Logic Gates & Truth Tables · soon
✅ Key takeaways
  • Boolean algebra operates on two values (0 and 1) with three operations: AND (·), OR (+), and NOT (overbar or prime).
  • The commutative, associative, and distributive laws hold — note that OR distributes over AND (A + BC = (A+B)(A+C)), which has no analogue in ordinary algebra.
  • Key identities include: A+0=A, A·1=A (identity), A+A'=1, A·A'=0 (complement), A+A=A, A·A=A (idempotent), and A+AB=A (absorption).
  • De Morgan's theorems — (A+B)' = A'·B' and (AB)' = A'+B' — let you transform between AND/OR forms by breaking the complement bar.
  • Algebraic simplification (e.g., AB+AB'+A'B → A+B) reduces gate count, which means smaller, faster, cheaper circuits.
➡️ With the laws of Boolean algebra in hand, the next lesson introduces the physical building blocks that implement these operations — logic gates such as AND, OR, NOT, NAND, and NOR.
Want to test yourself on this? Try the Electrical Aptitude test →