Algebre booleane e progetto logico dei calcolatori digitali/Funzioni booleane

Indice del libro


Definizioni

modifica

Si definisce variabile binaria, quella variabile che ha per dominio l'insieme {0,1} composto di 2 elementi. Il prodotto cartesiano di tale insieme per se stesso, cioè l' insieme delle coppie ordinate (a1,a2) di elementi in {0,1}, verrà indicato con {0,1}2 = {0,1}x{0,1}.

Iterando il ragionamento, l'insieme {0,1}n={0,1}x{0,1}x...{0,1} sarà composto dalle n-ple ordinate a1, a2...an), di elementi in {0,1}. A questo punto è possibile definire la funzione booleana di n variabili(od anche funzione binaria, o funzione di commutazione) come una applicazione di {0,1}n in {0,1}.

Abbiamo già detto che una funzione booleana può essere espressa o mediante una classe di espressioni booleane equivalenti, oppure mediante una tabella della verità nella quale in corrispondenza di ogni combinazione delle n variabili deve scrivere il valore associato della funzione. Se si assume come convenzione di scrivere le combinazioni delle n variabili in ordine crescente, cioè in modo tale che leggendole come numeri binari, esse rappresentino la sequenza di numeri da 0 a 2n-1, allora non sarà necessario scrivere tutta la tabella, ma risulterà sufficiente scrivere solo i valori della funzione.

 

Le tabelle della verità possono essere anche ‎di tipo rettangolare, e cioè le n variabili sono ripartite in due insiemi disgiunti (x1,...,xs) e (x{s+1},...,x{n})

A ciascuno dei due insiemi si assegna una delle due dimensioni del rettangolo e su di essa l'insieme di variabili assume tutte le possibili combinazioni: a ogni combinazione corrisponde una colonna (o una riga).

Spieghiamo con un esempio il funzionamento del nuovo tipo di tabella, paragonandolo alla tabella usata fino ad ora nella quale però, per brevità, non prenderemo in esame le combinazioni che corrispondono ad un valore nullo della funzione.

Sia f(x1, x2, x4, x5) definita dalla tabella (a) qui sotto:

 

Volendo riscrivere la tabella, questa volta in forma rettangolare procediamo prima nel seguente modo:

Consideriamo, ad esempio, la 5a colonna. Ad essa corrisponde l'assegnazione (x1, x2, x3)=(100) ed alla 2a riga corrisponde l'assegnazione (x4 x5)=(01). Se ora consideriamo contemporaneamente le due assegnazioni, esse corrispondono all'unica (x1, x2, x3, x4, x5)=(10001). A tale combinazione, nella tabella (a), corrisponde il valore 1 (della funzione); Nella tabella b (a fianco), allora, scriveremo all'intersezione della 5a colonna con la 2a riga il valore 1.

 

La tabella completa avrà la forma della tabella b2 accanto:

È sotto questa forma che utilizzeremo soprattutto le tabelle della verità: messa infatti sotto questa forma conveniente (diagramma di Karnaugh), una simile tabella è un mezzo per la semplificazione delle espressioni algebriche.

Inoltre questa forma serve ogni qualvolta si vuole mettere in rilievo il ruolo di una certa variabile; in tal caso le si attribuirà un lato della tabella.

Altri modi di definire una funzione booleana

modifica

Vettore caratteristico

modifica

La colonna di destra della tavola della verità, del 1° tipo, è un vettore binario.

 

Se si conservano le convenzioni fatte sulle combinazioni delle variabili, la conoscenza di questo vettore è sufficiente a definire la funzione. Chiameremo tale vettore vettore caratteristico della funzione f e lo denoteremo con:

 

dove Vk è il valore della funzione associata a quella combinazione binaria delle variabili, che rappresenta il numero k. (Esempio figura accanto)

Rappresentazione decimale

modifica

Prima rappresentazione

modifica

Il Vettore Vf costituisce la rappresentazione binaria di un numero intero compreso tra 0 e 2n-1.

Si può allora definire la funzione mediante l'equivalenza decimale di questo numero:

 

Esempio:

 
 

Seconda rappresentazione

modifica

