Funzioni booleane e minimizzazione

Le funzioni di due variabili

Le funzioni di due variabili

Nomi e simboli per le funzioni di due variabili

Si notino in particolare le seguenti funzioni:

Or esclusivo (XOR): f₆ = y + x = x y

rappresenta la proposizione logica 'l'uno o l'altro ma non entrambi' e costituisce altresì la tabella della somma di due cifre binarie;

Equivalenza (EQ): f₉ =

costituisce il complemento della precedente e rappresenta la proposizione 'entrambi falsi o entrambi veri';

NOR: f₈ = ∙ = = x y

è di notevole importanza nei circuiti di commutazione; il nome le deriva dal fatto che è la funzione negata della OR..

NAND: f₁₄ = += = xy

analoga alla precedente per importanza, costituisce la funzione negata della AND e la duale della NOR; insieme alla NOR, sarà ampiamente trattata in questo capitolo.

Implicazione: f₁₃ = + y = xy

rappresenta una proposizione falsa solo se x è vero e y è falso; si vedano i § 11-6 e 11-13.

In tabella si riporta per ciascuna delle principali funzioni la sua negata e la sua duale; si noti che la funzione XOR è nel medesimo tempo la negata e la duale della funzione EQ (e viceversa).

Fig. 1.3 - Negati e duali delle funzioni

Funzioni booleane generalizzate

Diremo variabile booleana generalizzata o vettore booleano di ordine n l'insieme ordinato di n variabili booleane:

X = x₁x₂x_n

Il vettore X può assumere uno dei 2ⁿ valori possibili rappresentati dai numeri interi espressi in binario e completati da eventuali 0 a sinistra. Porremo:

X = N_n                    (0 N 2ⁿ)

per indicare sinteticamente che il valore di X è N espresso su n bit. In particolare:

X = 0₅ significa X = 00000

X = 3₄ significa X = 0011

Diremo funzione booleana generalizzata una funzione

Y = F(X₁, X₂,,X_k)

con Y, X₁, X₂,,X_k variabili booleane generalizzate.

Se X è un vettore di n elementi e Y di m, la notazione

Y = F(X)                             

indica che il valore di Y è funzione del valore di X o, in altri termini:

La normale funzione booleana di n variabili può anche essere vista come caso particolare (m = 1) y = f(X)

Analogamente, la notazione Z = F(X, Y) che indica il vettore Z come funzione dei due vettori X, Y, è equivalente a:

e così via per funzioni di 3 o più vettori.

La notazione Y=F(X) rappresenta in particolare, nel campo dell'algebra dei circuiti, una rete logica a più uscite, che viene anche detta rete combinatoria

Schema di rete combinatoria

Si noti che ciascuna y_i può essere decomposta in funzioni componenti e che due distinte y_i possono contenere una identica funzione componente. Ciò indica che una medesima porta concorre a determinare il valore di due distinte variabili di uscita. Se è ad esempio

y₁ = x₁x₂ + x₃

y₂ = x₁x₂ + x₁

lo schema realizzativo della rete può essere quello mostrato in fig. 2.2, con l'impiego di 5 porte invece delle 6 necessarie con una realizzazione separata di y₁ e y₂.

Una rete combinatoria

La Z=F(X;Y) pone in evidenza come una rete combinatoria possa compiere una elaborazione su due dati, X e Y, formandone il risultato.

Se la Z=F(X,Y) assume la forma

z_i = f(x_i, y_i) i

si ottiene una particolare classe di funzioni booleane generalizzate (e di reti combinatorie) .

Si ha così

Z = z_i = _i

Z = X + Y z_i = x_{i +} y_i

Z = X ∙ Y z_i = x_i ∙ y_i

Z = X Y z_i = x_i y_i

etc.

che esprimono operazioni tra due vettori booleani.

Si può ancora definire, in analogia al prodotto fra uno scalare ed un vettore, la funzione

Y = ∙ X y_i = ∙ x_i

con variabile booleana, X e Y vettori di ordine n. Si ha:

Y = 0_n

= l Y = X

           

a) b)

Abilitazione vettoriale: a) schema a blocchi; b) Schema analitico

