Boolean Algebra & K-maps

Boolean algebra is where Digital Logic starts, and it supplies the vocabulary for everything that follows — combinational circuits, sequential circuits, and the control logic in Computer Organisation.

A Boolean function is completely determined by its truth table, so two expressions that look nothing alike are the same function if they produce the same output column. This is why algebraic manipulation is safe, and why a question asking "which of these is equivalent" is always answerable mechanically.

The central task is minimisation, and minimisation is a covering problem rather than an algebraic one. A function's 1s are a set of minterms, and the goal is to cover every one of them using the fewest and largest groups possible. Algebra can do this, but a Karnaugh map does it by inspection, which is why it dominates in an exam.

The third principle is that the map's adjacency is what makes grouping legal. Cells are arranged in Gray code order specifically so that neighbouring cells differ in exactly one variable, and it is that single-variable difference which allows the variable to be eliminated.

Everything in the chapter follows from those three.

1. Operations and Axioms

Three operations generate everything: AND written as a product, OR written as a sum, and NOT written as a bar or a prime.

The axioms come in dual pairs, and the pairing is worth learning as a structure rather than as a list.

The absorption laws are the ones most often missed in algebraic simplification, and recognising them saves several steps.

A less obvious but frequently useful identity is $A+\overline{A}B=A+B$. It is worth memorising directly, because it does not follow from a single axiom application.

The consensus theorem states that $AB+\overline{A}C+BC=AB+\overline{A}C$: the third term is redundant because it is already covered by the other two. On a K-map the consensus term appears as a group that adds no new cells, which is exactly why it can be dropped.

Exclusive-OR deserves separate treatment because it behaves unlike the other operations and appears constantly in arithmetic circuits.

XOR outputs 1 when its inputs differ, and it is both commutative and associative, so a chain of XOR gates can be reassociated freely and computes the parity of its inputs.

Two identities do most of the work: $A\oplus 0=A$ and $A\oplus 1=\overline{A}$. So XOR with a constant is either a pass-through or an inverter, which is exactly how a controlled inverter is built in an adder-subtractor.

A further consequence is that $A\oplus A=0$, which makes XOR self-inverting: applying the same value twice restores the original, and that is the basis of both parity checking and simple bitwise swaps.

2. Duality and De Morgan's Laws

The dual of an expression is obtained by swapping AND with OR and 0 with 1, leaving variables untouched. Every Boolean identity remains valid when dualised, which is why the axiom table above has two matched columns.

Duality is not complementation. The dual of $A+0$ is $A\cdot 1$, and both equal $A$; the complement of $A$ is $\overline{A}$, which is a different function.

De Morgan's laws convert between the two operations through complementation:

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

In words: break the bar and change the operation. The laws extend to any number of variables, and applying them repeatedly pushes every complement inward until it sits only on individual variables.

The practical consequence is that NAND and NOR gates can be redrawn as their opposites with inverted inputs, which is the basis of all NAND-only and NOR-only implementations.

3. Canonical Forms

A minterm is a product term containing every variable exactly once, in true or complemented form, and it is 1 for exactly one input combination.

A maxterm is the dual: a sum term containing every variable once, and it is 0 for exactly one combination.

Sum of products lists the minterms where the function is 1. Product of sums lists the maxterms where it is 0. Both describe the same function, so the two index sets are complementary.

For a 3-variable function, if the SOP form is $\sum m(0,2,5,7)$, then the POS form is $\prod M(1,3,4,6)$ — every index not in the first list appears in the second.

Minterm $m_i$ and maxterm $M_i$ are complements of each other, so $\overline{m_i}=M_i$. This is why the index sets partition the full range.

A canonical form is unique, which makes it the reliable way to prove two expressions equal: expand both to minterms and compare the index sets.

4. Karnaugh Maps

A K-map is a truth table redrawn so that adjacent cells differ in exactly one variable. The row and column labels follow Gray code order — 00, 01, 11, 10 — not binary counting order, and using binary order is the single most common way to get a K-map wrong.

Grouping rules are few and strict.

Groups must be rectangular and contain a number of cells that is a power of two: 1, 2, 4, 8 or 16. A group of three cells is never legal.

Groups may wrap around the edges, because the leftmost and rightmost columns differ in exactly one variable, as do the top and bottom rows. On a 4-variable map the four corner cells form a legal group of four.

Groups should be as large as possible, and overlapping is allowed and often necessary. A larger group eliminates more variables: a group of $2^k$ cells removes $k$ variables from the term.

The number of literals in a term is the number of variables that do not change across the group. A group of 8 on a 4-variable map leaves one literal; a group of 16 leaves the constant 1.

