minimization
minimization
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 μy . g(x1,…,xn,y)
is evaluated by searching for the smallest value of y for which g(x1,…,xn,y) = 0
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 g(x1,…,xn,y)
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: f(x1,…,xn) = μy . g(x1,…,xn,y)
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.
4. See optimization.
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 μy . g(x1,…,xn,y)
is evaluated by searching for the smallest value of y for which g(x1,…,xn,y) = 0
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 g(x1,…,xn,y)
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: f(x1,…,xn) = μy . g(x1,…,xn,y)
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.
4. See optimization.
More From encyclopedia.com
NEARBY TERMS
minimization