Algebra booleana e circuiti logici

Algebra & Circuiti Elettronici

• I computer operano con segnali elettrici con valori di potenziale discreti
  • sono considerati significativi soltanto due potenziali (high/low)
  • i potenziali intermedi, che si verificano durante le transizioni di potenziale, non vengono considerati
• L’aritmetica binaria è stata adottata proprio perché i bit sono rappresentabili naturalmente
  • tramite elementi elettronici in cui siamo in grado di distinguere i 2 stati del potenziale elettrico (high/low)
• Il funzionamento dei circuiti elettronici può essere modellato tramite l’Algebra di Boole
  • solo 2 valori:
    • valore logico True (1 o asserted) ⇒ livello di potenziale alto
    • valore logico Falso (0 o deasserted) ⇒ livello di potenziale basso
  • operazioni logiche Booleane per combinare i valori

Blocco logico

• Blocco logico
  • circuito elettronico con linee (fili) in input e output
  • possiamo associare variabili logiche con le varie linee in input/output
    • i valori che le variabili possono assumere sono quelli dell’Algebra di Bool
  • il circuito calcola una o più funzioni logiche, ciascuna esprimibile tramite la combinazione di operazioni dell’Algebra di Bool sulle variabili in input
• Circuito combinatorio
  • senza elementi di memoria - produce output che dipende funzionalmente solo dall’input
• Circuito sequenziale
  • con elementi di memoria - produce output che dipende non solo dall’input ma anche dallo stato della memoria
• All’inizio ci concentreremo sui circuiti combinatori

Algebra & Circuiti Elettronici

• I computer operano con segnali elettrici con valori di potenziale discreti
  • sono considerati significativi soltanto due potenziali (high/low)
  • i potenziali intermedi, che si verificano durante le transizioni di potenziale, non vengono considerati
• L'aritmetica binaria è stata adottata proprio perché i bit sono rappresentabili naturalmente
  • tramite elementi elettronici in cui siamo in grado di distinguere i 2 stati del potenziale elettrico (high/low)
• Il funzionamento dei circuiti elettronici può essere modellato tramite l'Algebra di Boole
  • solo 2 valori:
    • valore logico True (1 o asserted) ⟹ livello di potenziale alto
    • valore logico Falso (0 o deasserted) ⟹ livello di potenziale basso
  • operazioni logiche Booleane per combinare i valori

Blocco logico

• Blocco logico
  • circuito elettronico con linee (fili) in input e output
  • possiamo associare variabili logiche con le varie linee in input/output
    • i valori che le variabili possono assumere sono quelli dell'Algebra di Bool
  • il circuito calcola una o più funzioni logiche, ciascuna esprimibile tramite la combinazione di operazioni dell'Algebra di Bool sulle variabili in input
• Circuito combinatorio
  • senza elementi di memoria - produce output che dipende funzionalmente solo dall'input
• Circuito sequenziale
  • con elementi di memoria - produce output che dipende non solo dall'input ma anche dallo stato della memoria
• All'inizio ci concentreremo sui circuiti combinatori

Algebra Booleana

• Funzione logica completamente specificato tramite Equazione logica
• bit in input e output rappresentati tramite variabili logiche (con valori 0 o 1)
• input combinati tramite le operazioni di somma (OR), prodotto (AND) e inversione (NOT) logica dell’algebra di Boole
  • OR (A+B): risultato uguale ad 1 (true) se almeno un input è 1 (true)
  • AND (A·B): risultato uguale ad 1 (true) solo se tutti gli input sono 1 (true)
  • NOT (¬A): risultato uguale all’inverso dell’input (0→1 oppure 1→0)

Tabelle di verità delle operazioni di NOT, AND, OR:

A X 0 1 1 0

X = ¬A

A B X 0 0 0 0 1 0 1 0 0 1 1 1

X = A · B

A B X 0 0 0 0 1 1 1 0 1 1 1 1

X = A + B

Proprietà dell’algebra di Boole

Proprietà

• Identità: A+0=A
• Nullo: A+1=1
• Idempotente: A+A=A
• Inverso: A+(¬A)=1
• Commutativa: A+B=B+A
• Associativa: A+(B+C)=(A+B)+C
• Distributiva: A·(B+C)=(A·B)+(A·C)
• DeMorgan: ¬(A+B)=(¬A)·(¬B)

Ad esempio, gli output D ed E della precedente Tabella di verità possono essere espressi come Equazioni logiche, semplificate applicando le proprietà di sopra

A B C D E 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0

D = ¬(¬A + B·C) + (¬A + ¬B·C) + (A + B · ¬C) =

E = (¬A + ¬B·C) + (A + ¬B·C)

Dalle equazioni logiche ai circuiti combinatori

• Porte logiche
• AND: A · B
• OR: A + B
• NOT: ¬A

Esempio di equazione e corrispondente circuito:

¬((AB) + (¬BC))

Operazioni NAND o NOR

NAND: porta e tabella di verità

A B Out 0 0 1 0 1 1 1 0 1 1 1 0

NAND (inverso dell’operazione AND) : ¬(A · B) = A NAND B

NOR: porta e tabella di verità

A B Out 0 0 1 0 1 0 1 0 0 1 1 0

NOR (inverso operazione OR) ¬(A + B) = A NOR B

• Si può dimostrare che le operazioni NAND o NOR (e le corrispondenti porte) sono sufficienti per implementare qualsiasi funzione logica
• NAND
  • ¬A = A + 0 = ¬(A · 1) = A NAND 1
  • A+B = ¬(¬A · ¬B) = ¬((A · B) · ¬ ¬(A · B)) = ((A NAND B), (A NAND B) )
  • A · B = (A · B) · 0 = ¬((A · B)+0) = ¬((A · B)+0) = ¬((A NAND B) , (A NAND B) )
• NOR
  • ¬A = A + 1 = ¬(A + 1) = A NOR 1
  • A+B = (A+B) · ¬(A + B) · 1) = ((A NOR B) (A NOR B))
  • A · B = ¬ (¬A + ¬ B) = ¬((A + B) = ( A NOR B) (A NOR B))