RICERCA ITALIANA     

Logiche a più valori e informazione incerta: metodologie algebriche e algoritmiche.

Università degli Studi di Siena

Abstract

Le logiche a più valori costituiscono uno strumento fondamentale nel trattamento dell'informazione incerta. Su questo tema, una collaborazione di lunga data fra logici, algebristi e informatici ha prodotto risultati profondi e fertilizzazioni incrociate. Come si può notare dalla bibliografia acclusa e dai curricula, questo campo in continua e rapida espansione ha fra i suoi leaders internazionali alcuni fra i proponenti. Essi hanno saputo coniugare temi apparentemente lontani fra loro come i codici correttori con feedback, la Logica di Lukasiewicz, i gruppi Abeliani reticolari, il procedimento di ‘starring' di De Concini-Procesi su fan unimodulari, le AF C*-algebre e i loro diagrammi di Bratteli, ottenendo da raffinate tecniche algebriche e geometriche algoritmi deduttivi e strategie di codifica.
Il nostro gruppo è all'avanguardia anche per quanto riguarda gli sviluppi recenti delle logiche a più valori quali la logica di base di Hàjek ed altre logiche a più valori legate alle logiche sottostrutturali, la versione many-valued della probabilità senza punti nello stile di Caratheodory, e il problema della soddisfacibilità probabilistica. Consideriamo infatti un merito importante del nostro gruppo di ricerca quello di avere offerto contributi decisivi in quasi tutti i temi di ricerca in ambito many-valued.
L'approfondimento ulteriore di questi temi attraverso fertilizzazioni incrociate fra tecniche algebriche ed algoritmiche è uno dei principali obiettivi del progetto.
In dettaglio, ci proponiamo di:
a) Migliorare ulteriormente la nostra conoscenza generale delle MV-algebre, cercando ad esempio una caratterizzazione intrinseca (non legata quindi a rappresentazioni tramite funzioni) delle MV-algebre libere.
b) Approfondire parallelamente lo studio dei gruppi Abeliani reticolari, cercando di fornire una descrizione completa dei gruppi Abeliani reticolari di rango infinito e dei gruppi Abeliani reticolari finitamente generati proiettivi.
c) Studiare in modo analitico strutture più ricche delle MV-algebre, come le MV-algebre con prodotto, le MV-algebre con operazione di composizione, con applicazioni allo studio di proprietà dinamiche delle stesse, i rapporti fra MV-algebre e semianelli e fra MV-algebre e frames.
d) Approfondire le ricerche sui legami fra multiinsiemi e MV-algebre, studiando in particolare la combinatoria dei multiinsiemi finiti e i multiinisiemi su uno spazio connesso.
e) Migliorare la nostra conoscenza, attraverso teoremi di rappresentazione, di strutture più generali delle MV-algebre, come le BL-algebre di Hàjek, le MTL-algebre e altre classi di reticoli residuati.

Faremo poi interagire i risultati algebrici con la messa a punto di algoritmi per codici correttori con feedback, per calcoli logici e per il problema della soddisfacibilità probabilistica. In dettaglio, ci proponiamo di:

f) Applicare metodologie logiche e algebriche ai codici correttori su canali pesati, e nella direzione opposta, applicare la teoria dei giochi di Ulam Renyi multi-canale ai fini di una nuova semantica per la logica di base di Hàjek.
g) Approfondire i legami fra strutture algebriche e logiche sottostrutturali, studiando in dettaglio il problema dell'interpolazione.
h) Elaborare nuovi sistemi per la ricerca di dimostrazioni per le principali logiche a più valori.
i) Applicare tecniche algebriche al problema della soddisfacibilità probabilistica.

Ulteriori obiettivi del progetto sono l'interazione con altri gruppi di ricerca e la formazione dei nostri giovani ricercatori. Il nostro gruppo infatti si distingue non solo per la presenza di esperti di fama consolidata, ma anche per la sua vitalità, che si manifesta sia attraverso continue interazioni con la comunità scientifica, sia attraverso il coinvolgimento di brillanti giovani ricercatori, che si sono segnalati alla comunità internazionale per la profondità dei risultati ottenuti e per la qualità della collocazione editoriale delle loro pubblicazioni. <<<

