Newsgroup: it.scienza.fisica
Titolo: mappe di Karnaugh

Conosco superficialmente le mappe di Karnaugh, ma ho bisogno di
informazioni più dettagliate a carattere universitario.
se possedete tale informazione vi pregherei di rispondermi.
Vi ringrazio anticipatamente.
ROCCO.

Ciao!
non vorrei cadere in un clamoroso errore di omonimia, ma le mappe di K.
sono dei divertenti giochini che servono a sintetizzare in modo
ottimizzato delle reti logiche (solo) combinatorie.
Sono la base per chi studia reti logiche, e quindi puoi trovarle
descritte  in molti testi di elettr. digitale (es. Ronald Tocci)
Marco.
P.S. Gia' visto che la domanda mi sembra un po' OT su it.scienza.fisica,
non vorrei aver descritto un ruolo delle mappe il realta' limitato....
Anna & Rocco ha scritto:


informazioni più dettagliate a carattere universitario.
Mettere la spiegazione completa delle mappe di Karnaugh sarebbe un po lungo,
anche perche' bisognerebbe capire quali sono le "informazioni piu' 
dettagliate" (che per'altro puoi trovare in qualunque testo che tratti
i sistemi combinatori e le reti logiche. Io ho sottomano un Luccio-Grasseli, 
"Teoria delle reti logiche: reti combinatorie", Boringhieri, 1977 - 5.000
lire, all'epoca! :-) )
Comunque, le mappe sono usate per minimizzare una funzione logica: questa
e' espressa in forma estesa come somma di tutte le combinazioni di
ingressi che rendono la funzione "vera". Spesso, questa forma e' ridondante,
essendo possibile semplificarla (
p.es
, se ho 2 termini a.b.c + a.b.non-c,
posso semplificare sostituend con a.b)
Le mappe, essendo costruite in modo che tra una casella e l'adiacente ci sia
solo un termine di differenza, permettono di visualizzare immediatamente
questi casi, sostituendo a termini adiacenti un solo termine ed eliminando gli
ingressi che appaiono sia al diritto che al negato.
Il problema e' che una mappa del genere puo' essere facilmente costruita 
solo per 4, max 5 termini.
Come spiegazione e' un po stringata, ma se hai quesiti piu' specifici, non
farti scrupoli
-- 
Renato Croci
Roma - Italy
home page: 
http://www.geocities.com/CapeCanaveral/Hangar/8528
Remove "ky" from the address for e-mail reply
Togliere "ky" dall'indirizzo per risposte in e-mail

 > ROCCO.