Forniamo una 2a rappresentazione del vettore caratteristico: rappresentazione molto usata anche se meno compatta della prima

Se si esamina l'esempio 1°, si vede che il vettore caratteristico assume il valore 1 in corrispondenza a quelle combinazioni che rappresentano i numeri decimali 0,2,5,6. Allora si può rappresentare il vettore caratteristico, fornendo quest'insieme di valori decimali.

Esempio:

 
 

Operazioni sulle funzioni booleane

modifica

Usando le tavole della verità, che ci permettono di definire le funzioni booleane, possiamo ora definire le operazioni di somma, prodotto e complementazione delle funzioni.

 

Somma di 2 funzioni f+g

modifica

Date le due funzioni f e g, a n variabili, con i vettori caratteristici Vf e Vg, la funzione somma di f è g è quella il cui vettore caratteristico è Vf+Vg (vedi 6.4.4).

Si ha dunque per definizione:

 

Prodotto di 2 funzioni: f*g

modifica
 

In maniera analoga, il prodotto di f e g è la funzione di vettore caratteristico Vf*Vg:

 

=== Complemento di una funzione:   ===o

 

È la funzione notata   e definita mediante  

Per definizione si ha quindi:

 

Funzione identicamente nulla: (0)

modifica

È la funzione il cui vettore caratteristico è il vettore nullo.

Funzione identicamente uguale a 1

modifica

È la funzione il cui vettore caratteristico è il vettore (1).

L'insieme delle funzioni booleane a n variabili possiede 2n elementi distinti.Infatti ogni vettore caratteristico è formato da una sequenza di 2n elementi: l'insieme delle funzioni sarà dato da tutte le possibili combinazioni (disposizioni con ripetizione) di questi 2n elementi; per cui avremo 22n vettori distinti.

È mediante l'aiuto dei vettori caratteristici che noi abbiamo definito sull'insieme delle funzioni booleane le operazioni +, *, -.

Questi ultimi formano un'algebra di Boole a 2N = 22n elementi e quindi segue che l'insieme delle funzioni di n variabili, munite di queste operazioni, formano ugualmente un'algebra di Boole a 2N elementi.

Espressioni algebriche di una funzione booleana

modifica

Esaminiamo ora il seguente problema: data una funzione booleana di n variabili x1...xn conosciuta mediante la sua tavola della verità, trovarne una rappresentazione algebrica.

Per fare ciò definiamo alcune funzioni di n variabili che ci saranno utili in seguito.

Prodotto fondamentale

modifica

Definizione: si chiama prodotto fondamentale o minterm a n variabili un prodotto della forma:

 
con   se   cioè  
con   se   cioè  

In altri termini un prodotto fondamentale è un prodotto di n variabili (dirette o complementate) in cui ogni variabile compare una sola volta.

Tavole della verità di un prodotto fondamentale

modifica

Affinché il prodotto

 

sia uguale a 1, è necessario e sufficiente che tutti i suoi fattori siano uguali a 1.

Cioè che si abbia:

 

Ora con riguardo a quanto detto nel par.6.6 si ha:

 

Quindi perché  =1, è necessario e suffciente che xi=ei.

 

Per cui affinché P=1 è necessario e sufficiente che si abbia:

 

Il prodotto fondamentale P è dunque uguale ad 1 quando le variabili assumono le combinazioni (e1, e2,...en); cioè quando si ha che:

 

Per esempio, il prodotto fondamentale   assumerà il valore 1 solo per la combinazione (1 0 1); cioè, se esprimiamo tale prodotto sotto forma di tabella, avremo (tabella affiancata):