e quindi, con riferimento allo schema, = 1 'lascia passare' il valore di X, mentre = 0 pone Y = 0 indipendentemente dal valore di X.

Dualmente si può assumere come 'abilitante' il valore di 0 di e porre:

Y = + X (2.6)

avendosi allora che per = 1, Y è un vettore di tutti 1 e per = 0 è Y = X.

Nei due casi diremo valore neutro della variabile generalizzata Y rispettivamente i valori 000 e 111.

Insiemi funzionalmente completi

Poiché tutte le funzioni dell' algebra posseggono una forma normale che si esprime come somma di mintermini, l'insieme è un insieme funzionalmente completo..

Per il teorema di De Morgan anche l'insieme e, dualmente, l'insieme sono funzionalmente completi.

L'importanza della individuazione di un insieme f.c. risiede nel fatto che un qualsiasi circuito logico si può realizzare adoperando esclusivamente porte che realizzano le operazioni dell'insieme: un circuito logico, dunque, si può costruire adoperando solo porte

AND, OR, NOT

oppure

AND, NOT

oppure

OR, NOT

Le funzioni NAND e NOR

Notevole importanza applicativa hanno le funzioni NAND e NOR:

              

che rappresentano rispettivamente il negato delle funzioni AND e OR e che sono l'una la duale dell'altra.

Si noti che la funzione NAND (e, dualmente, la NOR) non gode della proprietà associativa, avendosi

Si definiscono funzioni NAND e NOR di n variabili, come segue:

 

Si ha ovviamente

E' possibile esprimere una funzione AND (OR) in termini di NAND o NOR:

             

È anche possibile esprimere la funzione NOT in termini di NAND (NOR):

                   

o anche

       

Ne deriva che la sola funzione NAND (e, dualmente, la sola NOR) costituisce un insieme funzionalmente completo.

Ovviamente, potranno aversi forme NAND (NOR) a 2 livelli:

Ad esempio

Sono ovviamente anche possibili forme 'miste' di una funzione, cioè forme che adoperano operatori di insiemi f.c. diversi. Si notino in proposito le seguenti eguaglianze:

                     (4.6)

e tali relazioni sono facilmente generalizzabili:

Analogamente, si ha:

                        (4.7)

ed in generale:

Si ha infine:

    (4.8)

Le forme NAND e NOR di una funzione

Esiste una precisa corrispondenza fra le forme elementari di primo e secondo tipo e, rispettivamente, le forme a due livelli NAND e NOR. Posto

f = ₁ + ₂ + + _n

ove ciascuna _i è una clausola. Si ha per il teorema di De Morgan

=

Se _i è un letterale, deve essere complementato; se viceversa è un prodotto di più letterali, occorre farne la NAND. Si ha dunque:

Per dualità si ricava facilmente che una forma elementare di tipo S si trasforma in una forma NOR a due livelli, sostituendo gli operatori AND e OR con il NOR e negando i fattori elementari costituiti da un solo letterale.

La regola precedente si estende facilmente alle forme a più livelli:

Dunque, una forma elementare di tipo P si trasforma naturalmente e meccanicamente in una forma NAND a due livelli, una di tipo S in una forma NOR.

Se viceversa si vuole trasformare in NOR una funzione y che sia in forma elementare P (oppure in una forma con ultimo livello OR) basta considerare che essa è uguale a e quindi può essere trasformata in forma NOR, ponendo

Dualmente le forme che abbiano come ultimo livello una AND possono essere trasformate in forma NAND. e si ha quindi:

Per concludere, una forma a n livelli con funzioni AND e OR si può sempre trasformare meccanicamente in una forma NAND o NOR a n oppure o n+1 livelli.

Alcuni esempi serviranno a chiarire le idee.

Esempio 1

Dalla funzione a 2 livelli in forma P:

si ottiene la forma NAND

ove c è negato perché singolo letterale (livello complementare 1) oppure quella NOR

ove a,b sono negate in entrambe le clausole perché diventate di livello 3 e c non lo è più perché di livello 2.

Esempio 2

Dualmente dalla funzione in forma S

si ottiene la forma NOR

oppure quella NAND

Esempio 3

La funzione a 4 livelli

si trasforma nella forma NOR ancora a 4 livelli

