Minimalizzazione

Enciclopedia on line

Particolare tipo di procedimento, usato in logica matematica e soprattutto nella teoria della ricorsività, nel quale si fa uso dell’operatore di m., o operatore-μ, che consente di definire in modo opportuno una funzione a partire da una funzione data o da un predicato dato. Procedimento e operatore di m. possono essere intuitivamente descritti mediante la formula μxPx che si legge «il più piccolo x tale che risulti vero l’enunciato Px». In generale, per definire una funzione (x1, ..., xn) a partire da una funzione nota g(x1, ..., xn, y), per m. di y, si usa la formula:

f(x1, ..., xn) = μy[g(x1, ..., xn, y) = 0]

che si legge: «f(x1, ..., xn) è uguale al più piccolo y tale che sia g(x1, ..., xn, y)=0». Se, invece, si parte da un predicato noto Px1 ... xn y, la formula è:

f(x1, ..., xn) = μyPx1 ... xn y.

Qualora in una delle due definizioni si supponga che questo valore minimo esista sempre, la m. si dice normale. Se si suppone che questo valore minimo debba, in ogni caso, essere minore di un valore z dipendente da x1, ..., xn, la m. si dice limitata.

CATEGORIE
TAG

Logica matematica