Coordinatore Scientifico del Programma di Ricerca

Franco MONTAGNA Università degli Studi di SIENA

Obiettivo del Programma di Ricerca

Ben lungi dall'aver esaurito il proprio compito, la logica a più valori costituisce un campo in continua espansione: da un lato, nonostante la ricchissima letteratura esistente, vengono prodotti continuamente sorprendenti risultati su temi classici come la Logica di Lukasiewicz, i gruppi Abeliani reticolari, la AF C* algebre e i codici correttori, dall'altro emergono nuove prospettive di ricerca, come ad esempio il rapporto fra le logiche a più valori deboli e le logiche sottostrutturali, o il rapporto fra logiche a più valori e probabilità. Come testimoniato dai curricula e dall'elenco delle pubblicazioni accluse, il nostro gruppo ha saputo offrire contributi sostanziali a questa area di ricerca.
Stanti queste premesse, il nostro obiettivo è quello di migliorare la nostra conoscenza sulle logiche a più valori, e in particolare di:

a) Puntare ad una trattazione unitaria di vari temi collegati fra loro, come la Logica di Lukasiewicz, i gruppi Abeliani reticolari, il procedimento di starring su fan unimodulari, le AF C* algebre e i loro diagrammi di Bratteli, e i codici correttori con feedback.
b) Estendere l'applicabilita' degli strumenti offerti dalle MV-algebre a strutture più generali, come le BL-algebre, e a strutture più ricche, ad esempio le MV-algebre con operatori di vario tipo.
c) Ottenere fertilizzazioni incrociate fra teoria algebrica e applicazioni logiche ed algoritmiche, puntando in particolare a sistemi di dimostrazione efficienti per logiche a più valori e a nuovi algoritmi per i codici correttori adattivi e per la soddisfacibilità probabilistica.

Il nostro progetto, pur essendo il risultato di una collaborazione di un gruppo di ricerca omogeneo, non sarà limitato ad un numero ristretto di problemi, ma coprirà invece un ampio spettro di temi di ricerca. Riteniamo infatti che solo in questo modo si possano ampliare gli orizzonti e trovare sinergie fra metodologie di tipo diverso.
Entrando nel dettaglio, le nostre ricerche saranno rivolte innanzitutto ad un approfondimento della teoria delle MV-algebre e di strutture ad esse legate come i gruppi Abeliani reticolari e le AF C* algebre. In particolare, ci proponiamo di ottenere una caratterizzazione intrinseca (quindi non tramite rappresentazione geometrica nello stile di McNaughton) delle MV-algebre libere. Un problema collegato a questo, tramite il funtore Gamma, riguarda la caratterizzazione dei gruppi Abeliani reticolari liberi (e più in generale, proiettivi). A partire dai recenti risultati di Mundici (Trans. Amer. Math. Soc., vol 356, 2004) e di Glass-Marra (J.London. Math. Soc. vol.68, 2004), continueremo le nostre ricerche sugli aspetti algoritmici e combinatori dei gruppi Abeliani reticolari proiettivi e sulle MV-algebre finitamente presentate ad essi associate.
Due ulteriori aspetti delle MV-algebre che saranno oggetto della nostra ricerca sono le proprietà d'ordine e le connessioni con i multiinsiemi. Come mostrato dal lavoro di Riecan e Mundici, le MV-algebre sigma complete costituiscono l'ambiente algebrico adatto ad una generalizzazione della teoria della probabilità di Caratheodory. Ora, la sigma additività dipende solo dalla struttura d'ordine delle MV-algebre. Questo fatto costituisce una delle motivazioni per studiare il rapporto fra proprietà d'ordine e struttura additiva in queste algebre.
Le connessioni con i multiinsiemi nascono invece da un profondo risultato di Cignoli, Dubuc e Mundici, (J.Pure and Applied Algebra, vol. 189, 2004), che stabilisce una dualità categoriale fra multiinsiemi e MV-algebre localmente finite. La combinatoria dei multiinsiemi finiti e la nozione di multiinsieme su un insieme connesso costituiscono un obiettivo del nostro progetto.