dove b e sono negate rispettivamente ai livelli complementari 1 e 3, oppure nella forma NAND a 5 livelli

ove al livello 3 e ,d al livello 5 sono negati.

A conclusione di quanto esposto, si può affermare che, esistendo la corrispondenza vista tra forme AND-OR, forme NAND e forme NOR, tutte le funzioni potranno esprimersi e manipolarsi adoperando gli operatori AND, OR, NOT (di più semplice scrittura e di più immediata visione), intendendo che le analoghe espressioni o manipolazioni vadano applicate sulle forme NAND o NOR corrispondenti.

Costo convenzionale e minimizzazione di una forma

È indubbiamente conveniente esprimere una funzione booleana nella forma più sintetica possibile in quanto equivale ad una realizzazione più economica della funzione .

Per definire un criterio oggettivo in base al quale si possa valutare la maggiore sinteticità di una forma rispetto ad un'altra, si possono fornire alcune definizioni matematiche di 'costo' di una funzione.

a)     Costo di letterali CL è pari al numero delle variabili indipendenti della funzione, ciascuna moltiplicata per il numero di volte che essa compare nella forma. Il valore così ottenuto equivale, per le reti bilaterali, al numero di contatti adoperati.

b)     Costo di funzioni o di porte CP è pari al numero delle funzioni elementari f_i che la compongono. Tale definizione equivale, per le reti unilaterali, al numero complessivo di porte adoperate.

c)     Costo di ingressi CI è il numero delle funzioni f_i che la compongono, ciascuna moltiplicata per le variabili (dipendenti o indipendenti) di cui è funzione. Tale definizione equivale, per le reti unilaterali, al numero complessivo di porte adoperate, ciascuna 'pesata' per il numero di ingressi che possiede.

Il problema della ricerca di una forma booleana 'sintetica' si può porre come problema di minimizzazione di una delle tre definizioni di costo convenzionale.

Non esistono metodi matematici che consentano di risolvere il problema della minimizzazione nella sua generalità.

Il problema nella sua generalità è anche di scarso interesse pratico, in quanto l'insieme F di funzioni elementari f_i ed il numero di livelli di una funzione sono di solito fissati 'a priori' in base a considerazioni di ordine circuitale.

Il problema che interessa risolvere è quello della ricerca di una forma elementare minima, cioè di una forma minima fra tutte quelle possibili a 2 livelli di tipo P (o dualmente di tipo S).

Si può innanzitutto dimostrare che:

Si supponga infatti che la funzione posta in forma elementare contenga un termine che non sia primo implicante; si ha allora:

con primo implicante; quest'ultimo può essere aggiunto alla f e si ottiene ; essendo poi , può essere eliminato dalla sommatoria, dove viene sostituito dal primo implicante . Operando analogamente per tutte le clausole non primi implicanti, la y viene trasformata in forma PI.

Si può altresì dimostrare che:

Infatti, fra tutte le forme elementari non PI, si scelga quella minima; se questa viene trasformata in una forma PI nella quale sostituisce , poiché è una clausola di ordine inferiore ad , diminuiscono CL (diminuendo i letterali) e CI (diminuendo il numero di variabili indipendenti della funzione componente) mentre CP non aumenta (diminuisce se era già nella sommatoria, resta inalterato altrimenti).

In altri termini, una forma minima (o una delle forme minime) si può sempre trovare fra le forme PI;

Si forniscono ora le seguenti definizioni:

e si può dimostrare il seguente teorema:

In altri termini, in ogni forma minima sono contenuti tutti i primi implicanti essenziali (donde il nome di 'essenziale'). Se infatti è un primo implicante essenziale, si ha per definizione che esiste un mintermine (eventualmente coincidente con ) che non implica nessun altro implicante primo, tale cioè che da = 1 non derivi nessun altro = 1: se in una forma PI fosse assente, dunque, da P_k = 1 non scaturirebbe y = 1.

Dalle considerazioni di cui sopra deriva il metodo di minimizzazione dovuto a Quine e McCluskey, che consiste nelle seguenti fasi:

a)       ricerca di tutti i primi implicanti della funzione f da minimizzare;

b)       selezione dei primi implicanti essenziali, per individuare il nucleo N;