Diremo che una funzione è generata da un prodotto fondamentale, quando la sua tabella (o il vettore caratteristico è del tipo di cui alla tabella mostrata, e rappresentiamo la funzione con l'espressione:

 

dove e1....en è la combinazione di valori per cui il prodotto fondamentale risulta uguale ad 1.

 

Consideriamo ora la funzione a tre variabili definita dalla tabella A e prendiamo in esame le tre funzioni f1, f2, f3 definite dalla tabella B: ora, confrontando i vettori Vf, V{f1}, V{f2}, V{f3}, è facile verificare che le quattro funzioni soddisfano la seguente relazione:

 

dove le f1, f2, f3, sono generate, ciascuna, da un prodotto fondamentale. Indichiamo quest'ultimo prodotto con mabc, dove abc è la combinazione binaria che rende uguale ad 1 tale prodotto; cioè avremo:

 

Se ora consideriamo i tre prodotti fondamentali che generano le funzioni f1,f2,f3, e trasformiamo il numero binario abc in decimale, avremo le seguenti notazioni:

 
 
 

e inoltre, essendo le tre funzioni generate da tali prodotti, si può scrivere:

 

da cui

 

È chiaro che il ragionamento effettuato nel caso di tre variabili e su di una funzione particolare, vale anche in generale; e che ogni funzione booleana si può esprimere come somma booleana dei prodotti fondamentali.

Per fare ciò si seguiranno le seguenti regole:

  1. si scrivono tutti i prodotti fondamentali corrispondenti alle combinazioni delle variabili per le quali la funzione f(x1...xn) vale 1.
  2. si forma la somma booleana di tutti questi prodotti.

L'espressione così ottenuta, costituisce una rappresentazione algebrica della funzione, chiamata prima forma canonica o forma canonica disgiuntiva. Si ha:

 

La prima forma canonica è unica: il carattere di unicità risulta direttamente dalla corrispondenza biunivoca che esiste tra i prodotti fondamentali componenti la forma canonica e le combinazioni binarie della tabella della verità per le quali la funzione vale 1.

 

Esempio

modifica

Si voglia determinare la forma canonica disgiuntiva della funzione f definita dalla tabella relativa.

Per fare ciò, determiniamo prima i tre prodotti fondamentali:

 
 
 

da ciò ne discende che la forma canonica disgiuntiva della funzione sarà:

 

Somma fondamentale

modifica

Si chiama somma fondamentale, o maxterm una espressione della forma:

 

dove, per le xiei, valgono le convenzioni fatte precedentemente.

In altri termini, una somma fondamentale a n variabili è una somma delle n variabili (dirette o complementate) dove ciascuna dellexi compare una sola volta.

Tavola della verità di una somma fondamentale di n variabili

modifica

Affinché la somma:

 

sia nulla, è necessario e sufficiente che tutti i suoi termini siano nulli: cioè che si abbia:

 

Dunque, perché S sia nulla, è necessario e sufficiente che la combinazione delle variabili sia identica a quella delle ei complementate.

Riassumendo: la somma S ha una tavola della verità che è nulla in corrispondenza ad una sola combinazione delle variabili:

 

e vale 1 per tutte le altre.

Inversamente, ogni funzione avente una tavola della verità di questo tipo, cioè nulla per una sola combinazione (a1,a2,...,an) delle variabili, potrà essere rappresentata con una somma fondamentale:

 

cioè se (a1 a2...an) è l'unica combinazione che annulla la f potremo scrivere tale funzione come somma delle xi aventi, per indice superiore, i valori complementari della n-pla.

Esempio

modifica
 

1) La somma fondamentale

 

è nulla per la combinazione 0110 e per questa soltanto.

2) Si consideri la funzione definita dalla tabella affiancata: essendo 011 l'unica combinazione che annulla la f si può scrivere:

 
 

3) Si considerino le funzioni f,f1,f2,f3 definite dalla tabella sulla destra:

esaminando 9 vettori caratteristici delle funzioni si vede che si può scrivere f=f1 f2 f3, dove f1, f2, f3, sono funzioni generate da somme fondamentali associate agli zeri della colonna f

Si ha inoltre che:

 
 
 

da cui

 .

Forma canonica congiuntiva di una funzione a n variabili

modifica

Ragionando come nel caso della forma disgiuntiva, si vede che ogni funzione potrà essere espressa come un prodotto di somme fondamentali, utilizzando le regole seguenti:

  1. scrivere tutte le somme fondamentali corrispondenti alle combinazioni per le quali la funzione f=(x1...xn) vale zero.
  2. scrivere il prodotto di queste somme.