Le ricerche riguardanti le MV-algebre e le altre strutture algebriche ad esse collegate ci consentiranno, grazie al teorema di decomposizione di Aglianò e Montagna (J. Pure and Applied Algebra 181, 2003) di approfondire la conoscenza delle BL-algebre, strutture legate alle t-norme continue proposte da Hàjek come semantica naturale per le logiche a più valori. Un primo passo in questa direzione sarà quello di estendere il teorema di Hahn sulla rappresentazione dei gruppi ordinati al caso delle BL-algebre ordinate. Un obiettivo ancora più difficile da raggiungere è quello di estendere le tecniche importate dalla teoria delle MV-algebre a reticoli residuati ancora più generali come ad esempio le MTL-algebre.
I progressi ottenuti nella teoria algebrica e geometrica delle algebre per le logiche a più valori ci consentiranno applicazioni di vario tipo. Innanzitutto, metteremo a confronto il metodo di starring di De Concini Procesi e le basi di Schauder con le procedure algoritmiche di desingolarizzazione di varietà toriche tidimensionali di Mundici e Aguzzoli. In seguito ci concentreremo sulle logiche più deboli, a partire dalla Logica BL di Hàjek, alla quale estenderemo le tecniche geometriche di cui sopra, utilizzando il sopraccitato teorema di decomposizione di Aglianò e Montagna.
Sempre nell'ambito delle generalizzazioni delle MV-algebre, un obiettivo del progetto sarà quello di estendere il concetto di MV-algebra nella direzione opposta, cioè verso strutture più ricche e più espressive. Fra i temi che saranno oggetto della nostra ricerca citiamo le MV-algebre con prodotto, le MV-algebre con composizione, con riferimento alle proprietà dinamiche, le proprietà topologiche delle MV-algebre (frames), i moduli su MV-algebre.
Come abbiamo detto in precedenza, un obiettivo caratterizzante del progetto sarà costituito dalle fertilizzazioni incrociate fra metodi algebrici ed algoritmici. Le applicazioni delle teoria algebrica verteranno soprattutto sugli aspetti logici, sui codici correttori con feedback e sul problema della soddisfacibilità probabilistica.
Fra le applicazioni alla logica, un importante obiettivo è costituito da uno studio generale delle proprietà di interpolazione in logiche a più valori. Vi sono infatti due tipi di interpolazione, equivalenti nelle logiche aventi il Teorema di Deduzione: la prima espressa tramite l'implicazione, la seconda tramite la relazione di conseguenza logica. Mentre la prima versione non vale in generale per le logiche a più valori (con l'eccezione della Logica di Goedel), la seconda vale per la Logica di Lukasiewicz. Utilizzando i risultati di Ono (Algebra Universalis vol. 23 1986), studieremo le varie proprietà di interpolazione in un ambito più generale possibile, partendo dalle MV-algebre e dalle MV_n-algebre, per arrivare poi alle BL-algebre e possibilmente a strutture ancora più generali.
Per quanto riguarda le applicazioni alla logica di tipo algoritmico, ci proponiamo di costruire calcoli logici efficienti per le principali logiche a più valori. In particolare, ci concentreremo sui sistemi di dimostrazione goal-oriented.
Applicheremo poi la teoria algebrica allo studio dei codici correttori su canali pesati, cercando di estendere i nostri risultati sui codici asimmetrici con un errore, e nella direzione opposta, tenteremo di utilizzare i giochi di Ulam-Renyi multicanale per una semantica della Logica di Base di Hàjek.
Infine, un'importante applicazione sarà costituita dalla costruzione di algoritmi efficienti per il problema della soddisfacibilità probabilistica (con particolare riferimento a CPA) e alla costruzione di varianti probabilistiche della logica temporale lineare.
Ulteriori obiettivi del progetto sono l'interazione con altri gruppi di ricerca e la formazione dei nostri giovani ricercatori. Infatti, come abbiamo detto, il nostro gruppo si distingue non solo per la presenza di esperti che svolgono il ruolo di leaders, ma anche per la sua intensa collaborazione con altri gruppi di ricerca, e per la formazione di giovani brillanti, che si sono affermati grazie alla profondità dei loro risultati e alla collocazione editoriale delle loro pubblicazioni. <<<

