Logica e reti logiche

Docente: Francesco Pasquale

Comunicazioni

Test Intermedi

13-06-2018 12:42

Primo Test (23 aprile 2018): Compito A, Compito B. Risultati.
Secondo Test (11 giugno 2018): Compito A, Compito B. Risultati.
Ammessi all'orale.


Lezioni

2611-06-2018

Secondo test intermedio: Compito A, Compito B. Risultati.

2507-06-2018

Esercitazione.

2404-06-2018

Rappresentazione dei numeri frazionari: notazione in virgola fissa e notazione in virgola mobile, lo standard IEEE 754. Principali blocchi funzionali sequenziali: contatori e registri a scorrimento. ([2]: Cap. 5)

2331-05-2018

Circuiti aritmetici: richiami sul circuito Sommatore/Sottratore (ripple-carry adder). Migliorare l'efficienza riducendo il ritardo di propagazione: un circuito sommatore con "anticipazione di riporto" (carry-lookahead adder). Traslatori, comparatori e cenni alle ALU (Arithmetic/Logic Unit) e ai circuiti per la moltiplicazione. ([2]: Cap. 5)

2228-05-2018

Cenni ai linguaggi per la descrizione dell'hardware (HDLs). Simulazione e sintesi. Esempi. ([2]: Cap. 4). Cenni ai sistemi di controllo versione e Git. (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).

2124-05-2018

Esercitazione.

2021-05-2018

Esempi di macchine a stati finiti. Codifica degli stati: binaria e one-hot Fattorizzazione di macchine a stati finiti. Modello matematico. ([2]: Cap. 3)

1917-05-2018

Macchine a stati finiti: Equazioni di stato e di ingresso/uscita, Tabelle di stato, Diagrammi di stato. Macchine alla Moore e macchine alla Mealy. ([2]: Cap. 3)

1814-05-2018

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

1710-05-2018

Esercitazione.

1607-05-2018

Progettazione di circuiti combinatori: affrontare un problema complesso scomponendolo in blocchi funzionali più semplici. I blocchi funzionali principali dei circuiti combinatori: Decodificatori e Multiplexer. Introduzione ai circuiti per operazioni aritmetiche: Half Adder, Full Adder e un circuito Adder/Subtractor. Cenni al problema della temporizzazione. ([2]: Cap. 2)

1503-05-2018

Implementazione di formule della logica proposizionale tramite circuiti. Forme canoniche: somma di prodotti (alias forma normale disgiuntiva) e prodotto di somme (alias forma normale congiuntiva). Il codice Gray e le mappe di Karnaugh. ([2]: Cap. 2)

1426-04-2018

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 (effetto in c: int_behavior.c). Porte logiche e circuiti. ([2]: Cap. 1)

1323-04-2018

Primo test intermedio: Compito A, Compito B. Risultati.

1219-04-2018

Esercitazione.

1116-04-2018

Logica del Primo Ordine (III). Correttezza del metodo dei tableaux e cenni alla sua completezza. Un sistema di assiomi per la logica del primo ordine. Cenni alle teorie del primo ordine e all'incompletezza sintattica. ([1]: Cap. 9)
Cenni ad altre logiche: Logica della conoscenza e il mistero degli isolani dagli occhi blu. (Chi volesse approfondire può vedere, per esempio, qui)

1012-04-2018

Logica del Primo Ordine (II). Formule valide e il metodo dei tableaux per la logica del primo ordine. ([1]: Cap. 9)

909-04-2018

Logica del Primo Ordine (I). Sintassi e semantica. Quantificatori, variabili, parametri e predicati; formule nella logica del primo ordine. Variabili libere e vincolate. Interpretazioni. Formule valide vs tautologie. ([1]: Cap. 8)

805-04-2018

Esercitazione.

729-03-2018

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 "Teorema", "Dimostrazione" e "Derivazione" in un sistema assiomatico. Un esempio di sistema assiomatico per la logica proposizionale. Il teorema di deduzione. Correttezza del sistema e cenni alla sua completezza. ([1]: Prima parte del Cap. 7)

626-03-2018

Logica Proposizionale (III). Correttezza e completezza del metodo dei tableaux. Gli insiemi di Hintikka e il Lemma di Hintikka. ([1]: Cap. 6). Cenni a un altro sistema di refutazione: Formule in forma normale congiuntiva e resolution.

522-03-2018

Logica Proposizionale (II). Il metodo dei tableaux per dimostrare una formula. ([1]: Cap. 6) Implicazione logica e il significato di condizione necessaria e condizione sufficiente.

419-03-2018

Esercitazione.

315-03-2018

Logica Proposizionale (I). Sintassi e semantica. Variabili, costanti e connettivi: negazione, congiunzione, disgiunzione, implicazione, equivalenza. Tabelle di verità. Formule proposizionali e interpretazioni. 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)

212-03-2018

I paradossi nella teoria degli insiemi elementare: "l'insieme di tutti gli insiemi", il paradosso di Russell, Hypergame. Richiami di matematica: Il principio di induzione e le dimostrazioni per induzione; i grafi; cammini, cicli, connessione, esempi: l'ipercubo. ([1]: Cap 3 e 4)

108-03-2018

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


Materiale didattico

Si veda la pagina del corso sul sito del docente

http://www.mat.uniroma2.it/~pasquale/dida/aa1718/lrl/index.html

Informazioni

Anno accademico2017-2018
Crediti6
SettoreINF/01
Anno1
Semestre2
PropedeuticitàNessuna

Programma

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)

Segnali analogici e informazione digitale. Sistemi numerici, operazioni aritmetiche. Le codifiche ASCII e Unicode. I codici Gray. Porte logiche e circuiti logici, linguaggi per la descrizione dell'hardware (HDLs). Funzioni Booleane e forme canoniche. Mappe di Karnaugh.

Circuiti combinatori: codificatori e decodificatori, multiplexer, sommatori e sottrattori.

Circuiti sequenziali: Latch e Flip-Flop. Sincronizzazione.

Automi a stati finiti.


Testi di riferimento

      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


Ricevimento studenti

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

Al di fuori del periodo delle lezioni:
Su appuntamento.


Modalità di esame

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.