G.- F. Dalla Betta, G. Soncini. Appunti di Elettronica 2.
Cap. II. Funzioni Logiche
II.1. Funzioni logiche binarie
II.2. Operatori logici elementari AND, OR, NOT
II.3. Operatori logici universali NAND, NOR
II.4. Mappe di Karnaugh
II.5. Progetto logico
Esempi ed Esercizi
Appendice
1
2
II.1. Funzioni logiche binarie
Funzione logica binaria: F  F ( A, B, C ,....)
il valore F dipende da un insieme ordinato di variabili binarie A,B,C,..
dove A, B, C, … possono assumere i valori 0 od 1.
Ad n variabili binarie corrispondono 2n possibili combinazioni per F
Le cifre binarie 0 e 1 possono venire associate a operazioni logiche
1 vero 0  falso
(logica positiva)
La funzione logica F è rappresentabile tramite la Tabella della Verità:
ad ogni possibile combinazione dei valori 0 ed 1 delle variabili binarie
indipendenti di ingresso viene associato il valore binario dipendente
della funzione F di uscita.
In alternativa, la funzione logica F è rappresentabile mediante una
espressione contenente le variabili e le operazioni primitive di
somma logica, prodotto logico e complementazione.
Esempio 1: rappresentare la tabella della verità della
funzione logica F=F(A,B) che assume valore 1 (vero)
solo quando A=B
A 0 0 1 1
n=2 variabili binarie
Soluzione:
B 0 1 0 1 22=4 combinazioni
F 1 0 0 1
Esempio 2: rappresentare la tabella della verità della
funzione logica F=F(A,B,C) che assume valore 1 (vero)
solo quando A=B e BC
Soluzione:
n=3 variabili binarie
23=8 combinazioni
A
B
C
F
0
0
0
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
1
1
1
0
3
Funzioni incomplete o non completamente specificate
Il valore dell’uscita non risulta definito per alcune configurazioni di
ingresso. Ciò può accadere per due diversi motivi:
1) Il codice di ingresso alla rete non impiega tutte le configurazioni
disponibili.
2) Particolari valori di alcune variabili tolgono ogni significato ai
valori contemporanemente presenti in uscita.
Le funzioni incomplete possono essere rappresentate da Tabelle della
Verità ricorrendo all’impiego di un nuovo simbolo (-) per le
condizioni di indifferenza.
A
Esempio B
C
F
0
0
0
0
0
0
1
-
0
1
0
0
1
0
0
0
0
1
1
-
1
0
1
-
1
1
0
1
1
1
1
-
4
5
II.2. Operatori logici elementari
Funzioni logiche binarie
• esprimibili tramite Tabella della Verità
• sintetizzabili tramite operatori logici elementari, OR,
AND e NOT, traducibili in circuiti elettronici digitali (porte
logiche) immediatamente realizzabili in forma integrata.
Esistono quattro diverse funzioni di una variabile binaria
i
u1
u2
u3
u4
0
0
0
1
1
1
0
1
0
1
u1 = 0, u4 = 1
i
costanti
u2
Buffer
6
Operatore logico NOT (invertitore)
convenzionalmente rappresentato dal simbolo di figura
svolge la funzione logica evidenziata dalla tabella
A
NOT
A
X= complemento di X o X negato
Significato logico:
Se A è vero, A è falso
A
A
0
1
1
0
Tabella della Verità
(Truth Table)
7
Esistono sedici diverse funzioni di due variabili binarie
i1 i2 u5 u6 u7 u8 u9 u10 u11 u12 u13 u14 u15 u16 u17 u18 u19 u20
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
AND
OR NOR
XOR
SAME
NAND
8
Operatore logico OR (somma logica)
convenzionalmente rappresentato dal simbolo di figura
svolge la funzione logica evidenziata dalla tabella
A
B
OR
Significato logico:
A+B
A
B
A+B
0
0
1
1
0
1
0
1
0
1
1
1
Tabella della Verità
(Truth Table)
Se o A o B o entrambi sono veri, anche A+B è vero
9
Operatore logico AND (prodotto logico)
convenzionalmente rappresentato dal simbolo di figura
svolge la funzione logica evidenziata dalla tabella
A
B
AND
Significato logico:
A·B
A
B
A·B
0
0
0
0
1
1
1
0
1
0
0
1
Tabella della Verità
Truth Table
Se e A e B sono veri, anche A·B è vero
Leggi elementari della logica binaria
Postulati
1) 0 + X = X
2) 1 + X = 1
3) X + X = X
4) X + X = 1
5) 0·X = 0
6) 1·X = X
7) X·X = 0
8) X·X = X
9) X = X
10) X + Y = Y + X
11) X·Y = Y·X
10
proprietà
commutativa
12) X + (Y + Z) = (X + Y) + Z
13) X·(Y·Z) = (X·Y)·Z
proprietà
associativa
14) X·(Y + Z) = (X·Y) + (X·Z)
proprietà
distributiva
15) X + X·Y = X
16) X·(X + Y) = X
17) (X + Y)·(X + Z) = X + Y·Z
18) X + X·Y = X + Y
19) X·Y + Y·Z + X·Z = X·Y + X·Z
identità
ausiliarie
• Dimostrabili mediante ragionamento deduttivo
• Consentono di semplificare le funzioni logiche complesse
Esempio 1: semplificare la seguente funzione logica
F  A  B  D  A  B  D  B C  D  AC  D
Soluzione:
regola 14
regola 4
regola 14
regole 14 e 18
regola 14
regola 14
regole 2 e 6
Funzione logica binaria in forma minima
N.B. La minimizzazione della funzione logica binaria ne consente la
sintesi con un numero minimo di operatori logici fondamentali.
11
Leggi di De Morgan
a) prima legge di De Morgan
(X+Y) = X·Y
b) seconda legge di De Morgan
(X·Y) = X + Y
Ne consegue che una qualsiasi funzione logica può essere
implementata utilizzando:
o sole porte logiche OR e NOT
o sole porte logiche AND e NOT
La scelta ottimale dipende dalla tecnologia con cui vengono
integrate le porte logiche elementari
12
13
Dimostrazione prima legge di De Morgan:
?
Z = X + Y; Z = X + Y = X · Y Dimostriamo che soddisfa le
due proprieta’del complemento:
Z+Z=1
X+Y+X· Y=X+Y+X=1+Y=1
Z·Z=0
(X + Y) · (X · Y) = X · X · Y + Y · Y · X = 0
Oppure:
X
0
0
1
1
Y
0
1
0
1
X+Y
0
1
1
1
X+Y
1
0
0
0
X
1
1
0
0
Y
1
0
1
0
X·Y
1
0
0
0
Forme canoniche
14
Una qualsiasi funzione logica binaria F  F ( A, B, C ,....)
di cui sia nota la Tabella della verità, può essere espressa da:
a) somma di prodotti delle variabili binarie di ingresso
b) prodotto di somme delle variabili binarie di ingresso
Tali espressioni costituiscono le cosidette
Forme canoniche della funzione
a) somma di prodotti
15
Esempio 1: esprimere come somma di prodotti fondamentali
la funzione logica
A 0 0 0 1 0 1 1 1
a tre variabili binarie
B 0 0 1 0 1 0 1 1
definita dalla
C 0 1 0 0 1 1 0 1
Tabella della Verità:
F 0 1 1 1 0 0 1 0
Si considerino le sole combinazioni delle variabili binarie di
ingresso corrispondenti ad una uscita F di valore 1, e per queste sole
si scrivano i prodotti delle variabili (se 1) o dei loro negati (se 0).
F  A ·B ·C  A ·B·C  A·B ·C  A·B·C
Forma canonica della funzione logica definita dalla tabella della verità.
b) prodotto di somme
16
Esempio 2: esprimere come prodotto di somme fondamentali
la funzione logica
A 0 0 0 1 0 1 1 1
a tre variabili binarie
B 0 0 1 0 1 0 1 1
definita dalla
C 0 1 0 0 1 1 0 1
Tabella della Verità:
F 0 1 1 0 1 1 1 0
Si considerino le sole combinazioni delle variabili binarie di ingresso
corrispondenti ad una uscita F di valore 0, e per queste sole si
scrivano le somme delle variabili (se 0) o dei loro negati (se 1).
F   A  B  C  A  B  C  A  B  C 
Forma canonica della funzione logica definita dalla tabella della verità
17
II.3 Operatori logici universali
NOR = OR negato = OR con NOT in cascata
NAND = AND negato = AND con NOT in cascata
Altri operatori di conveniente impiego:
XOR
OR esclusivo
SAME
OR esclusivo negato
Tutti disponibili in forma integrata (Porte logiche)
Operatore logico NOR
18
(somma logica complementare o negata)
convenzionalmente rappresentato dal simbolo di figura svolge la
somma logica negata delle variabili binarie evidenziata dalla tabella
A
B
NOR
A+B
Equivalente a:
A
B
OR
NOT
A
B
0
0
1
1
0
1
0
1
A+B
A+B
1
0
0
0
Operatore logico NAND
19
(prodotto logico complementare o negato)
convenzionalmente rappresentato dal simbolo di figura svolge il
prodotto logico negato delle variabili binarie evidenziato dalla tabella
A
B
NAND
A·B
Equivalente a:
A
B
AND
NOT
A
B
0
0
1
1
0
1
0
1
A·B
A·B
1
1
1
0
NAND e NOR sono operatori logici universali
Una qualsiasi funzione logica F(A,B,C,…) è implementabile
tramite opportune combinazioni:
• o di soli operatori logici NAND
• o di soli operatori logici NOR
Dimostrazione:
Tramite soli operatori logici NAND (o analogamente NOR)
è possibile implementare i tre operatori logici fondamentali
AND, OR, NOT
Segue verifica per gli operatori NAND.
Analoga procedura si applica per gli operatori NOR
20
21
Esempio 1:
implementare l’operatore NOT mediante operatori NAND
soluzione
A
B=A
NAND
Tabella della Verità
A
B=A
0
1
0
1
A·B
0
1
A·B
1
0
A·A=A
22
Esempio 2:
implementare l’operatore AND mediante operatori NAND
Soluzione
A
B
NAND
A·B
NAND
Tabella della Verità
A
B
0
0
1
1
0
1
0
1
A·B
1
1
1
0
A·B
0
0
0
1
A·B
Esempio 3:
implementare l’operatore OR mediante operatori NAND
Soluzione
A
NAND
A
NAND
B
NAND
B
De Morgan
Tabella della Verità
A
0
0
1
1
B
0
1
0
1
A·B
1
0
0
0
A·B
0
1
1
1
A·B= A+B
A+B
0
1
1
1
23
24
Sintesi a NAND ( )
A partire da un’espressione del tipo somme di prodotti (SP) oppure
somme di prodotti di somme (SPS), ecc.:
1) inserire tutte le parentesi sottintese dalla espressione SP
(priorità al prodotto logico);
2) complementare tutte le variabili che risultano direttamente operate
dal simbolo di somma logica;
3) sostituire tutti i simboli + e · con
Esempio (SP) :
F
= a+b·c
Caso particolare F = b · c
F= b c
=b·c+0
= (a + (b · c) )
= ((b · c) + 0 )
( a + (b · c) )
( (b · c) + 1)
= ( a (b c) )
= ( (b c) 1)
25
Sintesi a NOR ( )
A partire da un’espressione del tipo prodotti di somme (PS) oppure
prodotti di somme di prodotti (PSP), ecc.:
1) inserire tutte le parentesi sottintese dalla espressione PS;
2) complementare tutte le variabili che risultano direttamente operate
dal simbolo di prodotto logico;
3) sostituire tutti i simboli + e · con
Esempio (PSP):
Caso particolare F = b + c
F= c · (a + d ) · (a + c · d)
F= b c
= (b + c) · 1
= c · (a + d ) · (a + ( c · d ))
= ((b + c) · 1 )
c · (a + d ) · (a + ( c · d ))
( (b + c) · 0)
= c (a d ) (a ( c d ))
= ( (b c) 0)
Operatore logico XOR (Exclusive OR)
26
convenzionalmente rappresentato dal simbolo di figura
confronta le variabili in ingresso e fornisce uscita 1 solo quando gli
ingressi sono fra loro differenti
A
B
A

