Glossary: Minterm and Maxterm Expansions

Key terms and definitions for Unit 4. Definitions follow ISO 11179 metadata registry standards.

B

Binary Representation of Minterms — The encoding of each minterm as a binary number where each bit indicates whether a variable appears in complemented (0) or uncomplemented (1) form.

Boolean Expression — A combination of Boolean variables, constants, and operators that evaluates to either 0 or 1.

Binary Decision Diagram — A directed acyclic graph that represents a Boolean function by repeated Shannon expansion, where each internal node tests one variable and terminal nodes are the constants 0 and 1.

Boolean Variable — A symbol in Boolean algebra that can assume only the value 0 or 1.

C

Canonical Form — A standard representation of a Boolean function where each term contains all variables in the function, either in complemented or uncomplemented form.

Canonical POS Form — A Boolean expression written as a product of maxterms, where each maxterm contains all variables.

Canonical SOP Form — A Boolean expression written as a sum of minterms, where each minterm contains all variables.

Cofactor — The resulting function when a variable in a Boolean function is set to a constant value (0 or 1).

D

Dont Care Condition — An input combination for which the output value is unspecified, allowing flexibility in optimization.

Dont Care in POS — The use of unspecified output conditions as 1s when simplifying using product-of-sums form.

Dont Care in SOP — The use of unspecified output conditions as 1s when simplifying using sum-of-products form.

Duality Principle — The property that any Boolean theorem remains valid when AND and OR are interchanged and 0 and 1 are interchanged.

E

Expansion Theorem — A theorem allowing a Boolean function to be expressed in terms of its cofactors with respect to a variable.

F

Function from Truth Table — The process of deriving a Boolean expression from a truth table by identifying rows where the output is 1.

I

Incompletely Specified — A Boolean function for which some input combinations have undefined (don't care) outputs.

L

Literal — A Boolean variable or its complement appearing in a Boolean expression.

Literal Count — The total number of variable appearances in a Boolean expression, used as a primary metric for expression complexity and implementation cost.

M

Maxterm — A sum term containing all variables of a function, each appearing either complemented or uncomplemented.

Maxterm Designation — The notation identifying a maxterm by its decimal index, equal to the input combination that makes it 0.

Maxterm Expansion — The expression of a Boolean function as a product of all maxterms for which the function equals 0.

Maxterm from Truth Table — The process of writing a maxterm for each row where the function output is 0.

Maxterm List Notation — A compact representation listing the indices of maxterms that form a function's POS expression.

Maxterm to Minterm — The conversion between maxterm and minterm indices using the complement relationship.

Minimal POS Expression — A product-of-sums expression with the minimum number of maxterms and literals.

Minimal SOP Expression — A sum-of-products expression with the minimum number of product terms and literals.

Minterm — A product term containing all variables of a function, each appearing either complemented or uncomplemented.

Minterm Designation — The notation identifying a minterm by its decimal index, equal to the input combination that makes it 1.

Minterm Expansion — The expression of a Boolean function as a sum of all minterms for which the function equals 1.

Minterm from Truth Table — The process of writing a minterm for each row where the function output is 1.

Minterm List Notation — A compact representation listing the indices of minterms that form a function's SOP expression.

Minterm to Maxterm — The conversion between minterm and maxterm indices for a function and its complement.

O

Off-Set of Function — The set of input combinations for which a Boolean function evaluates to 0.

On-Set of Function — The set of input combinations for which a Boolean function evaluates to 1.

Ordered BDD — A Binary Decision Diagram in which every path from root to terminal tests variables in the same fixed order, enabling a canonical representation when fully reduced.

P

Pi Notation — The product notation using the Greek letter Π to represent a Boolean function as a product of maxterms.

Product of Maxterms — A Boolean expression formed by ANDing multiple maxterms together.

Product of Sums — A Boolean expression structured as an AND of OR terms.

Product Term — A Boolean expression formed by ANDing one or more literals.

S

Shannon Expansion — A theorem expressing a Boolean function as a sum of products involving a variable and its cofactors.

Shannon Expansion Tree — The tree structure formed by recursively applying Shannon expansion to a Boolean function, where each level splits on one variable and leaf nodes hold the resulting sub-function values.

Sigma Notation — The summation notation using the Greek letter Σ to represent a Boolean function as a sum of minterms.

Standard Form — A Boolean expression written as either sum-of-products or product-of-sums but not necessarily in canonical form.

Sum of Minterms — A Boolean expression formed by ORing multiple minterms together.

Sum of Products — A Boolean expression structured as an OR of AND terms.

Sum Term — A Boolean expression formed by ORing one or more literals.

T

Truth Table — A table listing all possible input combinations and corresponding output values for a logic function.

Two-Level Circuit — A logic circuit in which signals pass through at most two levels of gates from input to output, corresponding directly to sum-of-products (AND-OR) or product-of-sums (OR-AND) expressions.