Esercizio 20quiz su algebra di Boole, forme canoniche, mappe di Karnaugh e blocchi combinatori (temi d'esame 2022-2026)

---

Teoria usata: Porte logiche, ritardi e porte universaliLe porte AND, OR, NOT realizzano le operazioni dell'algebra di Boole; NAND, NOR, XOR e XNOR ne derivano. Ogni funzione si descrive con la tabella di verità ($2^n$ righe). XOR a più ingressi = funzione di disparità (1 se gli 1 sono in numero dispari). Una porta reale ha ritardo di propagazione $t_G$ (diverso per 0→1 e 1→0): in un diagramma temporale l'uscita cambia $t_G$ dopo l'ingresso. NAND e NOR sono universali: bastano da sole a realizzare qualunque funzione. In VHDL: and, or, not, nand, nor, xor, xnor.Porte logiche, ritardi e porte universali →, Algebra di Boole - assiomi, teoremi e complemento di una funzioneL'algebra di Boole opera su variabili a due valori con AND, OR, NOT. Identità fondamentali (neutro, idempotenza, complemento, commutativa, associativa, distributiva in entrambe le forme), dualità (si scambiano AND/OR e 0/1), De Morgan $\overline{X+Y}=\overline X,\overline Y$, assorbimento $X+XY=X$, $X+\overline XY=X+Y$, adiacenza $XY+X\overline Y=X$, consenso $XY+\overline XZ+YZ=XY+\overline XZ$. Si dimostrano per induzione perfetta (tabella) o algebricamente. Il complemento di una funzione si ottiene con De Morgan o con duale + negazione dei letterali. Costo: numero di letterali o di ingressi delle porte.Algebra di Boole - assiomi, teoremi e complemento di una funzione →, Forme canoniche - mintermini, maxtermini, SOP e POSUn mintermine è un prodotto che contiene una e una sola volta tutte le variabili (dirette o negate) e vale 1 su una sola riga della tabella di verità; un maxtermine è la somma duale e vale 0 su una sola riga; con $n$ variabili ci sono $2^n$ mintermini e $2^n$ maxtermini, e $\overline{m_i}=M_i$. Forma canonica SOP = somma dei mintermini delle righe con $F=1$; POS = prodotto dei maxtermini delle righe con $F=0$. Le forme canoniche si ricavano sempre dalla tabella ma sono ridondanti: servono come punto di partenza per la minimizzazione. SOP e POS si realizzano con circuiti a due livelli.Forme canoniche - mintermini, maxtermini, SOP e POS →, Mappe di Karnaugh - implicanti e copertura minimaLa mappa di Karnaugh è la tabella di verità disposta in una griglia con righe e colonne in codice Gray, così che celle adiacenti (anche tra bordi opposti) differiscano in una sola variabile. Si raggruppano gli 1 in rettangoli di $2^k$ celle: ogni gruppo elimina $k$ variabili e dà un prodotto. Implicante primo = gruppo massimo; essenziale = unico a coprire un mintermine; la copertura minima contiene tutti gli essenziali più il minimo di altri primi (può non essere unica). Efficace fino a 4 variabili.Mappe di Karnaugh - implicanti e copertura minima →, Decoder, encoder e priority encoderUn decoder $n$-to-$m$ ($m\le2^n$) converte un ingresso binario a $n$ bit in un'uscita 1-hot (un solo 1, nella posizione indicata): le sue uscite sono i mintermini degli ingressi, realizzati con $m$ AND; per decoder grandi si usa l'approccio gerarchico (costo in ingressi: 3-to-8 = 27, 6-to-64 = 182) e un enable. Ogni funzione = decoder + OR dei suoi mintermini. L'encoder fa l'operazione inversa (1-hot $\to$ binario) ma sbaglia con più ingressi a 1 o tutti a 0: il priority encoder risolve con una priorità e un'uscita V (valid).Decoder, encoder e priority encoder →, Multiplexer e funzioni logiche realizzate con decoder e multiplexerIl multiplexer (MUX) $2^n$-to-1 ha $2^n$ ingressi dati, $n$ ingressi di selezione e un'uscita che copia l'ingresso selezionato: $Y=\sum_i m_i(S),I_i$. Si realizza con decoder + AND di enable + OR (costo 22 per il 4-to-1) o direttamente (costo 18). Un MUX $2^n$-to-1 realizza qualunque funzione di $n$ variabili (ingressi dati = colonna della tabella di verità); con un MUX $2^{n-1}$-to-1 si usano le $n-1$ variabili come selezione e gli ingressi dati valgono $0$, $1$, $X$ o $\overline X$ (l'ultima variabile). I MUX a vettori selezionano gruppi di bit.Multiplexer e funzioni logiche realizzate con decoder e multiplexer →.

Porte e algebra

Mintermini, maxtermini, forme SOP e POS

Mappe di Karnaugh (domande d'esercitazione)

$F(X,Y,Z,W)=\sum m(0,2,4,6,8,12,14,15)$. Implicanti primi: $\overline Z\,\overline W$ ($0,4,8,12$), $\overline X\,\overline W$ ($0,2,4,6$), $Y\overline W$ ($4,6,12,14$), $XYZ$ ($14,15$); essenziali: $\overline Z\,\overline W$, $\overline X\,\overline W$, $XYZ$. Quindi: non esiste nessun IPE o IP con un solo letterale; $XYZW$ (la cella $15$) è un implicante ma non è primo (è contenuto in $XYZ$) e non è essenziale. Risposta: "$XYZW$ è un implicante".

Decoder, comparatore, sommatore, multiplexer (esercitazioni)

Errori comuni

• Scrivere $\overline{x+y+z}=\overline x\,\overline y+\overline z$ (De Morgan incompleto).
• Calcolare lo XOR di tre ingressi come "esattamente un 1": è "numero dispari di 1".
• Credere che un mintermine sia una somma.
• Chiamare "implicante primo" un implicante che è contenuto in uno più grande.