Algebre booleane e progetto logico dei calcolatori digitali/Algebre booleane

Definizioni assiomatiche

Si chiamera algebra di Boole o algebra Booleana il sistema:

$B=<E,(+),(\cdot )\ ,0,1,>$

dove:

1. E è un insieme non vuoto che contiene almeno due elementi, e cioè 1 e 0,
2. (+) e ($\cdot$) sono due operazioni binarie definite su E e tali che E sia chiuso rispetto ad esse.
3. su E è definita una relazione di equivalenza, rappresentata dalla notazione = (e si legge uguale), e come tale soddisfacente, $\forall \ x,\ y,\ z\in E$ alle seguenti relazioni:
   1. $(x=y)\leftrightarrow {(y=x)}$ simmetria
   2. $X=X$ riflessivata
   3. $(x=y)\land (y=z)\rightarrow {(x=z)}$ transitivita

e tale che, $\forall \ A,\ B,\ C,\ \in E$, risultano soddisfatti i seguenti assiomi:

$Assiomi\ A_{i,j}$

${\underline {associativita}}$

$A1.1\qquad (A+B)+C=A+(B+C)\qquad A1.2\qquad (A\cdot B)\cdot C=A\cdot (B\cdot C)$

${\underline {commutativita}}$

$A2.1\qquad A+B=B+A\qquad \qquad \qquad \qquad A2.2\quad \ A\cdot B=B\cdot A$

${\underline {distributivita}}$

$A3.1\qquad A\cdot (B+C)=(A\cdot B)+(A\cdot C)\quad A3.2\quad \ A\cdot B=B\cdot A$

$A4.1\qquad A+0=0+A\qquad \qquad \qquad \qquad \ \ A4.2\qquad A\cdot 1=1\cdot A=A$

Nei precedenti due capitoli, abbiamo studiato l'algebra dei circuiti, l'algebra delle classi e l'algebra della logica; tutte e tre queste algebre rappresentano esempi di strutture algebriche Booleane. La definizione assiomatica dell'algebra di Boole riassume infatti le regole di calcolo incontrate nello studio delle algebre su menzionate. Per quanto riguarda l'applicazione dell'algebra astratta di Boole, vogliamo fare un breve cenno ad alcuni risultati dell'algebra dei circuiti (più avanti considereremo esempi di applicazione). Partendo dalla constatazione che operazioni quali connettere in serie, connettere in parallelo due o più interruttori elettrici e invertire un interruttore (chiuderlo se esso è aperto, aprirlo se esso è chiuso), soddisfano a tutti gli assiomi A_i,j(i=1,..,5); J=1, 2) si giunge alla conclusione che ogni risultato, ottenuto in sede astratta per le algebre di Boole, può essere tradotto in termini di interruttori, o più in generale, di circuiti.

Relazioni fondamentali in una algebra di Boole

Gli assiomi precedenti ci permettono di dimostrare diversi teoremi. Per semplificare le dimostrazioni si scriverà a destra di ogni identità o equazione, gli assiomi o i teoremi utilizzati.

Si hanno i seguenti teoremi:

${\underline {T1}}\qquad \quad \ A+A=A\qquad \qquad infatti:$

$\ A+A=(A+A)\cdot 1\ \ \ \ \ \ (A4.2)$

$\ =(A+A)\cdot (A+{\bar {A}})\ \ \ \ \ \ (A5.1)$

$\ =A+(A\cdot {\bar {A}})\ \ \ \ \ \ \ \ \ \ \ \ \ \ (A3.2)$

$\ =A+0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.2)$

$\ =A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.1)$

In maniera più generale si può dimostrare (per ricorrenza per esempio) che:

$A+A+A.....+A=A$

${\underline {T2}}\qquad \quad \ A\cdot A=A\qquad \qquad infatti:$

$\ A\cdot A=(A\cdot A)+0\ \ \ \ \ \ (A4.1)$

$\ A\cdot A=(A\cdot A)+(A\cdot {\bar {A}})\ \ \ \ \ \ (A5.2)$

$\ =A\cdot (A+{\bar {A}})\ \ \ \ \ \ (A3.1)$

$\ =A\cdot 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.1)$

$\ =A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)$

In maniera analoga si potrà generalizzare il risultato nella maniera seguente:

$A\cdot A\cdot A.....\cdot A=A$

(T1) e (T2) costituiscono le proprietà di idem potenza; ossia che in un'algebra di Boole non vi sono ne multipli ne potenze.

${\underline {T3}}\qquad \quad \ A+1=1\qquad \qquad infatti:$

$\ A+1=(A+1)\cdot 1\ \ \ \ \ \ (A4.2)$

$\ =(A+1)\cdot (A+{\bar {A}})\ \ \ \ \ (A5.1)$

$\ =A+(1\cdot {\bar {A}})\ \ \ \ \ \ \ \ \ \ \ \ \ \ (A3.2)$

