Logica combinatoria

logica combinatoria

logica combinatoria locuzione utilizzata in due diverse accezioni:

• per indicare un modello di calcolo logico introdotto nel 1920 dal matematico ucraino M.I. Schönfinkel (combinatory logic);

• per indicare la teoria booleana dei circuiti logici (combinational logic).

Qui si fa riferimento al primo significato; per il secondo si veda → circuito logico. Nel primo dei due significati la logica combinatoria fornisce una notazione che ha lo scopo di rappresentare formalmente il procedimento di calcolo di una funzione matematica. In questo senso la logica combinatoria è analoga ad altri modelli di computazione, come per esempio il → lambda-calcolo, e trova notevoli applicazioni in informatica teorica essendo la base di alcuni linguaggi di programmazione funzionale. Come il lambda-calcolo, anche la logica combinatoria ha degli elementi di base, detti termini; dato un termine di una certa complessità è possibile ridurlo, dopo una successione di riscritture, a un termine più semplice. I termini rappresentano formalmente le funzioni, mentre il processo di riduzione simula il calcolo del valore della funzione. Una differenza essenziale fra il lambda-calcolo e la logica combinatoria riguarda la sostituzione all’interno dei termini e le variabili legate. Nel lambda-calcolo le variabili che compaiono nel campo d’azione dell’operatore di astrazione, indicato con la lettera λ, sono considerate come variabili legate; per esempio nel lambda-termine λx(y)x la variabile x è legata. Di ciò bisogna tener conto nel momento in cui si effettua una sostituzione; per esempio, nel termine precedente, la variabile y può essere sostituita con qualsiasi altra variabile tranne x, altrimenti cambierebbe il suo status passando da variabile libera a variabile legata. Questo problema viene evitato nella logica combinatoria perché non esistono operatori (come l’astrazione λ) che leghino le variabili presenti nel termine. Nonostante tale differenza, il lambda-calcolo e la logica combinatoria hanno lo stesso potere espressivo, nel senso che rappresentano la stessa classe di funzioni: le → funzioni ricorsive parziali. Il lambda-calcolo ha avuto, nella storia, una diffusione più ampia rispetto alla logica combinatoria perché rappresenta una notazione più concisa e di minore complessità computazionale.

La logica combinatoria trova inoltre applicazioni in teoria della → dimostrazione. In particolare, è possibile stabilire una corrispondenza fra le formule deducibili della → logica intuizionista, ridotta al solo frammento implicativo (cioè utilizzando nel linguaggio logico solo il connettivo di implicazione), e i termini della logica combinatoria, ciò in analogia a quanto stabilito dall’isomorfismo di → Curry-Howard.

Per definire formalmente i termini della logica combinatoria si considera un insieme numerabile di variabili x, y, z… e un insieme di costanti M, N, P… Fra le costanti sono inclusi anche i cosiddetti → combinatori cioè elementi che, se applicati ad altri termini, danno origine a un processo di riscrittura dei termini stessi.

I termini sono definiti per induzione sulla complessità per mezzo delle seguenti regole:

• ogni variabile x, y, z… è un termine;

• ogni costante M, N, P … è un termine;

• se A e B sono due termini, allora (AB) è un termine costruito mediante l’applicazione (indicata dalle due parentesi) del termine A al termine B.

L’ultima regola definisce l’operazione di applicazione di un termine A a un termine B. Spesso, per maggiore concisione, alcune delle parentesi sono omesse nella scrittura di un termine; per esempio, invece di ((xy)z) si scrive più semplicemente (xy)z oppure xyz. Utilizzando tale convenzione, si sottintende che l’operazione di applicazione debba essere svolta a partire dai termini che si trovano più a sinistra. Per esempio il termine xyzv è la forma abbreviata (senza parentesi) del termine (((xy)z)v) ed è diverso dal termine (xy)(zv).

Di seguito sono riportate alcune regole di riduzione che definiscono i combinatori piu utilizzati (il simbolo ≡ indica la possibilità di convertire un termine in un altro):

• il combinatore identità: è indicato con il simbolo I, può essere applicato a ogni variabile e ne restituisce il valore inalterato, in simboli (Ix) ≡ x;

• il combinatore costante: si indica con il simbolo K e agisce nel modo seguente: data una variabile x, il combinatore (Kx) può essere applicato a qualsiasi altra variabile e darà sempre un risultato costante uguale a x. Per esempio ((Kx) y) ≡ x;

• il combinatore composizione: si indica con il simbolo S e può essere applicato a tre termini ƒ, g e x, dove i primi due rappresentano funzioni e l’ultimo rappresenta l’argomento delle due funzioni. Applicando il combinatore S si ottiene la composizione delle due funzioni ƒ e g. In formule si ha (((Sf )g)x) ≡ (ƒx)(gx);

• il combinatore duplicazione: è indicato con il simbolo M e se applicato a un termine x lo duplica: (Mx) ≡ (xx);

• il combinatore di permutazione: è indicato con il simbolo T e definito dalla formula ((Tx)y) ≡ (yx);

• il combinatore punto fisso: è indicato con il simbolo Y e, se applicato a un termine ƒ, rappresenta il punto fisso di ƒ come espresso dalla formula (Yƒ ) ≡ (ƒ(Yf )).

Si può dimostrare che i due combinatori S e K formano una base per i termini della logica combinatoria. Ciò significa che utilizzando solo i due combinatori S e K è possibile costruire tutti gli altri combinatori. A titolo di esempio, la seguente catena di uguaglianze mostra come ricavare il combinatore identità a partire dai combinatori S e K: (((SK)K)x) ≡ ((Kx)(Kx)) ≡ x.