B
XOR
Funzione logica XOR
F  A B
A
B A B
0
0
1
1
0
1
0
1
0
1
1
0
Significato logico:
Se o A o B (non entrambi!) sono veri, anche F è vero
Operatore logico SAME (Exclusive OR negato)
convenzionalmente rappresentato dal simbolo di figura
confronta le variabili in ingresso e fornisce uscita 1 solo quando gli
ingressi sono fra loro uguali
A
B
SAME
F
Funzione logica SAME
A
B
SAME
0
0
1
1
0
1
0
1
1
0
0
1
Significato logico:
Se entrambi A e B sono o veri o falsi, anche F è vero
27
II.4. Mappe di Karnaugh
28
Metodo alternativo di rappresentazione delle funzioni logiche binarie
Funzione logica binaria: F  F ( A, B, C ,....)
Alle n variabili binarie di ingresso A, B, C,… corrispondono
2n possibili combinazioni (minterms) per F
Esempio: n=2 (22=4 minterms)
A
A
B A·B A·B
B A·B A B
Esempio: n=3 (23=8 minterms)
AB
AB
AB
AB
C ABC ABC ABC ABC
C ABC ABC ABC ABC
Esempio: n=4
(24=16
minterms)
AB
AB
AB
AB
CD ABCD ABCD ABCD ABCD
CD ABCD ABCD ABCD ABCD
CD ABCD ABCD ABCD ABCD
CD ABCD ABCD ABCD ABCD
N.B. La sequenza delle variabili di ingresso in caselle adiacenti si
diversifica sempre per un solo bit.
Per n>4 introduco un’adiacenza nella terza dimensione …
29
Esempio: n=5
(25=32
minterms)
E
AB
AB
AB
AB
CD ABCD ABCD ABCD ABCD
CD ABCD ABCD ABCD ABCD
CD ABCD ABCD ABCD ABCD
CD ABCD ABCD ABCD ABCD
E
AB
AB
AB
AB
CD ABCD ABCD ABCD ABCD
CD ABCD ABCD ABCD ABCD
CD ABCD ABCD ABCD ABCD
CD ABCD ABCD ABCD ABCD
30
Esempio: n=6
(26=64
31
minterms)
EF
EF
AB
AB
AB
AB
C D ABCD ABCD ABCD ABCD
AB
AB
AB
AB
ABCD ABCD ABCD ABCD
C D ABCD ABCD ABCD ABCD
C D ABCD ABCD ABCD ABCD
C D ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
EF
EF
AB
AB
AB
AB
C D ABCD ABCD ABCD ABCD
AB
AB
AB
AB
ABCD ABCD ABCD ABCD
C D ABCD ABCD ABCD ABCD
C D ABCD ABCD ABCD ABCD
C D ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
Rappresentazione della funzione logica binaria: F  F ( A, B, C ,....)
Mappa di Karnaugh
Tabella della verità
A
B
C
F
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
0
AB
00
C
0 0
1 1
01
1
0
11
1
0
10
1
0
In ognuna delle 2n caselle della Mappa di Karnaugh si riporta il
valore assunto dalla funzione F corrispondente alla combinazione
delle n variabili di ingresso relativa alla casella stessa (valore del
mintermine).
F  A  B C  A  B C  A B C  A B C
32
Rete combinatoria di costo minimo
Criteri di ottimalità
Una R.C. si dice di costo minimo se soddisfa in ordine gerarchico i
seguenti obiettivi:
• minimo transitorio (massima velocità di elaborazione)
• minimo numero di gates
• minimo numero di interconnessioni tra i gates
La corrispondente espressione minima ha le seguenti proprietà:
• è di tipo S.P. o P.S. (due stadi in cascata di AND/OR o OR/AND)
• impiega il minimo numero di AND, OR, NOT
• i prodotti e le somme elaborano il minimo numero di letterali
(raggruppamenti di massima dimensione)
33
Procedura di minimizzazione di funzioni logiche binarie
rappresentate mediante mappa di Karnough
• Sintesi di F minima come somma di prodotti logici.
Procedura:
a) raggruppare gli 1 contigui (in orizzontale o in verticale)
in sottogruppi di 1, 2, 4, 8, …
b) identificare il numero minimo di sottogruppi distinti, partendo
dai sottogruppi maggiori
b) con riferimento al sottogruppo:
escludere le variabili binarie che cambiano
considerare le sole variabili binarie che rimangono invariate come
variabile stessa se 1, variabile negata se 0
c) trascrivere il prodotto logico per ciascun sottogruppo
d) rappresentare la F come somma dei prodotti logici suddetti
34
Esempio 1
35
Tabella della verità
A
B
C
F
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
0
Mappa di Karnaugh
AB
00
01
11
C
0 0
1
1
1 0
0
0
10
0
0
Funzione logica minima:
Individuo il sottogruppo (1 sottogruppo da 2)
F = BC
individuo la variabile che cambia: A
trascrivo il prodotto delle variabili che rimangono invariate: BC
Procedura convenzionale: applico le regole della logica binaria
Forma canonica: F  A BC  ABC
F  A BC  ABC  BC A  A  BC assendo:
A  A 1
Esempio 2
36
Mappa di Karnaugh
AB
00
C
0 1
1 0
01
0
11
0
10
1
0
0
0
Funzione logica minima:
F  BC
N.B.: le celle al bordo orizzontale o verticale si considerano fra loro contigue
Esempio 3
Mappa di Karnaugh
AB
00
C
0 0
1 0
01
1
1
11
1
0
10
0
0
Funzione logica minima:
F  CB  AB
due sottogruppi da 2 celle, di cui uno verticale ed uno orizzontale
Esempio 4
37
Mappa di Karnaugh
AB
00
CD
00 1
01 1
11 0
10 0
01
1
1
0
0
11
0
0
0
0
10
0
1
0
1
1 sottogruppo da 4: A C
1 sottogruppo da 2: B C D
1 sottogruppo da 1: AB CD
Funzione logica minima:
F= A C + B C D + A B C D
Esempio 5 (comprese condizioni indifferenza)
Mappa di Karnaugh
AB
00
CD
00 1
01 1
11 0
10 0
01
1
1
0
11
10
0
0
0
0
1
1 sottogruppi da 4: A C
1 sottogruppo da 2: A B D
Funzione logica minima:
F= A C + A B D
38
Mappe di Karnaugh con variabili riportate
• Sono mappe che contengono variabili al loro interno e si possono
ottenere come “compressione” di mappe ordinarie.
• Possono essere considerate una forma intermedia tra l’espressione
booleana e la mappa di una funzione logica.
Esempio
AB
C
0
1
00
X
0
01
0
11
0
Y
10
1
0
39
Procedura di sintesi di una mappa a variabili riportate
• Sintesi basata su somma di prodotti logici.
a) Si azzerano tutte le variabili riportate nella mappa e si esegue una
normale sintesi degli 1 contigui
b) Si pongono uguali ad indifferenza gli 1 appena sintetizzati e si
sceglie poi una variabile ponendola uguale a 1 lasciando le
rimanenti a 0. Si sintetizza la mappa cosi’ ottenuta e si pone il
risultato in AND con la variabile scelta (le altre si tralasciano !).
c) Si ripete l’operazione precedente per tutte le variabili riportate
sulla mappa considerando una variabile e la sua negata come
variabili indipendenti da sintetizzare in due passi distinti.
d) L’espressione booleana finale e’ l’OR di tutti gli AND trovati.
N.B. Le condizione di indifferenza restano immutate e possono essere
usate per ottimizzare la copertura.
40
41
Esempio 1
Sintetizzare la seguente mappa a una variabile riportata.
AB
C
0
1
00
D
0
01
D
11
D
0
10
1
0
10
1
Azzero le variabili e sintetizzo gli 1.
AB
C
0
1
00
0
01
-
11
0
0
0
0
0
A B C
42
Pongo D=1, D=0, 1=indifferenza.
AB
C
0
1
00
1
0
01
0
11
1
0
10
0
11
0
0
10
0
D C
Pongo D=0, D=1, 1=indifferenza.
AB
C
0
1
00
0
0
01
1
Calcolo F come OR dei tre AND.
F  A B C  D C  D  A  B
D  AB
Esempio 2
43
Sintetizzare la seguente mappa a due variabili riportate.
AB
00
01
11
10
C
0 D
1
E
1 E
0
0
Azzero le variabili e sintetizzo gli 1.
AB
00 01 11
C
0 0
1 0
0
0
Pongo D=1, E=0, E=0, 1=indifferenza.
AB
00 01 11
C
0 1
1
0
0
0
10
1
0
10
0
AC
D C
Pongo D=0, E=1, E=0, 1=indifferenza.
AB
C
0
1
00
1
01
0
1
11
0
44
10
0
E AB
Pongo D=0, E=0, E=1, 1=indifferenza.
AB
0
00
-
01
0
11
-
1
0
1
0
C
10
1
E  A B
Calcolo F come OR dei tre AND.
F  AC  D C  E  A  B  E  A B
45
Esempio 3
Sintetizzare la seguente mappa con caselle contenenti espressioni
booleane di due variabili riportate.
AB
C
00
01
0 0
0
1 D·E 1
11
1
-
10
D+E
D
Metodo 1: ogni operazione booleana distinta va trattata come una
variabile “indipendente” (cosi’ come in precedenza si e’ fatto
per una variabile e la sua negata).
Azzero le variabili e sintetizzo gli 1.
AB
00 01 11
C
0 0
0
1
1 0
1
-
10
0
0
A B  B  C
Pongo D=1, DE=0, D+E=0, 1=indifferenza.
AB
C
0
1
00
0
0
01
0
-
11
-
10
0
1
46
D  A C
Pongo D=0, DE=1, D+E=0, 1=indifferenza.
AB
C
0
1
00
0
1
01
0
-
11
-
10
0
0
D  E  A C
Pongo D=0, DE=0, D+E=1, 1=indifferenza.
AB
C
0
1
00
01
11
0
0
0
-
-
10
1
0
D  E   A  C
Calcolo infine F come OR delle diverse sottoespressioni.
F  A  B  B  C  D  A  C  D  E  A  C  D  E   A  C
N.B. L’espressione cosi’ ottenuta non e’ minima!
Metodo 2: per ottenere una sintesi migliore devo considerare le
come variabili le singole variabili e non le celle.
Azzero le variabili e sintetizzo gli 1.
AB
00
01
11
10
C
0 0
0
0
1
A

