Algebra di Boole e reti di interruttori convertito

Reti logiche – Algebra di Boole e reti di interruttori

Algebra di Boole

Il collegamento tra la matematica e la logica si deve al matematico Boole, che riconobbe che il formalismo utilizzato in matematica potesse essere applicato ai ragionamenti e alla logica, che fino ad allora erano stati appannaggio del pensiero filosofico piuttosto che di quello matematico. Applicare il rigore matematico alla logica ha creato i presupposti per la formalizzazione di sistemi che portassero all'elaborazione automatica delle informazioni, una volta che queste fossero state codificate in termini di 0 e 1, cioè di simboli binari che potessero essere eventualmente interpretati come FALSO e VERO.

Un’algebra di Boole è un sistema matematico deduttivo che è definito dai seguenti elementi:

• Un insieme di elementi.
• Insieme di operatori definiti su quell’insieme dato.
• 0 e 1 sono costanti che appartengono all’insieme. Non è detto che ci siano solo questi due elementi, cioè queste due costanti esistono sicuramente, ma non è detto che non ci siano altri elementi in A.
• Insieme di assiomi, cioè affinché l’insieme sia un’algebra di Boole deve godere di alcune proprietà assiomatiche.

Questa tupla ci riassume gli elementi dell’algebra di Boole, dove il simbolo A viene utilizzato per identificare l’insieme di elementi, mentre i simboli +, ·, ' sono tre operatori definiti sull’insieme A. Questi operatori non indicano la somma, moltiplicazione e l’apostrofo ma l’AND logico (·, operatore binario, detto congiunzione), l’OR logico (+, operatore binario, detto disgiunzione) e il NOT logico (', operatore unario, detto complemento), quindi gli operatori logici.

Assiomi dell’algebra di Boole

Il fatto che queste proprietà siano assiomatiche significa che non abbiamo bisogno di dimostrarle, ma sono proprietà che imponiamo che debbano valere affinché ciò di cui stiamo parlando possa essere considerata un’algebra di Boole. Possiamo al massimo verificarle.

• Legge commutativa. Questa legge ci dice che gli operatori AND e OR godono della proprietà commutativa.
• Elemento identità. Questa proprietà assiomatica ci dice che 1 è l’elemento neutro dell’operatore AND e che la costante zero 0 è l’elemento neutro dell’operazione OR.
• Legge distributiva. Sulla sinistra vediamo la proprietà che vale per l’AND rispetto all’OR. A destra vediamo la stessa proprietà ma dell’OR rispetto all’AND. La proprietà di destra è applicata in modo duale. Nell’algebra non vale, mentre nell’algebra di Boole sì.
• Legge del complemento. Questa legge ci dice che l’AND tra un elemento e il suo complemento è sempre pari a 0. Invece, l’OR tra un elemento e il suo complemento è sempre pari a 1. Questa proprietà ci dice che l’insieme A deve essere composto da alcuni elementi e dai loro complementi in modo tale da essere chiuso rispetto a queste operazioni di AND, OR e NOT che in esso abbiamo definito. Quindi l’esistenza di un generico elemento a presuppone anche, all’interno dell’insieme. Quindi qualora quest’insieme contenesse più elementi dovrebbe necessariamente contenere anche i loro complementi.

Algebra booleana di commutazione

Questo tipo di algebra è un caso particolare di algebra di Boole, cioè l’algebra di commutazione, in inglese switching algebra. Avendo definito in modo assiomatico l’algebra di Boole non si presuppone di dover lavorare su un insieme binario perché abbiamo visto che si possono avere anche più elementi all’interno di un insieme. Questa algebra di Boole speciale, che definiamo come algebra di commutazione, è quella che si applica all’insieme binario che è l’insieme che viene chiamato insieme di Boole, o insieme booleano.

L’insieme booleano è quell’insieme che contiene come unici elementi le costanti 0 e 1 che compaiono nelle proprietà assiomatiche. L’insieme booleano è l’insieme minimo sotto al quale potremmo scendere per poter definire un’algebra di Boole perché senza le costanti 0 e 1 non riusciremmo ad esprimere delle proprietà assiomatiche e avere un solo elemento implica che non può avere complemento.