c)       copertura della funzione, cioè determinazione della forma minima di R, da aggiungere ad N per minimizzare f (cfr. 6.3).

La ricerca dei primi implicanti

Metodo algebrico (di Quine)

Si determinano inizialmente gli eventuali implicanti di ordine n (con n numero delle variabili della funzione), poi quelli di ordine n-1 e così via fino a quelli ordine minimo. A tale scopo, si può procedere sistematicamente come segue:

Si riconduce la funzione f alla forma canonica di tipo P.

Si generano tutti i possibili consensi (cfr. § II -13) fra le clausole di ordine n associate a due a due; sono primi implicanti di ordine n le clausole dalle quali non è scaturito alcun consenso, mentre i consensi generati costituiscono implicanti di ordine n-1 di f

Sui consensi generati si ripete l'operazione 2, ottenendosi i primi implicanti di ordine n-1 ed implicanti di ordine n-2;

Il procedimento si applica successivamente agli implicanti generati di ordine via via decrescente fino agli implicanti di ordine 1 o comunque finché non sia più possibile generare consensi

A titolo di esempio, si illustra il procedimento applicato alla funzione di 4 variabili

f = abdc + bdc + cd + d + abd + abc + ab

Dagli implicanti di ordine 4 si generano i seguenti consensi:

abcd + bdc = bcd

abcd + abd = abd

abcd + abc = abc

bcd + cd = cd

cd + d = d

abd + ab = ab

abc + ab = ab

Poiché tutti i mintermini generano almeno un consenso, non esistono primi implicanti di ordine 4, mentre gli implicanti di ordine 3 da tenere in conto sono:

bcd, abd, abc, cd, d, ab, ab

Da questi deriva l'implicante di ordine 2, ab, ottenuto sia dalla coppia (abd, ab) sia dalla coppia (abc, ab) mentre risultano primi bcd, cd, d

Tutti gli implicanti primi di f risultano pertanto:

bcd, cd, d, ab

Metodo tabellare (di McCluskey)

Si procede dunque come segue:

Si riconduce la funzione f alla forma canonica di tipo P e i mintermini (clausole di ordine n) si esprimono nel formato con '1' e '0'.

Si suddividono i mintermini in classi che si ordinano, da 'classe 0' a 'classe n'; si pone, k=n.

Per ogni i da 0 a k-1: si generano i consensi di ordine k-1accoppiando le clausole della 'classe i' con quelle della 'classe i+1'; si spuntano le clausole che generano consenso.

Le clausole non spuntate sono implicanti primi di ordine k. Nei consensi generati si eliminano gli eventuali doppioni; i consensi stessi sono ordinati e riorganizzati da 'classe 0' a 'classe k-1'.

Si pone k=k-1 e si ripete il passo 3 finché non sia k

Ad esempio con riferimento alla stessa funzione precedente, si ha.

Fig. 7.1 - Ricerca dei primi implicanti (Mc Cluskey)

Metodo grafico (mappe di Karnaugh)

La tecnica di ricerca dei primi implicanti sulle mappe di Kamaugh deriva dal fatto che la relazione di implicazione è una relazione di inclusione in un'algebra degli insiemi e che, pertanto i primi implicanti sono i sottocubi di 'area massima'. Pertanto i primi implicanti di una funzione sono agevolmente ricavati dall'ispezione visiva degli '1' della funzione segnati sulla mappa.

La copertura di una funzione

Problema di copertura

f = abdc + bdc + cd + d + abd + abc + ab

Fig. 8.1 - Tabelle dei primi implicanti della funzione di fig.7.1

Individuazione del nucleo

Con riferimento all'esempio di fig. 8.1, sono essenziali A= (unico ad essere implicato da ) e D= ab (per , e ); il nucleo della funzione è dunque

N = A + D

Copertura minima

Nell'esempio mostrato resta da coprire il solo mintermine , che può essere ricoperto indifferentemente da B o C, avendosi quindi le due forme minime equivalenti

y = (A + D) + B

y = (A + D) + C

Metodo di Petrick

Per la matrice già ridotta di fig. 8.2 la copertura si può ottenere con A oppure B per M₁, B oppure C per M2, etc.; in formula:

(A + B)(B + C)(A + D)(B + E)(A + F)(C + E + G)(A + B + D)(A + B + F)(A + C + G) = ACE + ABC + ABG + ABE + BCDF + BDFG

e pertanto , , etc. sono le possibili coperture tra cui va scelta quella minima.

Fig. 8.2 - Esempio di copertura minima (Petrick)

Un metodo per avviare a soluzione la copertura è quello delle righe e colonne dominanti

Una volta che dalle matrici siano state eliminate righe e colonne per dominanza, può accadere che una (o più) riga assuma la proprietà di coprire da sola una colonna: tale riga e gli implicanti associati si dicono 'essenziali secondari'. Ne deriva, allora, l'algoritmo che segue:

ricerca dei primi implicanti (PI) ed individuazione di quelli essenziali;

inclusione nella forma minima dei PI essenziali; loro eliminazione dalla matrice, unitamente con i mintermini ricoperti;

eliminazione delle righe dominate e delle colonne dominanti;

individuazione dei PI essenziali 'secondari' della matrice così ridotta;

ripetizione dei passi 2, 3, 4 finché è possibile.

L'algoritmo termina o perché si eliminano tutte le righe e colonne dalla matrice o perché quest'ultima non possiede né primi implicanti né righe dominate né colonne dominanti. La struttura della tabella è allora 'ciclica'.

Esempio 1

Il metodo esposto viene descritto in fig. 8.3 per la funzione:

(x₁, x₂, x₃, x₄, x₅) = (0,1,2,8,9,15,17,21,24,25,27,28,31).

Passo 1) si ricavano i primi implicanti:

; ; ;

; ;

a)

b) c) d)

Fig. 8.3 - Algoritmo di righe dominate e colonne dominanti

Passo 2) sono essenziali (cfr. fig. 8.3a):

E per P₁₅ , G per P₂₁ , H per P₂₈ , J per P₂

ed il nucleo risulta:

N = E + G + H + J

Passo 3) dalla matrice ridotta di fig. 8.3b risulta:

D riga dominata da F

P₉ colonna dominante di P_l e P₈

che si eliminano

Passo 4) dalla fig. 8.3c risulta che F è un primo implicante essenziale secondario per P₂₇;

Passo 2) al nucleo N va aggiunto F ;

Passo 3) dalla matrice ridotta di fig. 8.3d risulta che A e B sono righe dominate da C, con conseguente eliminazione;

Passo 4) la matrice si riduce alla sola riga C, per cui la forma minima è

= (E + G + H + J) + F + C

Esempio 2

In fig. 8.4 si mostra il caso di una funzione per la quale il nucleo è vuoto; in fig. 8.5 la matrice di copertura associata, che è ciclica.

B

Fig. 8.4 - Mappa di una funzione ciclica

Fig. 8.5 - Tabella di copertura dells funzione di fig. 8.4

Applicando il metodo di Petrick, l'espressione logica che definisce la copertura è:

(A+B)(B+C)(C+D)(D+E)(E+F)(F+G)(G+H)(H+A)=

=ABCDEFGH+BCDEFGH+.+BDFH+.+ACEG+.=

= BDFH+ACEG

e quindi le due coperture minime.

Esempio 3

In fig. 8.6 è illustrata la versione grafica delle minimizzazione della funzione dell'esempio 1, a 5 variabili.

x3x4 x5
	x1x2
C

F

B

H

D

G

Fig. 8.6 - Mappa della funzione di fig. 8.3

In conclusione, i primi implicanti possono dividersi in