For a product-of-sums form, group the zeros instead and complement each variable when reading the term. This gives a genuinely different expression, and for some functions it is cheaper than the SOP form.

5. Don't Cares

A don't-care condition marks an input combination that cannot occur or whose output is irrelevant, written as X or d.

Each don't care may be treated as 1 or 0 independently, whichever makes the grouping larger. They are opportunities rather than obligations.

The rule that follows is precise and is where marks are lost: a don't care may be included in a group to enlarge it, but a group consisting only of don't cares must never be formed, because it covers no actual 1 and adds a term for nothing.

Don't cares arise naturally in BCD circuits, where the input combinations 1010 through 1111 never occur, which is why BCD-to-seven-segment decoders are a standard exam context.

6. Prime Implicants

An implicant is any legal group. A prime implicant is a group that cannot be made larger — no adjacent group of double the size exists.

An essential prime implicant is one that covers at least one 1 which no other prime implicant covers. That uncovered 1 forces its inclusion.

The minimisation procedure follows directly.

First, find all prime implicants. Second, identify the essential ones by looking for 1s covered exactly once. Third, select the essential prime implicants, then add the fewest remaining prime implicants needed to cover whatever is left.

A minimal expression is not always unique. When two different selections of the same size both cover everything, the function has more than one minimal form, and a question asking "the minimal SOP" may have several correct answers of equal cost.

Counting prime implicants and essential prime implicants is asked directly, often as a NAT question, so the distinction between the two must be exact rather than approximate.

7. Quine-McCluskey

The Quine-McCluskey method does the same job as a K-map but works for any number of variables and is mechanical enough to be programmed.

It proceeds in two phases.

The first phase finds all prime implicants by repeatedly combining terms that differ in exactly one bit position, replacing that position with a dash. Terms are grouped by the number of ones they contain so that only adjacent groups need comparing.

A term that combines with something is ticked; a term that combines with nothing at the end of a round is a prime implicant.

The second phase builds a prime implicant chart with prime implicants as rows and minterms as columns, then selects a minimum cover. A column with a single mark identifies an essential prime implicant.

The method is exhaustive and therefore reliable, but the number of comparisons grows quickly, which is why K-maps remain preferable up to about five variables.

8. Functional Completeness

A set of gates is functionally complete if every Boolean function can be built from it alone.

NAND alone is functionally complete, and so is NOR alone. Each can produce NOT, AND and OR, and those three generate everything.

To see it for NAND: tying both inputs together gives NOT, since $\overline{A\cdot A}=\overline{A}$. A NAND followed by that NOT gives AND. And by De Morgan, a NAND with both inputs inverted gives OR.

{AND, OR} is not complete because both operations are monotonic: increasing an input can never decrease the output, whereas NOT does exactly that. No composition of monotonic functions can be non-monotonic.

XOR alone is not complete either, but XOR together with AND is, since $A\oplus 1=\overline{A}$ supplies the complement once a constant 1 is available.

9. Worked Examples

Example 1. Simplify $F=A\overline{B}+AB+\overline{A}B$.

Group the first two terms and factor: $A\overline{B}+AB=A(\overline{B}+B)=A\cdot 1=A$.

So $F=A+\overline{A}B$.

Now apply the identity $A+\overline{A}B=A+B$.

$F=A+B$.

Verify with a truth table: the original is 0 only when $A=0$ and $B=0$, since each of the three terms requires at least one of them to be 1. That is exactly the behaviour of $A+B$.

The step worth noting is the second one. Attempting to factor $A+\overline{A}B$ directly leads nowhere, and the identity must be recognised rather than derived.

Example 2. Minimise $F(A,B,C,D)=\sum m(0,1,2,3,5,7,8,10)$ using a K-map.

Place 1s at those minterm positions on a 4-variable map with rows $AB$ and columns $CD$, both in Gray code order 00, 01, 11, 10.

Minterms 0, 1, 2, 3 fill the entire first row, giving a group of four. Across that group $A=0$ and $B=0$ hold throughout while $C$ and $D$ both vary, so the term is $\overline{A}\overline{B}$.

Minterms 1, 3, 5, 7 form a two-by-two block in the $A=0$ half where $D=1$ throughout. The term is $\overline{A}D$.

Minterms 0, 2, 8, 10 form a group of four using edge wrap-around: all have $B=0$ and $D=0$. The term is $\overline{B}\overline{D}$.

Every 1 is now covered, so the minimal form is

$F=\overline{A}\overline{B}+\overline{A}D+\overline{B}\overline{D}$