Adesso possiamo allora definire l’insieme generale A come insieme specifico di Boole B, composto dalle costanti 0 e 1 e definiamo variabile una qualunque variabile definita sull’insieme {0,1}, quindi ad esempio una variabile può assumere come valore soltanto 0 o 1. Una funzione booleana è una funzione che va da B a B. Questo significa che la funzione prende valori in B che attribuiamo a variabili indipendenti (perché questi valori possono essere presi in modo arbitrario) ma la funzione dice come da questi valori dipende un valore in B che è il valore della funzione. Quindi la funzione sancisce un legame funzionale tra le variabili indipendenti e una variabile dipendente. La funzione prende valori in B e restituisce un valore in B.

Β sta ad indicare il prodotto cartesiano dell’insieme booleano per sé stesso, perché noi, in questo prodotto cartesiano, andiamo a prendere le configurazioni delle variabili che utilizziamo come input per la nostra funzione. L’output è il valore calcolato sulla base di questi valori di ingresso e del legame funzionale che li lega alla variabile dipendente.

Specializzazione delle operazioni dell’algebra di Boole

In questo contesto andiamo a specializzare le tre operazioni che caratterizzano l’algebra di Boole. Questa specializzazione si fa sia ribadendo il simbolo che utilizzeremo per rappresentarle sia dando loro un significato usando due tipi di rappresentazione:

• Tabella della verità: per ogni coppia, nel caso degli operatori binari di valori, ci dice qual è il risultato. Qualora l’operatore sia unario, cioè che prende un solo operando, allora in questo caso la tabella della verità avrà solo un valore della variabile indipendente al quale corrisponderà il valore della variabile dipendente.
• Rappresentazione insiemistica utilizzando i diagrammi di Eulero Venn: Il quadrato rappresenta quello che nell’insiemistica viene chiamato insieme universo, cioè tutti i possibili casi, è lo spazio in cui ogni punto al suo interno rappresenta una situazione. I cerchi al suo interno rappresentano degli insiemi propri, o meglio, dei sottoinsiemi propri dell’insieme universo che sono rappresentativi di, in questo caso, e intese come condizioni di appartenenza a questi insiemi. Quindi posso dire che = 0, se prendo un punto al di fuori di un cerchio posso dire che = 1. Se io prendo un altro cerchio, cioè un altro insieme, e lo associo, posso dire analogamente che all’interno del cerchio ci sono i punti per i quali = 0 e all’esterno ci sono i punti per i quali = 1. Quindi, se i due cerchi si intersecano e un punto si trova all’interno di entrambi i cerchi succede che = 1 e = 1. Se un punto sta fuori da entrambi i cerchi allora succede che = 0 e = 0. Se un punto appartiene solo ad un cerchio può succedere che = 1 e = 0 oppure che = 0 e = 1. Il fatto che possono assumere solo due valori ci consente di rappresentare in modo netto il confine tra i vari casi.

Rappresentazione dell'AND

La configurazione 00 corrisponde ad un punto fuori dal cerchio. 01 e 10 corrispondono ad un punto che sta in uno solo dei due cerchi. 11 corrisponde ad un punto che si trova in entrambi i cerchi (parte arancione). Poi vediamo che 00 fa 0 e lo sappiamo perché 0x0=0, e sappiamo anche che l’AND è un’operazione per la quale l’1 è un elemento neutro e allora sappiamo anche che 0x1=0, che 1x0=0 e che 1x1=1. Quindi la parte arancione corrisponde alle configurazioni VERE di AND, che in questo caso è solo una. L’insieme si riduce all’intersezione arancione. Dal punto di vista insiemistico, l’AND corrisponde all’intersezione, ossia ∩.

Rappresentazione dell'OR

Con un procedimento analogo a quello precedente riusiamo a capire che 0+0=0, infatti questa volta l’elemento neutro è lo 0 e quindi possiamo anche dire che 0+1=1, che 1+0=1 e che 1+1=1. Questa volta abbiamo tre configurazioni VERE: due che mi dicono che la condizione di appartenenza è VERA se un punto appartiene solo ad uno dei due cerchi e una che mi dice che è VERA se un punto appartiene ad entrambi i cerchi. Quindi la parte arancione questa volta è l’unione tra i due insiemi. Dal punto di vista insiemistico, l’OR corrisponde all’unione, ossia ∪.