B

B

C
0
1 0
1
Pongo D=1, E=0, 1=indifferenza, implicazioni D+E=1, DE=0
AB
C
0
1
00
0
0
01
0
-
11
-
10
1
1
D A
47
Pongo D=0, E=1, 1=indifferenza, implicazioni D+E=1, DE=0
AB
C
0
1
00
0
0
01
0
-
11
-
10
1
0
E  AC
Pongo D=1, E=1, 1=indifferenza, implicazioni D+E=1, DE=1
AB
C
0
1
00
0
1
01
0
-
11
-
10
1
1
Gia’ coperta !
D E C
Calcolo infine F come OR delle diverse sottoespressioni.
F  A B  B C  D  A  E  AC  D  E C
48
49
II.5. Progetto logico
Data una funzione logica binaria, determinare una possibile
combinazione di Operatori logici che la implementino
• Operatori logici elementari AND; OR; NOT
• Operatori logici universali NAND; NOR
La soluzione non è univoca: esiste una soluzione ottimale:
vincoli tecnologici ed economici
50
Progetto logico: procedura
• Descrizione funzionale della rete combinatoria
definizione della relazione logica fra l’uscita F e le variabili
binarie di ingresso A, B, C,...
• Rappresentazione tramite Tabella della verità
• Deduzione della funzione logica F(A, B, C,…) in forma canonica
(o somma di prodotti o prodotti di somme)
• Minimizzazione della funzione logica
o tramite le leggi elementari della logica binaria
o tramite le Mappe di Karnaugh
• Sintesi della funzione tramite Operatori logici
elementari (AND, OR, NOT) e/o universali (NAND, NOR)
• Descrizione funzionale della rete combinatoria
Esempio: date tre variabili binarie in ingresso A, B, C, si abbia:
F=A per C=0; F=B per C=1
• Rappresentazione tramite Tabella della verità
A
B
C
F
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
1
• Deduzione della funzione logica F(A, B, C,…) in forma canonica
Somma di prodotti:
F  A  B C  A B C  A B C  A B C
Prodotto di somme:
F   A  B  C    A  B  C    A  B  C   A  B  C 
51
• Minimizzazione della funzione logica
o tramite le leggi elementari della logica binaria
F  AB C  A BC  ABC  ABC 
 AC B  B   BC A  A   AC  BC
