Algebre booleane e progetto logico dei calcolatori digitali/Funzioni booleane

Definizioni

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 (a₁,a₂) di elementi in {0,1}, verrà indicato con {0,1}² = {0,1}x{0,1}.

Iterando il ragionamento, l'insieme {0,1}ⁿ={0,1}x{0,1}x...{0,1} sarà composto dalle n-ple ordinate a₁, a₂...a_n), 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}ⁿ 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 2ⁿ-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 (x₁,...,x_s) 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(x₁, x₂, x₄, x₅) definita dalla tabella (a) qui sotto:

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

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

La tabella completa avrà la forma della tabella b₂ 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

Vettore caratteristico

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:

$V_{f}=(V_{0},V_{1},...V_{k},...V_{2^{n}-1})$

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

Rappresentazione decimale

Prima rappresentazione

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

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

$N_{10}^{f}=\sum _{i=0}^{2^{n}-1}v_{i}*2^{n}-1-i$

Esempio:

$V_{f}=(10100110)$

$N_{10}^{f}=2^{7}+2^{5}+2^{2}+2^{1}=166$

Seconda rappresentazione

Forniamo una 2^a 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:

$V_{f}=(10100110)=(0,2,5,6)$

$1^{a}\ rappr.\qquad \qquad 2^{a}\ rappr.$

Operazioni sulle funzioni booleane

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

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

Si ha dunque per definizione:

$V_{f+g}=V_{f}+V_{g}$

Prodotto di 2 funzioni: f*g

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

$V_{f*g}=V_{f}*V_{g}$

=== Complemento di una funzione: $\lnot f$ ===o

È la funzione notata $\lnot f$ e definita mediante $\lnot V_{f}$

Per definizione si ha quindi:

$\lnot V_{f}=V_{\lnot f}$

Funzione identicamente nulla: (0)

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

Funzione identicamente uguale a 1

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

L'insieme delle funzioni booleane a n variabili possiede 2ⁿ elementi distinti.Infatti ogni vettore caratteristico è formato da una sequenza di 2ⁿ elementi: l'insieme delle funzioni sarà dato da tutte le possibili combinazioni (disposizioni con ripetizione) di questi 2ⁿ elementi; per cui avremo 2²ⁿ 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 2^N = 2²ⁿ elementi e quindi segue che l'insieme delle funzioni di n variabili, munite di queste operazioni, formano ugualmente un'algebra di Boole a 2^N elementi.

Espressioni algebriche di una funzione booleana

Esaminiamo ora il seguente problema: data una funzione booleana di n variabili x₁...x_n 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

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

$P=x_{1}^{e_{1}}*x_{2}^{e_{2}}*...*x_{n}^{e_{n}}=\sum _{i=1}^{i=n}x_{i}^{e_{i}}$

con $x_{i}^{e_{i}}=x_{i}$ se $e_{i}=1$ cioè $x^{1}=x$

con $x_{i}^{e_{i}}={\bar {x}}_{i}$ se $e_{i}=0$ cioè $x^{0}={\bar {x}}$

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

Affinché il prodotto

$P=e_{1}^{e_{1}}\cdot x_{2}^{e_{2}}\cdot ....\cdot x_{n}^{e_{n}}$

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

Cioè che si abbia:

$e_{i}^{e_{i}}=1\qquad (i=1,2.....n)$

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

$e_{i}^{e_{i}}{\begin{cases}=x_{i}&{\mbox{se}}\quad e_{i}=1\\={\bar {x}}_{i}&{\mbox{se}}\quad e_{i}=0\end{cases}}$

Quindi perché $e_{i}^{e_{i}}$=1, è necessario e suffciente che x_i=e_i.

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

$x_{i}=e_{i}\qquad (i=1,2,....,n)$

Il prodotto fondamentale P è dunque uguale ad 1 quando le variabili assumono le combinazioni (e₁, e₂,...e_n); cioè quando si ha che:

$x_{1}=e_{1}\quad x_{2}=e_{2},....x_{n}=e_{n})$

Per esempio, il prodotto fondamentale $x_{1}^{1}x_{2}^{0}x_{3}^{1}$ 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:

$f=P=e_{1}^{e_{1}}\cdot ..........\cdot e_{n}^{e_{n}}$

dove e₁....e_n è 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 f₁, f₂, f₃ definite dalla tabella B: ora, confrontando i vettori V_f, V_{f1}, V_{f2}, V_{f3}, è facile verificare che le quattro funzioni soddisfano la seguente relazione:

$f=f_{1}+f_{2}+f_{3}$

dove le f₁, f₂, f₃, sono generate, ciascuna, da un prodotto fondamentale. Indichiamo quest'ultimo prodotto con m_abc, dove abc è la combinazione binaria che rende uguale ad 1 tale prodotto; cioè avremo:

$m_{abc}=x_{1}^{a}\cdot x_{2}^{b}\cdot x_{3}^{c}$

Se ora consideriamo i tre prodotti fondamentali che generano le funzioni f₁,f₂,f₃, e trasformiamo il numero binario abc in decimale, avremo le seguenti notazioni:

$m_{001}=x_{1}^{0}x_{2}^{0}x_{3}^{1}={\bar {x}}_{1}{\bar {x}}_{2}x_{3}=m_{1}\qquad (001_{2}=1_{10})$

$m_{010}=x_{1}^{0}x_{2}^{1}x_{3}^{0}={\bar {x}}_{1}x_{2}{\bar {x}}_{3}=m_{1}\qquad (010_{2}=2_{10})$

$m_{100}=x_{1}^{1}x_{2}^{0}x_{3}^{0}=x_{1}{\bar {x}}_{2}{\bar {x}}_{3}=m_{1}\qquad (100_{2}=4_{10})$

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

$f_{1}=m_{1}\qquad f_{2}=m_{2}\qquad f_{3}=m_{4}$

da cui

$f=f_{1}+f_{2}+f_{3}=m_{1}+m_{2}+m_{4}={\bar {x}}_{1}{\bar {x}}_{2}x_{3}+{\bar {x}}_{1}x_{2}{\bar {x}}_{3}+x_{1}{\bar {x}}_{2}{\bar {x}}_{3}$

È 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(x₁...x_n) 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:

$f(x_{1},..x_{i},..x_{n})=\sum _{e_{1}..e_{n}=0}^{e_{1}..e_{n}=2^{n}-1}$

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

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

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

$m_{001}=m_{1}=x_{1}^{0}x_{2}^{0}x_{3}^{1}={\bar {x}}_{1}{\bar {x}}_{2}x_{3}$

$m_{101}=m_{5}=x_{1}^{1}x_{2}^{0}x_{3}^{1}=x_{1}{\bar {x}}_{2}x_{3}$

$m_{111}=m_{7}=x_{1}x_{2}x_{3}$

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

$f={\bar {x}}_{1}{\bar {x}}_{2}x_{3}+x_{1}{\bar {x}}_{2}x_{3}+x_{1}x_{2}x_{3}$

Somma fondamentale

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

$S=e_{1}^{e_{1}}+...+x_{i}{e_{i}}.....+x_{n}^{e_{n}}=\sum _{i=0^{i}=n}x_{i}^{e_{i}}$

dove, per le x_i^e_i, valgono le convenzioni fatte precedentemente.

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

Tavola della verità di una somma fondamentale di n variabili

Affinché la somma:

$S=x_{1}^{e_{1}}+...+x_{i}^{e_{i}}+...+x_{n}^{e_{n}}$

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

$x_{i}^{e_{i}}=0\qquad (i=1,2,.....,n)\qquad \qquad \ ovvero\ x_{i}={\bar {e}}_{i}$

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

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

$({\bar {e}}_{1},{\bar {e}}_{2}...{\bar {e}}_{n})$

e vale 1 per tutte le altre.

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

$f=x_{1}^{{\bar {a}}_{1}}+x_{2}^{{\bar {a}}_{2}}+...+x_{n}^{{\bar {a}}_{n}}$

cioè se (a₁ a₂...a_n) è l'unica combinazione che annulla la f potremo scrivere tale funzione come somma delle x_i aventi, per indice superiore, i valori complementari della n-pla.

Esempio

1) La somma fondamentale

$x_{1}+{\bar {x}}_{2}+{\bar {x}}_{3}+x_{4}=x_{1}^{1}+x_{2}^{0}+x_{3}^{0}+x_{4}^{1}$

è 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:

$f=x_{1}^{\bar {0}}+x_{2}^{\bar {1}}+x_{3}^{\bar {1}}=x_{1}+{\bar {x}}_{2}+{\bar {x}}_{3}$

3) Si considerino le funzioni f,f₁,f₂,f₃ definite dalla tabella sulla destra:

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

Si ha inoltre che:

$f_{1}=x_{1}+x_{2}+{\bar {x}}_{3}$

$f_{2}=x_{1}+{\bar {x}}_{2}+x_{3}$

$f_{3}={\bar {x}}_{1}+f_{2}+x_{3}$

da cui

$f=(x_{1}+x_{2}+{\bar {x}}_{3})\cdot (x_{1}+{\bar {x}}_{2}+x_{3})\cdot ({\bar {x}}_{1}+f_{2}+x_{3})$.

Forma canonica congiuntiva di una funzione a n variabili

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=(x₁...x_n) 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:

$f(x_{1},x_{2}....x_{n})=\prod _{e_{1}..e_{n}=0}^{e_{1}..e_{n}=2^{n}-1}[f({\bar {e}}_{1}...{\bar {e}}_{n})+x_{1}^{e_{1}}+...+x_{n}^{e_{n}}]$

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

Le somme fondamentali sono:

$f_{1}=x_{1}+x_{2}+{\bar {x}}_{3}$

$f_{2}=x_{1}+{\bar {x}}_{2}+{\bar {x}}_{3}$

$f_{3}={\bar {x}}_{1}+x_{2}+{\bar {x}}_{3}$

$f_{4}={\bar {x}}_{1}+{\bar {x}}_{2}+{\bar {x}}_{3}$

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

$f=(x_{1}+x_{2}+{\bar {x}}_{3})+(x_{1}+{\bar {x}}_{2}+{\bar {x}}_{3})+({\bar {x}}_{1}+x_{2}+{\bar {x}}_{3})+({\bar {x}}_{1}+{\bar {x}}_{2}+{\bar {x}}_{3})$

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 $f(e_{1}...e_{n})$ scompaiono se f è nulla. Nella forma canonica congiuntiva, i fattori scompaiono dal prodotto quando $f({\bar {e}}_{1}...{\bar {e}}_{n})$ vale1, cioè quando il fattore è della forma

$1+x=1$

Qualche notazione abbreviata

Prodotti fondamentali

$si\ ponga\qquad \qquad m_{i}=e_{1}^{e_{1}}\cdot x_{2}^{e_{2}}....x_{n}^{e_{n}}$

dove $i=e_{1}e_{2}...e_{n}$ è un indice espresso nella base decimale e tale che $0\leq i\leq 2^{n}-1$, mentre $e_{1}e_{2}....e_{n}$ è la sua rappresentazione binaria.

$si\ ha\qquad \qquad m_{i}\cdot m_{j}=0\qquad \qquad per\ i\neq j$

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

Somme fondamentali

$\qquad \qquad Si\ ponga\qquad \qquad M_{i}=x_{1}^{e_{1}}+x_{2}^{e_{2}}+......+x_{n}^{e_{n}}$

dove per $i=e_{1}e_{2}....e_{n}$ vale quanto sopra.

$Si\ avra\qquad \qquad M_{1}+M_{2}=1\qquad \qquad per\ i\neq j$

Forma canonica disgiuntiva

$f=\sum _{i=0}^{i=2^{n}-1}f(i)m_{i}$

Forma canonica congiuntiva

$f=\prod _{i=0}^{i=2^{n}-1}f(2^{n}-1-i)+M_{i}$

poiché ${\bar {e}}_{1}{\bar {e}}_{2}....{\bar {e}}^{n}=2^{n}-1-i$ se si pone $i=e_{1}e_{2}....e_{n}$.

Funzioni duali

Data una funzione $f(x_{1},x_{2},...,x_{n})$, si chiama funzione duale la funzione ${\tilde {f}}{(x_{1},x_{2},...x_{n})}$ che soddisfa alla relazione

${\tilde {f}}{(x_{1},x_{2},..,x_{n})}={\overline {f({\bar {x}}_{1},..,{\bar {x}}_{n})}}=f(x_{1},...,x_{n})$

Proprietà duale di una funzione duale

${\tilde {\tilde {f}}}=f$

infatti

${\tilde {\tilde {f}}}={\tilde {\tilde {(f)}}}=({\bar {\bar {f}}}({\bar {x_{1}}},...{\bar {x_{n}}}))=f(x_{1},..,x_{n})$

Proprietà duale di una somma

$\sim {\sum _{i}{x_{i}}}={\overline {\sum _{i}{\bar {x}}_{i}}}=\prod _{i}x_{i}$

Proprietà duale di un prodotto