$\ =A+{\bar {A}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)$

$\ =1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.1)$

${\underline {T4}}\qquad {\underline {A\cdot 0=0}}\qquad \qquad infatti:$

$\ A\cdot 0=(A\cdot 0)+0\ \ \ \ \ \ \ \ (A4.1)$

$\ =(A\cdot 0)+(A\cdot {\bar {A}})\ \ \ \ \ \ \ \ (A5.2)$

$\ =A\cdot (0+{\bar {A}})\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A3.1)$

$\ =A\cdot {\bar {A}})\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.1)$

$\ =0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.2)$

${\underline {T5}}\qquad {\underline {A+(A\cdot B)=A}}\ \ (legge\ di\ assorbimento)\qquad \qquad infatti:$

$\ A+(A\cdot B)=(A\cdot 1)+(A\cdot B)\ \ \ \ \ \ \ \ \ \ (A4.2)$

$\ A\cdot (1+B)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A3.1)$

$\ A\cdot 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (T3)$

$\ A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)$

${\underline {T6}}\qquad {\underline {A\cdot (A+B)=A}}\ \ (legge\ di\ assorbimento)\qquad \qquad infatti:$

$\ A\cdot (A+B)=(A\cdot A)+(A\cdot B)\ \ \ \ \ \ \ \ \ \ \ (3.1)$

$\ A+(A\cdot B)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (T2)$

$\ A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (T5)$

${\underline {T7}}\qquad {\underline {A+({\bar {A}}\cdot B)=A+B}}\qquad \qquad infatti:$

$\ A+({\bar {A}}\cdot B)=(A+{\bar {A}})\cdot (A+B)\ \ \ \ \ \ \ \ \ \ (A3.2)$

$\ 1\cdot (A+B)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.1)$

$\ A+B\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)$

${\underline {T8}}\qquad {\underline {A\cdot ({\bar {A}}+B)=A\cdot B}}\qquad \qquad infatti:$

$\ A\cdot ({\bar {A}}+B))=(A\cdot {\bar {A}})+(A\cdot B)\ \ \ \ \ \ \ \ \ \ \ (A3.1)$

$\ 0+(A\cdot B)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.2)$

$\ A\cdot B\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.1)$

${\underline {T9}}\qquad {\underline {Il\ complemento\ {\bar {A}}\ di\ un\ elemento\ A\ e\ unico}}$

$\ barA_{1}={\bar {A}}_{1}\cdot 1\ \ \ \ \ \ \ \ \ \ \ \ (A4.2)$

Ragionando per assurdo, si supponga che l'elemento A possieda due componenti ${\bar {A}}_{1}$ e ${\bar {A}}_{2}$. In virtù dell'assioma (A5)si avranno le relazioni:

${\begin{cases}A+{\bar {A}}_{1}=1\\A\cdot {\bar {A}}_{1}=0\end{cases}}$

${\begin{cases}A+{\bar {A}}_{2}=1\\A\cdot {\bar {A}}_{2}=0\end{cases}}$

Si ha allora:

$\ {\bar {A}}_{1}={\bar {A}}_{1}\cdot 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)$

$={\bar {A}}_{1}\cdot (A+{\bar {A}}_{2})\ \ \ \ \ \ \ \ \ \ \ \ \ (A5.1)$

$={\bar {A}}_{1}\cdot A+{\bar {A}}_{1}\cdot {\bar {A}}_{2}\ \ \ \ \ \ (A3.1)$

$=0+{\bar {A}}_{1}\cdot {\bar {A}}_{2}\ \ \ \ \ \ \ (A5.2)$

$=A\cdot {\bar {A}}_{2}+{\bar {A}}_{1}\cdot {\bar {A}}_{2}\ \ \ \ \ \ \ (A5.2)$

$={\bar {A}}_{2}\cdot A+{\bar {A}}_{2}\cdot {\bar {A}}_{1}\ \ \ \ \ \ \ (A2.2)$

$={\bar {A}}_{2}\cdot (A+{\bar {A}}_{1})\ \ \ \ \ \ \ (A3.1)$

$={\bar {A}}_{2}\cdot 1\ \ \ \ \ \ \ (A5.1)$

$={\bar {A}}_{2}\ \ \ \ \ \ \ (A4.2)$

Quindi A_1 e A_2 non possono che essere uguali.

Si chiama complementazione l'operazione che consiste nel far corrispondere l'elemento ${\bar {A}}\ ad\ A$.

${\underline {T10}}\qquad {\bar {\bar {A}}}=A\ \ \ \ \ involuzione$

Si consideri l'elemento ${\bar {A}}$ e si cerchi il suo complemento che verrà scritto ${\bar {\bar {A}}}$.

Si avrà:

${\begin{cases}A+{\bar {\bar {A}}}=1\\{\bar {A}}\cdot {\bar {\bar {A}}}=0\end{cases}}$

d'altra parte:

${\begin{cases}A+{\bar {A}}=1\\A\cdot {\bar {A}}=0\end{cases}}$

Si ha allora che ${\bar {A}}\ e\ {\bar {\bar {A}}}$ soddisfano alle stesse equazioni e poiché per il teorema T9, il complemento è unico, segue che ${\bar {\bar {A}}}=A$

${\underline {T11}}\qquad {\bar {(}}A+B)={\bar {A}}\cdot {\bar {B}}\ \ \ \ \ primo\ teorema\ di\ de\ Morgan$

Si cercherà il complemento di${\bar {A}}\cdot {\bar {B}}$ e si dimostrerà che esso è A+B.

Si consideri la quantità $(A+B)+({\bar {A}}\cdot {\bar {B}})$:

$(A+B)+({\bar {A}}\cdot {\bar {B}})=[(A+B)+{\bar {A}}]\cdot [(A+B)+{\bar {B}}]$

$=[A+(B+{\bar {A}})]\cdot [A+(B+{\bar {B}})]$

$=[(A+{\bar {A}})+B]\cdot [A+(B+{\bar {B}})]$

$=(1+B)\cdot (A+1)$

$=1\cdot 1$

Analogamente si ha:

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

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

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

$=0\cdot {\bar {B}}+{\bar {A}}\cdot 0$

$=0$

Dunque $x=A+B\ e\ y={\bar {A}}\cdot {\bar {B}}$ verificano le due equazioni:

${\begin{cases}x+y=1\\x\cdot y=0\end{cases}}$

per cui $A+B$ è il complemento (unico) di ${\bar {A}}\cdot {\bar {B}}$: dunque

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

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

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

${\underline {T12}}\qquad {\bar {(}}A+B)={\bar {A}}\cdot {\bar {B}}\ \ \ \ \ secondo\ teorema\ di\ de\ Morgan$

Si consideri il secondo membro e se ne prenda il complemento:

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

$=A\cdot B\ \ \ \ \ \ \ \ \ \ \ \ \ \ (T10)$

Si consideri ancora il complemento dei due membri:

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

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

Espressioni duali - Principio di dualità

Si considerino le coppie degli assiomi Ai.j. Due assiomi di una qualunque di queste coppie si corrispondono nella maniera indicata nella tabella seguente (dove x rappresenta la variabile generica che figura negli assiomi).

Regole di dualizzazione

$+\ \ \ \cdot$

$\cdot \ \ \ +$

$0\ \ \ 1$

$1\ \ \ 0$

$x\ \ \ x$

$x\ \ \ x$

Con questo procedimento, da un assioma di una coppia, si deduce l'altro.

Per esempio, a partire da A1.1:

$A+(B+C)=(A+B)+C$

si può scrivere immediatamente A1.2

$A\cdot (B\cdot C)=(A\cdot B)\cdot C$

Si dice che i due assiomi di una tale coppia sono duali: oppure che le identità che li esprimono sono duali. In generale, si chiameranno espressioni duali due espressioni algebriche che si deducono l'una dall'altra meddiante le regole della tabella precedente.

Esempio di espressioni duali

$A+(B\cdot C)\ \ \ \ \ A\cdot (B+C)$

$A\cdot {\bar {B}}+{\bar {A}}\cdot B\ \ \ \ \ \ \ (A+{\bar {B}})\cdot ({\bar {A}}+B)$

Il fatto che gli assiomi di un'algebra di Boole si raggruppino in coppie duali costituisce già una particolarità interessante. Ma più interessante è la considerazione che se ne trae sotto la forma detta del principio di dualità. Si consideeri un terorema valido su un'algebra di Boole; per dimostrarlo si deve applicare una successione di operazioni che, in ultima analisi, è una applicazione, in tappe successive, degli assiomi. Se ora si sostituisce ad ognuna di queste operazioni intermedie l'0perazione duale, si otterrà, ovviamente, il risultato duale; si potrà quindi fare a meno di dimostrare il duale di un teorema.
Il principio di dualità si può così enunciare:

A ogni teorema, vero in un'algebra di Boole, corrisponde un teorema duale che è altrettanto vero.

Data una espressione E si indicherà con E l'espressione duale.

Esempi di algebra di Boole

Algebra a due elementi

Si consideri un insieme I a due elementi: siano 0 ed 1; definiamo su questo insieme {0,1} 3 operazioni, date dalla tavola 6.1.

L'insieme {0,1} fornito delle operazioni +,*,neg ha una struttura algebrica Booleana:

$B=<{0,1},+,*,neg,0,1>$

Per giustificare tale asserzione, è sufficiente dimostrare che gli assiomi Ai.j sono soddisfatti.

Cominciamo col verificare gli assiomi A4.1 e A4.2.