Risultati parziali attesi

Generalizzazione del teorema di immergibilità di Higman a gruppi Abeliani reticolari di rango infinito (il problema è arduo, ma prevediamo di fare significativi passi avanti in questa direzione già nella prima fase, individuando operazioni che preservano l'immergibilità).
Rappresentazioni di BL-algebre linearmente ordinate come algebre di funzioni a valori reali, generalizzando il Teorema di Hahn.
Caratterizzazione intrinseca delle MV-algebre libere, teoria generale delle basi di Schauder astratte nelle MV-algebre libere e nei gruppi Abeliani reticolari proiettivi, e loro applicazioni ai fan unimodulari.
Costruzione di una sostituzione con la proprietà di Bernoulli su 3 variabili per le MV-algebre. (Questo risultato appare difficile, ma prevediamo di fare almeno dei passi avanti importanti). Descrizione delle sostituzioni generiche per la logica di Goedel e per la logica prodotto.
Dimostrazione puramente MV-algebrica dell'amalgamazione nelle MV_n-algebre (senza utilizzare l'analogo risultato per i gruppi Abeliani reticolari e il funtore Gamma, ma utilizzando una proprietà di interpolazione di Ono).
Studio delle proprietà equazionali dell'operatore ‘parte standard' nelle LP-algebre.
Descrizione delle proprietà algebriche delle MV-algebre con composizione.
Estensione dei risultati esistenti per la correzione di un singolo errore sul canale asimmetrico Zeta.
Determinazione di calcoli goal-directed per le principali logiche a più valori.
Determinazione di calcoli logici completi per le versioni probabilistiche e many-valued della Logica Temporale Lineare.
Giustificazione teorica del punto di cross-over del parametro a=m/n per la performance dell' algoritmo che risolve 2CPA, e determinazione del punto di cross-over per altri sottoproblemi di PSAT.Generalizzazione del teorema di Higman per ampie classi di gruppi Abeliani reticolari di rango infinito.
Soluzione di alcuni problemi combinatori e algoritmici sui gruppi Abeliani reticolari proiettivi e le loro corrispondenti MV-algebre finitamente presentate, (con un'analisi della complessità della procedura di starring di De Concini-Procesi).
Sistemi di dimostrazione per la Logica di Base basati su proprietà geometriche.
Studio generale delle proprietà di interpolazione per le logiche a più valori. (Prevediamo di dimostrare una forma opportuna di interpolazione almeno per la logica di Lukasiewicz, per la logica prodotto e per la logica BL).
Teoremi di completezza standard per logiche a più valori senza weakening.
Implementazione di sistemi di prova goal-directed per le principali logiche proposizionali a più valori.
Approfondimento delle proprietà combinatorie dei multiinsiemi finiti e dei multiiinsiemi definiti su spazi connessi.
Descrizione di una semantica a giochi per la Basic Logic basata sui giochi di Ulam multicanale.
Codici correttori perfetti con minimo feedback per canali di massima generalità.
Sviluppo di algoritmi per CPA, stima della complessità media per sottoproblemi particolari e valutazione sperimentale dei possibili punti di cross-over del parametro a=m/n.
Sviluppo di algoritmi per la versione many-valued di CPA.
Valutazione della complessità computazionale del problema di soddisfacibilità per la logica temporale lineare probabilistica, e implementazione di calcoli basati su tableau per alcuni frammenti di tale logica. <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

Le logiche a più valori costituiscono uno strumento fondamentale nel trattamento dell'informazione incerta. Rispetto ad altri metodi per trattare l'incertezza, la logica dispone infatti di naturali meccanismi deduttivi molto adatti alle applicazioni. Se consideriamo le formule a meno di dimostrabile equivalenza, la logica viene ad avere importanti connessioni con la matematica, specialmente con l'algebra e la geometria. Questo è avvenuto per la logica classica tramite il teorema di Stone, ed avviene in modo ancora più evidente per le logiche a più valori. Grazie anche a contributi fondamentali di alcuni dei proponenti, sono emerse infatti sorprendenti connessioni fra settori apparentemente lontani come la codifica con feedback (il gioco "pensa un numero" di Renyi-Ulam), la logica a più valori di Lukasiewicz, i gruppi Abeliani reticolari, l'operazione di starring sui fan unimodulari, e le AF C*-algebre. Infatti, in una serie di risultati, essenzialmente dovuti a ricercatori del nostro gruppo, è stato mostrato che la logica del gioco di Ulam-Renyi è il calcolo infinito-valente di Lukasiewicz, che le algebre di tale logica, le MV-algebre di Chang, sono categoricamente equivalenti ai gruppi Abeliani reticolari con unita' forte, che le forme normali disgiuntive in tale logica (basi di Schauder) sono canonicamente associate a fan unimodulari, e che lo starring può essere interpretato come passo dimostrativo in tale logica, che usando la classificazione di Elliott, il funtore K_0 di Grothendieck induce una corrispondenza biunivoca tra le AF C*algebre il cui ordine di Murray-von Neumann è reticolare e le MV-algebre numerabili.
Parallelamente, mentre l'indagine su questi temi si andava raffinando, dando luogo a risultati profondi e a connessioni sempre più sorprendenti, dal lavoro di Hàjek sono emerse semantiche più generali per la logica a più valori. Fra queste, le algebre prodotto, strettamente legate ai coni negativi dei gruppi Abeliani reticolari, e le cosiddette algebre di Goedel, particolari algebre di Heyting che costituiscono un anello di collegamento fra logiche a più valori e logiche intermedie. Una semantica ancora più generale è costituita dalla varietà generata dalle t-norme continue con i loro residui, ossia la varietà delle BL-algebre. L'approfondimento di tale semantica ha portato a varie generalizzazioni delle MV-algebre. Da un lato sono state studiate strutture più ricche, (ottenute ad esempio combinando le MV-algebre con le algebre prodotto) e particolarmente adatte ad uno studio algebrico della probabilità e alla programmazione a più valori con casi non esclusivi, dall'altro sono state studiate strutture più deboli, fra cui le BL-algebre e altri tipi di reticoli residuati, legati alle logiche sottostrutturali.
I ricercatori del nostro gruppo hanno svolto un ruolo fondamentale in queste ricerche, ottenendo continui riconoscimenti internazionali. Infatti, come i desume dai Modelli B, molti dei proponenti sono stati o sono membri di comitati di programma o relatori invitati in convegni internazionali, o coordinatori scientifici di progetti nazionali o internazionali, o consulting editors di riviste scientifiche. Essi hanno svolto anche una intensa attività di formazione, ad esempio seguendo tesi di PhD, ed hanno avuto fecondi scambi scientifici con altri studiosi.
Anche i nostri giovani ricercatori hanno ottenuto importanti riconoscimenti ufficiali come prestigiose borse di studio per l'estero, premi per tesi di dottorato, inviti a convegni internazionali, etc.
I contributi del nostro gruppo riguardano praticamente tutti i temi trattati nell'ambito delle logiche a più valori. Alcuni risultati classici (e.g., il funtore Gamma di Mundici, la dimostrazione costruttiva di Mundici del Teorema di McNaughton, l'interpretazione, sempre di Mundici, della Logica di Lukasiewicz attraverso il gioco di Ulam-Renyi, il teorema di Di Nola sulla rappresentazione delle MV-algebre come algebre di funzioni continue da uno spazio compatto ad un intervallo reale non-standard) fanno ormai parte della storia del ragionamento in condizioni di incertezza, e sono citati frequentemente nei libri di testo.
Limitandoci alla storia recente, possiamo suddividere le tipologie dei nostri contributi come segue:

CODICI CORRETTORI ADATTIVI
Lo studio dell'informazione in condizioni di incertezza coinvolge informatici, matematici, e ingegneri. Il nostro gruppo di ricerca ha notevole competenza teorico-applicativa sui codici correttori di errori con feedback. Il problema di codifica con minimo feedback essenzialmente chiede di minimizzare il numero di domande e di interazioni nel gioco "Pensa un numero" in cui chi risponde puo' mentire un certo numero E di volte (gioco di Ulam-Renyi). Se tutte le domande sono fatte all'inizio, indipendentemente dalle risposte, e dunque senza interazione, strategie ottimali (perfette) per indovinare il numero sono la stessa cosa dei classici codici E-correttori ottimali (perfetti). La letteratura e' piena di risultati negativi per l'esistenza di tali codici perfetti. Sorprendentemente, in una serie di lavori scientifici apparsi sulle migliori riviste internazionali di informatica e matematica combinatoria, Mundici e Cicalese (vedi bibliografia) hanno mostrato l'esistenza di velocissimi codici correttori perfetti e con minima interazione. I loro protocolli perfetti di minimo feedback per la correzione di errori sono oggetto di grande interesse internazionale, si veda ad esempio, il survey di A. Pelc "Searching games with errors", Theoretical Computer Science 270 (2002), 71-109.