essenziali, cioè costituenti il nucleo della funzione (E,G,H,J nell'esempio);

assolutamente eliminabili, se coperti dal nucleo della funzione;

secondari, se essenziali per la funzione ridotta come al passo 4 (F);

superflui, se comunque non presenti nella copertura minima (D);

alternativi, se sono presenti in alternativa in distinte forme minime (B e C di fig. 8.1).

Altri problemi di minimizzazione

Funzioni incompletamente specificate

Per funzioni incompletamente specificate l'impiego delle condizioni di indifferenza può tornare utile in quanto per rappresentarla si può scegliere la funzione compatibile a costo minimo.

Dette:

y₁ la funzione compatibile con y ed avente tutti i punti di indifferenza uguali ad 1

y_o la funzione compatibile con tutti i punti di indifferenza posti a 0

la minimizzazione procede come segue:

si ricercano tutti gli implicanti primi PI₁ di y₁, con esclusione di quelli che coprono solo punti di indifferenza;

si studia la copertura di y_o con l'insieme PI₁,

Esempio 1

Per la funzione di fig. 9.1a, si ha: e dalla matrice di copertura di y_o con (fig. 9.1b), si ricava che il nucleo è e copre tutta la funzione; pertanto risulta

Fig. 9.1 - Funzione incompletamente specificata:

a) Mappa, b) Tabella di copertura

In particolare, ai mintermini P_o e P₄, impiegati per ottenere y_min, si è associato il valore 1, mentre a P₁ si è associato uno 0; y_min rappresenta la forma minima fra tutte le otto funzioni compatibili di y in forma elementare di tipo P.

Esempio 2

Data la funzione

avente come don't care P₂, P₇, P₁₃, P₁₄, si trovano i primi implicanti di y_l (fig. 9.2a), ottenendosi: PI₁ =

a)

b)

Fig. 9.2 - Ricerca dei primi implicanti per y_l (a) e copertura di y₀ (b,c).

Si costruisce poi la matrice di copertura di y₀ con i primi implicanti PI₁ (fig. 9.2b): si ricava che il nucleo è costituito da (essenziale per P₉). Eliminando la riga F e le colonne 8, 9, 12, si ha la tabella di fig. 9.2c, nella quale risultano uguali (e quindi reciprocamente dominatesi) le coppie di righe (A,C), (D,E), (B,G); le prime due hanno il medesimo numero di letterali e quindi sono del tutto equivalenti, nella terza B ha un letterale di più di G e quindi, avendo un maggior costo, viene eliminata. L'insieme di righe rimanenti è dunque , tutti implicanti essenziali secondari e la forma minima risulta:

y = F + G + (A oppure C) + (D oppure E)

per le quali si ha CL = l0, CP = 5, CI = 14.

Minimizzazione in forma S

La forma minima in prodotti di somme (funzioni a due livelli OR-AND) può essere ottenuta con un procedimento duale di quello esposto, ove quindi si scambiano i ruoli fra 0 e 1. In particolare, nel delle mappe di Karnaugh si pongono in evidenza gli 0 piuttosto che gli 1 e le clausole-somma sono individuate leggendo i letterali affermati in corrispondenza degli 0 e negati in corrispondenza degli 1.

Si noti che

Infatti, ha i suoi 0 ovunque y ha gli 1 ed i due procedimenti di minimizzazione sono l'uno il duale dell'altro.

Quanto sopra consente di procedere in ogni caso con il più agevole metodo delle forme in somme di prodotti.

Esempio 3

Figura 9.3 - Minimizzazioni in forma P ed S

La funzione di fig. 9.3a che in forma P minima è , in forma S risulta (fig.9.3b):

oppure