In sede di definizione dell'algebra di Boole, si era detto che l'insieme E doveva essere composto da almeno due elementi, e che tali elementi devevano essere 0 e 1; per cui il nostro insieme I soddisfa a questa prima proprietà.

Passiamo a verificare ora la A4.1:

$A4.1\qquad \qquad A+0=0+A=A$

cioè, quale che sia l'elemento $A\in E$, associato con l'elemento $0\in E$ mediante l'operatore (+), il risultato di tale applicazione deve essere ancora A. E questo si verifica puntualmente nel nostro insieme I; verifichiamo l'assioma A4.1 prima con l'elemento $1\in I$ e quindi con l'elemento $0\in I$:

$A4.1\qquad \qquad 1+0=1\qquad \qquad 0+0=0$

abbiamo cioè riottenuto gli elementi 1 e 0 sfruttando la definizione dell'0perazione (+) (vedi tabella 6.1a).

Analogo discorso si farà per l'assioma A4.2:

$A4.2\qquad \qquad A\cdot 1=1\cdot A=A$

usufruendo della tabella 6.1b, che riguarda l'operatore ($\cdot$) verifichiamo tale assioma per l'insieme I.

$\qquad \qquad 0\cdot 1=0\qquad \qquad 1\cdot 1=1$

Per quanto riguarda l'assioma A5:

$A5.1\qquad A+{\bar {A}}=1\qquad \qquad A5.2\qquad A\cdot {\bar {A}}=0$

usufruendo della tabella 6.1, possiamo facilmente verificarlo ponendo A=1, A=0 e viceversa:

$A5.1\qquad {\begin{cases}1+{\bar {1}}=1\\0+{\bar {0}}=1\end{cases}}\qquad \qquad A5.2\quad {\begin{cases}1\cdot {\bar {1}}=0\\0\cdot {\bar {0}}=0\end{cases}}$

Lasciamo come esercizioal lettore la verifica dei restanti assiomi.

Algebra delle classi

Un secondo esempio di algebra di Boole è quello costituito dall'insieme di tutti i sottoinsiemi di un dato insieme M quando per ∪, ∩ e −, si prendano rispettivasmente le ordinarie operazioni di riunione, intersezione e complementazione tra insiemi, e perle costanti 0 e 1 ris\ ettivamente l'insieme vuoto Φ e l'insieme delle parti I_M:

$B_{M}=<I_{M},\cap {},\cup {},{\bar {}}\ ,\phi ,I_{M}>$

Per vedere che gli assiomi Ai.j sono verificati è sufficiente considerare le relazioni incontrate nel 5° capitolo.

Giova rilevare che M non è necessariamente finito; se lo è, se contiene cioè n (>2) elementi, l'algebra di Boole B_M ne contiene 2ⁿ.

Algebra delle proposizioni

Consideriamo un insieme L di proposizioni, fornito delle operazioni $\land ,\lor ,\sim$ tale che se $P,Q\in L$, si abbia $\sim P\in L,P\land Q\in L,P\lor Q\in L$. In queste condizioni gli assiomi Ai,j prenderanno la forma delle relazioni (L₁...L₁₀): l'insieme L delle proposizioni, con le operazioni $\land ,\lor ,\sim$ è un'algebra di Boole:

$B_{L}=<L,\lor ,\land ,\sim ,P,P>$

L'algebra delle proposizioni ha l'implicazione reciproca (↔) come relazione di equivalenza.

Algebra dei vettori a n dimensioni

Si consideri l'insieme dei vettori binari a n dimensioni. Un vettore binario (matrice riga) X è un insieme ordinato di variabili (componenti) capaci di assumere uno dei valori:0 e 1:

$X=(x_{1},x_{2},...,xi...,x_{n})=(x_{i})\quad x_{i}\in {0,1}\quad (i=1...n)$

Questo insieme comprende:

${\begin{matrix}\underbrace {2\cdot 2\cdot 2...\cdot 2} _{n\ fattori}\end{matrix}}=2^{n}\quad {elementi}$

Si possono introdurre le operazioni seguenti:

1) Prodotto

Dati due vettori X e Y

$X=(x_{1},x_{2}....,x-n)=(x_{i})$

$Y=(y_{1},y_{2}....,y_{n})=(y_{i})$

si chiama prodotto booleano di X e Y, denotato con $X\cdot Y$, il vettore

$X\cdot Y=(x_{1}\cdot y_{1},x_{2}\cdot y_{2}....x_{i}\cdot y_{i}....x_{n}\cdot y_{n})=(x_{i}\cdot y_{i})$

2) Somma

Dati due vettori X e Y definiti come sopra, si chiama somma booleana di X e Y il vettore:

$X+Y=(x<-1+y_{1},....x_{i}+y_{i},....x_{n}+y_{n})=(x_{i}+y_{i})$

