Glossary: Karnaugh Maps

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

C

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.

Corner Grouping — The technique in K-maps of grouping cells at opposite corners that are logically adjacent due to wraparound.

Cost of Expression — A metric measuring the complexity of a Boolean expression, typically counting the number of gates or literals required.

Covering All Ones — The process in K-map SOP simplification of ensuring every cell containing a 1 belongs to at least one group.

Covering All Zeros — The process in K-map POS simplification of ensuring every cell containing a 0 belongs to at least one group.

D

DC-Set of Function — The set of input combinations for which the function output is unspecified (don't care conditions).

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.

E

Essential Prime Implicant — A prime implicant that is the only one covering at least one minterm of the function.

Entered Variable K-Map — A K-map technique where cells contain variables or expressions instead of just 0s and 1s, reducing the map size.

F

Five Variable K-Map — A Karnaugh map for functions of five variables, typically drawn as two adjacent 4-variable maps.

Five Variable Technique — The method of handling 5-variable K-maps by comparing corresponding cells in two 4-variable submaps.

Four Variable K-Map — A Karnaugh map with 16 cells arranged in a 4×4 grid for functions of four variables.

G

Gate Count Minimization — The optimization goal of implementing a Boolean function with the fewest possible logic gates.

Gray Code — A binary code where successive values differ by exactly one bit, minimizing switching errors.

Group of Ones — A rectangular grouping of cells containing 1s on a K-map, used for SOP simplification.

Group of Zeros — A rectangular grouping of cells containing 0s on a K-map, used for POS simplification.

I

Implicant — A product term that evaluates to 1 only for input combinations where the function also equals 1.

K

K-Map Adjacency — The property where cells in a Karnaugh map differ by exactly one variable, allowing them to be grouped.

K-Map Cell — A single square in a Karnaugh map representing one minterm or maxterm of the function.

K-Map Gray Code Order — The arrangement of K-map rows and columns using Gray code sequence so adjacent cells differ by one bit.

K-Map Grouping — The process of combining adjacent cells in a K-map to simplify Boolean expressions.

K-Map Limitations — The practical constraints of Karnaugh maps, including difficulty with more than 5-6 variables and potential for human error.

K-Map POS Simplification — The process of using a K-map to derive a minimal product-of-sums expression by grouping 0-cells.

K-Map SOP Simplification — The process of using a K-map to derive a minimal sum-of-products expression by grouping 1-cells.

K-Map Structure — The two-dimensional grid layout of a Karnaugh map with Gray-coded row and column headers.

K-Map Variables — The Boolean variables represented by the rows and columns of a Karnaugh map.

K-Map vs Algebraic Method — A comparison of the graphical K-map approach versus algebraic simplification using Boolean laws.

K-Map with Dont Cares — A Karnaugh map containing cells marked with 'X' or 'd' representing don't care conditions.

Karnaugh Map — A graphical method for simplifying Boolean expressions using a grid where adjacent cells differ by one variable.

L

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

Literal Minimization — The optimization goal of reducing the number of variable occurrences in a Boolean expression.

Logical Adjacency — The property of two K-map cells differing in exactly one variable, allowing them to be grouped.

M

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.

Multiple Solutions — The existence of more than one minimal Boolean expression with the same cost.

O

Overlapping Groups — The practice in K-map simplification of allowing groups to share cells, which is valid and often necessary.

P

Physical Adjacency — The spatial nearness of cells on a K-map grid, not always matching logical adjacency due to wraparound.

Prime Implicant — An implicant that cannot be combined with another to form a larger implicant.

R

Rectangular Groups — Valid K-map groupings that form rectangles (including squares) with sides of power-of-2 length.

Redundant Prime Implicant — A prime implicant that is not essential and whose minterms are all covered by other prime implicants.

T

Three Variable K-Map — A Karnaugh map with 8 cells for functions of three variables.

Two Variable K-Map — A Karnaugh map with 4 cells for functions of two variables.

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.

U

Using Dont Cares — The technique of treating don't care conditions as 1s or 0s to create larger K-map groups.

V

Valid Group Sizes — The allowable number of cells in a K-map group, which must be powers of 2 (1, 2, 4, 8, 16, ...).

W

Wrapping in K-Maps — The property that K-map edges are logically adjacent, allowing groups to wrap around the map.