e la funzione di fig. 9.3c che in forma P minima è (oppure , in forma S risulta (fig.9.3d):

Le due funzioni sono l'una il complemento dell'altra (limitatamente ai punti di non specificazione) ed esemplificano anche la dualità fra forme P ed S.

Si noti che, al di la della forma, nel caso di funzioni non completamente specificate, il complemento di una funzione in forma minima non è in generale uguale alla forma minima del suo complemento.

Esempio 4

Nell'esempio 3, il complemento di y è

mentre la forma minima del complemento è (cfr. esempio precedente)

La differenza è nei quattro punti centrali di non specificazione, che in un caso sono assunti eguali a 0 e nell'altro a 0.

Forme minime NAND e NOR

Per le reti NAND (NOR) a due livelli si può adoperare la forma minima AND-OR (OR-AND) in base a quanto riportato nel paragrafo 5: infatti la trasformazione da AND-OR (OR-AND) a NAND (NOR) non comporta variazioni della funzione costo, in nessuna delle tre definizioni date nel paragrafo 6. Per la minimizzazione di funzioni con più di 2 livelli, particolarmente interessante nel caso di reti NAND e NOR, sono stati proposti diversi algoritmi non trattati in questo testo.

Minimizzazione simultanea di più funzioni

Nel caso che si debba procedere alla minimizzazione di m funzioni delle medesime n variabili sul tipo delle (2.2), ovvero di una rete combinatoria a più uscite, il costo complessivo non è in generale la sommatoria dei costi minimi delle singole funzioni, in quanto, come illustrato in fig. 2.2, è possibile trovare soluzioni ottime impiegando alcune porte di primo livello in comune fra più uscite.

Esempio 5

Siano date le tre funzioni in forma minima

la cui realizzazione separata avrebbe un costo CI = 21; peraltro la copertura di y₃ può anche essere ottenuta con la funzione

che può essere realizzata impiegando le porte già disponibili rispettivamente per ; la rete quindi può essere costruita come nello schema di fig. 9.4 con un costo CI = 17, che minimizza le 3 funzioni nel loro complesso, nonostante che le due forme proposte di abbiano costo equivalenti .

fig. 9.4 - Esempio di minimizzazione di rete a più uscite.

Pertanto la minimizzazione per le reti a più uscite non deve essere realizzata separatamente: è preferibile utilizzare il metodo tabellare, includendo in tabella tutti i mintermini comuni e non comuni, specificando su apposite colonne a quali uscite si riferiscono in modo da consentire successivamente la copertura individuale, che comunque deve essere garantita; la matrice di copertura avrà sulle righe tutti i primi implicanti così ricavati; mentre le colonne saranno suddivise in tanti sottoinsiemi quante sono le uscite e il procedimento illustrato nel precedente paragrafo va applicato ad ogni sottoinsieme.

È evidente che questo procedimento diventa particolarmente oneroso per m e n maggiori di qualche unità, per cui di solito ci si limita a determinare le varie forme minime alternative individuali, verificando successivamente la possibilità di semplificazioni del tipo di fig. 9.4.

Le funzioni XOR e EQ

              

              

La terza si ottiene dalla prima sommando x and not x e y and not y, in essa il costo di porta, nella ipotesi di costo effettivo della NOT, si riduce dal valore 5 al valore 4, in quanto si eliminano le due NAND per la negazione di x e di y sostituendole con una unica .

Le funzioni OR esclusivo ed equivalenza non costituiscono un insieme funzionalmente completo, ma essendo

                                 

è possibile esprimere il NOT mediante XOR o EQ e quindi gli insiemi (AND, XOR) (AND, EQ), (OR, XOR) e (OR, EQ) sono insiemi f.c.

Le funzioni di parità e disparità

Dato un insieme X di n variabili, diremo p(X) funzione parità di X una funzione che vale 'l' se è pari il numero di valori '1' di X, '0' altrimenti; diremo funzione disparità di X il complemento della funzione di parità

                     

Per n = 2

   

in generale

            

costi convenzionali

CP = 2^n-l + 1 CI = (n + 1) ^. 2^n-l

Analogamente

            

Per 3 variabili si ha:

                           

Si noti che:

 

e quindi

                   

La funzione disparità gode della proprietà associativa;

In termini algebrici, ciò così si esprime:

d(X) = d(d(X₁), d(X₂). d(X_n)       

Per la funzione di parità l'associatività non è sempre valida|:

dove è a seconda dei casi la funzione di parità o di disparità.

Fruttando la proprietà associativa della d(X) è possibile costruire forme della funzione d(X) a più livelli, di costo inferiore.

Per tre variabili, si ha ad esempio:

d(a, b, c) = d(d(a, b), c) = (a b) c = a b c

e per quattro:

d(x₁, x_2, x_3, x₄) = d(d(x₁, x₂), d(x_3, x₄)) = (x₁ x₂) (x₃ x₄)

In generale per funzioni di n variabili si possono adoperare m funzioni componenti di 2, 3 o 4 variabili su livelli in una 'struttura ad albero'

Rete di disparità per 27 variabili: k=3, =3, m=13.

Fig. 11.2 - Rete di disparità con k=3. a) per 8 variabili: =2, m=4 (1da 2)

b) per 16: =3, m=8 (1da 2); c) per 15: =3, m=7 (tutte da 3)