LA LOGICA DEI CODICI CORRETTORI; MULTINSIEMI, PARTIZIONI DELL'UNITA', BASI DI SCHAUDER.
Come dimostrato da Mundici, nel gioco di Ulam-Renyi le risposte seguono una logica polivalente, e le varianti del gioco di Ulam-Renyi forniscono semantiche per varie logiche polivalenti. Ciò arricchisce il significato del lavoro, già copioso ed apprezzato internazionalmente, di Aguzzoli e Ciabattoni: algoritmi di ricerca e codifica sono l'analogo delle dimostrazioni nella logica polivalente.
Lo studio algebrico della logica polivalente ci ha portato a un'analisi dettagliata di varie nozioni classiche, mediante le loro estensioni MV-algebriche. E' il caso di "multinsieme infinito", "partizione dell'unita'", e di "funzione definita per casi non separati". Per quanto riguarda la prima nozione, in [MuCD], viene mostrata una dualità tra multinsiemi e MV-algebre localmente finite. Quando i multinsiemi hanno molteplicità uno, recuperiamo la classica dualità di Stone.
Funzioni definite per casi costituenti una partizione dell' unità sono frequentemente usate dagli ingegneri nella loro descrizione delle funzioni di controllo. Dopo una prima esposizione dei risultati di alcuni dei proponenti in un lavoro apparso nel libro "From Synapses to Rules", è stata approfondita la nozione di "simultanea raffinabilità", che è lo strumento chiave per garantire l'amalgamabilità di due differenti descrizioni per casi della stessa funzione, e sono state analizzate le condizioni che assicurano tale proprietà.