$\sim \prod _{i}x_{i}={\overline {\prod _{i}{\bar {x}}_{i}}}=\sum _{i}x_{i}$

Proprietà duale di un complemento

$\sim ({\bar {A}})={\overline {\overline {({\bar {A}})}}}={\bar {A}}$

Proprietà duale di una funzione costante

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:

$f(x_{1},x_{2},...,x_{n})=0$

allora si ha che

$f({\bar {x}}_{1},{\bar {x}}_{2},...,{\bar {x}}_{n})=0$

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

$\sim f(x_{1},...,x_{n})={\bar {f}}({\bar {x}}_{1},...,{\bar {x}}_{n})=1$

Nella stessa maniera si ha che se

$f(x_{1},...,x_{n})=1$

allora

$\sim f(x_{1},...,x_{n})=0$

Riassumendo possiamo dire che, data una espressione rappresentante una funzione, si ottiene l'espressione della funzione duale sostituendo a + con $\bullet$, $\bullet$ 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

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

È la funzione che vale

$f(n)={\begin{cases}1,&{\mbox{quando }}x_{1}=x_{2}=...=x_{n}=1\\0,&{\mbox{altrimenti }}\end{cases}}$

si scrive

$f=x_{1}\cdot x_{2}\cdot ....\cdot x_{n}$

Funzione di OR a n variabili

È la funzione che vale

$f(n)={\begin{cases}1,&{\mbox{quando }}x_{1}=x_{2}=...=x_{n}=0\\0,&{\mbox{altrimenti }}\end{cases}}$

si scrive

$f=x_{1}+x_{2}+....+x_{n}$

Funzione di PEIRCE a n variabili o funzione di NOR

È la funzione che vale

$f(n)={\begin{cases}1,&{\mbox{quando }}x_{1}=x_{2}=...=x_{n}=0\\0,&{\mbox{altrimenti }}\end{cases}}$

e si scrive

$f=x_{1}\downarrow x_{2}\downarrow x_{3}...\downarrow x_{n}=\downarrow _{i=1}^{i=n}x_{i}$

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

$\downarrow x=x\downarrow ={\begin{cases}1,&{\mbox{se }}x=0\\0,&{\mbox{se }}x=1\end{cases}}\qquad {da\ cui\ \downarrow x=x\downarrow ={\bar {x}}}$

Per la funzione PEIRCE non vale la legge associativa.

Funzione di SHEFFER a n variabili o funzione di NAND

È la funzione che vale

$f(n)={\begin{cases}0,&{\mbox{quando }}x_{1}=x_{2}=...=x_{n}=1\\1,&{\mbox{altrimenti }}\end{cases}}$

si scrive

$f=x_{1}/x_{2}/.../x_{n}=/_{i=1}^{i=n}x_{i}$

anche la funzione di SHEFFER è definita se n=1 cioè $/x=x/={\bar {x}}$, e non gode della proprietà associativa.

Proprietà degli operatori $\downarrow$ e /

Espressione degli operarori $\downarrow$ e / mediante (+), ($\cdot$), (-)

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 1^a forma canonica, come il prodotto fondamentale m₀ cioè:

$\downarrow _{i=0}^{i=n}x_{i}=\downarrow x_{2}\downarrow x_{3}\downarrow ...\downarrow x_{n}=m_{0}=x_{1}^{0}x_{2}^{0}....x_{n}^{0}={\bar {x}}_{1}\cdot {\bar {x}}_{2}\cdot ....\cdot {\bar {x}}_{n}$

o ancora, tenendo presente le regole della complementazione

$\downarrow _{i=0}^{=n}x_{i}=\prod _{i}{\bar {x}}_{i}={\overline {\sum _{i}x_{i}}}$

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

$/_{i=0}^{i=n}x_{i}=x_{1}/x_{2}/.../x_{n}=M_{00..0}=M_{0}=x_{1}^{0}+x_{2}^{0}+...+x_{n}^{0}=\sum _{i}{\bar {x}}_{i}$

o ancora, tenendo presente le regole della complementazione

$/_{i=0}^{i=n}x_{i}=\sum _{i}{\bar {x}}_{i}={\overline {\prod _{i}x_{i}}}$

Proprietà di dualità

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

Consideriamo la funzione di PEIRCE $x_{1}\downarrow x_{2}\downarrow ...\downarrow x_{n}$ a n variabili.

Si può scrivere:

${\overline {{\bar {x}}_{1}\downarrow ...{\bar {x}}_{n}\downarrow }}={\overline {\prod _{i}{\bar {\bar {x}}}_{i}}}={\overline {\prod _{i}x_{i}}}=\sum _{i}{\bar {x}}_{i}=x_{1}/x_{2}/.../x_{n}$

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

Viceversa: considerando la funzione di Sheffer x₁/x₂/.../x_n a n variabili, si può scrivere:

${\overline {{\bar {x}}_{1}{\bar {x}}_{2}/..{\bar {x}}_{n}}}={\overline {\sum _{i}{\overline {\overline {x_{i}}}}}}={\overline {\sum _{i}x_{i}}}=\prod _{i}{{\bar {x}}_{i}}=x_{1}\downarrow {}x_{2}\downarrow {}..\downarrow {x_{n}}$

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

Consideriamo la funzione di Peirce espressa mediante l'operazione (*), si ha: $\downarrow _{i}x_{i}=\prod _{i}{\bar {x}}_{i}$ complementando ambo i membri si ottiene:

${\overline {\downarrow _{i}x_{i}}}={\overline {\prod _{i}{\bar {x}}_{i}}}=\sum _{i}x_{i}\qquad \qquad (a)$

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

$/_{i}x_{i}=\sum _{i}{\bar {x}}_{i}\qquad \qquad \qquad (b)$

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

${\overline {\downarrow _{i}x_{i}}}=/_{i}{\bar {x}}_{i}$

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

${\overline {/_{i}x_{i}}}=\downarrow _{i}{\bar {x}}_{i}$

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

${\overline {\sum _{i}x_{i}}}=\prod _{i}{\bar {x}}_{i}=\downarrow {x_{i}}$

${\overline {\prod _{i}}}x_{i}=\sum _{i}{\bar {x}}_{i}=/x_{i}$

Pseudo associatività

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

$F=A\downarrow {(B\downarrow {C})}$

$F'=(A\downarrow {B})\downarrow {C}$

si ha che $F\neq F'$, infatti:

$F={\overline {A+(B\downarrow {C})}}={\bar {A}}\cdot {\overline {B\downarrow {C}}}={\bar {A}}\cdot {\overline {\overline {(B+C)}}}={\bar {A}}(B+C)={\bar {A}}B+{\bar {A}}C$

$F'={\overline {(A\downarrow {B})+C}}={\overline {A\downarrow {B}}}\cdot {\bar {C}}=(A+B){\bar {C}}=A{\bar {C}}+B{\bar {C}}$

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

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

$A\downarrow {B}\downarrow {C}=A\downarrow {\overline {(B\downarrow {C})}}={\overline {(A\downarrow {B})}}\downarrow {C}$

Dimostrazione:

$A\downarrow {\overline {(B\downarrow {C})}}=A\downarrow {(B+C)}={\bar {A}}{\overline {(B+C)}}={\bar {A}}{\bar {B}}{\bar {C}}=A\downarrow {B}\downarrow {C}$

${\overline {A\downarrow {B}}}\downarrow {C}=(A+B)\downarrow {C}={\overline {(A+B)}}\cdot {\bar {C}}={\bar {A}}{\bar {B}}{\bar {C}}=A\downarrow {B}\downarrow {C}$

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

${\overline {x_{1}\downarrow {x_{2}}\downarrow {}...\downarrow {x_{k}}}}\downarrow {k_{k+1}}\downarrow {}...\downarrow {x_{n}}=x_{1}\downarrow {x_{2}}...{\overline {x_{k}\downarrow {x_{k+1}}...\downarrow {x_{n}}}}\qquad \qquad {(1<k<n)}$

${\overline {x_{1}/{x_{2}}/{}.../{x_{k}}}}/{k_{k+1}}/{}.../{x_{n}}=x_{1}/{x_{2}}...{\overline {x_{k}/{x_{k+1}}.../{x_{n}}}}\qquad \qquad {(1<k<n)}$

Dalla definizione dell'operatore $\downarrow {}$ si deducono le seguenti relazioni:

${\begin{cases}x_{1}\downarrow {x_{2}}...\downarrow {x_{n}}\downarrow {0}=x_{1}\downarrow {x_{2}}\downarrow {}...\downarrow {x_{n}}\qquad {(n>1)}\\x_{1}\downarrow {x_{2}}\downarrow {}...\downarrow {x_{n}\downarrow {1}}=0\end{cases}}$

