Algebre booleane e progetto logico dei calcolatori digitali/Funzioni booleane

Wikibooks, manuali e libri di testo liberi.
Jump to navigation Jump to search

Parte prima: Algebre booleane

1.1 IntroduzioneAlgebre booleane e progetto logico dei calcolatori digitali/Introduzione
1.2 Sistemi di numerazione, aritmetica binariaAlgebre booleane e progetto logico dei calcolatori digitali/Sistemi di numerazione, aritmetica binaria
1.3 CodiciAlgebre booleane e progetto logico dei calcolatori digitali/Codici
1.4 Teoria della commutazioneAlgebre booleane e progetto logico dei calcolatori digitali/Teoria della commutazione
1.5 Algebra delle classi - Algebra della logicaAlgebre booleane e progetto logico dei calcolatori digitali/Algebra delle classi - Algebra della logica
1.6 Algebre booleaneAlgebre booleane e progetto logico dei calcolatori digitali/Algebre booleane
1.7 Funzioni booleaneAlgebre booleane e progetto logico dei calcolatori digitali/Funzioni booleane
1.8 Rappresentazione geometrica delle funzioni booleane e loro minimizzazioneAlgebre booleane e progetto logico dei calcolatori digitali/Rappresentazione geometrica delle funzioni booleane e loro minimizzazione

Parte seconda: Circuiti logici e calcolatori digitali

2.1 Circuiti logici e di memoriaAlgebre booleane e progetto logico dei calcolatori digitali/Circuiti logici e di memoria
2.2 Circuiti di un calcolatore digitale (a)Algebre booleane e progetto logico dei calcolatori digitali/Circuiti di un calcolatore digitale (a)
2.3 Circuiti di un calcolatore digitale (b)Algebre booleane e progetto logico dei calcolatori digitali/Circuiti di un calcolatore digitale (b)
2.4 Progetto logico di un calcolatore digitaleAlgebre booleane e progetto logico dei calcolatori digitali/Progetto logico di un calcolatore digitale


Indice

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.

Combinazioni di variabili con valore della funzione pari ad 1.png

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:

Tabella rettangolare.png

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 x59=(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.

Tabella rettangolare b2.png

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.

Vettore caratteristico.png

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.

F+g.png

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]

Prodotto di 2 funzioni.png

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

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

Complemento di una funzione.png

È 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 Errore del parser (errore di sintassi): {\displaystyle x_i^{e_i}=x_i\qquad se\quad e_i=1\qquad cioè\quad x^1=x}
con Errore del parser (errore di sintassi): {\displaystyle x_i^{e_i}=\bar x_i\qquad se\quad e_i=0\qquad cioè\quad x^0=\bar x}

In altri termini un prodotto fondamentale è un prodotto di n variabili (dirette o complamentate) 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.

Prodotto fodamentale 101.png

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.

Tabelle A e B.png

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.

Tabella della funzione f.png

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]

Esempio somma fondamentale.png

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:

Definizione tabellare di funzioni.png

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:

Forma canonica congiuntiva di una funzione a tre variabili.png

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

Errore del parser (errore di sintassi): {\displaystyle poiché\quad \bar e_1\bar e_2....\bar e^n=2^n -1 -i\qquad\qquad se\ si\ pone\quad i=e_1 e_2....e_n.}

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 dedfinire 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]

Definizione tabellare di una funzione.png

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.