o tramite le Mappe di Karnaugh
AB
Mappa di Karnaugh
00
C
0 0
1 0
01
0
1
11
1
1
10
1
0
Funzione logica minima:
F  AC  BC
2 sottogruppi orizzontali da 2: AC, BC
Equivalente (ma meno conveniente): F  CA B  C AB  AB
1 sottogruppo verticale da 2: AB
2 sottogruppi singoli da 1: CA B; C AB ;
52
53
• Sintesi della funzione tramite operatori logici elementari
(AND; OR; NOT)
F  AC  BC
A
B
C
A
B
C
B
AND
BC
C
C
NOT
OR
C
A
AND
AC
F
54
• Sintesi della funzione tramite operatori logici universali
(NAND oppure NOR)
In questo esempio parto da forma SP, quindi uso il NAND:
A
B
C
A
B
C
NAND
BC
NAND
NAND
AC
F
55
Appendice
Esempio: dimostrazione della identità ausiliaria X·(X + Y) = X
Applico le regole dell’algebra binaria per la verifica “a posteriori”
della identità. X·(X + Y) = X ·X + X ·Y = X + X ·Y = X
Verifica mediante tabella della verità
X
0
0
1
1
Y
0
1
0
1
X+Y X·(X+Y)
0
0
1
0
1
1
1
1
Tutte le leggi elementari della logica binaria sono dimostrabili
mediante analoga procedura
56
Esempio: dimostrazione della identità ausiliaria
X·Y + Y·Z + X·Z = X·Y + X·Z
mediante diagrammi di Venn (teoria degli insiemi)
X
X
X
X·Y
Y
Z
Y·Z = X· Y· Z +X· Y· Z
X·Z
Esercizio
“Cinque astronauti A, B, C, D, E sono stati addestrati per
partecipare ad una missione spaziale. Individuare gli equipaggi
possibili tenendo conto che prove psico-fisiche impongono di
soddisfare contemporaneamente i seguenti vincoli:
- A o B devono essere sicuramente inclusi, ma non insieme;
- C o E devono essere sicuramente inclusi, anche insieme;
- qualora D sia incluso, lo deve essere anche B;
- A e C possono essere o entrambi inclusi o entrambi esclusi;
- qualora E sia incluso, lo devono essere anche C e D.
Soluzione - ???
Risposta - Devono partire A e C.
57
Dimostrazione seconda legge di De Morgan:
?
Z = X · Y ; Z = X · Y = X + Y complemento ?
Z+Z=1
X· Y+X+Y=Y+X+Y=1+X=1
Z·Z=0
(X · Y) · (X + Y) = X · Y · X + X ·Y ·Y = 0
X
0
0
1
1
Y
0
1
0
1
X·Y
0
0
0
1
X·Y
1
1
1
0
X
1
1
0
0
Y
1
0
1
0
X+Y
1
1
1
0
58
59
Forme algebriche compatte
a) somme di prodotti
F  S m(a, b, c, ...), dove a, b, c rappresentano il corrispondente
decimale dei valori delle variabili d’ingresso per cui l’uscita vale 1.
b) prodotti di somme
F  P M(A, B, C, ...) dove A, B, C rappresentano il corrispondente
decimale dei valori delle variabili d’ingresso per cui l’uscita vale 0
Nel caso di funzioni incomplete si aggiunge un termine d(x, y, z, ...)
dove x, y, z rappresentano il corrispondente decimale dei valori delle
variabili d’ingresso per cui l’uscita è indeterminata)
Esempio: A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
F 0 1 - 1 0 - 1 0
F  Sm(1, 3, 6)+d(2, 5)
F  PM(0, 4, 7)+d(2, 5)
Procedura di minimizzazione di funzioni logiche binarie
rappresentate mediante mappa di Karnough
• Sintesi di F minima come prodotto di somme logiche
Procedura:
a) raggruppare gli 0 contigui (in orizzontale o in verticale)
in sottogruppi di 1, 2, 4, 8, …
b) identificare il numero minimo di sottogruppi distinti, partendo
dai sottogruppi maggiori
b) con riferimento al sottogruppo:
escludere le variabili binarie che cambiano
considerare le sole variabili binarie che rimangono invariate come
variabile stessa se 0, variabile negata se 1
c) trascrivere la somma logica per ciascun sottogruppo
d) rappresentare la F come prodotto delle somme logiche suddette
60
Esempio 1
61
Mappa di Karnaugh
Tabella della verità
A
B
C
F
0
0
0
1
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
AB
C
00
0 1
01
0
11
1
10
1
1 1
0
1
1
Funzione logica minima:
Individuo il sottogruppo (1 sottogruppo da 2)
individuo la variabile che cambia: C
F  A B
trascrivo la somma delle variabili che rimangono invariate: A  B
62
Esempio 2
Mappa di Karnaugh
AB
00
CD
00 1
01 1
11 0
10 1
01
1
0
0
1
11
1
1
0
1
10
1
1
0
1
Funzione logica minima:
F = ( C + D ) · (A + B + D )
63
Esercizio
Realizzare la sintesi a NOR della funzione logica espressa dalla
seguente Mappa di Karnaugh:
AB
CD
00
01
11
10
0
0
0
00
01
0
0
0
11
1
0
0
1
10
1
0
1
1
Funzione logica minima di tipo PS:
F = A ·( B + D ) · (C + D )
64
F = (A) · ( B + D ) · ( C + D )
(A) ( B
D)
(C
D)
A
B
NOR
D
C
(A ) · ( B + D ) · ( C + D )
NOR
F
NOR