A + /A /B Ricapitolando A + /A /B Ricapitolando

(1)

Tabella verità Rete combinatoria

Ricapitolando

Porte logiche

Architettura degli elaboratori - 30 -

Espressione booleana

A + /A /B

A B X

0 0 1

0 1 0

1 0 1

1 1 1

1:1

∞:1

Rete combinatoria Rete combinatoria Rete combinatoriaRete combinatoriaRete combinatoria

Ricapitolando

(ciascuna freccia rappresenta un procedimento, che vedremo)

Porte logiche

Espressione booleana

A + /A /B

Tabella verità A B X

0 0 1

0 1 0

1 0 1

1 1 1

Analisi

(2)

Regole di trasformazione delle espressioni booleane

Porte logiche

Assorbimento A (A + B) = A A + A B = A De Morgan /(A B) = /A + /B /(A + B) = /A /B Distributiva A + B C = (A + B) (A + C) A (B + C) = A B + A C

Commutativa A B = B A A + B = B + A

Associativa (A B) C = A (B C) (A + B) + C = A + (B + C)

Inverso A /A = 0 A + /A = 1

Elemento nullo 0 A = 0 1 + A = 1

Idempotenza A A = A A + A = A

Elem. identità 1 A = A 0 + A = A

Regola Prodotto logico (AND) Somma logica (OR)

Tertium non datur / / A = A

Proprietà degli operatori booleani: note

Le le regole di trasformazione (o «di riscrittura»)

ci consentono di passare da una espressione ad un’altra, equivalente.

l’equivalenza è garantita dalla teoria!

Obiettivo delle riscritture: ottimizzare l’espressione di partenza Cioè: rendere il circuito associato piú economico, o piú veloce, etc Gli A, B nelle regole rappresentano sotto-espressioni qualsiasi