12. Decomposizione funzionale semplice disgiunta

Una funzione booleana f(X) si dice decomposta funzionalmente se viene espressa come funzione di funzioni, secondo il concetto generale espresso nella (II.3.2).

Particolare tipo di decomposizione funzionale è quella delle forme canoniche o, più in generale, quella delle forme a due livelli; altri tipi di decomposizione funzionale sono studiati per costruire forme di funzioni a più livelli, come ad esempio le funzioni di disparità realizzate secondo la (11.7).

A partire dalla forma normale ed applicando i postulati dell'algebra, si possono ottenere diverse forme a più livelli di una funzione data.

Ad esempio, posto

y = f(a, b, c, d) = (0, 3, 5, 6, 9, l0, 12, 15)

ponendo in evidenza i letterali di a e b fra coppie di mintermini consecutivi si ha:

Poiché la f è la funzione di parità delle variabili a, b, c, d, la forma cui si perviene esprime la funzione secondo la (11.8), avendo suddiviso l'insieme delle variabili in due sottoinsiemi (a, b) e (c, d). Altre possibili decomposizioni di f, avendo posto sono:

I gradi di libertà della decomposizione sono notevoli e possono essere condizionati da scelte dipendenti da:

forma preventivamente assegnata alla funzione,

funzioni prescelte come funzioni componenti,

suddivisione dell'insieme X delle variabili indipendenti in diversi sottoinsiemi a ciascuno dei quali si applica una funzione al primo livello.

In particolare la decomposizione dicesi semplice per e disgiunta se i sottoinsiemi sono disgiunti f. L'esempio di cui sopra è una decomposizione semplice disgiunta.

Particolarmente interessanti sono le decomposizioni ottenute nella forma di fig. 12.1, nelle quali la f(X) viene realizzata mediante una 'cascata' delle funzioni componenti g_i, date da

   y₀ f (12.1)

Fig. 12.1 - Decomposizione in cascata

Poniamoci allora il problema di cercare una decomposizione semplice disgiunta di una f(X) nella forma (12.1), tale cioè che si arresti al livello f=y₂. Sarà poi possibile allungare la cascata cercando una eventuale decomposizione di g₂ e così via. È necessario trovare la partizione (X₁, X₂) di X e le funzioni g₁ e g₂; al fine di ottenere

                           (12.2)

Ovviamente, non è detto che tale decomposizione esista.

Per verificare se è possibile realizzare una decomposizione semplice disgiunta, avendo partizionato X nei due sottoinsiemi X₁ e X₂, si può rappresentare f(X) in una tabella - detta matrice di decomposizione -, con tutte le combinazioni di X₁ sulle colonne e di X₂ sulle righe (o viceversa)[3] ; si dice allora molteplicità della tabella il numero di colonne distinte della funzione.

È facile allora dimostrare che:

Infatti, escludendo il caso banale di M=1 (le colonne sono tutte eguali, y₂ non è funzione di y₁), per M=2 esiste una funzione y₁=g₁(X₁) che associa ad una delle due colonne distinte il valore 0 e all'altra 1 (o viceversa) e la f(X) si può esprimere in funzione di y₁ e delle X₂, come nella (12.2); al contrario, per M>2 tale funzione non esiste. ???

Esempio 12.1

Per la funzione f(a, b, c, d) = Σ(l, 2, 4, 7, 8, 11, 13, 14), avendo posto X₁=(a, b) X₂ = (c,d). si ha che la tabella ha molteplicità 2 e ponendo y₁=0 in corrispondenza delle colonne 00, 11 e y₁=1 nelle altre, si ha (fig. 12.2):

			ab=01,10

f(X) g₂

Fig. 12.2 - Esempio di decomposizione semplice disgiunta: la tabella

Ne deriva lo schema di fig. 12.3. dove g₂ è la scatola nera racchiusa nel rettangolo tratteggiato.

Fig. 12.3 - Esempio di decomposizione semplice disgiunta: la rete

Applicando ancora iterativamente la decomposizione funzionale a g₂, si può scomporre l'insieme in e si otterrebbe ancora una tabella a molteplicità 2, con

e quindi lo schema di fig. 12.3 nel quale la scatola nera di g2 diventa trasparente.