Boolean algebra and minimization

Boolean variables and basic operations

Definition. A Boolean variable takes one of two values, 0 or 1. Complement is written $A'$; it interchanges 0 and 1. AND, OR, and XOR are written $AB$, $A+B$, and $A\oplus B$. Unless parentheses say otherwise, complement binds first, then AND, then OR.

$A$	$B$	$A'$	$AB$	$A+B$	$A\oplus B$
0	0	1	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	1	0	1	1	0

Example. If $A=1$ and $B=0$, then $A'B+A=0\cdot0+1=1$.

Exam point. Treat Boolean addition as OR, not integer addition; $1+1=1$ in this algebra.

Fundamental identities

Definition. Boolean identities hold for every assignment of their variables. The laws of identity, null, idempotence, complement, absorption, and distributivity are used to shorten expressions without changing their truth tables. The dual of a valid identity follows by exchanging $+$ with multiplication and 0 with 1.

Law	AND form	OR form
Identity	$A\cdot1=A$	$A+0=A$
Null	$A\cdot0=0$	$A+1=1$
Idempotence	$AA=A$	$A+A=A$
Complement	$AA'=0$	$A+A'=1$
Absorption	$A(A+B)=A$	$A+AB=A$

Example. $A+AB=A$ because $A+AB=A(1+B)=A\cdot1=A$.

Exam point. Distribution has two valid forms: $A(B+C)=AB+AC$ and $A+BC=(A+B)(A+C)$.

Simplifying with algebra

Definition. Algebraic minimization applies identities until redundant literals or terms disappear. A literal is a variable or its complement. The result is not necessarily a globally minimum expression unless all alternatives are compared; a valid simplification only needs to preserve the function.

Example. Simplify $F=A'B+AB+AC$.

Exam point. Pair terms that differ in one literal: $A'B+AB=B$.

Solved calculation.

