Numeri binari ed algebre booleane

I computer: macchine superveloci, potenti e sempre più “intelligenti”, capaci oramai di riconoscere visi, suoni, immagini – svolgere calcoli mostruosi come i sistemi di equazioni differenziali non lineari, scomporre in fattori primi, operare algoritmi di crittografia, anche i più complessi svolgere alcune dimostrazioni matematiche come il famoso “teorema dei 4 colori” ecc… Tutte operazioni non banali, che non si sa come sia possibile – un insieme di componenti elettroniche nascoste in quella “scatola nera” – sia in grado di fare! La cosa sorprendente è che alla base di tutto ci sono solo due simboli, su cui si fonda tutta l’informatica e l’elettronica digitale! Due simboli che hanno aperto la strada alla più grande era tecnologia mai vista prima, sin dagli anni 30, da quando i calcolatori hanno iniziato a muovere i primi passi: lo \( 0\) e l’\(1\). Questi due simboli, costituiscono il cosiddetto sistema binario (di numerazione in base 2), già intuito, addirittura da Leibniz nel 1671 e formalizzato da George Boole nel 1854. Scopo della disquisizione è analizzare rapidamente le caratteristiche di questo sistema, delle conseguenze in ambito elettronico e del ruolo centrale nell’informatica.

---

il nulla ed il tutto

---

Sistemi posizionali

Un sistema di numerazione, è un insieme finito di simboli che soddisfano a certe regole e convenzioni. Ad esempio il sistema decimale è un insieme di \( 10 \) simboli, le cifre definito nel modo seguente: $$ \mathrm{DEC} = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} $$ Il nome “decimale”, indica proprio che le cifre sono dieci (da 0 a 9). Il sistema decimale, così come molti altri sistemi (incluso il sistema binario) è un sistema posizionale; nel senso che in un numero (inteso come giustapposizione di una o più cifre) conta la posizione che la singola cifra assume relativamente nel numero (cosa non valida nei sistemi additivi: vedi: sistema romano). Inoltre, per i sistemi posizionali è importante il numero di simboli del sistema, questo numero è chiamato base del sistema di numerazione e come vedremo sarà fondamentale nel prosieguo.

Vediamo ora qual è il significato dei numeri: ad esempio consideriamo il numero (in decimale, notate il pedice) \( 15163_{10} \). Vedete che compaiono due cifre \(1\) in “posizioni diverse”. Questo fa si che il valore degli \( 1\) differisca, l’un l’altro per via della posizione diversa. Per capire questa caratteristica bisogna introdurre un’operazione molto importante nella teoria dei sistemi di numerazione: la cosiddetta decomposizione polinomiale del numero rispetto alla base:

$$ 15163_{10} = 3\cdot \color{#990000}{10}^{0} + 6\cdot \color{#990000}{10}^{1} +
1\cdot \color{#990000}{10}^{2} + 5\cdot \color{#990000}{10}^{3} +
1\cdot \color{#990000}{10}^{4} $$

Osservate questa espressione: Ogni cifra viene moltiplicata per la base elevata alla posizione
(si parte dalla posizione 0 per la cifra più a destra meno significativa (LSB), e
si aumenta di uno spostandoci verso sinistra fino all’ultima cifra più significativa
(MSB) di: “unità”, “decine”, “centinaia” e così via…). Più in generale dato un numero
\( c_{n}c_{n-1}\ldots c{1}c_{0} \) (insieme di \( n\) cifre giustapposte), espresso
in un sistema posizionale a base ( B ), la decomposizione polinomiale intrinseca è data dalla formula:

$$ {\large c_{n-1}\ldots c_{1}c_{0} = \sum_{j=0}^{n-1} c_jB^j } $$

$$ \diamond $$

Sistema binario

Siamo pronti adesso, per introdurre il
sistema binario nella sua semplicità e potenza.
Iniziamo dalla base, che è ovviamente \( 2\), motivo per il quale, talvolta, il sistema binario è noto anche con
il nome più tecnico: sistema in base 2

$$ \mathrm{BIN} = {0, 1} \hspace{2cm} \mathrm{B_{BIN} = |\mathrm{BIN}| = 2} $$

Per il sistema binario, valgono le operazioni elementari
analoghe al classico e noto sistema decimale:

• Somma Binaria
  La somma binaria tra due numeri in base 2, si svolge allo stesso modo di come si svolge nel sistema decimale, si sommano le singole cifre e si effettuano i riporti
• Prodotto Binario
  Il prodotto binario tra due numeri in base 2, si svolge allo stesso modo di come si svolge nel sistema decimale, si svolgono i semo-prodotti e si somma tutto.

I due algoritmi di somma e prodotto, non l’abbiamo detto, ma è sottinteso, e si assume che si sappiano sommare le singole cifre, ossia, che siano definite tutte le somme possibili e tutti i prodotti possibili tra ogni simbolo del sistema. Queste somme-banali vengono riportate nelle cosiddette tavole pitagoriche che a scuola si imparano a memoria. Nel sistema binario le suddette tavole sono relativamente semplici:

Gli algoritmi di somma e prodotto, sono una semplificazione della regola della decomposizione a cis sussegue il raccoglimento e la somma dei termini simili, come se si operasse in algebra elementare. Ad esempio: sappiamo che la somma tra \( 13\) e \( 38 \) è \( 51 \). possiamo esprimere questo mediante la decomposizione:

$$ \Bigl( 3\cdot 10^0 + 1\cdot 10^1 \Bigr) + \Bigl( 8\cdot 10^0 + 3\cdot 10^1 \Bigr) = $$
$$ = \Bigl( (3+8)\cdot 10^0 + (3+1)\cdot 10^1 \Bigr) = $$
$$ = 11 \cdot 10^0 + 4\cdot 10^1 = 1\cdot 10^0 + 1 \cdot 10^1 + 4\cdot 10^1 = $$
$$ = 1\cdot 10^0 + (1+4)\cdot 10^1 = 51 $$

Osservate come il riporto sia legato ad un semplice cambio di raggruppamento.

Per esprimere un numero binario nella rappresentazione classica si giustappongono le cifre
binarie tenendo conto della decomposizione polinomiale di base \( 2\): \( \left(\sum_{j=0}^{n-1}b_j2^j \right) \).
Nel sistema binario la decomposizione assume un significato molto semplice, spesso utile nelle conversioni ( ) da sistema a sistema:
Le posizioni delle cifre corrispondono ai pesi (per convertire da base 2 a base 10 si sommano i pesi
corrispondenti agli 1) che compaiono nel numero come mostrato negli esempi di seguito:

$${\Large\underbrace{\overset{\small 8}{\overset{\downarrow}{1}}\overset{\small 4}{\overset{\downarrow}{0}}
\overset{\small 2}{\overset{\downarrow}{1}}
\overset{\small 1}{\overset{\downarrow}{0}}}
} $$
$${\large 10 }$$

E’ possibile rappresentare anche i numeri negativi. I metodi principali sono il complemento ad 1, la rappresentazione in modulo e segno ( ) ed il complemento a 2 ( ). Nella rappresentazione in modulo e segno (abbr: MS), si rappresentano separatamente il modulo (mediante la codifica naturale binaria (NBN)) ed il segno (- con un 1) e (+ con uno 0). Nel complemento ad 1 si invertono semplicemente i bit, ed infine nel complemento a 2 (più importante) si invertono i bit e si aggiunge 1, e si scopre sorprendentemente (per la felicità dei progettisti hardware, gli ingegneri elettronici per intenderci 😉 ), che così facendo si riconduce la differenza binaria ( ) alla somma a livello circuitale… un vero traguardo!

$$ (c_{n}c_{n-1}\ldots c_{1}c_{0}){MS} = (0 \leftrightarrow +, 1 \leftrightarrow – )|c{n}c_{n-1}\ldots c_{1}c_{0}| $$

$$ (c_{n}c_{n-1}\ldots c_{1}c_{0}){C1} = (\overline{c{n}}\hspace{1mm}\overline{c_{n-1}}\ldots \overline{c_{1}}\hspace{1mm}\overline{c_{0}})$$

$$ (c_{n}c_{n-1}\ldots c_{1}c_{0}){C2} = (c{n}c_{n-1}\ldots c_{1}c_{0})_{C1} + 1 $$

$$ \diamond $$

L’algebra della logica

Possiamo interpretare i simboli \( 0\) ed \( 1\) come valori di verità.
Ad esempio posso associare all’\( 1\) il valore di verità VERO (V), mentre allo \( 0\)
il valore di verità FALSO (F), o viceversa (è una scelta) – nel caso dell’esempio si parla di logica positiva, nel caso opposto di logica negativa.

Così facendo la somma ed il prodotto assumono il corrispettivo dei connettivi logici elementari ; in particolare la somma (+) corrisponde alla disgiunzione inclusiva \((\mathrm{OR} \) o, nel linguaggio insiemistico all’unione \( \cup\); il prodotto \( \cdot \) corrisponde alla congiunzione \( \mathrm{AND} \) o, nel linguaggio insiemistico all’intersezione \( \cap\), ed infine, aggiungendo il complemento \(\neg\) \(\mathrm{NOT}\) che corrisponde alla negazione, si definisce un’algebra reticolare detta anche algebra della logica o algebra booleana ( ) di cui ne parleremo a lungo.

Un concetto estremente importante è il teorema di dualità, che ci consente di ricavare a partire da una qualsiasi espressione booleana, la corrispettiva “gemella” duale, semplicemente scambiando gli operatori di somma e prodotto e gli \( 1\) con gli \( 0\). Come esempio, possiamo fare riferimento ai due importanti Teoremi di De-Morgan, che come potete osservare sono l’uno il “duale” dell’altro:

$$ \diamond $$

Teoremi di De-Morgan

$$ \overline{x\cdot y} = \overline{x} + \overline{y} \hspace{1cm} \overline{x + y} = \overline{x} \cdot \overline{y}
$$
Versione algebrica

$$ \overline{\left( \mathop{\bigcup}{i}\mathrm A_i \right) } = \mathop{\bigcap}{i}\overline{\mathrm A_i} \hspace{1cm} \overline{\left(\mathop{\bigcap}{i}\mathrm A_i \right) } = \mathop{\bigcup}{i}\overline{\mathrm A_i} $$

Versione insiemistica

$$ \spadesuit $$

$$ \diamond $$

Porte Logiche elementari

Cento anni dopo la scoperta di Boole, un ingegnere statunitense Claude Shannon (padre della teoria dell’informazione), ebbe l’idea grandiosa ed unica, di applicare l’algebra della logica all’elettronica, introducendo i circuiti logici di commutazione, su cui si aprì la strada verso la costruzione degli elaboratori elettronici, si cui diedero enormi contributi due colossi della scienza: John Von Neumann ed Alan Mathison Turing
ma questa è un’altra storia… Le porte logiche elementari sono un’astrazione circuitale degli
operatori booleani standard – le prime 3 sono l’\( \mathrm{AND}\), l’\( \mathrm{OR}\) ed il
\( \mathrm{NOT}\) che vi riporto di seguito.

Queste porte logiche sono alla base dei circuiti elettronici dei computers e di tutta la tecnologia elettronica. Tutta l’algebra di commutazione ruota attorno al concetto di porta logica. I circuiti vengono implementati con diverse tecniche di sintesi combinatoria e sequenziale e gli apparati elettronici costituiscono un insieme di queste porte interconnesse nei modi più disparati per realizzare ogni tipo di funzionalità.

Che dire… sull’algebra booleana si apre un mondo. Ci sarebbe tanto da dire, per ora potete iniziare a sbirciarvi qualche video sul canale ufficiale.

$$ \diamond $$

Codici

Un codice \( C\) è un insieme di simboli su cui sia stata definita una funzione biunivoca di mapping \( \Phi\), che associ a ciascun simbolo de codice un oggetto di un dato insieme \( A\). Questa funzione si chiama in gergo informatico: codifica ed esprime la corrispondenza codice-oggetto.

Ad esempio il (codice BCD ) ha una codifica espressa direttamente dalla formula di decomposizione, per i numeri dallo 0 al 10 (a lunghezza 4) :
$$ c_3c_2c_1c_0 \rightarrow \sum_{j=0}^3c_j2^j = \Phi(c_3c_2c_1c_0) $$

$$ {\Phi(0000) = 0, \Phi(0001) = 1, \ldots, \Phi(1010) = 10} $$

Altri esempi di codici sono il (codice Aiken 2421 ), il (codice XS3 ), il codice Gray ecc. di cui ne parlo in questa playlist () sul canale ufficiale.

$$ {\Large \diamond} $$