1. The process of manipulating a logical expression and thereby transforming it into a simpler but equivalent expression with the same truth table. In practice this commonly means reducing the number of logic gates, gate inputs, or logic levels in a combinational circuit that realizes the logical expression. Minimization methods include use of Karnaugh maps and algebraic manipulation (often computer-aided).
2. The process of converting a finite-state machine to an equivalent minimal machine.
3. In the study of effective computability, the process of defining a new function by searching for values of a given function using the minimization operator or μ-operator. The functions involved are usually over the natural numbers. Let g be a function of n+1 variables. Then, for any given values of x1,…,xn, the expression
is evaluated by searching for the smallest value of
y for which
This can be done by letting
y run through all natural numbers, in increasing order, until a suitable
y is found, whereupon that value of
y is returned as the value of the μ-expression. If no suitable
y exists the μ-expression is undefined. Also it may happen that before a suitable
y is found a value of
y is encountered for which
is itself undefined; in this case again the μ-expression is undefined.
This construct is used to define a function f of n variables from the function g of n+1 variables:
Because of the possibility of the μ-expression being undefined,
f is a partial function. The process of searching for values, and the use of minimization, are essential factors that allow the formalism of recursive functions to define all the computable functions.