ALGORITMI PER ALGEBRE DI OPERATORI E REALIZZAZIONE DI PI GRECO
Un filone di ricerca implicito nella trattazione MV-algebrica della logica a più valori è costituito dall'esportazione di metodologie algoritmiche nel campo dell'analisi funzionale. Bratteli, Jorgensen ed altri hanno ottenuto profondi risultati di decidibilità per il problema dell'isomorfismo di certe AF C*-algebre definite da matrici stazionarie. Invece, Mundici ha ottenuto risultati di indecidibilità per altre classi di AF C*algebre descritte da complessi simpliciali astratti, si veda [Mu].
Un altro risultato profondo è stato ottenuto da Marra e Glass [MaG], combinando tecniche dei fan, delle basi di Schauder, di approssimazione diofantea, e presentazioni di gruppi reticolari non Abeliani. Il loro risultato estende il teorema di Higman alla classe di gruppi Abeliani reticolari ricorsivamente presentati e di rango finito. Il gruppo di Effros-Shen totalmente ordinato corrispondente alla frazione continua lenta di pi greco e' uno di questi gruppi, e questo giustifica il titolo di [MaG].

MV-ALGEBRE CON ULTERIORE STRUTTURA. La programmazione a più valori in cui i casi non sono incompatibili, insieme alla probabilità MV-algebrica, costituisce uno dei motivi per introdurre un ‘prodotto' nelle MV-algebre. La logica più naturale da questo punto di vista appare la logica LP, risultante dalla combinazione della logica di Lukasiewicz e della logica prodotto. Le strutture algebriche corrispondenti costituiscono una categoria equivalente ad una categoria di f-anelli commutativi regolari nel senso di Von Neumann. Un difetto di questa logica è la discontinuità nello 0 dell'operatore che interpreta semanticamente il residuo del prodotto. Al fine di evitare questo inconveniente, sono stati studiati i sottoridotti privi di 0 della varietà delle LP-algebre [M0]. Una versione più generale di MV-algebre con un prodotto è stata studiata da Di Nola e Dvurucenski [DND]. Infine, Mundici ha affrontato il problema attraverso il concetto di prodotto tensoriale fra MV-algebre.
Un altro modo per generalizzare le MV-algebre consiste nello studio delle MV-algebre divisibili, ottenute aggiungendo una famiglia numerabile di operatori unari interpretati come "divisione per p", con p numero primo. La logica che si ottiene in questo modo, oltre ad avere la proprietà di interpolazione, è uno strumento flessibile per modellare diversi fenomeni: in particolare è stata usata nella programmazione a più valori e come modello logico per le reti neurali con pesi razionali. Proseguendo in questa direzione, in [DFL] sono state introdotti e studiati i moduli su MV-algebre.
Un altro modo di aggiungere struttura alle MV-algebre consiste nell'introdurre un operatore monadico. Mentre le trattazione della logica predicativa di Lukasiewicz è problematica (l'insieme delle formule valide nella semantica standard non è ricorsivamente assiomatizzabile), tali strutture sono completamente caratterizzate in [DNGr].

LOGICA DI BASE. Nel suo libro ‘Metamathematics of Fuzzy Logic', Kluwer 2000, Hàjek propone una semantica per le logiche a più valori basata non solo sulle MV-algebre, ma più in generale su una varietà di algebre generata dalle cosiddette ‘t-norme continue' su [0,1], ossia da reticoli residuati commutativi e integrali su [0,1] la cui operazione monoidale è continua. Oltre alla congiunzione di Lukasiewicz, che dà origine alle MV-algebre, importanti t-norme continue sono il prodotto e l'operazione di ‘minimo' in [0,1]. Gli elementi della varietà generata da tali strutture sono dette BL-algebre. Un teorema classico di rappresentazione per le t-norme continue dovuto a Mostert e Schields consente di scomporre le t-norme continue attraverso le tre t-norme citate. Il risultato è stato generalizzato in [AM]: ogni BL-algebra linearmente ordinata (quindi a fortiori ogni BL-algebra sottodirettamente irriducibile) è scomponibile in BL-algebre che sono o MV-algebre o sottoridotti privi di 0 di MV-algebre. Come prevedibile, questo risultato ha consentito di esportare almeno in parte i profondi risultati e le tecniche raffinate che fanno parte della letteratura delle MV-algebre, ai fini di una classificazione e di uno studio approfondito delle BL-algebre. Inoltre, essa ha consentito una dimostrazione di Co-NP completezza di BL [BHMV] ed un calcolo a tableau con regole invertibili per tale logica [MPT]. E' stato poi fornito [EGM] un algoritmo per dare una assiomatizzazione finita delle varietà generate da t-norme continue. Le BL-algebre finite sono pienamente descritte in [DNL], mentre in [DIG] viene studiata la versione non commutativa delle BL-algebre.