1. Factor the first two terms: $F=B(A'+A)+AC$.
2. Use complementarity: $A'+A=1$, so $F=B+AC$.
3. This form is often shorter than the original sum of three products.

De Morgan laws and complements of expressions

Definition. De Morgan's laws are $(AB)'=A'+B'$ and $(A+B)'=A'B'$. For a longer expression, complement every literal and exchange every AND and OR gate, including nested groups. These laws apply to Boolean values and are the basis of NAND and NOR transformations.

Example. $(A+BC)'=A'(B'+C')$.

Exam point. The complement of a sum is a product of complements; parentheses must be retained when expanding it.

Solved calculation. Find the complement of $F=(A+B')C+D$.

1. Complement the outer OR: $F'=((A+B')C)'D'$.
2. Complement the product: $F'=(A+B')'+C'$ multiplied by $D'$.
3. Apply De Morgan to the sum: $(A+B')'=A'B$.
4. Thus $F'=(A'B+C')D'$. Answer. $(A'B+C')D'$.

Sum of products and product of sums

Definition. A product term is an AND of literals, and a sum term is an OR of literals. A sum-of-products (SOP) expression ORs product terms; a product-of-sums (POS) expression ANDs sum terms. Canonical SOP lists minterms where the function is 1; canonical POS lists maxterms where it is 0.

Example. $A'BC+AB'C$ is SOP; $(A+B)(B'+C)$ is POS.

Exam point. A minterm has every input variable once; a maxterm also has every input variable once, but its zero row determines its signs.

Solved calculation. Write the minterm for input $A B C=101$ and the maxterm for row 010.

1. In a minterm, a 1 input appears uncomplemented and a 0 input complemented: row 101 gives $AB'C$.
2. A maxterm must evaluate to 0 on its row. A 0 input appears uncomplemented, while a 1 input is complemented: row 010 gives $(A+B'+C)$. Answer. $m_5=AB'C$ and $M_2=(A+B'+C)$ when $A$ is the most significant bit.

Minterm indexing and canonical forms

Definition. For variables ordered $A,B,C$, binary input $ABC$ denotes decimal minterm index $4A+2B+C$. The notation $F=\Sigma m(S)$ identifies the 1 rows, while $F=\Pi M(Z)$ identifies the 0 rows. Indices are meaningful only with the variable order stated.

Example. $ABC=011$ is $m_3=A'BC$.

Exam point. Check the order before converting an index; changing variable order changes each index.

Solved calculation. A three-input function is 1 on rows 001, 011, 100, and 111. Give both canonical forms.

1. Convert rows to indices: $1,3,4,7$.
2. Therefore $F=\Sigma m(1,3,4,7)$.
3. The remaining rows are $0,2,5,6$.
4. Therefore $F=\Pi M(0,2,5,6)$. Answer. $F=\Sigma m(1,3,4,7)=\Pi M(0,2,5,6)$.

Karnaugh maps and Gray-code order

Definition. A Karnaugh map places truth-table rows in a grid so adjacent cells differ in exactly one input bit. Axis labels use Gray order, such as 00, 01, 11, 10, rather than ordinary binary order. The first and last rows or columns are adjacent because the map wraps around.

Example. For a four-variable map, the columns labelled 00 and 10 are adjacent; they differ in one bit at the wrap boundary.

Exam point. Diagonal cells are not adjacent, and Gray order is essential for valid groups.

Solved map setup. Use rows $AB=00,01,11,10$ and columns $CD=00,01,11,10$. Locate minterms $m_0,m_2,m_8,m_{10}$.

1. $m_0=0000$ goes to row 00, column 00.
2. $m_2=0010$ goes to row 00, column 10.
3. $m_8=1000$ goes to row 10, column 00.
4. $m_{10}=1010$ goes to row 10, column 10.
5. The occupied cells make a wraparound four-cell rectangle across the first and last rows and columns.

$AB\backslash CD$	00	01	11	10
00	1 ($m_0$)	0	0	1 ($m_2$)
01	0	0	0	0
11	0	0	0	0
10	1 ($m_8$)	0	0	1 ($m_{10}$)

Answer. The four cells share $B=0$ and $D=0$, so the simplified term is $B'D'$.

Grouping ones for minimum SOP

Definition. In an SOP K-map, group adjacent 1 cells into rectangles of size $1,2,4,8,\ldots$. Each group must have a power-of-two size and may wrap around. A group of $2^k$ cells removes $k$ changing variables; the variables constant throughout the group form its product term.

Example. Pairing cells where $A$ changes but $B=1,C=0$ gives $BC'$.

Exam point. Overlap is allowed when it helps cover all 1s with fewer or larger groups.

Solved calculation. Minimize $F(A,B,C)=\Sigma m(1,3,5,7)$.

1. The minterms are 001, 011, 101, 111.
2. In all four rows, $C=1$, while $A$ and $B$ vary freely.
3. Group all four 1s as a four-cell group.
4. The only constant literal is $C$. Answer. $F=C$.

Essential prime implicants and coverage

Definition. A prime implicant is a valid group that cannot be enlarged while staying within the 1 cells (and any permitted don't-cares). It is essential if it covers a 1 not covered by any other prime implicant. A minimum cover must include every essential prime implicant and then cover remaining 1s with as little additional cost as possible.

Example. If one minterm belongs to only one prime implicant, that implicant is essential.

Exam point. First identify uniquely covered minterms; do not select groups by visual size alone.

Solved calculation. Let $F=\Sigma m(0,1,2,5,6,7)$ for variables $A,B,C$.

1. Pair $(0,2)$ gives $A'C'$; pair $(2,6)$ gives $BC'$; pair $(5,7)$ gives $AC$; pair $(1,5)$ gives $B'C$.
2. Minterm 0 is covered only by $A'C'$, so that term is essential.
3. Minterm 6 is covered by $BC'$ (among these pairs), so include $BC'$.
4. Minterm 7 is covered by $AC$ or a pair containing 6 and 7 only if that pair is formed; include the group $(6,7)$, giving $AB$.
5. The resulting cover is $A'C'+BC'+AB+B'C$ if all selected pairs are retained, but check whether a smaller cover exists: $A'C'$ covers 0,2; $BC'$ covers 2,6; $AB$ covers 6,7; $B'C$ covers 1,5. These four pairs cover all six minterms. Answer. One minimum SOP is $A'C'+BC'+AB+B'C$. Trap. A quick pair list is not automatically minimum; confirm every selected group is needed and every minterm is covered.

Grouping zeros for minimum POS

Definition. A POS K-map groups 0 cells rather than 1 cells. For each zero group, retain variables that stay constant; a constant 0 appears uncomplemented in the sum term, and a constant 1 appears complemented. AND the resulting sum terms.

Example. A zero group with $A=0$ and $C=1$ gives the sum term $(A+C')$.

Exam point. POS sign selection is the reverse-looking rule from minterms; test the term on the zero row.

Solved calculation. Find a POS for a function that is 0 at minterms 0, 1, 4, and 5 of $A,B,C$.

1. Rows 000, 001, 100, 101 are the zero cells.
2. They form a four-cell group with $B=0$ fixed; $A$ and $C$ vary.
3. The zero-producing sum term is $B$ because $B=0$ throughout the group.
4. Thus the product of sums has one factor. Answer. $F=B$.

Don't-care conditions

Definition. A don't-care input is an input combination whose output is irrelevant or unspecified. It may be treated as either 0 or 1 when forming a K-map cover, whichever produces a simpler valid implementation. It need not be included in any group.