Minterms and Maxterms

Introduction to Minterms

A minterm is a product (AND) of all variables in a function, where each variable appears exactly once, either in normal or complemented form.

For two variables A and B, there are 4 minterms:

• $\neg$A $\land$ $\neg$B (true only when A=F, B=F)
• $\neg$A $\land$ B (true only when A=F, B=T)
• A $\land$ $\neg$B (true only when A=T, B=F)
• A $\land$ B (true only when A=T, B=T)

Each minterm is true for exactly ONE row of the truth table.

Introduction to Maxterms

A maxterm is a sum (OR) of all variables in a function, where each variable appears exactly once, either in normal or complemented form.

For two variables A and B, there are 4 maxterms:

• A $\lor$ B (false only when A=F, B=F)
• A $\lor$ $\neg$B (false only when A=F, B=T)
• $\neg$A $\lor$ B (false only when A=T, B=F)
• $\neg$A $\lor$ $\neg$B (false only when A=T, B=T)

Each maxterm is FALSE for exactly ONE row of the truth table.

Minterm Notation

Minterms are often written using m-notation with a decimal subscript:

For variables A, B (where A is MSB):

• $m_0$ = $\neg$A $\land$ $\neg$B (row 00 = 0)
• $m_1$ = $\neg$A $\land$ B (row 01 = 1)
• $m_2$ = A $\land$ $\neg$B (row 10 = 2)
• $m_3$ = A $\land$ B (row 11 = 3)

The subscript is the decimal value when uncomplemented variables = 1, complemented = 0.

Maxterm Notation

Maxterms are written using M-notation with a decimal subscript:

For variables A, B (where A is MSB):

• $M_0$ = A $\lor$ B (false when 00 = 0)
• $M_1$ = A $\lor$ $\neg$B (false when 01 = 1)
• $M_2$ = $\neg$A $\lor$ B (false when 10 = 2)
• $M_3$ = $\neg$A $\lor$ $\neg$B (false when 11 = 3)

Note: In maxterms, variables are complemented OPPOSITE to minterms!

Mₖ has uncomplemented variables where the bit is 1; Mₖ has complemented variables where the bit is 1.

Writing Minterms from Truth Table Rows

To write the minterm for a truth table row:

1. Look at each variable's value in that row
2. If the variable is 1 (true), include it as-is
3. If the variable is 0 (false), include its complement

Example: For row A=1, B=0, C=1:

• A is 1 $\to$ use A
• B is 0 $\to$ use $\neg$B
• C is 1 $\to$ use C
• Minterm: A $\land$ $\neg$B $\land$ C

Writing Maxterms from Truth Table Rows

To write the maxterm for a truth table row (the row where it's FALSE):

1. Look at each variable's value in that row
2. If the variable is 1 (true), include its complement
3. If the variable is 0 (false), include it as-is

This is OPPOSITE to minterms!

Example: For row A=1, B=0 (where maxterm is false):

• A is 1 $\to$ use $\neg$A
• B is 0 $\to$ use B
• Maxterm: $\neg$A $\lor$ B

Minterm-Maxterm Relationship

Minterms and maxterms with the same index are complements:

mₖ = $\neg$Mₖ and Mₖ = $\neg$mₖ

For example, with variables A, B:

• $m_3$ = A $\land$ B (true only at row 3)
• $M_3$ = $\neg$A $\lor$ $\neg$B (false only at row 3)
• $\neg$(A $\land$ B) = $\neg$A $\lor$ $\neg$B ✓ (De Morgan!)

This makes sense: if mₖ picks out exactly row k, then Mₖ excludes exactly row k.

Identifying Minterms vs Maxterms

To identify minterms and maxterms:

Minterm: Product (AND) of ALL variables, each appearing once

Maxterm: Sum (OR) of ALL variables, each appearing once

Not a minterm/maxterm if:

• Missing a variable
• Has extra terms
• Uses wrong operation

Counting Minterms and Maxterms

For n variables, there are exactly 2ⁿ possible input combinations.

Each combination corresponds to:

• One unique minterm (true for exactly that combination)
• One unique maxterm (false for exactly that combination)

Minterm-Maxterm Duality

Duality: Minterms and maxterms are complements!

For row i: mᵢ = $\neg$Mᵢ and Mᵢ = $\neg$mᵢ

Example (A, B with row 01):

• Minterm $m_1$ = $\neg$A $\land$ B (true only when A=F, B=T)
• Maxterm $M_1$ = A $\lor$ $\neg$B (false only when A=F, B=T)
• $m_1$ = $\neg$$M_1$ ✓

This duality connects DNF and CNF!

Building Minterms from Truth Table Rows

Building a minterm from a row:

1. Look at each variable's value in that row
2. If value is T (1): use the variable as-is
3. If value is F (0): use the negated variable
4. AND all terms together

Example for row A=T, B=F, C=T:

• A is T $\to$ use A
• B is F $\to$ use $\neg$B
• C is T $\to$ use C
• Minterm: A $\land$ $\neg$B $\land$ C

Four-Variable Minterms

With 4 variables (A, B, C, D), we have 16 minterms ($m_0$ to $m_{15}$).

Row numbering uses binary:

• $m_0$ = 0000 = $\neg$A $\land$ $\neg$B $\land$ $\neg$C $\land$ $\neg$D
• $m_5$ = 0101 = $\neg$A $\land$ B $\land$ $\neg$C $\land$ D
• $m_{10}$ = 1010 = A $\land$ $\neg$B $\land$ C $\land$ $\neg$D
• $m_{15}$ = 1111 = A $\land$ B $\land$ C $\land$ D

Same pattern works for any number of variables!

Why Canonical Forms

The problem: Multiple expressions can compute the same function.

• A $\land$ B $\lor$ A $\land$ $\neg$B simplifies to A
• $\neg$($\neg$A) is just A
• These look different but behave identically

What canonical forms provide:

• Every function has exactly one canonical representation
• Two expressions are equivalent iff their canonical forms match
• No need to test all 2ⁿ input combinations

The trade-off: Canonical forms may be longer than minimal expressions. That is acceptable—their purpose is comparison, not implementation.