Algebre booleane e progetto logico dei calcolatori digitali/Algebre booleane: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m fix |
wikifico, correggo refusi e sistemo |
||
Riga 1:
{{Algebre booleane e progetto logico dei calcolatori digitali}}
== Definizioni assiomatiche ==
Si chiamera algebra di Boole o algebra Booleana il sistema:
:::::::<math>B=<E, (+),(\cdot) \ , 0, 1, > </math>
dove:
# '''E''' è un insieme non vuoto che contiene almeno due elementi, e cioè '''1''' e '''0''',
# '''(+)''' e '''(<math>\cdot</math>)''' sono due operazioni binarie definite su '''E''' e tali che '''E''' sia chiuso rispetto ad esse.
# su '''E''' è definita una relazione di equivalenza, rappresentata dalla notazione '''=''' (e si legge uguale), e come tale soddisfacente, '''<math>\forall\ x,\ y,\ z\in E</math>''' alle seguenti relazioni:
## <math>(x=y)\leftrightarrow {(y=x)}</math> simmetria
## <math>X=X</math> riflessivata
## <math>(x=y)\land (y=z)\rightarrow {(x=z)}</math> transitivita
e tale che, <math>\forall\ A,\ B,\ C,\ \in E</math>, risultano soddisfatti i seguenti assiomi:
:::::::::<math>Assiomi\ A_{i,j}</math>
::::::::<math>\underline {associativita}</math>
Line 22 ⟶ 25:
::<math>A4.1\qquad A+0=0+A\qquad\qquad\qquad\qquad\ \ A4.2\qquad A\cdot 1=1\cdot A=A</math>
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<sub>i,j</sub>(i=1,..,5); J=1, 2)''' si giunge alla conclusione che ogni risultato
== 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
Si hanno i seguenti teoremi:
Line 34 ⟶ 37:
::::<math>\ =A+(A\cdot \bar A)\ \ \ \ \ \ \ \ \ \ \ \ \ \ (A3.2)</math>
::::<math>\ =A+0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.2)</math>
::::<math>\ =A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.1)</math
In maniera più generale si può dimostrare (per ricorrenza per esempio) che:
:::<math>A+A+A.....+A=A</math>
:<math>\underline {T2}\qquad\quad\ A\cdot A=A\qquad\qquad infatti:</math>
Line 44 ⟶ 48:
::::<math>\ =A\cdot (A+\bar A)\ \ \ \ \ \ (A3.1)</math>
::::<math>\ =A\cdot 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.1)</math>
::::<math>\ =A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)</math
In maniera analoga si potrà generalizzare il risultato nella maniera seguente:
:::<math>A\cdot A\cdot A.....\cdot A=A</math>
(T1) e (T2) costituiscono le proprietà di
:<math>\underline {T3}\qquad\quad\ A+1=1\qquad\qquad infatti:</math>
Line 56 ⟶ 62:
::::<math>\ =A+\bar A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)</math>
::::<math>\ =1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.1)</math>
:<math>\underline {T4}\qquad\underline {A\cdot 0=0}\qquad\qquad infatti:</math>
Line 65 ⟶ 70:
::::<math>\ =A\cdot\bar A)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.1)</math>
::::<math>\ =0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A5.2)</math>
:<math>\underline {T5}\qquad\underline {A+(A\cdot B)=A}\ \ (legge\ di\ assorbimento) \qquad\qquad infatti:</math>
::::<math>\ A+(A\cdot B)=(A\cdot 1)+(A\cdot B)\ \ \ \ \ \ \ \ \ \ (A4.2)</math
::::<math>\ A\cdot (1+B)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
::::<math>\ A\cdot 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (T3)</math>
::::<math>\ A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)</math>
Line 77 ⟶ 84:
:<math>\underline {T6}\qquad\underline {A\cdot (A+B)=A}\ \ (legge\ di\ assorbimento) \qquad\qquad infatti:</math>
::::<math>\ A\cdot (A+B)=(A\cdot A)+(A\cdot B)\ \ \ \ \ \ \ \ \ \ \ (3.1)</math
::::<math>\ A+(A\cdot B)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (T2)</math>
::::<math>\ A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (T5)</math>
:<math>\underline {T7}\qquad\underline {A+(\bar A\cdot B)=A+B}\qquad\qquad infatti:</math>
Line 93 ⟶ 100:
::::<math>\ A\cdot B\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.1)</math>
:<math>\underline {T9}\qquad\underline {Il\ complemento\ \bar A\ di\ un\ elemento\ A\ e\ unico}</math>
::::<math>\ bar A_1=\bar A_1\cdot 1\ \ \ \ \ \ \ \ \ \ \ \ (A4.2)</math>
Ragionando per assurdo, si supponga che l'elemento '''A''' possieda due componenti <math>\bar A_1</math> e <math>\bar A_2</math>. In virtù dell'assioma '''(A5)'''si avranno le relazioni:
::::::::::<math>\begin{cases} A+\bar A_1=1 \\ A\cdot \bar A_1=0
\end{cases}</math>
::::::::::<math>\begin{cases} A+\bar A_2=1 \\ A\cdot \bar A_2=0
\end{cases}</math
Si ha allora:
::::<math>\ \bar A_1=\bar A_1\cdot 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A4.2)</math>
:::::<math> =\bar A_1\cdot (A+\bar A_2)\ \ \ \ \ \ \ \ \ \ \ \ \ (A5.1)</math>
Line 111 ⟶ 121:
:::::<math> =\bar A_2\cdot (A+\bar A_1)\ \ \ \ \ \ \ (A3.1)</math>
:::::<math> =\bar A_2\cdot 1\ \ \ \ \ \ \ (A5.1)</math>
:::::<math> =\bar A_2\ \ \ \ \ \ \ (A4.2)</math
Quindi '''A_1''' e '''A_2''' non possono che essere uguali.
Si chiama '''complementazione''' l'operazione che consiste nel far corrispondere l'elemento <math>\bar A \ ad\ A</math>.
:<math>\underline {T10}\qquad \bar\bar A=A\ \ \ \ \ involuzione</math>
Si consideri l'elemento <math>\bar A</math> e si cerchi il suo complemento che verrà scritto <math>\bar\bar A</math>.
Si avrà:
::::::::::<math>\begin{cases} A+\bar\bar A=1 \\ \bar A\cdot \bar\bar A= 0
\end{cases}</math
d'altra parte:
::::::::::<math>\begin{cases} A+\bar A=1 \\ A\cdot \bar A=0
\end{cases}</math
Si ha allora che <math>\bar A \ e\ \bar\bar A</math> soddisfano alle stesse equazioni e poiché per il teorema '''T9''', il complemento è unico, segue che <math>\bar\bar A=A</math>
:<math>\underline {T11}\qquad \bar (A+B)=\bar A\cdot\bar B \ \ \ \ \ primo\ teorema\ di\ de\ Morgan</math>
Si cercherà il complemento di<math>\bar A\cdot\bar B</math> e si dimostrerà che esso è '''A+B'''.
Si consideri la quantità <math>(A+B)+(\bar A\cdot\bar B)</math>:
<math>(A+B)+(\bar A\cdot\bar B)=[(A+B)+\bar A]\cdot [(A+B)+\bar B]</math>
:::::<math> =[A+(B+\bar A)]\cdot [A+(B+\bar B)]</math>
:::::<math> =[(A+\bar A)+B]\cdot [A+(B+\bar B)]</math>
:::::<math> =(1+B)\cdot (A+1)</math>
:::::<math> =1\cdot 1</math
Analogamente si ha:
<math>(A+B)\cdot (\bar A\cdot\bar B)=(\bar A\cdot\bar B)\cdot (A+B)</math>
:::::<math> =(\bar A\cdot\bar B)\cdot A+(\bar A\cdot\bar B)\cdot B</math>
:::::<math> =(\bar A\cdot A)\cdot\bar B+\bar A\cdot (\bar B\cdot B) </math>
:::::<math> =0\cdot \bar B+\bar A\cdot 0</math>
:::::<math> =0</math
::::::::::<math>\begin{cases} x+y=1 \\ x\cdot y= 0 \end{cases}</math>
per cui <math>A+B</math> è il complemento (unico) di <math>\bar A\cdot\bar B</math>: dunque
:::::::<math>A+B=\overline {(\bar A\cdot\bar B)}</math>
:::::::<math>\overline {(a+B)}=\overline {\overline {(\bar A\cdot\bar B)}}=\bar A\cdot\bar B</math>
:::::::<math>\overline {(A+B)}=\bar A\cdot\bar B</math>
:<math>\underline {T12}\qquad \bar (A+B)=\bar A\cdot\bar B \ \ \ \ \ secondo\ teorema\ di\ de\ Morgan</math>
Si consideri il secondo membro e se ne prenda il complemento:
:::::::<math>\overline {(\bar A+\bar B)}=\bar\bar A\cdot \bar\bar B\ \ \ \ \ \ \ \ (T11)</math>
:::::::::<math> =A\cdot B\ \ \ \ \ \ \ \ \ \ \ \ \ \ (T10)</math
Si consideri ancora il complemento dei due membri:
:::::::<math>\overline{\overline {(\bar A+\bar B)}}=\overline {A\cdot B}</math>
:::::::<math>\bar A+\bar B=\overline {A\cdot B}\ \ \ \ \ \ \ \ \ \ \ (T10)</math>
== 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
:::::::::::<math>+ \ \ \ \cdot</math>
:::::::::::<math>\cdot \ \ \ +</math>
Line 166 ⟶ 194:
:::::::::::<math>1 \ \ \ 0</math>
:::::::::::<math>x \ \ \ x</math>
:::::::::::<math>x \ \ \ x</math
Con questo procedimento, da un assioma di una coppia, si deduce l'altro.
Per esempio, a partire da '''A1.1''':
::::::::::<math>A+(B+C)=(A+B)+C</math>
si può scrivere immediatamente '''A1.2
::::::::::<math>
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 ===
::::::::::<math>A+(B\cdot C)\ \ \ \ \ A\cdot (B+C)</math>
:::::::::<math>A\cdot \bar B+\bar A\cdot B\ \ \ \ \ \ \ (A+\bar B)\cdot (\bar A+B)</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.<bar/>
Il principio di dualità si può cosi 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.
Line 184 ⟶ 223:
[[File:Somma prodotto e negazione.png|right]]
=== 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:
:::::::<math> B=<{0,1}, +, * , neg, 0, 1></math
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''':
:<math> A4.
cioè, quale che sia l'elemento <math>A\in E</math>, associato con l'elemento <math>0\in E</math> 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 '''<math>1\in I</math>''' e quindi con l'elemento '''<math>0\in I</math>''':
:<math>
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''':
:<math>A4.2\qquad\qquad A\cdot 1=1\cdot A=A</math>
usufruendo della tabella '''6.1b''', che riguarda l'operatore '''(<math>\cdot </math>)''' verifichiamo tale assioma per l'insieme '''I'''.
:<math>\qquad\qquad 0\cdot 1=0\qquad\qquad 1\cdot 1=1</math>
Per quanto riguarda l'assioma '''A5''':
:<math>A5.1\qquad A+\bar A=1\qquad\qquad A5.2\qquad A\cdot \bar A=0</math>
usufruendo della tabella '''6.1''', possiamo facilmente verificarlo ponendo '''A=1''', '''A=0''' e viceversa:
:<math>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}</math>
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<sub>M</sub>''':
:::::<math>B_M=<I_M,\cap{},\cup {},\bar {}\ ,\phi,I_M> </math>
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<sub>M</sub>''' ne contiene '''2<sup>n</sup>'''.
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<sub>1</sub>...L<sub>10</sub>): l'insieme '''L''' delle proposizioni, con le operazioni <math>\land,\lor,\sim </math> è un'algebra di Boole:
:::::::<math>B_L=<L, \lor , \land, \sim , P, P> </math>
L'algebra delle proposizioni ha l'implicazione reciproca (↔) come relazione di equivalenza.
=== Algebra dei vettori
Si consideri [[w:matrice|l'insieme]] dei vettori binari
::<math>X=(x_1,x_2, ...,xi ...,x_n)=(x_i)\quad x_i\in {0,1}\quad (i=1...n)</math>
Questo insieme comprende:
::::<math>\begin{matrix}\underbrace{2\cdot 2\cdot 2...\cdot 2}_{n\ fattori}\end{matrix}=2^n\quad {elementi}</math>
Si possono introdurre [[w:matrice|le operazioni seguenti]]:
1) Prodotto
Dati due vettori '''X''' e '''Y'''
::::<math>X=(x_1,x_2....,x-n)=(x_i)</math>
::::<math>Y=(y_1,y_2....,y_n)=(y_i)</math>
si chiama prodotto booleano di '''X''' e '''Y''', denotato con <math>X\cdot Y</math>, il vettore
::<math>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) </math>
2) Somma
Dati due vettori '''X''' e '''Y''' definiti come sopra, si chiama somma booleana di '''X''' e '''Y''' il vettore:
:::<math>X+Y=(x<-1+y_1,....x_i+y_i,....x_n+y_n)=(x_i+y_i)</math>
3) Complemento
Dato un vettore <math>X=(x_1,..,x_i,...,x_n)</math> il complemento di '''X''' è il vettore:
:::<math>\overline {X}=(\overline {x_1},....\overline {x_i},....\overline {x_n})=(\overline {x_i})</math>
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:
::::<math>0=(0,0, ...,0)\qquad (x_i=0\quad i=1,...n)</math>
5) Vettore unità
È il vettore formato unicamente da '''1''':
:::<math>1=(1_1,1_2,...1_i,...1_)\qquad x_i=1\qquad i=(1....n)</math>
In queste condizioni l'insieme dei vettori binari ad '''n''' dimensioni, fornito di queste tre operazioni, è un'algebra di Boole a 2<sup>n</sup> elementi, con '''0''' e '''1''' per elementi costanti:
::::<math>B=<{x},+,\cdot, -, 0,1></math>
Si può dimostrare l'asserto facendo vedere che gli assiomi'''A1.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:
:::<math>[(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)]</math>
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 '''( <math> +,\cdot ,\bar {} \ )</math>'''.
Più precisamente si può dire:
# '''0''' e '''1''' sono espressioni
# ogni variabile '''x''' è una espressione
# se '''A''' è una espresssione, anche '''<math>\bar A</math>''' lo è
# se '''A''' e '''B''' sono espressioni, anche '''A+B''' e '''A*B''' lo sono
# un'espressione può essere ottenuta applicando le regole'''1, 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
:::<math>G(x_1,x_2.....x_n)</math>,
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 <math>(a_1,a_2...a_n)</math> di valori particolari attribuiti alle variabili <math>(x_1.x_2...x_n)</math>. L'elemento ottenuto, calcolando la '''G''' in corrispondenza dell'assegnazione <math>(a_1,a_2...a_n)</math>, è il valore dell'espressione a tale assegnazione.
Sia data ad esempio l'espressione:
:::<math>G(A,B,C)=A\cdot B+A\cdot C+B\cdot C+\bar A\cdot \bar B\cdot \bar C</math>
il suo valore per la combinazione ( 1,0,1 ) (cioè A=1, B=0, C=1) sarà:
:::<math>G(1,0,1)=1\cdot 0+1\cdot 1+0\cdot 1+0\cdot 1\cdot 0=1</math>
Se si calcolano i valori dell'espressione in corrispondenza a tutte le possibili combinazioni dei valori delle variabili, si definisce una funzione '''<math>f_G(x_1...x_n) </math>''' di '''E<sup>n</sup>''' 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<sub>G</sub>'''.
Consideriamo ad esempio la funzione ''Somma di due variabili'' che, ad ogni coppia di valori, associa la loro somma; l'espressione sarà:
::::<math>S(A,B)=A+B</math>
avremo:
:::<math>S80,0)=0\quad S(0,1)=1\quad S(1,0)=1\quad S(1,1)=1</math>
in tal modo abbiamo definito la funzione somma; cioè la corrispondenza che, mediante '''S(A,B)''', viene generata tra '''E<sup>2</sup>''' ed '''E'''.
Vi è inoltre da notare che un'espressione definisce un'unica funzione mentre, per una funzione data di '''E<sup>n</sup>''' in '''E''', esistono infinite (a causa, ad esempio, della legge di idempotenza) espressioni che la generano. Così nell'algebra
::::<math>B=<|0,1|, + ,\cdot , \bar {} , 0 , 1 ></math>
le espressioni
:::<math>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)}</math>
rappresentano la stessa funzione definita dalla tabella:
{| class="wikitable"
|-
Line 306 ⟶ 419:
|}
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<sup>'</sup>''' sarà rappresentata dal segno '''='''. Si può verificare che essa è una relazione di equivalenza nel senso usuale.
Line 313 ⟶ 428:
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:
Ogni espressione booleana di una variabile si può sempre esprimere medfiante una espressione del tipo:
:::<math>F(x)=F(1)* x+F(0)* \bar x\qquad\qquad (\sigma)</math
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è:
:::::<math>F(x)=F(1)=F(0)=A</math>
Line 329 ⟶ 446:
:::::<math>F(x)=A=A\cdot 1=A(x+\bar x)=A x+a \bar x=F(1)x+F(0)\bar x</math>.
b) La funzione assume il valore della variabile '''x''': P(x)=x; avremo:
:::::<math>P(1)=1\qquad\qquad\qquad P(0)=0</math>
Line 337 ⟶ 454:
:::::<math>P(x)=x=x+0=x+0\cdot\bar x=1\cdot x+0\cdot\bar x=P(1)x+P(0)\bar x</math>
c) La funzione assume il valore della variabile complimentata: '''<math>G(x)=\bar x</math>''' avremo:
:::::<math>G(1)=0\qquad\qquad G(0)=1</math>
Line 357 ⟶ 474:
applicando la (<math>\sigma</math>) su '''F(x)''' e '''G(x)''' otterremo:
:::<math>K(x)=[F(1)x+F(0)\bar x]+[G(1)x+G(0)\bar x]=</math
:::<math>[F(1)+G(1)]x+[F(0)+G(0)]\bar x=K(1)x+K(0)\bar x</math>
Line 366 ⟶ 484:
applicando la (<math>\sigma</math>) su '''F(x)''' e per il primo e secondo teorema di Morgan avremo:
:::::<math>N(x)=\overline {F(1)x+F(0)\bar x=}</math
:::::<math>\overline {F(1)x}\cdot \overline{F(0) \bar x}=[ {\overline {F(1)}+\bar x}]\cdot [ {\overline {F(0)}+\bar \bar x}]=</math
:::::<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
:::::<math>[\overline{F(1)}\cdot\overline{F(0)}] (x+\bar x)+\overline{F(0)}\bar x+\overline{F(1)} x=</math
:::::<math>\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=</math
:::::<math>[\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=</math
:::::<math>\overline{F(1)}\cdot x+\overline{F(0)}\cdot\bar x=N(1)\cdot x+N(0)\cdot\bar x</math>
Abbiamo così dimostrato che le operazioni
:::::<math>f(x)=A x+B \bar x\qquad\qquad (dove\ A=F(1) e B=F(0))</math>
Line 381 ⟶ 499:
nella quale compaiono solo due costanti '''F(1)''', '''F(0)''' facilmente determinabili data l'espressione della funzione.
È 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:
::::::<math>F(x_1,x_2,....,x_n</math>
Line 393 ⟶ 513:
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(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}+</math
::::::<math>[F(
::::::<math>
::::::<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>
Si può continuare ad applicare il teorema di '''Shannon''' fino all'esaurimento delle variabili; infine si otterrà la seguente espressione:
Line 406 ⟶ 527:
::::<math>x_i^{e_i}=\begin{cases}x_i,&\mbox{quando}\quad{e_i=1}\\\bar x,&\mbox{quando}\quad{e_i=0}\end{cases}</math>
ed '''<math>e=(e_1,e_2,...,ee_n)</math>''' 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:
:::<math>(\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}</math>
:
La forma algebrica del secondo menbro di <math>(\sigma ')</math> porta il nome di '''[[w:Forma normale disgiuntiva|forma canonica disgiunta]]''', volendo indicare con questa terminologia, cher essa è una somma di prodotti.
In essa compaiono i <math>2^n</math> possibili coefficienti '''F(e)''' ed altrettanti monomi della forma:
:::::<math>(\alpha)\qquad e_1^{e_1} x_2^{e_2}...e_i^{e_i}...x_n^{e_n}</math>
Una espressione booleana
Un prodotto della forma <math>(\alpha)</math> si chiama '''[[w:Algebra di Boole|prodotto fondamentale]].'''
Applicando il principio di dualità si deducono le formule seguenti:
:::::<math>F(x)=[F(1)+\bar x]\cdot[F(0)+x]</math> (teorema di Shannon duale)
::<math>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}]</math>
che prende il nome di '''forma congiuntiva'''.
Essa è un prodotto di somme. Le somme della forma:
:::::::<math>x_1^{e_1}+x_2^{e_2}+...+x_i^{e_i}+...+x_n^{e_n}</math>
sono chiamate somme '''somme fondamentali'''.
In maniera più compatta si scriverà:
Line 445 ⟶ 572:
dove <math>2^n -1-e</math> = complemento ad 1 di e.
== Metodo pratico del calcolo di un complemento ==
Line 452 ⟶ 578:
[[File:Regole di complementazione.png|right]]
Si noterà che questa tabella è differente, nelle ultime righe, da quella che definisce la regola di dualizzazione:
=== Esempio ===
:<math>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}</math>
Line 462 ⟶ 590:
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.
:::::<math>\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}}=</math>
:::::<math>(A\cdot{\bar B+\bar C\cdot\bar D+\bar A\cdot B})\cdot ({\overline{A\cdot B}\cdot {\overline{B\cdot C}}})=</math>
:::::<math>(A\cdot{\bar B+\bar C\cdot\bar D+\bar A\cdot B})\cdot (\bar A+\bar B)\cdot (\bar B+\bar C)</math>
==== Secondo metodo ====
:::::<math>(A\cdot{\bar B+\bar C\cdot\bar D+\bar A\cdot B})\cdot (\bar A+\bar B)\cdot (\bar B+\bar C)</math>
come si vede questo secondo metodo è molto più rapido.
== Riduzione ad un livello di complementazione in una espressione ==
Line 478 ⟶ 609:
:::::<math>F=\overline{\bar A+B+\overline{C+D}+E}</math>
è 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à:
:::::<math>F=\overline{(\bar A+B)}\cdot \overline{\overline{(C+D)}+E}=(A\cdot \bar B)\cdot (C+D)\cdot \bar E</math>}
cioè si è ottenuta una espressione dove gli elementi sono complimentati al massimo una volta.
Tale espressione si potrà sviluppare in somma di prodotti:
:::::<math>F=A\cdot \bar B\cdot C\cdot \bar E+A\cdot \bar B\cdot D\cdot \bar E</math>
== Relazione tra espressione duale e complemento ==
Data una espressione di una funzione '''<math>F(x_1,x_2,...,x_n)</math>''' le tavole delle regole di dualizzazione e di complementazione permettono di dedurre due espressioni associate alla funzione data:
[[File:Tabella duale e complemento.png|right]]
:::::<math>\sim F(x_1,x_2,...x_n)\qquad\qquad (duale)</math
:::::<math>\bar F(x1,x2,...,x_n)\qquad\qquad (complemento)</math>
La
:::::<math>\sim F(x1,x_2,...,x_n)=)\bar F(\bar x_1,\bar x_2,...,\bar x_n)\qquad\qquad (\beta)</math>
Line 507 ⟶ 640:
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 <math>(\beta)</math> è verificata.
[[Categoria:Algebre booleane e progetto logico dei calcolatori digitali|Algebre booleane]]
{{Avanzamento|100%|12 giugno 2018}}
| |||