Logica e Algebra

1.    RELAZIONI ED APPLICAZIONI

1.1 Relazioni, con particolare riguardo alle relazioni binarie su un insieme. Prodotto di relazioni. Proprietà delle relazioni binarie: serialità, riflessività, simmetria, transitività, antisimmetria.  Chiusure di una relazione rispetto ad un insieme dato di proprietà.

1.2 Relazioni di equivalenza ed applicazioni. Concetti di insieme quoziente, di kernel di una applicazione, teoremi di fattorizzazione di una applicazione. Cardinalità di un insieme e teorema di Cantor.

1.3 Relazioni d’ordine, i reticoli come insiemi ordinati.

1.4 Operazioni interne ed esterne, proprietà delle operazioni. Unità ed inverso di un elemento rispetto ad una operazione binaria.

2.    LOGICA PROPOSIZIONALE

2.1 Il linguaggio della logica delle proposizioni, formule sintatticamente corrette. Valutazione di una formula, tautologie e contraddizioni. Deduzione ed equivalenza semantica. Forme normali disgiuntive e congiuntive.

2.2 Sistemi formali. Teoria L, teoremi di deduzione, correttezza e completezza, decidibilità. Risoluzione e raffinamenti.

3.    LOGICA DEL I ORDINE

3.1 Il linguaggio del calcolo predicativo del I ordine, termini e formule sintatticamente corrette. Variabili libere e vincolate. Formule chiuse. Valutazione di una formula: il concetto di interpretazione. Formule soddisfacibili, vere, false in un’interpretazione. Formule logicamente valide. Forma normale prenessa, forma di Skolem.

3.2 Sistemi formali: cenni sulla teoria K e risoluzione.

3.3 Teorie del primo ordine e teorie del primo ordine con identità.

3.4 Modelli di una teoria.

3.5 Teoremi di deduzione, di correttezza e completezza. Questioni di decidibilità.

4.    STRUTTURE ALGEBRICHE

4.1 Le principali strutture algebriche: semigruppi, monoidi, gruppi, anelli, corpi, campi (definizioni ed esempi).

4.2 Sottostrutture, criteri relativi.

4.3 Relazioni di congruenza, strutture quozienti. La relazione di congruenza modulo n e cenni di aritmetica modulare

4.4 Strutture simili, omomorfismi ed isomorfismi fra strutture simili, il kernel di un omomorfismo ed il teorema di fattorizzazione degli omomorfismi.