Logica e reti logiche

Esami sessione estiva - Modalità on-line

In ottemperanza al D.R. 888/2020 del 11/05/2020 gli esami della sessione estiva si svolgeranno "con modalità a distanza".

Io non uso Microsoft Office 365 per la gestione dei corsi e personalmente disapprovo l'utilizzo in ambito accademico di qualunque piattaforma basata su software proprietario.
Gli esami di Logica e Reti Logiche si svolgeranno qui:
https://tvalgoteam.site/lrl
(si tratta di un'istanza di Jitsi installata su un pc che si trova nella nostra Università).

Per sostenere l'esame è necessario prenotarsi tramite il sistema Delphi. Istruzioni dettagliate sulle modalità di svolgimento delle prove d'esame sono disponibili qui.

Test Intermedi

Primo Test (23 aprile 2020): Compito. Hash consegnati. Risultati.
Secondo Test (11 giugno 2020): Compito. Hash consegnati. Risultati.
Ammessi direttamente al colloquio orale.

Secondo test intermedio. Compito. Hash consegnati. Risultati.

Esercitazione. Lavagna.

Rappresentazione dei numeri frazionari: notazione in virgola fissa e notazione in virgola mobile, lo standard IEEE 754. ([2]: Cap. 5). Cenni allo standard Unicode e alla codifica utf-8.
Lavagna.

Circuiti aritmetici: un circuito Sommatore/Sottratore (ripple-carry adder). Riconoscere gli overflow. Migliorare l'efficienza del circuito: sommatore/sottrattore con "anticipazione di riporto" (carry-lookahead adder). Cenni alle ALU (Arithmetic/Logic Unit). ([2]: Cap. 5).
Lavagna.

Cenni ai linguaggi per la descrizione dell'hardware (HDLs). Simulazione e sintesi. ([2]: Cap. 4). Cenni ai sistemi di controllo versione e Git.
Esempi.
(I software utilizzati durante la lezione sono: Icarus Verilog per la compilazione del codice Verilog, Yosys per la sintesi dei circuiti, GTKWave per le simulazioni).

Esercitazione. Lavagna.

Macchine alla Moore e macchine alla Mealy. Codifica degli stati: binaria e one-hot. Modello matematico di automa a stati finiti. Linguaggi. ([2]: Cap. 3)
Lavagna.

Circuiti sequenziali sincroni. Macchine a stati finiti: equazioni, tabelle e diagrammi di stato. Esempi. ([2]: Cap. 3)
Lavagna.

Introduzione ai circuiti sequenziali: Latch, Flip-Flop e registri. ([2]: Cap. 3)
Lavagna.

Esercitazione. Lavagna.

Minimizzazione di formule in forma normale: Il codice Gray e le mappe di Karnaugh. I blocchi funzionali principali dei circuiti combinatori: Encoder, Decoder e Multiplexer. ([2]: Cap. 2)
Lavagna. Appunti ed esercizi: Prima parte, Seconda parte.

Dalla logica ai circuiti. Circuiti per le operazioni aritmetiche Half Adder, Full Adder e un circuito Addizionatore. Forme normali e circuiti: Somme di prodotti (alias, disgiuntiva) e prodotto di somme (alias, congiuntiva). ([2]: Cap. 1-2)
Lavagna. Appunti ed esercizi.

Introduzione alla seconda parte del corso: Reti Logiche. Rappresentazione delle informazioni: binaria, esadecimale, base64. Operazioni aritmetiche e conversioni. Rappresentazione dei numeri in complemento a due (esempio in c: es2compl.c). ([2]: Cap. 1)
Lavagna. Appunti ed esercizi.

Primo test intermedio. Compito. Hash consegnati. Risultati.

Esercitazione. Lavagna.

Logica del Primo Ordine (IV). Sistemi assiomatici per la logica del primo ordine. Teorie del primo ordine: assiomi propri e modelli. Cenni all'aritmetica di Peano e di Presburger. I concetti di consistenza, completezza sintattica e decidibilità di una teoria del primo ordine. ([1]: Cap. 8-10)
Cenni ad altre logiche: Logica della conoscenza e il mistero degli isolani dagli occhi blu. (Chi volesse approfondire può vedere, per esempio, qui).
Lavagna. Appunti ed esercizi.

Logica del Primo Ordine (III). Formule soddisfacibili e insiemi soddifacibili. Correttezza del metodo dei tableaux per la logica del primo ordine. Insiemi di Hintikka e cenni alla completezza del metodo ([1]: Cap. 9)
Lavagna. Appunti ed esercizi.

Logica del Primo Ordine (II). Il metodo dei tableaux per la logica del primo ordine. ([1]: Cap. 9)
Lavagna. Appunti ed esercizi.

Logica del Primo Ordine (I). Sintassi e semantica. Quantificatori, variabili, lettere predicative, formule. Variabili libere e vincolate, formule chiuse. Formule e interpretazioni nella logica del primo ordine. Formule valide vs tautologie. ([1]: Cap. 8)
Lavagna. Appunti ed esercizi.

Logica Proposizionale (IV). Sistemi assiomatici (Hilbert systems) per la logica proposizionale. Schemi di assiomi e regole di inferenza. La regola di inferenza Modus Ponens. Le definizioni di "Dimostrazione", "Teorema" e "Derivazione" in un sistema assiomatico. Il teorema di deduzione. ([1]: Prima parte del Cap. 7]).
Lavagna. Appunti ed esercizi.

