Logica e Reti Logiche

CdL Informatica - Univ. Roma Tor Vergata
AA 2020/2021

Prof. Francesco Pasquale

Diario delle lezioni

• 8 marzo 2021: 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)
  Video. (N.B.: A causa di un problema tecnico col microfono esterno, la qualità dell'audio di questa lezione è pessima)
• 11 marzo 2021: I principi di non contraddizione e del terzo escluso e i paradossi. Richiami di matematica: il teorema di Cantor e le dimostrazioni per assurdo; il principio di induzione matematica e le dimostrazioni per induzione. ([1]: Cap 3 e 4)
  Video.
• 15 marzo 2021: 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). Cenni alla notazione polacca. ([1]: Cap. 5)
  Video.
• 18 marzo 2021: Esercitazione.
• 22 marzo 2021: Logica Proposizionale (II). Il metodo dei tableaux per dimostrare una formula. ([1]: Cap. 6).
  Video.
• 25 marzo 2021: Logica Proposizionale (III). Correttezza e completezza del metodo dei tableaux. ([1]: Cap. 6)
  Video.
• 29 marzo 2021: 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. ([1]: Prima parte del Cap. 7 - Per approfondire si veda, per esempio, il Cap 1.4 in [3])
  Video.
• 31 marzo 2021: Esercitazione.
• 8 aprile 2021: 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)
  Video.
• 12 aprile 2021: Logica del Primo Ordine (II). Il metodo dei tableaux per la logica del primo ordine. ([1]: Cap. 9)
  Video.
• 15 aprile 2021: 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). Cenni alle teorie del primo ordine e ai concetti di consistenza e completezza sintattica. ([1]: Cap. 8-10)
  Video.
• 19 aprile 2021: Esercitazione. Video.
• 22 aprile 2021: Primo test intermedio. Compito.
• 26 aprile 2021: 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. ([2]: Cap. 1)
  Video.
• 29 aprile 2021: Dalla logica ai circuiti. Porte logiche elementari. Forme normali e circuiti: Somme di prodotti (alias, disgiuntiva) e prodotto di somme (alias, congiuntiva). Circuiti per le operazioni aritmetiche Half Adder, Full Adder e un circuito Sommatore/Sottrattore. ([2]: Cap. 1-2)
  Video.
• 3 maggio 2021: Minimizzazione di formule in forma normale: Il codice Gray e le mappe di Karnaugh. ([2]: Cap. 2)
  Video.
• 6 maggio 2021: Esercitazione.
• 10 maggio 2021: I blocchi funzionali principali dei circuiti combinatori: Encoder, Decoder e Multiplexer. ([2]: Cap. 2)
  Video.
• 13 maggio 2021: Introduzione ai circuiti sequenziali: Latch, Flip-Flop e registri. ([2]: Cap. 3)
  Video.
• 17 maggio 2021: Circuiti sequenziali sincroni. Macchine a stati finiti: equazioni, tabelle e diagrammi di stato. Macchine alla Moore e macchine alla Mealy. ([2]: Cap. 3)
  Video.
• 20 maggio 2021: Esercitazione.
• 24 maggio 2021: Cenni ai linguaggi per la descrizione dell'hardware (HDLs). Simulazione e sintesi. ([2]: Cap. 4). Cenni ai sistemi di controllo versione e Git.
  Video.
  (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).
• 27 maggio 2021: Richiami sul circuito Sommatore/Sottrattore (ripple-carry adder). Migliorare l'efficienza del circuito: sommatore/sottrattore con "anticipazione di riporto" (carry-lookahead adder). Cenni alle ALU (Arithmetic/Logic Unit). ([2]: Cap. 5).
  Video.
• 31 maggio 2021: Rappresentazione dei numeri frazionari: codifica in virgola fissa e codifica in virgola mobile, lo standard IEEE 754. ([2]: Cap. 5). Cenni allo standard Unicode e alla codifica utf-8.
  Video.
• 3 giugno 2021: Esercitazione. Video.
• 7 giugno 2021: Secondo test intermedio. Compito.

Testi di riferimento

[1] A Beginner's Guide to Mathematical Logic
Raymond M. Smullyan
Dover Publications, 2014

[2] Sistemi digitali e architettura dei calcolatori
Sarah L. Harris, David Money Harris
Zanichelli, 2017