3) Complemento

Dato un vettore $X=(x_{1},..,x_{i},...,x_{n})$ il complemento di X è il vettore:

${\overline {X}}=({\overline {x_{1}}},....{\overline {x_{i}}},....{\overline {x_{n}}})=({\overline {x_{i}}})$

Le operazioni +, ., -, sulle variabili x,y sono quelle definite nell'algebra a due elementi.

4) Vettore nullo

Per definizione esso è un vettore formato unicamente da zeri:

$0=(0,0,...,0)\qquad (x_{i}=0\quad i=1,...n)$

5) Vettore unità

È il vettore formato unicamente da 1:

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

In queste condizioni l'insieme dei vettori binari ad n dimensioni, fornito di queste tre operazioni, è un'algebra di Boole a 2ⁿ elementi, con 0 e 1 per elementi costanti:

$B=<{x},+,\cdot ,-,0,1>$

Si può dimostrare l'asserto facendo vedere che gli assiomiA1.1 sono verificati per i vettori si troverà ogni volta che la dimostrazione si riporta alle componenti. Ora, per quest' ultime, gli assiomi sono verificati in quanto si tratta di un'algebra di Boole a due elementi.

Si verifichi per esempio l'assioma A1.1. Si ha:

(X+Y)+Z=X+(Y+Z)

ma ciò equivale a scrivere:

$[(x_{i}+y_{i})+z_{i}=x_{i}+(y_{i}+z_{i})]\longleftrightarrow [i(i=1,2,3...,n)(x_{i}+y_{i})z_{i}=x_{i}+(y_{i}+z_{i})]$

Per ogni i quest'ultima relazione è vera in quanto abbiamo visto che per le componenti gli assiomi sono verificati (algebra a due elementi).

Per l'equivalenza, discende che anche la proposizione vettoriale è vera.

L'assioma (A1.1) è dunque verificato.

In maniera analoga si dimostrano gli alti assiomi.

Variabili ed espressioni booleane

Variabile booleana: è una variabile i cui valori appartengono ad una algebra di boole. Le lettere che abbiamo usato nelle definizioni degli assiomi e dei teoremi fino ad ora, rappresentano tali variabili. Si dirà anche che l'algebra considerata costituisce il dominio della variabile.

Espressione booleana: si chiamerà espressione booleana, o forma booleana, ogni espressione algebrica formata, a partire dalle variabili e dalle costanti appartenenti ad un'algebra booleana, mediante un numero finito di applicazioni delle operazioni ( $+,\cdot ,{\bar {}}\ )$.

Più precisamente si può dire:

1. 0 e 1 sono espressioni
2. ogni variabile x è una espressione
3. se A è una espresssione, anche ${\bar {A}}$ lo è
4. se A e B sono espressioni, anche A+B e A*B lo sono
5. un'espressione può essere ottenuta applicando le regole1, 2, 3 e 4 un numero finito di volte.

Valore di un'espressione booleana

Funzioni generate da una espressione.

Data una espressione booleana ad n variabili, e sia

$G(x_{1},x_{2}.....x_{n})$,

se si sostituiscono le variabili con degli elementi particolari di E, che è l'insieme sostegno, si ottiene come risultato dell'espressione un elemento di E.

Si chiama assegnazione (dei valori alle variabili) ogni combinazione $(a_{1},a_{2}...a_{n})$ di valori particolari attribuiti alle variabili $(x_{1}.x_{2}...x_{n})$. L'elemento ottenuto, calcolando la G in corrispondenza dell'assegnazione $(a_{1},a_{2}...a_{n})$, è il valore dell'espressione a tale assegnazione.

Sia data ad esempio l'espressione:

$G(A,B,C)=A\cdot B+A\cdot C+B\cdot C+{\bar {A}}\cdot {\bar {B}}\cdot {\bar {C}}$

il suo valore per la combinazione (1,0,1) (cioè A=1, B=0, C=1) sarà:

$G(1,0,1)=1\cdot 0+1\cdot 1+0\cdot 1+0\cdot 1\cdot 0=1$

Se si calcolano i valori dell'espressione in corrispondenza a tutte le possibili combinazioni dei valori delle variabili, si definisce una funzione $f_{G}(x_{1}...x_{n})$ di Eⁿ in E. Si dirà allora che l'espressione G genera la funzione in questione e, inversamente, che G è un'espressione o una rappresentanza di f_G.

Consideriamo ad esempio la funzione Somma di due variabili che, ad ogni coppia di valori, associa la loro somma; l'espressione sarà:

$S(A,B)=A+B$

avremo:

$S80,0)=0\quad S(0,1)=1\quad S(1,0)=1\quad S(1,1)=1$

in tal modo abbiamo definito la funzione somma; cioè la corrispondenza che, mediante S(A,B), viene generata tra E² ed E.