Note that minterm 8 and minterm 10 are covered only by the third group, which makes $\overline{B}\overline{D}$ essential. Minterm 5 and 7 are covered only by the second, making $\overline{A}D$ essential too.

Example 3. How many prime implicants and essential prime implicants does $F(A,B,C)=\sum m(0,1,2,5,6,7)$ have?

Draw the 3-variable map and find every maximal group.

Minterms 0 and 1 combine: both have $A=0$, $B=0$. Term $\overline{A}\overline{B}$.

Minterms 1 and 5 combine: both have $B=0$, $C=1$. Term $\overline{B}C$.

Minterms 0 and 2 combine: both have $A=0$, $C=0$. Term $\overline{A}\overline{C}$.

Minterms 2 and 6 combine: both have $B=1$, $C=0$. Term $B\overline{C}$.

Minterms 5 and 7 combine: both have $A=1$, $C=1$. Term $AC$.

Minterms 6 and 7 combine: both have $A=1$, $B=1$. Term $AB$.

None of these six groups extends to a group of four, so there are 6 prime implicants.

Now check which 1s are covered only once. Every minterm here appears in exactly two of the six groups, so no minterm forces any particular implicant.

There are therefore no essential prime implicants, and the function requires selecting three of the six groups to cover all six minterms — which can be done in more than one way, so the minimal form is not unique.

Example 4. Implement $F=A+B$ using only NAND gates.

Start from De Morgan: $A+B=\overline{\overline{A}\cdot \overline{B}}$.

The right-hand side is a NAND applied to $\overline{A}$ and $\overline{B}$.

Each complement is itself a NAND with both inputs tied together, since $\overline{A\cdot A}=\overline{A}$.

So the implementation is three NAND gates: one producing $\overline{A}$, one producing $\overline{B}$, and one NANDing those two outputs.

The general pattern for any SOP expression is: replace every AND with a NAND and every OR with a NAND, which works because the two inversions introduced at each level cancel. This is why NAND implementations of SOP forms need no extra inverters beyond those for complemented inputs.

Example 5. A BCD input drives a circuit. Minimise $F=\sum m(1,3,5,7,9)$ with don't cares $d(10,11,12,13,14,15)$.

The don't cares are exactly the six invalid BCD codes, which cannot occur.

Look at the pattern: minterms 1, 3, 5, 7 and 9 are all the odd values in range, so $D=1$ in every one of them.

Now use the don't cares. Combinations 11, 13 and 15 are also odd, and treating them as 1 completes a group of eight covering every cell where $D=1$.

That group of eight eliminates three variables and leaves the single term:

$F=D$

Without the don't cares, the minimal expression would have required several terms. This is the whole reason don't cares are worth hunting for.

Note the rule that was respected: every group formed contains at least one genuine 1. A group made solely from combinations 10, 12 and 14 would have been illegal, since it covers no minterm of the function.

Example 6. Show that $\{AND,OR\}$ is not functionally complete.

Both AND and OR are monotonic functions: changing any input from 0 to 1 can only leave the output unchanged or raise it, never lower it.

Any circuit built from monotonic gates is itself monotonic, because composing monotonic functions preserves the property — raising an input can only raise or preserve each intermediate signal, and so on to the output.

NOT is not monotonic: raising its input from 0 to 1 lowers the output from 1 to 0.

Therefore NOT cannot be built from AND and OR gates alone, however they are arranged, and the set is not functionally complete.

The argument also explains why adding any single non-monotonic element repairs the set. Adding NOT gives the standard complete set. Adding a constant 0 with XOR does the same, since $A\oplus 1=\overline{A}$ supplies the complement.

Summary

A Boolean function is determined by its truth table, so equivalence is always checkable by expanding both expressions to canonical form.

The axioms come in dual pairs; the dual swaps AND with OR and 0 with 1, and is not the same as the complement.

De Morgan's laws break the bar and change the operation, which is what lets NAND and NOR be redrawn as their opposites with inverted inputs.

SOP lists the minterms where the function is 1 and POS lists the maxterms where it is 0, so the two index sets are complementary.

K-map labels follow Gray code order, and adjacency is what permits a variable to be eliminated. Groups are rectangular, of size a power of two, may wrap around edges, may overlap, and should be as large as possible.

A group of $2^k$ cells eliminates $k$ variables.

Don't cares may be included to enlarge a group but a group of only don't cares is never legal.

A prime implicant cannot be enlarged; an essential prime implicant covers a 1 that nothing else covers. Minimal forms need not be unique.

Quine-McCluskey finds prime implicants by combining terms differing in one bit, then selects a cover from a chart.

NAND alone and NOR alone are functionally complete; {AND, OR} is not, because both are monotonic and NOT is not.