Logica fuzzy/2007-2008

News

Avviso: venerdì 2 novembre non ci sarà lezione.

Appelli

Su appuntamento.

Informazioni generali

Docenti

Vincenzo Marra
Stefano Aguzzoli

Corsi di laurea

Complementare per i corsi di laurea triennale in Informatica, Informatica per le Telecomunicazioni e Comunicazione Digitale e per il corso di laurea magistrale in Informatica.

Programma

• Prima Parte (Marra)

Introduzione alla logica fuzzy e alle sue applicazioni.
Logica proposizionale booleana.
Norme triangolari e relative logiche fuzzy.
Introduzione alla logica di Gödel.
Semantica della logica di Gödel.
Completezza della logica di Gödel.
Una semantica alternativa per la logica di Gödel.
Logica di Gödel e logica booleana a confronto.

• Seconda Parte (Aguzzoli)

Introduzione alla logica di Łukasiewicz.
Logica di Łukasiewicz e logica di Gödel a confronto.
Semantica della logica di Łukasiewicz: le MV-algebre di Chang.
Completezza della logica di Łukasiewicz.
Teorema di rappresentazione di McNaughton.
Complessità computazionale dei problemi di soddisfacibilità e tautologicità della logica di Łukasiewicz.
Un approccio generale alle gerarchie di logiche fuzzy: cenni a BL e MTL.

Seminari

• Nell'anno accademico 2007-2008 si prevedono i seminari seguenti:

Paolo Amato, ST Microelectronics. Titolo da stabilirsi. Data da stabilirsi.
Matteo Bianchi, Università di Milano. Estensioni predicative delle logiche fuzzy. Data da stabilirsi.
Simone Bova, Università di Siena. Introduzione alla Basic Fuzzy Logic di Hájek. Data da stabilirsi.

Modalità d'esame

L'esame consiste in un colloquio con i docenti sul programma del corso.

Gli studenti che ne facciano richiesta possono anche concordare con i docenti la redazione di una tesina o lo sviluppo di un progetto in sostituzione di parti del programma.

Alcuni esempi di tesine: relazione su un articolo di ricerca; rassegna della letteratura scientifica su un argomento di ricerca.

Alcuni esempi di progetti: implementazione (in C, Java, Prolog, etc.) di algoritmi inerenti al programma del corso; sviluppo di software di supporto alla ricerca nel campo della logica fuzzy.

Prerequisiti al corso

Nessuno.

Orari e luogo delle lezioni

• Martedì 13.30-15.30 auletta 5 (Comelico)
• Venerdì 13.30-15.30 auletta 5 (Comelico)

Orario di ricevimento studenti

• Marra: su appuntamento.
• Aguzzoli: mercoledì dalle 15.00 alle 16.00 o su appuntamento, stanza S204 via Comelico 39.

Materiale didattico

Non ci sono testi che coprano interamente gli argomenti trattati, ma il contenuto delle lezioni è sufficiente per sostenere l'esame.

Testi ausiliari consigliati

R. L. O. Cignoli, I. M. L. D'Ottaviano e D. Mundici, Algebraic Foundations of Many-Valued Reasoning, Kluwer, 1999.
P. Hájek, Metamathematics of Fuzzy Logic, Kluwer, 1998.
S. Gottwald, A Treatise on Many-Valued Logics, King's College Publications, Research Studies Press, 2001.

Dispense

 Durante le lezioni verrà distribuita una versione preliminare delle dispense del corso.

Diario del corso

Lezione di martedì 2/10/2007

• Definizione di logica fuzzy in senso stretto e in senso ampio.
• Concetti di funzione di appartenenza e di insiemi fuzzy.
• Richiamo di logica proposizionale classica: definizioni di proposizione atomica, proposizione composta, alfabeto, stringa, formula.

Lezione di venerdì 5/10/2007

Semantica della logica proposizionale classica

• Assegnamento alle variabili e assegnamento alle formule.
• Definizioni di tautologia, contraddizione e formula soddisfacibile.
• Esempi di tautologie: prelinearità, principio del terzo escluso, ex falso quodlibet, leggi di de Morgan.

Teoria della dimostrazione (sintassi)

• Assiomi della LPC.
• Definizione di dimostrabilità e derivabilità per modus ponens.
• Teorema di completezza della LPC.

Lezione di martedì 9/10/2007

Logica di Gödel

• Definizione di assegnamento alle variabili e alle formule nella LG (e variante di Zadeh).
• Analisi di alcune tautologie della LC che cadono nella LG (legge della doppia negazione, principio del terzo escluso) o restano tautologie (ex falso quodlibet, prelinearità).
• Inclusione stretta dell'insieme delle tautologie della LG nell'insieme delle tautologie della LC.
• Introduzione del problema di tautologicità nella LG.
• Lemma: l'insieme dei possibili valori di verità di una formula è composto da 1, 0 e i valori di verità delle variabili coinvolte nella formula.

Oggi sono state distribuite le fotocopie del primo capitolo delle dispense.

Lezione di venerdì 12/10/2007

• Definizione degli assiomi della LG e di formule deducibili (o dimostrabili).
• Teorema di completezza per la LG (senza dimostrazione).
• Definizione di assegnamenti equivalenti su n variabili (che si scrive $\mu \equiv _{n}\nu$).
• Lemma: dati due assegnamenti $\mu$ e $\nu$ equivalenti sulle prime n variabili, per ogni formula $\alpha \left(x_{1},\ldots ,x_{n}\right)$ vale:

