Overview

minimization


Show Summary Details

Quick Reference

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.

μy. g(x1,…,xn,y)

g(x1,…,xn,y) = 0

g(x1,…,xn,y)

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.

f(x1,…,xn) = μy. g(x1,…,xn,y)

4 See optimization.

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.