LOGICHE A PIU' VALORI E LOGICHE SOTTOSTRUTTURALI.
Se da un punto di vista semantico la logica BL può essere considerata come la naturale generalizzazione delle più importanti logiche a più valori, da un punto di vista puramente logico si può andare ancora oltre: interpretando le logiche a più valori come logiche aventi valori di verità in [0,1], si perviene ad una logica, detta MTL, ottenuta dal Full Lambek Calculus con scambio e indebolimento, aggiungendo una regola strutturale, la communication rule di Avron. Per tale logica, anche nella versione non commutativa, è stata dimostrata la completezza rispetto alla semantica sull'intervallo reale [0,1], [MJ]. Un calcolo a ipersequenti è stato proposto, almeno per il caso commutativo, in [BCM]. Tale calcolo ha la proprietà della sottoformula e ammette l'eliminazione del taglio, anche nel caso predicativo. In analogia con la Logica Lineare, ma con scopi dichiaratamente diversi, sono state introdotte in [M1] alcune logiche a più valori con un operatore * di ‘storage' (A* è interpretato come l'iterazione di A un numero indefinito di volte). I modelli algebrici sono i reticoli residuati commutativi e integrali linearmente ordinati tali che per ogni elemento a esiste un massimo idempotente sotto a. Tale operatore ha consentito l'introduzione di un quantificatore universale moltiplicativo (iterazione della congiunzione monoidale).

QUANTIFICATORI IN LOGICHE A PIU' VALORI. Mentre per le logiche a più valori proposizionali più comuni si ha un teorema di completezza standard (cioè rispetto alla semantica naturale su [0,1]), la situazione di solito cambia se si passa al primo ordine. L'insieme delle formule predicative della logica prodotto e della logica BL valide nella semantica su [0,1] non è aritmetico. Più in generale, con un numero finito di eccezioni, la logica al primo ordine di una t-norma continua non è aritmetica, e la sola t-norma continua la cui logica al primo ordine è ricorsivamente assiomatizzabile è quella di Goedel. Infine, con le possibili eccezioni della logica di Lukasiewicz e della logica prodotto, le logiche monadiche di t-norme continue sono indecidibili [M2]. Sorprendentemente invece, la versione predicativa della logica delle t-norme continue a sinistra è ricorsivamente assiomatizzabile, e coincide con la versione predicativa di MTL [MO].

LOGICHE A PIU' VALORI E PROBABILITA'. Le nostre ricerche su logica a più valori e probabilità hanno origine dal lavoro di Mundici e Riecan [MuR] sulla probabilità MV-algebrica, nella quale viene presentato un elegante approccio nello stile di Caratheodory. Il nostro interesse si è rivolto anche agli aspetti computazionali (problema della soddisfacibilità probabilistica). Un primo problema, detto PSAT, considera una assegnazione di valori di probabilità e chiede se c'è una misura di probabilità coerente con essa. Il problema rientra nell'ambito generale della coerenza di assegnazioni di probabilità, si veda G.Coletti-R.Scozzafava, 'Probabilistic Logic in a coherent setting', Kluwer 2002, per una trattazione generale, anche nel caso della probabilità condizionata. Il nostro gruppo ha considerato un nuovo problema detto CPA, in cui gli eventi vengono visti come elementi di un'algebra di Boole finitamente presentata da certe relazioni presenti nell'istanza. Ci siamo concentrati su 2CPA, trovando un algoritmo di complessità media polinomiale. Abbiamo poi dimostrato la NP-completezza del problema della soddisfacibilità della Logica di Luaksiewicz probabilistica. <<<