${\begin{matrix}\mu \left(\alpha \right)=1&\Leftrightarrow &\nu \left(\alpha \right)=1\\\mu \left(\alpha \right)=\mu \left(x_{i}\right)&\Leftrightarrow &\nu \left(\alpha \right)=\nu \left(x_{i}\right)\\\mu \left(\alpha \right)=0&\Leftrightarrow &\nu \left(\alpha \right)=0\\\end{matrix}}$

• Corollario: il problema di tautologicità della LG è decidibile.

Lezione di martedì 16/10/2007

• Algoritmo per la risoluzione del problema di tautologicità.
• Dimostrazione intuitiva del fatto che esiste sempre un assegnamento coerente con ogni catena di segni (purchè non siano tutti '=').
• Relazione d'ordine ${\leq }_{n}$ tra le classi di equivalenza degli assegnamenti nella LG.
• Rappresentazione di ${\mathcal {F}}_{n}$ (= insieme delle classi di equivalenza degli assegnamenti su n variabili nella LG) tramite diagrammi di Hasse.

Lezione di venerdì 19/10/2007

• Definizioni di: relazione (riflessiva, simmetrica, transitiva, antisimmetrica, di equivalenza, d'ordine), insieme parzialmente ordinato (=poset), insieme totalmente ordinato (=catena), elementi inconfrontabili, sottoposet, downset, foresta, elemento minimale, minimo, albero.
• Lemma: per ogni n, la struttura $\left({\mathcal {F}}_{n},{\leq }_{n}\right)$ è una foresta (dimostrazione lasciata per esercizio).

Lezione di martedì 23/10/2007

• Definizioni di downset di un insieme e sottoforesta.
• Equivalenza semantica e sintattica delle formule (sia nella LC sia nella LG), definizione di 1-set di una formula $\alpha$ nella LC (insieme associato $I_{\alpha }$) e nella LG (foresta associata $F_{\alpha }$), di classe di equivalenza di una formula.
• Lemma: la foresta associata ad una formula n-aria è una sottoforesta di ${\mathcal {F}}_{n}$.
• Lemma di sconnessione delle foreste: due formule sono equivalenti sse le foreste ad esse associate coincidono.
• Definizione di foglie e radici di una foresta.
• Fatto: $\left[\mu \right]\in {\mathcal {F}}_{n}$ è una foglia sse $\mu \left(x_{i}\right)=1$ per ogni i = 1,...,n .

Lezione di venerdì 26/10/2007

Forme normali disgiuntive (DNF)

• Definizioni (nella logica classica) di: letterale, clausola congiuntiva, mintermine, formula in DNF.
• Definizioni (nella logica di Gödel) di: formula equivalente a un mintermine, clausola di Gödel.
• Teorema:

${\begin{matrix}F_{{\alpha \vee \beta }}&=&F_{\alpha }\cup F_{\beta }\\F_{{\alpha \wedge \beta }}&=&F_{\alpha }\cap F_{\beta }\\F_{{\bot }}&=&\emptyset \\F_{{\top }}&=&{\mathcal  {F}}_{n}\\\end{matrix}}$

• Esercizio per casa: trovare $F_{{\alpha \rightarrow \beta }}$ e $F_{{\neg \alpha }}$.
• Osservazione: una foresta può sempre essere scritta come unione dei suoi rami massimali.
• Osservazione 2: una foresta $F$ può essere sintetizzata dalla formula $\alpha$ (cioè $F_{\alpha }=F$) se $\alpha$ è ottenibile come disgiunzione di formule che sintetizzano i rami massimali di $F$.
• Definizione del connettivo $\triangleleft$ (che si legge "minore di"):

$\beta \triangleleft \alpha \equiv \left(\alpha \rightarrow \beta \right)\rightarrow \alpha$.

• Definizione alternativa:

$\mu \left(\beta \triangleleft \alpha \right)=\left\{{\begin{matrix}1&{\mbox{ se }}\mu \left(\beta \right)<\mu \left(\alpha \right){\mbox{ oppure }}\mu \left(\beta \right)=\mu \left(\alpha \right)=1\\\mu \left(\alpha \right)&{\mbox{altrimenti}}\\\end{matrix}}\right.$

• Definizione di formula $\alpha _{\mu }$ associata a $\left[\mu \right]$.
• Lemma: il downset di $\left[\mu \right]$ coincide con la foresta associata ad $\alpha _{\mu }$.

Lezione di martedì 30/10/2007

• Esempi di corrispondenza tra clausole di Gödel e rami di ${\mathcal {F}}_{n}$.
• Lemma: una clausola risulta vera esattamente per gli assegnamenti nel downset del nodo corrispondente alla scelta di segni della clausola.
• Lemma: data una foresta F qualsiasi, esiste sempre un n nei naturali tale che F si immerge in ${\mathcal {F}}_{n}$ (cioè F è isomorfa a una foresta contenuta in ${\mathcal {F}}_{n}$).

Sistemi Fuzzy (argomento facoltativo)

• Introduzione ai sistemi fuzzy (pagina di Wikipedia).
• Definizione di fuzzy set.
• Formalizzazione delle regole fuzzy e assiomi extralogici.
• Esempi e considerazioni sugli insiemi fuzzy in relazione alle logiche polivalenti.