Matematica Discreta e Logica Matematica

Programma del corso

Elementi di logica. Linguaggi formali, alfabeto, sintassi, semantica. Il linguaggio del calcolo proposizionale. Connettivi, tavole di verità. Interpretazioni, soddisfacibilità. Equivalenza semantica. Completezza funzionale. Forme normali: forma normale congiuntiva e forma normale disgiuntiva. Costruzione di una formula in forma normale congiuntiva oppure disgiuntiva a partire dalla tavola di verità. Insiemi di connettivi funzionalmente completi.

Insiemi. Operazioni sugli insiemi: unione, intersezione, differenza, differenza simmetrica, prodotto cartesiano. Insieme delle parti di un insieme. Partizioni di un insieme.

Corrispondenze e applicazioni. Immagini e controimmagini. Applicazioni iniettive, suriettive, biettive. Applicazioni composte. Inversa di una applicazione biettiva.

Relazioni di equivalenza. Classi di equivalenza. Insieme quoziente. Teorema fondamentale.

Elementi di aritmetica. Numeri naturali e numeri interi. Il principio di induzione. Divisibilità. La divisione euclidea. Rappresentazione dei numeri naturali in base fissata. Numeri primi. Teorema fondamentale dell'aritmetica (senza dimostrazione). Teorema di Euclide sull'esistenza di infiniti numeri primi. Il massimo comun divisore e il minimo comune multiplo. L'algoritmo euclideo delle divisioni successive. Il teorema di Bézout (senza dimostrazione). Congruenze tra interi. Equazioni congruenziali lineari. Il teorema cinese del resto.

Matrici. Operazioni sulle matrici: somma, prodotto per uno scalare, prodotto righe per colonne, potenze. Matrice trasposta. Matrici a scala e matrici equivalenti. Matrici triangolari. Matrici invertibili. Determinante di una matrice quadrata e sue proprietà notevoli (senza dimostrazione). Teorema di Binet (senza dimostrazione). Calcolo della matrice inversa di una matrice invertibile. Rango di una matrice.

Strutture algebriche. Operazioni interne in un insieme. Tavola di moltiplicazione. Sottoinsiemi stabili e operazione indotta. Operazioni associative. Operazioni commutative. Elemento neutro. Elementi invertibili. Omomorfismi. Generalità su semigruppi, monoidi, gruppi. Il gruppo degli elementi invertibili di un monoide. Aritmetica modulo m. Generalità su anelli, domini di integrità, campi.

Spazi vettoriali. Definizioni ed esempi. Sottospazi e generatori. Dipendenza lineare, basi e dimensione. Applicazioni lineari. Spazi vettoriali isomorfi.

Sistemi di equazioni lineari. Generalità e metodi di risoluzione di Cramer e di Gauss-Jordan. Teorema di Rouché-Capelli.

Diagonalizzazione di una matrice quadrata. Autovalori e autovettori di una matrice quadrata. Autospazi. Matrici simili. Matrici diagonalizzabili.

Elementi di calcolo combinatorio. Il principio di addizione. Il principio di inclusione-esclusione. Il principio di moltiplicazione. Fattoriale di un numero naturale. Coefficienti binomiali. Disposizioni. Disposizioni con ripetizioni. Permutazioni. Permutazioni con ripetizioni. Combinazioni.

Relazioni d'ordine. Elementi minimali e massimali. Minimo e massimo. Minoranti e maggioranti. Estremo inferiore ed estremo superiore. Diagrammi di Hasse. Insiemi totalmente ordinati. Insiemi bene ordinati. Sottoinsiemi di un insieme ordinato e ordine indotto. Reticoli. Il reticolo delle parti di un insieme. Il reticolo degli interi. Sottoreticoli. Reticoli distributivi. Reticoli complementati. Reticoli booleani.

Elementi di geometria analitica nel piano e nello spazio. Vettori applicati e operazioni. Riferimenti affini. Equazioni parametriche e cartesiane della retta nel piano e nello spazio. Equazioni parametriche e cartesiane del piano nello spazio. Condizioni di parallelismo, di incidenza e di perpendicolarità.

Testi consigliati: