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
number of gate inputs, or number of logic levels in a
that realizes the logical expression. Minimization methods include use of
maps and algebraic manipulation (often computer-aided).
2. A process whereby a new function can be obtained from an old function using
the minimization or μ-operator, which is defined as follows. Let g be a function
of n+ 1 variables taking nonnegative integer values and having the integers as
its range. Then
produces the least nonnegative integer y for which
g(x1,x2,.....,xn,y) = 0
for the fixed x1,x2,.....,xn. Of course, such a y may not
exist. If y does exist a new partial function ƒ of n variables can be defined
from g by applying the μ operator:
= μy(g(x1,.....,xn,y) = 0)
Otherwise ƒ(x1,.....,xn) is undefined.
To illustrate the use of minimization, let
be defined as follows:
μy(| 2y - x| = 0)
Then ƒ = x/2 when x is even.