Algebra Booleana
 
  Esistono vari modi per esporre in maniera formale il concetto di algebra booleana, il modo scelto da noi è incline all'approccio algebrico ed è il meno referenziale possibile. Le decomposizioni concettuali che sono state fatte (reticolo/distributivo/limitato/complementato) hanno lo scopo di mettere in evidenza quanto in realtà il concetto di algebra booleana sia un caso particolare del concetto di reticolo. Soventemente, infatti, si utilizza il termine di algebra booleana con un'accezione molto piú limitata che in letteratura è nota invece come algebra binaria o algebra a due valori o ancora, con terminologia anglosassone switching algebra.

Un'algebra booleana è, per definizione, un reticolo distributivo, limitato e complementato. Vediamo in dettaglio che cosa ciò significa.

Formalmente, sia (A, ∧, ∨) la struttura algebrica costituita da un insieme A non vuoto e da due operazioni binarie ed interne. Tale struttura è un reticolo se soddisfa le seguenti proprietà formali:

  • A ≠ Ø
  • (a ∧ b) ∧ c = a ∧ (b ∧ c) essendo a, b, c ∈ A (proprietà associativa dell'operatore ∧)
  • (a ∨ b) ∨ c = a ∨ (b ∨ c) essendo a, b, c ∈ A (proprietà associativa dell'operatore ∨)
  • a ∧ b = b ∧ a essendo a, b ∈ A (proprietà commutativa dell'operatore ∧)
  • a ∨ b = b ∨ a essendo a, b ∈ A (proprietà commutativa dell'operatore ∨)
  • a ∧ a = a essendo a ∈ A (idempotenza dell'operatore ∧)
  • a ∨ a = a essendo a ∈ A (idempotenza dell'operatore ∨)
  • a ∧ (a ∨ b) = a essendo a ∈ A (assorbimento dell'operatore ∧)
  • a ∨ (a ∧ b) = a essendo a ∈ A (assorbimento dell'operatore ∨)

Se valgono inoltre le seguenti proprietà

  • a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) essendo a, b, c, ∈ A (proprietà distributiva del'operatore ∧ rispetto all'operatore ∨)
  • a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) essendo a, b, c, ∈ A (proprietà distributiva del'operatore ∨ rispetto all'operatore ∧) (dualmente derivabile, non è un assioma)
esso è detto anche distributivo.

Un reticolo in cui siano definiti gli elementi neutri per entrambe le operazioni si dice limitato. Formalmente:

  • ∃1 ∈ A | ∀ a ∈ A a ∧ 1 = a (elemento neutro dell'operatore ∧)
  • ∃0 ∈ A | ∀ a ∈ A a ∨ 0 = a (elemento neutro dell'operatore ∨)

a′ è il complementare di a se soddisfa le seguenti proprietà

  • a′ ∧ a = 0
  • a′ ∨ a = 1

il complementare di a viene anche indicato con il simbolo ¬a. Facciamo notare al lettore che è possibile parlare di complementare solo dopo aver accertato l'esistenza degli elementi neutri.

Un reticolo si dice complementato se vale la seguente proprietà

  • ∀ a ∈ A ∃ a′ | a′ = ¬a
ovvero ogni elemento del reticolo è dotato di complementare.

È immediato notare che le precedenti proprietà sono formalmente identiche a coppie avendo avuto l'accortezza di scambiare l'operatore ∧ con ∨ e 0 con 1;.

Due proprietà molto importanti sono le seguenti:

a ∧ 0 = 0  ∀a∈A (0 è lo zero formale dell'operatore ∧)
a ∨ 1 = 1  ∀a∈A (1 è lo zero formale dell'operatore ∨)

Dimostrazione. Limitiamoci a dimostrare la prima essendo la seconda formalmente identica.

a ∧ 0 ⇒ (per la proprietà di elemento neutro di 0 rispetto a ∨)
0 ∨ (a ∧ 0) ⇒ (per la proprietà dell'assorbimento)
0 (q.e.d.)

Il precedente risultato è di supporto alla derivazione di un teorema molto noto – il cosiddetto Teorema di De Morgan – il cui enunciato è riassunto nelle due leggi seguenti

¬(a ∧ b) = ¬a ∨ ¬b   ∀ a,b ∈ A
¬(a ∨ b) = ¬a ∧ ¬b   ∀ a,b ∈ A

Dimostrazione. Limitiamoci a dimostrare la prima delle due leggi essendo la seconda formalmente identica.

Osserviamo, preliminarmente, che ciò che si chiede di dimostrare è che ¬a ∨ ¬b è il complementare di a ∧ b. La nostra dimostrazione, invero molto semplice, dovrà mostrare che:

(a ∧ b) ∧ (¬a ∨ ¬b) = 0 ∀ a,b ∈ A
(a ∧ b) ∨ (¬a ∨ ¬b) = 1 ∀ a,b ∈ A

prendiamo la prima:

(a ∧ b) ∧ (¬a ∨ ¬b) ⇒ (proprietà distributiva di ∨ rispetto a ∧)
(a ∧ ¬a ∧ ¬b) ∨ (b ∧ ¬a ∧ ¬b) ⇒
0 ∨ 0 = 0

e ancora:

(a ∧ b) ∨ (¬a ∨ ¬b) ⇒ (proprietà distributiva di ∧ rispetto a ∨)
(a ∨ ¬a ∨ ¬b) ∧ (b ∨ ¬a ∨ ¬b) ⇒
1 ∧ 1 = 1

con ciò abbiamo concluso la prova.

Switching algebra

Dopo questa introduzione astratta cambiamo registro e approcciamo l'oggetto della discussione in modo più pragmatico. Andremo adesso a toccare quella che potremmo chiamare L'algebra degli interruttori, alla base della progettazione dei circuiti logici.

Consideriamo l'insieme costituito dagli elementi {0, 1} e definiamo su esso due operazioni binarie (ed ovviamente interne). Queste operazioni sono comunemente chiamate AND e OR e vengono indicate anche facendo uso dei simboli * e + che, ricordando le usuali operazioni di moltiplicazione e di addizione ne facilitano la manipolazione algebrica. Tuttavia è bene precisare sin d'ora una notevole differenza: la distributività vale anche per l'addizione rispetto alla moltiplicazione. A queste si aggiunge anche l'operatore di complementazione NOT anche indicato col segno meno (-) per le stesse ragioni di omogeneità con le regole dell'algebra elementare, o con un apice (') notazione che noi preferiremo.

Funzioni booleane e tabelle di verità

Una funzione che abbia per dominio l'insieme costituito dalle n-ple di {0, 1} e per codominio {0, 1} viene detta funzione booleana di arietà n o più semplicemente ancora, funzione booleana n-aria.

Il modo usuale di rappresentarle consiste nel ricorrere alla loro tabulazione che viene comunemente detta tabella di verità.

Le tabelle di verità degli operatori AND, OR e NOT sono:

x y x AND y
0 0 0
0 1 0
1 0 0
1 1 1
x y x OR y
0 0 0
0 1 1
1 0 1
1 1 1
x NOT x
0 1
1 0

Non dovrebbe costituire un problema verificare che la struttura ({0, 1}, AND, OR, NOT) soddisfa le proprietà di reticolo booleano. In effetti esso è il più piccolo reticolo booleano. Inoltre è possibile dimostrare che la cardinalità dell'insieme sostegno di un reticolo booleano è necessariamente una potenza di due. Questa è una manifestazione del più intimo legame con l'insieme potenza e le operazioni insiemistiche di intersezione e unione, tale struttura è, in ultima analisi, un reticolo booleano.

Le tabelle di verità sono uno strumento universale di rappresentazione di una funzione booleana. Gli operatori AND, OR e NOT sono casi particolari di funzioni diadiche e monadica. Una tabella di verità può essere vista sotto un particolare punto di vista, ovvero come costituita da due sottoinsiemi disgiunti costituiti dalle n-nuple che hanno valore di verità 1 e quelle che hanno valore di verità 0. Questo fatto ci porta in modo naturale alla cognizione dei cosiddetti teoremi di rappresentazione che in sostanza affermano quanto segue: ogni funzione booleana di qualsiasi arietà può essere rappresentata come combinazione degli operatori AND, OR e NOT. Questo fatto ha dei risvolti pratici eccezionali e la sua tesi è dovuta a Shannon.

Una funzione booleana è detta mintermine se essa assume il valore di verità 1 per una e una sola n-pla. Analogamente, una funzione booleana è detta maxtermine se essa assume il valore di verità 0 per una e una sola ennupla. Ad esempio, la funzione:

x y w z f( x, y, w, z )
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0

è un mintermine. I mintermini di una funzione booleana n-aria vengono enumerati secondo l'ordinamento naturale delle n-ple quando queste vengono viste come rappresentazione in base 2 di un numero naturale. Il mintermine viene indicato, usualmente, con m_4. Osserviamo che, a seconda dell'arietà della funzione booleana, il mintermine m_4 rappresenta funzioni totalmente diverse. Un modo meno ambiguo potrebbe essere quello di specificare anche la cardinalità del dominio della funzione booleana, nel nostro caso potremmo srivere m_4_16: tale notazione non è ambigua e risulta utile in quei contesti in cui si manipolano funzioni booleane di arietà diverse in cui la prima notazione sarebbe ovviamente esposta ad ambiguità. Discorso analogo vale per i maxtermini che vengono denotati con la lettera "M", ad esempio, un modo bizzaro per indicare il NOT potrebbe essere M_1, o più precisamente M_1_2, l'OR sarebbe indicato come M_0 (M_0_4), analogamenete l'AND sarebbe m_3 (m_3_4). Un ultima osservazione: gli indici dei mintermini sono enumerati a partire da 0 a 2^n-1 dove 2^n, come è facile dimostrare; rappresenta la cardinalità del dominio di una funzione booleana di arietà n.

Data una funzione booleana vediamo come essa possa essere rappresentata con i mintermini:

x y w z f( x, y, w, z )
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 0
1 0 1 1 1
1 1 0 0 1
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0

che è equivalente a:
f( x, y, w, z ) =
  m_1( x, y, w, z ) OR
  m_4( x, y, w, z ) OR
  m_7( x, y, w, z ) OR
  m_8( x, y, w, z ) OR
  m_9( x, y, w, z ) OR
  m_11( x, y, w, z ) OR
  m_12( x, y, w, z ) OR
  m_14( x, y, w, z )
o più sintenticamente ancora:
f = m_1 OR m_4 OR m_7 OR m_8 OR m_9 OR m_11 OR m_12 OR m_14.

A questo punto non ci rimane che far vedere che un mintermine può essere costruito utilizzando gli operatori AND e NOT. Nel nostro caso m_4 può essere realizzato attraverso la seguente espressione: m_4( x, y, w, z ) = x'yw'z' avendo sottointeso di citare l'operatore di congiunzione (AND) come si è soliti fare. Ad una più attenta osservazione dovremmo essere capaci di derivarne la regola generale: l'apice è presente per quelle variabili il cui bit nella rappresentazione del mintermine è nullo. La funzione f, in definitiva, può essere espressa come:
f( x, y, w, z ) = x'y'w'z + x'yw'z' + x'ywz + xy'w'z' + xy'w'z + xy'wz + xyw'z' + xywz'
questa forma di rappresentazione è solitamente indicata con l'acronimo CSP che sta per Canonical Sum of Products. Il ragionamento fatto per i mintermini può essere condotto in maniera analoga per i maxtermini avendo cura di apportare le opportune modifiche e pervenire ad una forma di rappresentazione denominata CPS che sta per Canonical Product of Sums.

Sottolineamo il notevole risultato che abbiamo raggiunto: Ogni funzione booleana può essere rappresentata facendo uso esclusivo degli operatori AND, OR e NOT (Shannon). Questo risultato ha un risvolto pratico notevole. I PLA (Programmable Logic Array) sono delle matrici di resistenze interconnesse disposte su due piani ortogonali detti, appunto, piano AND e piano OR. Sul piano AND vengono composti i mintermini necessari, sul piano OR vengono disgiunti a implementare più di una funzione booleana. In pratica un PLA è un dispositivo per realizzare implementazioni di più funzioni booleane su di uno stesso circuito.

Il processo di minimalizzazione può essere portato avanti. Oltre agli operatori AND e OR risultano molto importanti, per gli esiti applicativi, gli operatori NAND e NOR che, come il nome suggerisce, sono la negazione degi precedenti, più precisamente:

  • x NAND y = NOT ( x AND y )
  • x NOR y = NOT ( x OR y )

Gli operatori NAND e NOR sono detti universali per la loro caratteristica di poter "implementare" ogni altro operatore incontrato sin'ora, in particolare gli operatori AND, OR e NOT. A titolo di esempio dimostriamo che l'operatore NAND è universale:

Dimostrazione.

NOT x = NOT( x AND x) = x NAND x
x AND y = NOT( x NAND y) = (x NAND y) NAND (x NAND y)
x OR y = NOT(NOT(x) AND NOT(y)) (in virtù di DeMorgan)
   = (((x NAND x) NAND (y NAND y)) NAND ((x NAND x) NAND (y NAND y))) NAND (((x NAND x) NAND (y NAND y)) NAND ((x NAND x) NAND (y NAND y)))

Resta chiaro che un operatore universale, preso così com'è, lascia molto a desiderare. Tuttavia è possibile fare ancora qualcosa analizzando la tavola di verità dei due operatori:

x y x NAND y
0 0 1
0 1 1
1 0 1
1 1 0
x y x NOR y
0 0 1
0 1 0
1 0 0
1 1 0

in virtù della dualità se interpretiamo gli 0 come 1 e, viceversa, gli 1 come 0 la tabella del NAND rappresenta i NOR, e viceversa. Questo fatto viene proficuamente utilizzato nelle implementazioni in circuiti elettronici. Gli operatori NAND e NOR si implementano efficientemente utilizzando al massimo due transistor per porta (in gergo elettronico gli operatori logici sono chiamati porte logiche) raggiungendo degli elevati livelli di densità che ne sanciscono il successo ingegneristico.

 


Valid XHTML 1.0!

Valid CSS!

home – e-mail
(C) 2003 by Giovanni Costagliola — All Rites Reversed