${\begin{cases}x_{1}/{x_{2}}.../{x_{n}}/{1}=x_{1}/{x_{2}}/{}.../{x_{n}}\qquad {(n>1)}\\x_{1}/x_{2}/.../x_{n}/0=1\end{cases}}$

${\begin{cases}0\downarrow {x}=x\downarrow {0}={\bar {x}}\qquad {(n=1)}\\1/x=x/1={\bar {x}}\end{cases}}$

Espressione degli operatori ($\cdot {}$),(+),(-)

Mediante gli operatori $(\downarrow {})$ e (/) (n variabili)

Operazione $(\cdot )$

$x_{1}\downarrow {x_{2}}\downarrow {}...\downarrow {x_{n}}={\bar {x_{1}}}\cdot {\bar {x_{2}}}\cdot {}...\cdot {\bar {x_{n}}}$

ponendo <$x_{i}={\bar {A_{i}}}$

$\prod _{i}A_{i}=A_{1}\cdot {A_{2}}\cdot {}...\cdot {}\cdot {A_{n}}={\bar {A_{1}}}\downarrow {\bar {A_{2}}}\downarrow {}...\downarrow {\bar {A_{n}}}=\downarrow {_{i}}{\bar {A_{i}}}$

Operazione (+)

In maniera analoga si ha :

$x_{1}/x_{2}/.../x_{n}={\bar {x_{1}}}+{\bar {x_{2}}}+...+{\bar {x_{n}}}$

ponendo $x_{i}={\bar {A_{i}}}$

$\sum _{i}{A_{i}}=A_{1}+A_{2}+...+A_{n}={\bar {A_{1}}}/{\bar {A_{2}}}/.../{\bar {A_{n}}}=/_{i}{\bar {A_{i}}}$

Complemento (-)

È facile verificare dalle definizioni che

${\bar {A}}={\overline {A+A+...+A}}=A\downarrow {A\downarrow {}...\downarrow {A}}$

Analogamente:

${\bar {A}}={\overline {A\cdot {A}\cdot {}...\cdot {A}}}=A/A/.../A$

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

${\bar {x}}=0\downarrow {x}=x\downarrow {0}$

${\bar {x}}=1/x=x/1$}

Da ciò è facile vedere che:

$x\downarrow {\bar {x}}={\overline {x/{\bar {x}}}}=0$

Forme canoniche di Sheffer (n variabili)

A partire dalle due forme canoniche è facile ottenere delle espressioni utilizzanti $\downarrow {}$ 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:

$F={\bar {A}}BC+{\bar {A}}{\bar {B}}C+AB{\bar {C}}$

a) possiamo allora scrivere:

$F={\overline {({\overline {{\bar {A}}BC}})({\overline {{\bar {A}}{\bar {B}}C}})({\overline {AB{\bar {C}}}})}}$

(teorema di De Morgan e doppia negazione)

Per la definizione di / si ha:

$F=({\bar {A}}/B/C)({\bar {A}}/{\bar {B}}/C)(A/B/{\bar {C}})$

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:

$F=(A+B+C)(A+{\bar {B}}+C)({\bar {A}}+B+C)({\bar {A}}+B+{\bar {C}})({\bar {A}}+{\bar {B}}+{\bar {C}})$

possiamo scrfivere:

$F=({\overline {{\bar {A}}\cdot {\bar {B}}\cdot {\bar {C}}}})({\overline {{\bar {A}}\cdot B\cdot {\bar {C}}}})({\overline {A\cdot {\bar {B}}\cdot {\bar {C}}}})({\overline {A\cdot {\bar {B}}\cdot C}})({\overline {A\cdot B\cdot C}})$

$F=({\bar {A}}\cdot {\bar {B}}\cdot {\bar {C}})\downarrow {}({\bar {A}}\cdot B\cdot \mathbb {C} )\downarrow {}(A\cdot {\bar {B}}\cdot {\bar {C}})\downarrow {}(A\cdot {\bar {B}}\cdot C)\downarrow {}(A\cdot B\cdot C)$

$F=(A\downarrow B\downarrow C)\downarrow {}(A\downarrow {\bar {B}}\downarrow C)\downarrow {}({\bar {A}}\downarrow B\downarrow C)\downarrow {}({\bar {A}}\downarrow B\downarrow {\bar {C}})\downarrow {}({\bar {A}}\downarrow {\bar {B}}\downarrow {\bar {C}})$

Donde la regola:

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

Funzione OR esclusivo $\bigoplus {}$ (XOR)

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.