L'espressione così ottenuta, costituisce una rappresentazione algebrica della funzione, chiamata: seconda forma canonica o forma canonica congiuntiva.

Si scriverà in generale:

 
 

Esempio. Si voglia determinare la forma canonica congiuntiva della funzione tabellata a fianco:

Le somme fondamentali sono:

 
 
 
 

e la funzione f avrà la seguente forma canonica congiuntiva:

 

La seconda forma canonica, come la prima, è unica. Ciò discende dall'identico processo logico seguito.

Un'altra considerazione è che nella forma canonica disgiuntiva i termini il cui coefficiente risulta essere   scompaiono se f è nulla. Nella forma canonica congiuntiva, i fattori scompaiono dal prodotto quando   vale1, cioè quando il fattore è della forma

 

Qualche notazione abbreviata

modifica

Prodotti fondamentali

 

dove   è un indice espresso nella base decimale e tale che  , mentre   è la sua rappresentazione binaria.

 

in quantoi e j sono i numeri che corrispondono all'unica combinazione binaria che rende uguale ad 1 il prodotto fondamentale.

Somme fondamentali

 

dove per   vale quanto sopra.

 

Forma canonica disgiuntiva

 

Forma canonica congiuntiva

 

poiché   se si pone  .

Funzioni duali

modifica

Data una funzione  , si chiama funzione duale la funzione   che soddisfa alla relazione

 

Proprietà duale di una funzione duale

modifica
 

infatti

 

Proprietà duale di una somma

modifica
 

Proprietà duale di un prodotto

modifica
 

Proprietà duale di un complemento

modifica
 

Proprietà duale di una funzione costante

modifica

Poiché stiamo considerendo un'algebra a due elementi 0 e 1, le funzioni costanti possono assumere solo l'uno o l'altro di questi due valori, per cui se:

 

allora si ha che

 

in quanto il valore di una funzione costante non dipende dall'assegnazione delle variabili. Risulta allora:

 

Nella stessa maniera si ha che se

 

allora

 
Riassumendo possiamo dire che, data una espressione rappresentante una funzione, si ottiene l'espressione della funzione duale sostituendo a + con  ,   con + e lasciando le variabili (complementate o no) tali e quali e sostituendo 0 con 1, e 1 con 0; regole che sono le stesse viste nel capitolo 6 in generale.

Funzioni particolari

modifica

Nel capitolo 5 sono state definite le funzioni di AND, OR, PEIRCE, SHEFFER, di due argomenti; vogliamo ora definire di nuovo tali funzioni attribuendo loro n argomenti. <con ciò non intendiamo dire che la singola funzione opera ripetutamente fino all'esaurimento delle variabili, bensì che essa viene considerata una operazione n-aria che opera contemporaneamente sulla n-pla di argomenti.

Questa osservazione rivela la sua importanza in considerazione del fatto che non tutte le funzioni soprannominate godono della proprietà associativa e quindi, se la funzione non opera contemporaneamente su tutti gli argomenti, otterremmo risultati diversi a seconda delle associazioni fatte, e di conseguenza arbitrari.

Funzione di AND a n variabili

modifica

È la funzione che vale

 

si scrive

 

Funzione di OR a n variabili

modifica

È la funzione che vale

 

si scrive

 

Funzione di PEIRCE a n variabili o funzione di NOR

modifica

È la funzione che vale

 

e si scrive

 

questa funzione è definita anche per n=1 cioè:

 

Per la funzione PEIRCE non vale la legge associativa.

Funzione di SHEFFER a n variabili o funzione di NAND

modifica

È la funzione che vale

 

si scrive

 

anche la funzione di SHEFFER è definita se n=1 cioè  , e non gode della proprietà associativa.

Proprietà degli operatori e /

modifica

Espressione degli operarori   e / mediante (+), ( ), (-)

modifica

Tenendo presente le definizioni ora date, vediamo che la funzione PERIRCE vale 1 per una sola combinazione di valori delle variabili, ma allora possiamo facilmente scrivere tale funzione, mediante la 1a forma canonica, come il prodotto fondamentale m0 cioè:

 

o ancora, tenendo presente le regole della complementazione

 