Vi è inoltre da notare che un'espressione definisce un'unica funzione mentre, per una funzione data di Eⁿ in E, esistono infinite (a causa, ad esempio, della legge di idempotenza) espressioni che la generano. Così nell'algebra

$B=<|0,1|,+,\cdot ,{\bar {}},0,1>$

le espressioni

$A\cdot {\bar {B}}+{\bar {A}}\cdot B\qquad A\cdot {\bar {B}}+{\bar {A}}\cdot B+{\bar {A}}\cdot B\qquad {\overline {(A+{\bar {B}})({\bar {A}}+B)}}$

rappresentano la stessa funzione definita dalla tabella:

A	B	f(A,B)
0	0	0
0	1	1
1	0	1
1	1	0

Uguaglianza di 2 espressioni booleane

Si dice che 2 espressioni sono uguali (o equivalenti) se esse assumono gli stessi valori per ogni assegnazione di valori delle vasrabili, cioè se esse generano la stessa funzione.

L'uguaglianza di due espressioni G e G^' sarà rappresentata dal segno =. Si può verificare che essa è una relazione di equivalenza nel senso usuale.

Forme canoniche. Teorema di Shannon

Come si è detto precedentemente, una funzione booleana può essere rappresentata da infinite espressioni algebriche; tra tutte queste però, ve ne sono due particolari che prendono il nome di forme canoniche: Per giungere alla definizione di tali forme, occorre enunciare il seguente teorema:

Teorema di Shannon per espressioni a una variabile

Ogni espressione booleana di una variabile si può sempre esprimere medfiante una espressione del tipo:

$F(x)=F(1)*x+F(0)*{\bar {x}}\qquad \qquad (\sigma )$

dove con F(1) e F(0) s'intende la funzione calcolata per i valori 1 e 0 della variabile.

Verifichiamo la validità di tale teorema perle funzioni base:

a) Funzioni costanti: F(x)=A, in tal caso l'espressione è indipendente dal valore della variabile; si ha cioè:

$F(x)=F(1)=F(0)=A$

per cui applicando gli assiomi visti nel paragrafo 6.1 si può scrivere:

$F(x)=A=A\cdot 1=A(x+{\bar {x}})=Ax+a{\bar {x}}=F(1)x+F(0){\bar {x}}$.

b) La funzione assume il valore della variabile x: P(x)=x; avremo:

$P(1)=1\qquad \qquad \qquad P(0)=0$

per cui:

$P(x)=x=x+0=x+0\cdot {\bar {x}}=1\cdot x+0\cdot {\bar {x}}=P(1)x+P(0){\bar {x}}$

c) La funzione assume il valore della variabile complimentata: $G(x)={\bar {x}}$ avremo:

$G(1)=0\qquad \qquad G(0)=1$

per cui:

$G(x)={\bar {x}}=0+{\bar {x}}=0\cdot x+{\bar {x}}=0\cdot x+1\cdot {\bar {x}}=G(1)x+G(0){\bar {x}}$

Tenendo presente che ogni espressione booleana non sarà altro che una combinazione delle tre espressioni a), b), c), si può dimostrare la validità del teorema di Shannon per ogni espressione di una funzione ad una variabile. Per ottenere ciò è sufficiente far vedere che: date due funzioni F(x) e G(x) verificanti la ($\sigma$), allora anche il loro prodotto, la loro somma, ed il complemento di una di esse la verificano.

d) Sia H(x)=F(x)*G(x) e quindi H(1)=F(1) G(1) e H(0)=F(0) G(0) applicando la $(\sigma )$ su F(x) e G(x) otterremo:

$H(x)=[F(1)x+G(1){\bar {x}}]\cdot [G(0)x+G(0){\bar {x}}]$

e) Sia K(x)=F(x)+G(x) quindi

$K(1)=F(1)+G(1)\qquad \qquad e\qquad \qquad K(0)=F(0)+G(0)$

applicando la ($\sigma$) su F(x) e G(x) otterremo:

$K(x)=[F(1)x+F(0){\bar {x}}]+[G(1)x+G(0){\bar {x}}]=$

$[F(1)+G(1)]x+[F(0)+G(0)]{\bar {x}}=K(1)x+K(0){\bar {x}}$

f) Sia $N(x)={\overline {F(x)}}$ e quindi

$N(1)={\overline {F(1)}}\qquad \qquad e\qquad \qquad N(0)={\overline {F(0)}}$

applicando la ($\sigma$) su F(x) e per il primo e secondo teorema di Morgan avremo:

$N(x)={\overline {F(1)x+F(0){\bar {x}}=}}$

${\overline {F(1)x}}\cdot {\overline {F(0){\bar {x}}}}=[{{\overline {F(1)}}+{\bar {x}}}]\cdot [{{\overline {F(0)}}+{\bar {\bar {x}}}}]=$