Rappresentazione del NOT

In questo caso abbiamo un solo elemento da considerare. Allora ', vale 0 quando si dice che non appartiene all’insieme, perciò, che è il suo complemento sarà 1. Questa è l’unica configurazione VERA che corrisponde alla parte arancione, cioè tutto ciò che non appartiene all’insieme. Dal punto di vista insiemistico, il NOT corrisponde al complemento proprio come nell’ambito della logica. Il complemento di un elemento si indica con ' oppure con ⋅ + '. Queste operazioni sono dotate di un’ulteriore rappresentazione: per l’AND, per l’OR e per il NOT. Il simbolo utilizzato per l’AND può essere anche omesso. L’operazione AND si dice anche congiunzione logica perché rappresenta l’operazione logica che dice che le due condizioni di appartenenza agli insiemi devono valere contemporaneamente. L’operazione OR si dice anche disgiunzione logica perché affinché sia verificata la funzione è sufficiente che sia vera o o. L’OR non è esclusivo ma è un OR inclusivo, che vale a dire che anche il caso in cui e siano contemporaneamente vere soddisfa la funzione.

Funzioni booleane

La tabella della verità, che ci permette di dare significato e definire gli operatori dell’algebra di Boole, in realtà ci consente anche di definire una qualunque funzione di variabili booleane. Se noi abbiamo una funzione di variabili, dobbiamo specificare il valore che la funzione assume a fronte di tutte le possibili configurazioni di ingresso di queste variabili. C’è una differenza sostanziale tra quello che ci può capitare di fare in matematica quando abbiamo una qualunque funzione di una o di più variabili e quello che possiamo fare in questo caso. La differenza è che qui stiamo lavorando su un insieme finito che ha solo due elementi e questo ci consente di definire una funzione enumerando tutti i suoi valori in corrispondenza di tutti i possibili valori delle variabili di ingresso. In questo caso lavoriamo con l’insieme booleano e quindi sappiamo bene che se abbiamo variabili indipendenti, le loro configurazioni è come una parola di bit. Quindi con variabili di input avremo possibili configurazioni di ingresso. Per esempio, una funzione che ha tre variabili di ingresso avrà possibili configurazioni di ingresso. Il modo più semplice per definire una funzione è dire che valore assume la funzione a fronte di queste possibili otto configurazioni diverse di ingresso.

Andiamo a vedere come sarebbe la tabella della verità con tre variabili indipendenti. Questa tabella ha variabili indipendenti chiamate E, ciascuna di queste otto righe corrisponde ad una delle otto configurazioni delle variabili indipendenti. Il modo in cui le configurazioni sono enumerate, cioè associate alle righe, è coerente con il significato numerico di quelle parole interpretate come numeri interi, questo perché un ordine è conveniente. Non possiamo inventarci tutte le funzioni che vogliamo; fissato il numero di variabili esiste un numero finito di possibili funzioni. Questo lo capiamo dal numero di righe della tabella della verità, che è finito. Definire una funzione vuol dire avere questa tabella in cui le prime tre colonne (supponendo una funzione a tre variabili) sono sempre uguali per ogni funzione. Quello che caratterizza la funzione è il valore che noi attribuiamo alla funzione (quarta colonna) in corrispondenza di ciascuna delle righe. Se le righe sono otto, su ognuna di queste righe possiamo scrivere un valore scelto tra 0 o 1. Quindi le possibili funzioni diverse che mi posso inventare con tre variabili di ingresso sono 2⁸ = 256 possibili funzioni.

Perché due funzioni siano diverse devono differire per almeno un bit, cioè per almeno il valore assunto a fronte di una configurazione di ingresso. Quindi è il numero delle diverse configurazioni dei valori della colonna che noi possiamo inventarci. Per esempio, con quattro variabili di input posso inventare 2¹⁶ = 65536 diverse funzioni e cioè 2²². Le possibili funzioni diverse con due variabili sono 2², cioè 16. Le possibili funzioni diverse con una variabile sono 2¹, cioè 4.

