SCV0314 - LOGICA

insegnamento

ID:

SCV0314

Durata (ore):

48

CFU:

SSD:

LOGICA MATEMATICA

Sede:

Como - Università degli Studi dell'Insubria

Anno:

2025

Periodo di attività

Secondo Semestre (23/02/2026 - 29/05/2026)

Obiettivi Formativi

(1) Conoscenza e capacità di comprensione Il corso si propone di fornire le conoscenze dei meccanismi di base dell'inferenza logica, attraverso lo studio delle fondamentali nozioni di logica proposizionale classica e del primo ordine. Tali conoscenze sono rivolte a formare e ad aumentare la capacità di astrazione delle informazioni attraverso la rappresentazione simbolica e quindi la capacità della comprensione di un linguaggio scientifico astratto e simbolico. (2) Conoscenza e capacità di comprensione applicate Verranno accennati alcuni approfondimenti su strumenti di carattere più applicativo come i SAT-solver e le logiche non classiche (temporali e fuzzy) per la verifica dei programmi. (3) Autonomia di giudizio e abilità comunicative I risultati di apprendimento attesi comprendono la capacità di saper individuare eventuali errori in una argomentazione matematica, e di avere una proprietà di linguaggio tale da poter enunciare un teorema e descrivere una sua dimostrazione. (4) Capacità di apprendere La conoscenza dei meccanismi logici del ragionamento matematico permette l’acquisizione di adeguate capacità per l'approfondimento delle proprie conoscenze e per lo sviluppo individuale di nuove competenze.

Prerequisiti

Per un proficuo apprendimento di questo insegnamento lo studente deve padroneggiare le nozioni matematiche e le tecniche dimostrative di base impartite nell’insegnamento fondamentale di Algebra e Geometria del primo anno, che dunque costituisce propedeuticità obbligatoria. In particolare le nozioni e le tecniche di base che costituiscono preliminari imprescindibili sono i seguenti. - Basi di matematica discreta: teoremi e metodi di dimostrazione: implicazione, contronominale, dimostrazioni per assurdo, principio di induzione. - Teoria degli insiemi: insiemi, appartenenza e inclusione, sottoinsiemi, insieme delle parti, cardinalità, operazioni tra insiemi (unione, intersezione e complemento), coppie e prodotto cartesiano, contare gli elementi degli insiemi finiti. - Relazioni: relazioni, proprietà (riflessività, simmetria, transitività), relazioni d'equivalenza, classi d'equivalenza, insieme quoziente, partizioni, teorema fondamentale delle relazioni d'equivalenza, relazioni d'ordine, massimo, minimo, estremo inferiore e estremo superiore. - Funzioni: dominio e codominio, immagine e preimmagine, funzioni iniettive, suriettive e biettive, inversa di una funzione biettiva, composizione di funzioni. - Elementi di calcolo combinatorio: disposizioni semplici e con ripetizione, fattoriale, coefficiente binomiale, disposizioni e combinazioni, contare le funzioni e le funzioni iniettive.

Metodi didattici

32h lezioni frontali + 24h esercitazioni. Il corso si articola in lezioni frontali e esercitazioni: nelle lezioni verranno presentate le nozioni e teoremi che verranno applicati, con una partecipazione attiva degli studenti, nella soluzione di esercizi durante le esercitazioni. Gli esercizi presentati costituiscono una fondamentale linea guida per la preparazione dell’esame.

Verifica Apprendimento

L’obiettivo della prova d’esame è l'accertamento dell’acquisizione delle conoscenze e delle abilità descritte nella sezione “Obiettivi del corso”, valutando il livello di conoscenza e la capacità di applicare le nozioni e le tecniche dimostrative viste a lezione. L’esame consiste in una prova scritta della durata di 90 minuti consistente in un numero di esercizi del tipo discusso durante le lezioni L'esame è composto da indicativamente 3/4 domande che concorrono in eguale misura al voto finale di 31/30esimi, per poter arrivare alla lode.

Contenuti

Introduzione alla Logica (Obiettivi formativi 1-4) • Cosa è la logica: cenni storici • Linguaggio e Metalinguaggio • Sintassi e Semantica • Soddisfacilbilità e entailment • Metodi di deduzione: dimostrazioni dirette. • Correttezza per dimostrazioni dirette. Mancanza di completezza. • Dimostrazioni indirette, correttezza e cenni di completezza Logica Proposizionale (Obiettivi formativi 1-4) • Il linguaggio della logica proposizionale. Connettivi proposizionali. Semantica della logica proposizionale. Tavole di verità. Formule soddisfacibili e tautologie. •Insiemi soddisfacibili, conseguenze logiche, teorema di deduzione. Equivalenza logica, algebra delle classi di equivalenza delle formule, algebre di Boole. Completezza funzionale e forme normali disgiuntive e congiuntive. Le equivalenze fondamentali, trasformazione di una formula in forma normale. •Teorema di compattezza e lemma di König. •Metodi di dimostrazione automatica: i Tableaux. Teorema di completezza e correttezza per i tableaux, Hintikka set. •Altri sistemi deduttivi: Sequenti. Clausole, risoluzione, procedura di Davis Putnam, completezza e correttezza della procedura di Davis-Putnam. Clausole di Krom e clausole di Horn Logica dei Predicati (Obiettivi formativi 1-4)) •Il linguaggio della logica dei predicati, termini e formule. Campo d'azione di un quantificatore, variabili libere e vincolate, sostituzioni. •Strutture, interpretazioni e valutazioni Formule soddisfacibili e valide. Modelli di una formula. Equivalenze logiche per la logica dei predicati. Forme normali prenesse, Forma di Skolem. Trasformazione di una formula in forma di Skolem e equisoddisfacibilità. •Tableaux per la logica dei predicati, teorema di correttezza e completezza per i tableaux