Le mappe di Karnaugh non servono solo per semplificare reti combinatorie
e solo nell'elettronica digitale ma sono uno strumento utile per la sintesi
di
sistemi a stati finiti di qualunque tipo: la funzione di transizione di
stato in quel tipo di sistemi si studia appunto con la tecnica delle mappe,
oltre che con i diagrammi di stato. Questo significa che anche le reti
sequenziali, non solo quelle combinatorie, tramite le tabelle di transizione
possono utilmente essere rappresentate e studiate mediante queste mappe.
Posso provare a dire le poche cose che so in proposito, e che non si trovano
comunque tutte nella stessa fonte. Giudicane tu l'utilità per i tuoi scopi.
Intanto il numero di variabili trattabili con questa tecnica è in via di
principio illimitato, anche se, con elaborazione manuale, non si va in
genere oltre il sei. A partire dalle quattro variabili, che è il massimo per
una mappa sola, ogni aggiunta di una variabile raddoppia il numero di mappe,
cosa scomoda per l'elaborazione manuale ma non per quella automatica, che
può servirsi di array multidimensionali, ossia sfruttare le proprietà della
memoria di sistema, che ha la natura di matrice per definizione così come le
mappe sono matrici per definizione.
Come mi pare qualcuno abbia già osservato in un post precedente, la mappa
applica uno solo dei teoremi di base dell'algebra di Boole, che sono venti
se si includono quelli di De Morgan, quindi la sua capacità di
semplificazione non è esauriente. D'altra parte anche altri metodi, come
quello di Quine, si fondano sul medesimo teorema e sono almeno altrettanto
laboriosi col crescere del numero di variabili, e sono meno facilmente
meccanizzabili.
Un altro aspetto è che le mappe possono essere costruite con i "mintermini"
(condizioni vere della funzione logica, 1) ma anche con i maxtermini
(condizioni false, 0). La convenienza a scegliere uno dei due modi (somma di
prodotti o prodotto di somme) dipende dal numero di mintermini e maxtermini
presenti nella colonna che rappresenta la funzione logica. Un esempio: la
tavola della verità della funzione OR a due variabili ha un solo maxtermine,
quindi la funzione è subito scritta negando il valore corrispondente delle
variabili e sommandole, mentre usando i maxtermini la funzione è di tre
termini e ha bisogno di elaborazione successiva. Questo tipo di mappa è
duale rispetto alla mappa usuale, e in genere non è trattata dai testi,
anche perché con il tipo usuale il risultato è sempre e comunque garantito,
sia pure con elaborazioni inutilmente lunghe in molti casi.
Un aspetto non marginale è la scelta del codice Gray, e non del codice
binario naturale, per l'ordinamento delle righe e delle colonne delle mappe.
Il codice Gray è non pesato ed è ciclico, e non è solo utile ma è necessario
per l'ordinamento. Infatti il codice Gray ha la caratteristica di cambiare
valore a un solo bit da una posizione alla successiva, e perciò si adatta
perfettamente al teorema su cui si basano le mappe: la somma logica di una
variabile e della sua negata è sempre vera, cioè 1, quindi se fra i
mintermini di due caselle contigue cambia proprio solo un bit è
legittimamente possibile eliminare la variabile corrispondente (due
variabili su quattro caselle contigue, tre su otto e così via); questo
corrisponde al raccoglimento a fattore dei bit comuni, lasciando fra
parentesi, appunto, la sola variabile che è cambiata sommata con la sua
negazione, quindi la parentesi è 1 e la variabile sparisce. L'altra
proprietà del codice Gray è la sua ciclicità, intendendo con questo che
l'ultima combinazione è contigua con la prima. Di qui anche il suo uso per
la misura di posizioni angolari mediante il semplice conteggio delle
variazioni dei bit: se un disco è diviso con un codice Gray di 4 variabili,
a ogni variazione di un bit corrisponde sicuramente un passo di un
sedicesimo di 360°, senza discontinuità fra la prima e l'ultima
combinazione. Il vantaggio, per le mappe in questione, è che l'ultima riga
in basso è contigua con la prima in alto e quella più a destra è contigua
con quella più a sinistra, perciò sono possibili semplificazioni anche fra
queste estremità. E' come se il codice fosse, anche in questo caso,
distribuito su un cilindro. Il codice Gray si costruisce facilmente con una
tecnica a specchio: si parte da 0 1 in colonna (prima variabile), poi lo si
copia di sotto a specchio (0 1 - 1 0); alle prime due cifre si antepongono
due 0 e alle seconde due 1 (seconda variabile); questo blocco si copia di
sotto a sua volta a specchio ottenendo otto combinazioni; davanti alle prime
quattro si mette 0 e davanti alle seconde quattro 1 (terza variabile). E
così via.
Nel caso di più mappe la semplificazione fra due mappe è possibile fra
caselle omologhe che contengano 1, ma solo se le mappe, a loro volta, sono
contigue, ossia se differiscono per il valore di una sola variabile. Il
sistema, in altre parole, è annidato secondo la logica del teorema in
questione (primo teorema dei complementi: A + non-A = 1).
Una semplificazione esauriente, ripeto, deve servirsi di tutti i teoremi
dell'algebra di Boole, inclusi quelli di De Morgan, e inoltre delle
proprietà associative e distributive (diverse però, almeno alcune, da quelle
dell'algebra ordinaria), con un vantaggio in più rispetto all'algebra
ordinaria: grazie a uno dei due teoremi di idempotenza (A + A = A) è
possibile usare più volte il medesimo termine nell'applicazione di queste
proprietà, ossia lo si può duplicare quante volte si vuole, possibilità che
porta spesso a notevoli razionalizzazioni.
Spero, Rocco, di esserti stato utile
Ciao
Maurizio