${\overline {F(1)}}\cdot {\overline {F(0)}}+{\overline {F(0)}}{\bar {x}}+{\overline {F(1)}}x+{\bar {x}}x=$

$[{\overline {F(1)}}\cdot {\overline {F(0)}}]\cdot 1+{\overline {F(0)}}{\bar {x}}+{\overline {F(1)}}x=$

$[{\overline {F(1)}}\cdot {\overline {F(0)}}](x+{\bar {x}})+{\overline {F(0)}}{\bar {x}}+{\overline {F(1)}}x=$

${\overline {F(1)}}\cdot {\overline {F(0)}}\cdot x+{\overline {F(1)}}\cdot {\overline {F(0)}}\cdot {\bar {x}}+{\overline {F(0)}}\cdot {\bar {x}}+{\overline {F(1)}}\cdot x=$

$[{\overline {F(1)}}\cdot {\overline {F(0)}}+{\overline {F(1)}}]\cdot x]+[{\overline {F(1)}}\cdot {\overline {F(0)}}+{\overline {F(0)}}]\cdot {\bar {x}}=$

${\overline {F(1)}}\cdot x+{\overline {F(0)}}\cdot {\bar {x}}=N(1)\cdot x+N(0)\cdot {\bar {x}}$

Abbiamo così dimostrato che le operazioni, in una espressione di una funzione booleana, conservano la proprietà di Shannon e ciò ci permette sempre di ridurre l'espressione ad una forma lineare ed omogenea nelle variabili $x$ e ${\bar {x}}$:

$f(x)=Ax+B{\bar {x}}\qquad \qquad (dove\ A=F(1)eB=F(0))$

nella quale compaiono solo due costanti F(1), F(0) facilmente determinabili data l'espressione della funzione.

Teorema di Shannon per espressioni a n variabili

È possibile enunciare il teorema di Shannon anche per espressioni ad n variabili: ma prima di fornire tale enunciato, esponiamo il procedimento con cui si giunge a tale generalizzazione del teorema.

si consideri una espressione a n variabili:

$F(x_{1},x_{2},....,x_{n}$

e si supponga di fissare (cioè considerare costanti) n-1 variabili: l'espressione F è allora una espressione ad una variabile, che gode quindi della proprietà di Shannon e può, di conseguenza, essere espressa nella forma:

$F(x_{1},x_{2},...,x_{n})=F(1,x_{2},x_{3},...,x_{n})x_{1}+F(0,x_{2},x_{3},...,x_{n}){\bar {x_{1}}}$

I termini $F(1,x_{2},...,x_{n})'''e'''F(0,x_{2},...,x_{n}$ sono, non considerando più $x_{2},...,x_{n}$ costanti, delle espressioni ad n-1 variabili, nelle quuali noi possiamo di nuovo fissare momentaneamenten n-2 variabili, per esempio le ultime n-2, ed applicare ancora alla variabile x_2 il teorema di Shannon. Da cui:

$F(x_{1},x_{2},...,x_{n})=[F(1,1,x_{3},...,x_{n})x_{2}+F(1,0,x_{3},...,x_{n}){\bar {x_{2}}}]\cdot {x_{1}}+$

$[F(0,1,x_{3},...,x_{n})x_{2}+F(0,0,x_{3},...,x_{n}){\bar {x_{2}}}]\cdot {\bar {x_{1}}}=$

$F(1,1,x_{3},...,x_{n})x_{1}x_{2}+F(1,0,x_{3},...,x_{n})x_{1}{\bar {x_{2}}}+$

$+F(0,1,x_{3},...,x_{n}){\bar {x}}_{1}x_{2}+F(0,0,x_{3},...,x_{n}){\bar {x}}_{1}{\bar {x_{2}}}$

Si può continuare ad applicare il teorema di Shannon fino all'esaurimento delle variabili; infine si otterrà la seguente espressione:

$F(x_{1},x_{2},...,x_{n})=\sum _{e=0,0,..,0}^{e=1,1,..,1}F(e_{1},e_{2},...,e_{n})e_{1}^{e_{1}}e_{2}^{e_{2}}...e_{n}^{e_{n}}$

con la convenzione:

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

ed $e=(e_{1},e_{2},...,ee_{n})$ vettore binarioad n dimensioni.

Per scrivere in maniera più compatta, si può pensare di considerare "e" come la rappresentazione binaria di un numero.

Da ciò la notazione abbreviata:

$(\sigma ')\qquad F(x_{1},x_{2},...,x_{n})=\sum _{e=0}^{e=2^{n}-1}F(e)x_{1}^{e_{1}}x_{2}^{e_{2}}...x_{n}^{e_{n}}$

e ora possiamo enunciare il teorema di Shannon per espressioni a n variabili:

ogni funzione booleana di n variabili, si può sempre esprimere mediante una espressione del tipo $(\sigma ')$.

La forma algebrica del secondo membro di $(\sigma ')$ porta il nome di forma canonica disgiunta, volendo indicare con questa terminologia, cher essa è una somma di prodotti.

In essa compaiono i $2^{n}$ possibili coefficienti F(e) ed altrettanti monomi della forma:

$(\alpha )\qquad e_{1}^{e_{1}}x_{2}^{e_{2}}...e_{i}^{e_{i}}...x_{n}^{e_{n}}$

Una espressione booleana a n variabili è quindi conosciuta quando si hanno i $2^{n}$ coefficienti di F(e).

Un prodotto della forma $(\alpha )$ si chiama prodotto fondamentale.

Espressioni duali

Applicando il principio di dualità si deducono le formule seguenti:

$F(x)=[F(1)+{\bar {x}}]\cdot [F(0)+x]$ (teorema di Shannon duale)

da cui:

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

che prende il nome di forma congiuntiva.

Essa è un prodotto di somme. Le somme della forma:

$x_{1}^{e_{1}}+x_{2}^{e_{2}}+...+x_{i}^{e_{i}}+...+x_{n}^{e_{n}}$

sono chiamate somme somme fondamentali.

In maniera più compatta si scriverà:

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

dove $2^{n}-1-e$ = complemento ad 1 di e.

Metodo pratico del calcolo di un complemento

Consideriamo l'espressione $E(x_{1},x_{2},...x_{n})$. Per calcolare il complemento non è necessario applicare passo passo i teoremi di De Morgan: è sufficiente sostituire l'espressione $E(x_{1},x_{2},...x_{n})$ con l'espressione ${\overline {E(x_{1},x_{2},...x_{n})}}$, ottenuta con le regole seguenti:

Si noterà che questa tabella è differente, nelle ultime righe, da quella che definisce la regola di dualizzazione:

Esempio

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

Per definizione si ha:

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

Per semplificare tale espressione si può applicare il teorema di De Morgan oppure la regola sopra enunciata; applichiamo entrambe, e confrontiamo l'uguaglianza dei risultati.

Primo metodo

${\overline {F}}={\overline {\overline {A\cdot {\bar {B}}+{\bar {C}}\cdot {\bar {D}}+{\bar {A}}\cdot B}}}\cdot {\overline {A\cdot B+B\cdot C}}=$

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

$(A\cdot {{\bar {B}}+{\bar {C}}\cdot {\bar {D}}+{\bar {A}}\cdot B})\cdot ({\bar {A}}+{\bar {B}})\cdot ({\bar {B}}+{\bar {C}})$

Secondo metodo

$(A\cdot {{\bar {B}}+{\bar {C}}\cdot {\bar {D}}+{\bar {A}}\cdot B})\cdot ({\bar {A}}+{\bar {B}})\cdot ({\bar {B}}+{\bar {C}})$

come si vede questo secondo metodo è molto più rapido.

Riduzione ad un livello di complementazione in una espressione

Data una espressione che comporta più livelli di complementazione sovrapposti, come ad esempio:

$F={\overline {{\bar {A}}+B+{\overline {C+D}}+E}}$

è sempre possibile ricondurre una tale espressione ad una forma dove le complementazioni appaiono, al massimo, ad un livello.

Che ciò sia sempre possibile è una conseguenza dell'esistenza delle forme canoniche.

Comunque, applicando ripetutamente i teoremi di De Morgan, si può verificare tale affermazione senza dover ricorrere4 alle forme canoniche.

Per l'espressione precedente si avrà:

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

cioè si è ottenuta una espressione dove gli elementi sono complimentati al massimo una volta.

Tale espressione si potrà sviluppare in somma di prodotti:

$F=A\cdot {\bar {B}}\cdot C\cdot {\bar {E}}+A\cdot {\bar {B}}\cdot D\cdot {\bar {E}}$

Relazione tra espressione duale e complemento

Data una espressione di una funzione $F(x_{1},x_{2},...,x_{n})$ le tavole delle regole di dualizzazione e di complementazione permettono di dedurre due espressioni associate alla funzione data:

$\sim F(x_{1},x_{2},...x_{n})\qquad \qquad (duale)$

${\bar {F}}(x1,x2,...,x_{n})\qquad \qquad (complemento)$

La relazione che lega queste due funzioni è

$\sim F(x1,x_{2},...,x_{n})=){\bar {F}}({\bar {x}}_{1},{\bar {x}}_{2},...,{\bar {x}}_{n})\qquad \qquad (\beta )$

i procedimenti per costruire le espressioni F,sim F,\bar F possono essere riassunte nella tabella a fianco.

F è costituita da un numero finito di operazioni +, *, -, a partire dalle variabili e dalle costanti 0 ed 1; e si vede che applicando passo passo la corrispondenza della tabella, la relazione $(\beta )$ è verificata.