Logica Proposizionale (III). Correttezza e completezza del metodo dei tableaux. ([1]: Cap. 6)
Appunti ed esercizi.

Logica Proposizionale (II). Il metodo dei tableaux per dimostrare una formula. ([1]: Cap. 6)
Appunti ed esercizi.

Logica Proposizionale (I). Sintassi e semantica. Variabili, costanti e connettivi. Formule ben formate. Tabelle di verità. Tautologie, contraddizioni, contingenze. Interdipendenza dei connettivi: definire un connettivo in termini di altri connettivi. I connettivi joint denial (NOR) e alternative denial (NAND). ([1]: Cap. 5)
Appunti ed esercizi. Soluzione dell'Esercizio 5.

Richiami di matematica: Il principio di induzione e le dimostrazioni per induzione. ([1]: Cap. 4)
Appunti ed esercizi. Video.

Introduzione al corso. Richiami di matematica: teoria elementare degli insiemi; operatori Booleani ed equazioni Booleane; il metodo degli "indici" per verificare le equazioni Booleane; insiemi infiniti e cardinalità; insiemi numerabili; corrispondenze biunivoche; il teorema di Cantor. ([1]: Cap. 1 e 2)

Si veda la pagina del corso sul sito del docente
https://www.mat.uniroma2.it/~pasquale/dida/aa1920/lrl/index.html

Prima Parte (Logica)

Richiami di matematica: teoria degli insiemi elementare, algebra Booleana, relazioni e funzioni, principio di induzione.
Logica proposizionale: connettivi logici, tabelle di verità, variabili, formule, tableaux. Sistemi assiomatici. Correttezza e completezza.
Logica del primo ordine: quantificatori, relazioni, proprietà e predicati, formule della logica del primo ordine. Tableaux del primo ordine.
Cenni al fenomeno dell'incompletezza.


Seconda Parte (Reti Logiche)

Sistemi numerici e rappresentazione dei numeri: binaria, esadecimale, base64. Le operazioni aritmetiche. Rappresentazione delle informazioni: le codifiche ASCII e Unicode; lo standard IEEE754 per i numeri in virgola mobile.

Funzioni Booleane e forme canoniche. Mappe di Karnaugh. Porte logiche e circuiti logici.
Circuiti combinatori: codificatori e decodificatori, multiplexer, sommatori e sottrattori.
Circuiti sequenziali: Latch e Flip-Flop.

Cenni ai linguaggi per la descrizione dell'hardware (HDLs).

Automi a stati finiti.

      Raymond M. Smullyan
[1]  A Beginner's Guide to Mathematical Logic
      Dover Publications, 2014
 
      Sarah L. Harris and David Money Harris
[2]  Sistemi digitali e architettura dei calcolatori
      Zanichelli, 2017

Durante il periodo delle lezioni (Marzo - Giugno 2020):
Martedì 15:30 - 18:30 oppure su appuntamento.

Al di fuori del periodo delle lezioni:
Su appuntamento.

L'esame consiste in una prova scritta e in un colloquio orale.

Durante il corso si effettueranno due test intermedi. Gli studenti che ricevono una valutazione positiva a entrambi i test sono esonerati dalla prova scritta e ammessi a sostenere direttamente il colloquio orale.