Chapter 05 of 32

Boolean Algebra Laws

Look at these two circuits: F1 = AB + A(B + C) + B(B + C) needs five gates, while F2 = B + AC needs two. Yet for every input they give exactly the same output. How can we discover that the big circuit can be replaced by the small one, and prove it is safe? The answer is Boolean algebra, the mathematics of 0 and 1.

In Logic Gates we used AND, OR and NOT; in Universal Gates: NAND & NOR we converted between gate types. In this chapter we collect the laws that govern these operations, learn how to prove them, and use them step by step to simplify expressions. Fewer gates means a cheaper, faster, lower-power chip.

Boolean algebra is an algebraic system on a set of values (for switching circuits, {0, 1}) with two binary operations, + (OR) and · (AND), and one unary operation, ′ (complement), that satisfies a fixed set of postulates.

All laws below were checked by computer, both with a truth-table program (shown later) and with the sympy symbolic logic library.


The Postulates (Huntington's Axioms)

Every law in Boolean algebra can be derived from a few basic assumptions, called postulates. A common set, due to E. V. Huntington (1904), is:

Postulate

OR form

AND form (dual)

P1. Closure

A + B is in the set

A·B is in the set

P2. Identity elements

A + 0 = A

A·1 = A

P3. Commutative

A + B = B + A

A·B = B·A

P4. Distributive

A + (B·C) = (A + B)·(A + C)

A·(B + C) = A·B + A·C

P5. Complement

A + A′ = 1

A·A′ = 0

P6. Non-trivial

At least two distinct elements exist (0 ≠ 1)

(same)

Notice two things. First, OR distributes over AND: A + BC = (A + B)(A + C). This is false in ordinary arithmetic (2 + 3×4 ≠ 5×6) but true in Boolean algebra, and it is one of the most useful tools for simplification. Second, there is no subtraction and no division in Boolean algebra.


The Duality Principle

Look at the table again: each postulate comes in a pair, and one is obtained from the other by swapping + with · and 0 with 1.

The dual of an expression is obtained by interchanging + and ·, and interchanging 0 and 1, while leaving every variable and complement unchanged. Duality principle: if an identity is true, its dual is also true.

Since every postulate has its dual as a postulate, any proof can be "mirrored" line by line. So we only need to prove half of the theorems; the other half come free.

Expression                 Dual
A + 0 = A                  A·1 = A
A + A′B = A + B            A·(A′ + B) = A·B
A + BC                     A·(B + C)        ← keep the original grouping with brackets!
AB + A′C + BC              (A + B)(A′ + C)(B + C)

Dual vs complement. The dual does not complement the variables; the complement does. The dual of A + B′C is A(B′ + C); the complement of A + B′C is A′(B + C′). They are different functions. Finding the complement uses De Morgan's theorems, covered in the next chapter, De Morgan's Theorems.


The Basic Theorems

Here is the complete toolkit. Each row gives a law and its dual.

Law

OR form

AND form (dual)

Identity

A + 0 = A

A·1 = A

Null (domination)

A + 1 = 1

A·0 = 0

Idempotent

A + A = A

A·A = A

Complement

A + A′ = 1

A·A′ = 0

Involution (double complement)

(A′)′ = A

(self-dual)

Commutative

A + B = B + A

AB = BA

Associative

A + (B + C) = (A + B) + C

A(BC) = (AB)C

Distributive

A + BC = (A + B)(A + C)

A(B + C) = AB + AC

Absorption

A + AB = A

A(A + B) = A

Redundant literal (simplification)

A + A′B = A + B

A(A′ + B) = AB

Adjacency (combining)

AB + AB′ = A

(A + B)(A + B′) = A

De Morgan

(A + B)′ = A′B′

(AB)′ = A′ + B′

Consensus

AB + A′C + BC = AB + A′C

(A + B)(A′ + C)(B + C) = (A + B)(A′ + C)

Transposition

(A + B)(A′ + C) = AC + A′B

AB + A′C = (A + C)(A′ + B)

Intuition for the important ones:

  • Absorption, A + AB = A: if A is 1, the whole thing is 1 anyway; if A is 0, AB is also 0. The term AB never adds anything. In words: "a bigger term swallows a smaller term that contains it".

  • Redundant literal, A + A′B = A + B: the A′ in the second term is pointless, because the only time the second term matters is when A = 0, and then A′ is automatically 1.

  • Adjacency, AB + AB′ = A: whether B is 0 or 1, the output is A. This "combine two terms that differ in one variable" step is exactly what Karnaugh Maps do visually.

  • Consensus, AB + A′C + BC = AB + A′C: BC can only be 1 when B = C = 1. Then if A = 1 the term AB is already 1, and if A = 0 the term A′C is already 1. So BC is never needed. BC is called the consensus of AB and A′C: take the two terms containing A and A′, and AND the leftovers.


Two Ways to Prove a Law

Method 1: Perfect Induction (Truth Table)

Because each variable has only two values, we can simply check every combination. If both sides agree in all 2n rows, the identity is proved. Let us prove the distributive law A + BC = (A + B)(A + C):

A

B

C

BC

A + BC

A + B

A + C

(A + B)(A + C)

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

0

0

0

1

0

0

0

1

1

1

1

1

1

1

1

0

0

0

1

1

1

1

1

0

1

0

1

1

1

1

1

1

0

0

1

1

1

1

1

1

1

1

1

1

1

1

The two bold columns are identical, so the law holds. This method is foolproof but grows as 2n, which is why we also need algebra.

Method 2: Algebraic Proof from the Postulates

Each step must quote a postulate or an already-proved theorem. These short proofs are popular university exam questions.

Theorem: A + A = A   (idempotent)
A + A = (A + A)·1              P2 identity
      = (A + A)(A + A′)        P5 complement
      = A + A·A′               P4 distributive (OR over AND)
      = A + 0                  P5 complement
      = A                      P2 identity
Dual (A·A = A) follows by duality.

Theorem: A + 1 = 1   (null)
A + 1 = 1·(A + 1)              P2, P3
      = (A + A′)(A + 1)        P5
      = A + A′·1               P4
      = A + A′                 P2
      = 1                      P5

Theorem: A + AB = A   (absorption)
A + AB = A·1 + A·B             P2
       = A(1 + B)              P4
       = A·1                   null law (just proved), P3
       = A                     P2

Theorem: A + A′B = A + B   (redundant literal)
A + A′B = (A + A′)(A + B)      P4
        = 1·(A + B)            P5
        = A + B                P2, P3

Theorem: AB + A′C + BC = AB + A′C   (consensus)
AB + A′C + BC = AB + A′C + BC(A + A′)          P2, P5
              = AB + A′C + ABC + A′BC          P4
              = AB(1 + C) + A′C(1 + B)         P4, P3
              = AB + A′C                       null law, P2

The consensus proof shows a key trick: multiply a term by (X + X′) = 1 to split it, then absorb the pieces. It feels like making things worse before they get better, and it is often the only algebraic route.


How Boolean Algebra Differs from Ordinary Algebra

Statement

Ordinary algebra

Boolean algebra

A + A = A

False (A + A = 2A)

True

A + 1 = 1

False

True

A + BC = (A + B)(A + C)

False

True

A + B = A + C implies B = C

True (subtract A)

False: A = 1, B = 0, C = 1 gives 1 = 1

AB = AC implies B = C

True if A ≠ 0

False: A = 0 makes both sides 0

A + B = A + C and AB = AC implies B = C

-

True (both conditions together are enough)

The last row is a nice result: knowing only the OR or only the AND is not enough to cancel A, but knowing both is. (Check: if A = 0 the OR equation gives B = C; if A = 1 the AND equation gives B = C.)


Simplifying Expressions Step by Step

Simplification aims to reduce the number of literals (each appearance of a variable or its complement) and terms, since each literal is roughly one gate input. A good strategy:

  1. Expand brackets (distributive law) when it helps.

  2. Look for absorption (a term that contains another whole term).

  3. Look for adjacency (two terms differing in one variable: XY + XY′ = X).

  4. Look for redundant literals (X + X′Y = X + Y) and consensus terms.

  5. If stuck, duplicate a term (idempotent law, X = X + X) so it can combine with two others.

Example 1: F = AB + A(B + C) + B(B + C)

F = AB + AB + AC + BB + BC        distributive
  = AB + AC + B + BC              idempotent (AB + AB = AB, BB = B)
  = AB + AC + B                   absorption (B + BC = B)
  = B + AC                        absorption (B + AB = B)

Literals: 8 → 3.  Gates: 5 → 2 (one AND, one OR).

Example 2: The Majority Function, F = A′BC + AB′C + ABC′ + ABC

F is 1 when at least two of the three inputs are 1 (a "majority voter"). The trick is to use ABC three times, since it can pair with each of the other terms.

F = A′BC + AB′C + ABC′ + ABC + ABC + ABC          idempotent (ABC = ABC + ABC + ABC)
  = (A′BC + ABC) + (AB′C + ABC) + (ABC′ + ABC)    regroup
  = BC(A′ + A) + AC(B′ + B) + AB(C′ + C)          distributive
  = BC + AC + AB                                  complement, identity

Literals: 12 → 6.

This circuit is exactly the carry output of a full adder, which you will see again in Half & Full Adders.

Example 3: Product Forms

(a) (A + B)(A + B′) = A + BB′ = A + 0 = A            distributive (OR over AND), complement

(b) (A + B′ + C)(A + B′ + C′)
    Let X = A + B′:  (X + C)(X + C′) = X + CC′ = X
    = A + B′

(c) (A + B)(A′ + C)
    = AA′ + AC + A′B + BC          multiply out
    = AC + A′B + BC                AA′ = 0
    = AC + A′B                     consensus (BC is the consensus of AC and A′B)

Example 4: A Chain of Redundant Literals

F = A + A′B + A′B′C
  = A + B + A′B′C                 A + A′B = A + B
  = A + B + B′C                   (A + B) + A′(B′C): absorb A′ the same way
  = A + B + C                     B + B′C = B + C

The intuition: each later term only matters when all the earlier ones are 0, so the complemented literals are automatically true and can be dropped.

Example 5: Consensus with an Extra Literal

F = AB + A′C + BCD
  = AB + A′C + BC + BCD            add the consensus term BC (allowed: it is redundant)
  = AB + A′C + BC                  absorption (BC + BCD = BC)
  = AB + A′C                       remove the consensus term again

This "add the consensus, use it, then remove it" trick works whenever a term contains the consensus of two other terms.

Example 6: Using De Morgan Inside a Simplification

F = (AB)′(A′ + B)(B′ + B)
  = (A′ + B′)(A′ + B)·1            De Morgan: (AB)′ = A′ + B′;  B′ + B = 1
  = A′ + B′B                       distributive (OR over AND)
  = A′

All six results were confirmed by sympy's simplify_logic, which returned exactly the simplified expressions above.


Checking Laws with a Program

Perfect induction is easy to automate. This program checks several laws over all input combinations, and also catches a common wrong "law".

from itertools import product

def same(f, g, n):
    """True if f and g agree on all 2^n input combinations."""
    return all(f(*v) == g(*v) for v in product([0, 1], repeat=n))

NOT = lambda x: 1 - x

laws = {
    "Absorption      A + AB = A":
        (lambda a, b: a | (a & b), lambda a, b: a, 2),
    "Redundancy      A + A'B = A + B":
        (lambda a, b: a | (NOT(a) & b), lambda a, b: a | b, 2),
    "Distributive    A + BC = (A + B)(A + C)":
        (lambda a, b, c: a | (b & c), lambda a, b, c: (a | b) & (a | c), 3),
    "Consensus       AB + A'C + BC = AB + A'C":
        (lambda a, b, c: (a & b) | (NOT(a) & c) | (b & c),
         lambda a, b, c: (a & b) | (NOT(a) & c), 3),
    "Wrong!          A + BC = (A + B)C":
        (lambda a, b, c: a | (b & c), lambda a, b, c: (a | b) & c, 3),
}

for name, (lhs, rhs, n) in laws.items():
    print(f"{name:45s} -> {'holds' if same(lhs, rhs, n) else 'FAILS'}")

Output:

Absorption      A + AB = A                    -> holds
Redundancy      A + A'B = A + B               -> holds
Distributive    A + BC = (A + B)(A + C)       -> holds
Consensus       AB + A'C + BC = AB + A'C      -> holds
Wrong!          A + BC = (A + B)C             -> FAILS

A program like this is a great way to check your homework, but in exams you must show the algebraic steps or the truth table.


Common Mistakes

  • Cancelling terms as in ordinary algebra. From A + B = A + C you cannot conclude B = C.

  • Applying distribution wrongly: A + BC = (A + B)(A + C), not (A + B)C.

  • Complementing term by term: (A + B)′ is A′B′, not A′ + B′. Work through De Morgan's Theorems carefully.

  • Forgetting brackets when taking a dual. The dual of A + BC is A(B + C), not AB + C.

  • Confusing dual and complement. The dual keeps the literals; the complement flips them.

  • Thinking a "simpler-looking" step is always progress. Sometimes you must expand (multiply by X + X′ or duplicate a term) before things collapse.

  • Stopping too early. After absorption, check again for consensus and redundant literals.


GATE and Interview Questions

Q1. Simplify A′B′ + A′B.

A′(B′ + B) = A′·1 = A′ (adjacency).

Q2. Simplify (A + B)(A + C)(B′ + C′).

(A + B)(A + C) = A + BC. Then (A + BC)(B′ + C′) = AB′ + AC′ + BCB′ + BCC′ = AB′ + AC′ = A(B′ + C′).

Q3. Simplify AB + AB′C + BC.

AB + AB′C = A(B + B′C) = A(B + C) = AB + AC. So F = AB + AC + BC, the majority function. No literal can be removed.

Q4. What is the dual of X + Y′Z + 1? Is the dual the same as the complement?

Dual: X·(Y′ + Z)·0 (which equals 0, just as the original equals 1). The complement of the original is also 0 here, but in general they differ: the complement would be X′(Y + Z′)·0, with every literal flipped.

Q5. Which of these is NOT an identity? (a) A + A′B = A + B (b) A(A′ + B) = AB (c) (A + B)(A + C) = A + BC (d) A + BC = (A + B)C

(d). Counterexample: A = 1, C = 0 gives left side 1, right side 0. The other three are the redundant-literal law, its dual, and the distributive law.

Q6. Prove AB + A′C = (A + C)(A′ + B).

Expand the right side: AA′ + AB + A′C + BC = AB + A′C + BC = AB + A′C (consensus). This is the transposition theorem, useful for converting SOP to POS.

Q7. If X + Y = X + Z and XY = XZ, is Y = Z?

Yes. If X = 0, the first equation gives Y = Z. If X = 1, the second gives Y = Z. Either condition alone is not enough.

Q8. How many literals does AB + A(B + C) + B(B + C) have, and how many after simplification?

8 literals (A, B, A, B, C, B, B, C). After simplification, B + AC has 3.


Summary

  • Boolean algebra rests on a few postulates: identity, commutative, distributive (both ways!), complement. Everything else is derived.

  • Duality: swap + ↔ · and 0 ↔ 1 (keep the variables); the dual of a true identity is true.

  • Key simplification laws: absorption A + AB = A, redundant literal A + A′B = A + B, adjacency AB + AB′ = A, consensus AB + A′C + BC = AB + A′C.

  • Prove laws by perfect induction (truth table) or algebra from the postulates.

  • Boolean algebra has no cancellation, no subtraction, and OR distributes over AND.

  • Next, De Morgan's Theorems show how to complement any expression, the last tool we need before canonical forms and K-maps.