Minimizzazione
Mappe di Karnaugh
Tale tecnica di minimizzazione è basata
sull’idea che la somma di due prodotti di
letterali può essere sostituita da un singolo
prodotto se i due prodotti iniziali differiscono
per un solo letterale.
Mappe di Karnaugh
 partiamo
dalla forma canonica
disgiuntiva e introduciamo apposite
tabelle con 2n celle
yx
z
00 01 11 10
0 0 0 0 0
1
0
1
1
1
1 se il mintermine fa parte della f.n.d.
Mappe di Karnaugh
 raggruppiamo
gli uno che stanno in celle
adiacenti (adiacenti significa anche sopra e
sotto o destra e sinistra e quelle poste ai lati
opposti della mappa)
yx
z
00 01 11 10
0 0 0 0 0
1 0 1 1 1
in gruppi di singoletti, coppie, quadruple….
potenze di 2
Mappe di Karnaugh
i
gruppi sono determinati in modo
euristico (cioè basato su osservazioni ed
esperienza anziché su una teoria)
yx
z
00 01 11 10
0 0 0 0 0
1 0 1 1 1
i blocchi ottenuti sono i mintermini
che cerchiamo
Mappe di Karnaugh
 non
è possibile applicare il metodo a funzioni
con più di 4 variabili in maniera semplice
cerchiamo un altro modo
per poter minimizzare funzioni con più variabili
mappe di Karnaugh: metodo grafico
Metodo di Quine - McCluskey
 non
è grafico
 determino gli implicanti primi (vedremo
cosa sono)
 cerco
il ricoprimento minimo di tali
implicanti
implicanti
x
0
0
0
0
1
1
1
1
y
0
1
0
1
0
1
0
1
z f(x, y, z)
0
1
una funzione di n variabili f rico0
0
pre un'altra funzione g (f > g) se f
1
0
vale 1 dove anche g vale 1 (ma
1
1
non il vice versa)
0
0
0
0
un prodotto p di m
1
0
variabili (m < n)
1
1
f implica f
di f è un implicante per f
se f > p
implicanti
x
0
0
0
0
1
1
1
1
y
0
1
0
1
0
1
0
1
z f(x, y, z)
0
1
un implicante p è primo per f se
0
0
l'eliminazione di un letterale di p
1
0
dà luogo ad un prodotto p' tale
1
1
che f > p'
0
0
0
0
x  y  z e ~x  y  z
1
0
non sono primi: se elimino
1
1
x e ~x ottengo ancora 1
infatti y  z vale 1
è un implicante primo
implicanti
x
1
0
1
1
1
1
1
1
1
y
0
0
0
0
0
1
0
1
1
z
0
0
0
1
1
0
1
0
1
v
0
1
1
0
1
0
1
1
1
w
0
1
0
0
0
1
1
1
1
sono tutti i mintermini della
forma canonica congiuntiva
sono ordinati per peso: numero
di 1 nella riga e peso delle
variabili
w è quella che pesa di meno
implicanti
x
1
0
1
1
1
1
1
1
1
y
0
0
0
0
0
1
0
1
1
z
0
0
0
1
1
0
1
0
1
v
0
1
1
0
1
0
1
1
1
w
0
1
0
0
0
1
1
1
1
due "coppie" sono unificabili
se differiscono per un solo
simbolo
confronto il primo con tutti gli
altri, poi il secondo e cosi via...
creo una nuova tabella
implicanti
x
1
0
1
1
1
1
1
1
1
y
0
0
0
0
0
1
0
1
1
z
0
0
0
1
1
0
1
0
1
v
0
1
1
0
1
0
1
1
1
w
0
1
0
0
0
1
1
1
1
non unifica con nessuna
per ora la ignoriamo
implicanti
A
K
B
C
D
E
F
G
H
x
1
0
1
1
1
1
1
1
1
y
0
0
0
0
0
1
0
1
1
z
0
0
0
1
1
0
1
0
1
v
0
1
1
0
1
0
1
1
1
w
0
1
0
0
0
1
1
1
1
x
1
1
1
1
1
1
1
1
y
0
0
0
0
0
1
1
z
0
1
1
0
1
-
v
0
1
1
1
1
w
0
0
0
0
1
1
1
implicanti: diamo dei nomi alle righe
A
B
C
D
E
F
G
H
x
1
0
1
1
1
1
1
1
1
y
0
0
0
0
0
1
0
1
1
z
0
0
0
1
1
0
1
0
1
v
0
1
1
0
1
0
1
1
1
w
0
1
0
0
0
1
1
1
1
x
1
1
1
1
1
1
1
1
y
0
0
0
0
0
1
1
z
0
1
1
0
1
-
v
0
1
1
1
1
w
0
0
0
0
1
1
1
AB
AC
BD
CD
DF
EG
FH
GH
implicanti: proseguiamo….
x
AB 1
AC 1
BD 1
CD 1
DF 1
EG 1
FH 1
GH 1
y
0
0
0
0
0
1
1
z
0
1
1
0
1
-
v
0
1
1
1
1
w
0
0
0
0
1
1
1
x
1
y
0
z
-
v
-
w
0 ABCD
AB combina con CD
AC combina con DB
quali sono gli implicanti primi
 gli
implicanti primi sono quelli che non
sono stati fusi con altri:
K
 DF
 EG
 FH
 GH
 ABCD

Selezione degli implicanti primi
K
DF
EG
FH
GH
ABCD
K
X
A
B
C
D
E
X
F G
X
X
X
X
X
X
X
X
H
X
indica che l'implicante primo DF copre D
X
X
Selezione degli implicanti primi
 trovare
un insieme di righe di cardinalità
minima tale che, per ogni colonna della
tabella, vi sia almeno una riga che abbia
una X in quella colonna
 Due tecniche:
• Dominanza
• Essenzialità
Dominanza
 Una
riga i domina una riga j se i possiede
X in tutte le posizioni di j
Essenzialità
 Una
riga i è essenziale se è l'unica ad
avere una X in una certa posizione
 Possiamo eliminare le righe essenziali e
le relative colonne
Selezione degli implicanti primi
K
DF
EG
FH
GH
ABCD
K
X
A
B
C
D
E
X
F G
X
X
X
X
X
X
X
X
H
X
eliminiamo le righe e le colonne
X
X
Selezione degli implicanti primi
K
DF
EG
FH
GH
ABCD
K
X
A
B
C
D
E
X
F G
X
X
X
X
X
X
X
X
H
X
rimangono tre righe e due colonne
X
X
Selezione degli implicanti primi
K
DF
EG
FH
GH
ABCD
K
X
A
B
C
D
E
X
F G
X
X
X
X
X
X
X
FH domina GH e DF
X
X
H
X
X
Risultato finale
 La
forma minima è data da
K  EG  ABCD  FH
cioè
(~x  ~y  ~z  v  w)  (x  y  ~z  w)
 (x  ~y  w)  (x  z  v  w)
Considerazioni conclusive sulla
minimizzazione
 Osserviamo

che siamo partiti dai letterali
potrebbero esserci forme più compatte
 La
minimizzazione è molto costosa e non
sempre si riesce ad ottenere la forma
minima