Algebre booleane e progetto logico dei calcolatori digitali/Algebre booleane: differenze tra le versioni

 

::::<math>\ A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)</math>

 

:<math>\underline {T6}\qquad\underline {A\cdot (A+B)=A}\ \ (legge\ di\ assorbimento) \qquad\qquad infatti:</math>

::::<math>\ 1\cdot (A+B)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.1)</math>

::::<math>\ A+B\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)</math>

 

:<math>\underline {T8}\qquad\underline {A\cdot(\bar A+ B)=A\cdot B}\qquad\qquad infatti:</math>

 

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.<br/>

 

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

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

 

 

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

ma ciò equivale a scrivere:

 

 

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

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.

 

 

Più precisamente si può dire:

:::<math>G(A,B,C)=A\cdot B+A\cdot C+B\cdot C+\bar A\cdot \bar B\cdot \bar C</math>

 

 

:::<math>G(1,0,1)=1\cdot 0+1\cdot 1+0\cdot 1+0\cdot 1\cdot 0=1</math>

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

 

 

le espressioni

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

 

 

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

per cui:

 

 

c) La funzione assume il valore della variabile complimentata: '''<math>G(x)=\bar x</math>''' avremo:

per cui:

 

 

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 (<math>\sigma</math>), allora anche il loro '''prodotto''', la loro '''somma''', ed il '''complemento''' di una di esse la verificano.

 

 

 

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

applicando la (<math>\sigma</math>) su '''F(x)''' e '''G(x)''' otterremo:

 

 

 

f) Sia '''<math>N(x)=\overline {F(x)}</math>''' e quindi

applicando la (<math>\sigma</math>) su '''F(x)''' e per il primo e secondo teorema di Morgan avremo:

 

:::::<math>\overline {F(1)}\cdot \overline {F(0)}+\overline{F(0)}\bar x+\overline{F(1)}x+\bar x x=</math>

:::::<math>[\overline{F(1)}\cdot\overline{F(0)}]\cdot 1+\overline{F(0)}\bar x+\overline{F(1)} x=</math>

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:

 

 

I termini '''<math>F(1,x_2,...,x_n)''' e '''F(0,x_2,...,x_n</math>''' sono, non considerando più '''<math>x_2,...,x_n</math>''' 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:

 

 

::::::<math>+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}</math>

 

Da ciò la notazione abbreviata:

 

 

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