(non necessariamente variabili: es: (A(B+C)+ A(B+C)) = A(B+C) Tutte le regole sono in doppia copia: una per l’AND una per l’OR

una è la regola DUALEdell’altra

cioè una è ottenuta dall’altra scambiando fra di loro:

AND <==> OR e 0 <==> 1

Ciascuna regola si può usare in un verso, o nel verso opposto

XXX = YYY posso passare da XXX a YYY… oppure viceversa Alcune regole somigliano a quelle dell’algebra numerica tradizionale

(3)

De Morgan explained

Nel primale:

«affermare che sia vero A e-anche B signfica

negare che uno qualsiasi dei due sia falso»

Porte logiche

/(A B) = /A + /B cioè A B =/ ( /A + /B )

Nel duale:

«affermare che sia vero A oppure B (o entrambi) signfica

negare che siano entrambi falsi»

/(A + B) = /A /B cioè A + B = / ( /A /B )

De Morgan: una conseguenza

DeMorgan ci mostra che possiamo, se lo vogliamo, fare a meno di porte OR .

potremmo sempre sostituirle con porte AND (più alcuni NOT) e viceversa!

ecco le leggi di De Morgan…

…a circuito:

Porte logiche

(4)

Un altro assorbimento

Porte logiche

A + /A B = A + B A (/A + B) = AB

Esempio di applicazione delle regole di riscrittura

Si consideri la funzione booleana di 3 variabili G(a,b,c) espressa dalla seguente equazione:

G(a,b,c) = (/a /b /c) + (/a /b c) + (/a /b c) + (/a b c) +(a /b c) + (a b c) Semplificare l’espressione. Indicare le operazioni svolte

Espressione

(a¯ b¯ c¯ ) + (a¯ b¯ c) + (a¯ b¯ c) + (a¯ b c) + (a b¯ c) + (a b c)

a¯ b¯ (c¯ +c) + a¯ c (b¯ +b) + a c (b¯ +b) a¯ b¯ + a¯ c + a c

a

¯ b¯ + c (a¯ + a) a¯ b¯ + c

Regola utilizzata

X + X = X XY + XZ = X (Y + Z)

X + !X = 1 e X1=X XY + XZ = X (Y + Z)

X + !X = 1 (a¯ b¯ c¯ ) + (a¯ b¯ c) + (a¯ b c) + (a b¯ c) + (a b c)

(5)

Teorema del consenso

Porte logiche

Dimostrazione

Altri operatori booleani binari (e porte corrispondenti)

Noi useremo circuiti che usano porte AND, OR e NOT comodità, + uso diretto della logica classica Altre porte popolari:

Porte logiche

A B X

0 0 0

0 1 1

1 0 1

1 1 0

XOR («or esclusivo»)

uno o l’altro, ma

NON entrambi

Significati intuitivi di A XOR B:

A oppure B, ma non entrambi (in latino: Aaut B)

vero se A e B diversi falso se A e B uguali vale /A se B = 1 vale A se B = 0 (e viceversa)

il contrario di A, se B vale;

A immutato, altrimenti (e viceversa)

(6)

Altri operatori booleani binari (e porte corrispondenti)

Noi useremo circuiti che usano porte AND, OR e NOT comodità, + uso diretto della logica classica Altre porte popolari:

Porte logiche

A B X

0 0 1

0 1 0

1 0 0

1 1 1

NXOR

(«fa il contrario di XOR»)

Significati intuitivi di A NXOR B:

uno XOR seguito da un NOT A NXOR B = \( A XOR B) cioè…

entrambi veri oppure entrambi falsi cioè…

AB + \A\B cioè…

operatore di uguaglianza fra A e B:

vero se A e B sono uguali.

falso se sono diversi

Altri operatori booleani binari (e porte corrispondenti)

Noi useremo circuiti che usano porte AND, OR e NOT comodità, + uso diretto della logica classica Altre porte popolari:

A B X

0 0 1

0 1 1

1 0 1

1 1 0

NAND

(«fa il contrario di AND»)

A B X

0 0 1

0 1 0

1 0 0

1 1 0

NOR

(«fa il contrario di OR»)

(7)

Porte NAND e porte NOR

Convenienti:

Sono le porte più economiche da realizzare (solo 2 transistor) Hanno la latenza minore (vel maggiore) delle porte a 2 ingressi Molto popolari!

Nota:

A NOR A = \A B NAND B = \B

(verificare nella tabella!)

quindi: con un NAND (o un NOR) posso fare un NOT

Un NAND seguito da un NOT = AND Un NOR seguito da un NOT = OR

Porte logiche

A /A

/A A

equivalenti

Porte NAND e porte NOR

Se ho a disposizione solo porte NAND…

(e quindi posso fare anche il NOT)

…allora posso fare anche l’AND , negando il risutato del NAND

A AND B = NOT (A NAND B)

Porte logiche

A AB B

NOT

AND (con due NAND!)

(8)

Porte NAND e porte NOR

Se ho a disposizione solo porte NAND…

(e quindi posso fare anche il NOT e anche l’AND )

…allora posso fare anche l’OR , grazie a DeMorgan.

A AND B = NOT (A NAND B)

Porte logiche

A+B A

B

OR (con tre NAND!)

Operatori binari (porte logiche) universali

Vedremo che usando solo porte { AND, OR, NOT }

possiamo implementare a circuito qualsiasi funzione booleana data (con qualsiasi numero di parametri) – v. forme canoniche, dopo Ma, come abbiamo visto, grazie a De-Morgan:

con porte AND e NOT possiamo «fare» porte OR

(e viceversa, con OR e NOT possiamo «fare» porte AND) Quindi, potremmo limitarci a porte AND e NOT e fare tutto con loro

(oppure OR e NOT )

Usando solo NAND possiamo fare NOT e AND quindi possiamo fare tutto

Usando solo NOR possiamo fare NOT e OR quindi possiamo fare tutto

per questo, NAND e NOR sono detti operatori universali (sono gli unici due)

(9)

Avvertenza

Per progettare un buon circuito (= ottimizzato) che usa solo porte NAND (o solo NOR) non ci si può limitare ad:

costruire un circuito ottimizzato con le porte NOT, AND e OR (come vedremo nella prossima lezione)

sostiture queste con i circuiti visti che usano solo NAND.

Funzionerebbe, ma il risultato sarebbe molto lontano dall’ottimo!

Porte logiche