Viceversa, la funzione di SHEFFER, si annulla in un solo caso; quindi possiamo esprimerla facilmente, mediante la 2a forma canonica, come la somma fondamentale M0 cioè:

 

o ancora, tenendo presente le regole della complementazione

 

Proprietà di dualità

modifica

Vedremo ora le proprietà di complementazione, di pseudo associatività e altre, di   e /

Consideriamo la funzione di PEIRCE   a n variabili.

Si può scrivere:

 

Dunque la funzione duale della funzione di Peirce ( ) è la funzione di Sceffer (/).

Viceversa: considerando la funzione di Sheffer x1/x2/.../xn a n variabili, si può scrivere:

 

Quindi la funzione duale di Sheffer (/) è la funzione di Peirce  .

Consideriamo la funzione di Peirce espressa mediante l'operazione (*), si ha:   complementando ambo i membri si ottiene:

 

ma la funzione di Sheffer era stata espressa mediante una somma cioè:

 

da cui confrontando la (a) con la (b) risulta:

 

Ripetendo il ragionamento sulla funzione di Sheffer, espresso mediante la somma si ottiene:

 

Le ultime due relazioni generalizzano in un certo senso la formula di De Morgan:

 
 

Pseudo associatività

modifica

Come abbiamo già detto, gli operatori di Sheffer e di Peirce non sono associativi. Consideriamo le espressioni:

 
 

si ha che  , infatti:

 
 

Dunque, per un insieme di dati valori ABC, F e F' non sono necessariamente uguali. In altri termini l'operazione   non è associativa. Si vedrà in maniera analoga che l'operazione / non è associativa.

Tuttavia tali operatori godono di una notevole proprietà detta pseudo associatività:

 

Dimostrazione:

 
 

Queste proprietà si generalizzano, nel caso di n variabili, come segue:

 
 

Dalla definizione dell'operatore   si deducono le seguenti relazioni:

 
 
 

Espressione degli operatori ( ),(+),(-)

modifica

Mediante gli operatori   e (/) (n variabili)

Operazione  
 

ponendo < 

 
Operazione (+)

In maniera analoga si ha :

 

ponendo  

 
Complemento (-)

È facile verificare dalle definizioni che

 

Analogamente:

 

Inoltre grazie a delle proprietà già viste è possibile esprimere il complemento anche nel modo seguente:

 
 }

Da ciò è facile vedere che:

 

Forme canoniche di Sheffer (n variabili)

modifica
 

A partire dalle due forme canoniche è facile ottenere delle espressioni utilizzanti   e /, che si possono chiamare forme canoniche di Sheffer.

Consideriamo la funzione F a tre variabili, A,B,C, definita dalla tabella collaterale. Per la prima forma canonica abbiamo che:

 
a) possiamo allora scrivere:
 

(teorema di De Morgan e doppia negazione)

Per la definizione di / si ha:

 

Quindi: conoscendo la prima forma canonica, si ottiene una espressione della funzione mediante l'operatore di /, sostituendo semplicemente tutti i segni operativi (+), (*) con / e racchiudendo tra parentesi i gruppi di lettere corrispondenti ai prodotti fondamentali.

b) Consideriamo ora la seconda forma canonica:
 

possiamo scrfivere:

 
 
 

Donde la regola:

a partire dalla seconda forma canonica, si ottiene una espressione della funzione mediante l'operatore   sostituendo (+),   con (  e racchiudendo in parentesi i gruppi corrispondenti alle somme fondamentali della seconda forma canonica.

Funzione OR esclusivo (XOR)

modifica

Anche questa funzione l'abbiamo incontrata già, e sommariamente trattata al capitolo 5.3.

Oltre che con il nome di OR esclusivo, questa funzione la si può incontrare anche sotto il nome di inequivalenza, dilemma e addizione modulo 2. Mentre i primi tre nomi traggono origine dall'algebra delle proposizioni, addizione modulo 2 trova la sua giustificazione nel fatto che, se si considera come risultato di una somma la classe resto mod.2 a cui appartiene il risultato vero, allora si ottengono gli stessi valori della funzione XOR.