Proviamo a costruire le quattro tabelle della verità che hanno una sola variabile di ingresso:

Questa è una funzione costante. Questa è una funzione costante.

Le forme di rappresentazione delle funzioni sono più di una, infatti oltre a rappresentarle con la tabella della verità si possono rappresentare anche come espressioni booleane. Le espressioni booleane sono espressioni che sono composte da variabili booleane e costanti booleane unite da operatori booleani.

Come nelle espressioni matematiche, anche in questo caso si usano le parentesi per indicare la precedenza nella valutazione delle operazioni qualora questa non sia quella implicita. La precedenza implicita ci dice che per prima cosa si calcolano i complementi, poi si calcolano i risultati dell’AND e infine i risultati dell’OR. Di seguito possiamo vedere tutte le possibili funzioni diverse che possiamo costruire con quattro variabili indipendenti. Siccome sappiamo dare un’interpretazione numerica alle configurazioni di bit, possiamo anche dare, un’interpretazione numerica anche ad ogni riga della colonna, quindi possiamo dire che vale complessivamente 0 se ogni riga ha un valore pari a 0. Oppure, se la prima riga (supponiamo che sia quella meno significativa) della colonna è pari a 1 e poi tutti 0, allora posso dire che il valore della colonna è uguale a 1. Se le righe della colonna hanno come valori 0010, allora il valore colonna sarebbe 2. E così via. Questo valore che troviamo lo utilizziamo come pedice per dare il nome alle diverse (in questo caso 16) funzioni che rappresenta il valore numerico della configurazione dei bit della colonna.

Prendiamo in considerazione la funzione 5. Che espressione esprime questa funzione? Se guardo la tabella della verità, gli 1 che compaiono nella colonna sono in corrispondenza degli 0 della colonna, invece, valgono 0 in corrispondenza degli 1. Quindi in questo specifico caso, (, ) = '. Questa funzione non dipende da. Posso notare che le funzioni nella colonna di destra sono il complemento delle funzioni nella colonna di sinistra.

Proprietà non assiomatiche

Adesso vediamo delle proprietà che ora non sono più assiomatiche e quindi queste le dovremo dimostrare, mentre quelle assiomatiche possiamo solo dimostrarle.

Come facciamo a verificare che valga una proprietà? Prendiamo per esempio la proprietà commutativa della moltiplicazione. Se noi prendiamo la definizione dell’AND, cioè vediamo quali sono le righe della tabella della verità in cui l’AND vale 1 e quelle in cui vale 0. Possiamo provare a vedere cosa succederebbe alla tabella della verità se invertissimo le posizioni di e. Se la tabella della verità resta la stessa, vuol dire che vale la proprietà commutativa. Andare a vedere le righe dove e sono uguali non mi aiuta perché hanno lo stesso valore, devo andare a vedere se dove e sono diverse scambiando i due ottengo un’altra riga con lo stesso valore di. Se il valore di è lo stesso, allora vuol dire che la proprietà commutativa vale. Noi sappiamo che 0 ⋅ 1 = 0 e che 1 ⋅ 0 = 0, e allora possiamo dire che questa proprietà sia verificata. La proprietà commutativa dell’AND si mette in gioco solo nelle configurazioni dove e assumono valori diversi.

Come possiamo verificare l’assioma dell’elemento neutro? Possiamo ricorrere alla tabella della verità e osservare che se noi prendiamo la tabella della verità di AND abbiamo il caso in cui = 1 e = 0. Consideriamo le righe in cui = 0. A questo punto ci resta la riga = 1 e = 1 e la riga = 1 e = 0. Quindi in entrambi i casi abbiamo che è uguale a 0. Questo nel caso dell’elemento neutro della moltiplicazione (AND).

La verifica di tutte queste proprietà può essere fatta anche attraverso i diagrammi di Eulero Venn. Nei diagrammi di Eulero Venn, la costante 1 è l’insieme al quale appartengono tutti i sottoinsiemi.