Karnaughkaart

Karnaughkaart, often abbreviated as K-map, is a graphical method used for simplifying Boolean algebra expressions. Invented by Maurice Karnaugh in 1953, it provides a visual representation of a truth table, making it easier to identify and eliminate redundant terms. K-maps are particularly effective for functions with a small number of input variables, typically up to four or five.

The structure of a K-map is a grid of cells, where each cell corresponds to a unique combination of input variable values. The cells are arranged in a specific order, known as Gray code, which ensures that adjacent cells differ in only one variable. This adjacency property is crucial for the simplification process.

To use a K-map, one first fills the cells with the output values from the corresponding truth table. Ones represent terms that should be included in the simplified expression, while zeros can often be ignored. The next step involves grouping adjacent ones in rectangular or square shapes. These groups must contain a power of two number of cells (1, 2, 4, 8, etc.) and should be as large as possible. Each group represents a simplified product term.

The final simplified Boolean expression is obtained by ORing together the product terms derived from each group. The K-map method systematically identifies all possible simplifications, leading to a minimal sum-of-products or product-of-sums form of the Boolean function. While powerful for a limited number of variables, its complexity increases significantly with more inputs.