Algebra di Bool

I connettivi logici, riducendo all'essenziale la complessità del linguaggio comune, corrispondono ad operazioni logiche così semplici da poter essere eseguite anche da una macchina. Analizzeremo ora dei circuiti logici che sono alla base del funzionamento dei calcolatori elettronici, i circuiti logici che esamineremo costituiscono un vero e proprio modello fisico delle operazioni logiche fondamentali. Il circuito elettrico più semplice è costituito da un generatore di corrente, per esempio una pila, un filo metallico che collega i due poli del generatore, un utilizzatore di energia, per esempio una lampadina e un interruttore.


I circuiti logici


Consideriamo ora il circuito seguente:

stato interrutore Astato interrutore Bstato lampadina
111
100
010
000

Nella tabella sopra, sono riportati i possibili stati in ingresso e i corrispondenti stati in uscita, tenendo presente che l'interruttore può essere aperto o chiuso e la lampadina accesa o spenta:

0 - stato chiuso/spento    1 - stato aperto/acceso

La tabella è identica alla tavola di verità del connettivo logico AND tenendo presente che: lo stato dell'interruttore A corrisponde allo stato della proposizione p e quello dell'interruttore B allo stato della proposizione q. Lo stato della lampadina corrisponde allo stato della proposizione composta p ∧ q. Il numero 1 corrisponde al valore vero, il numero 0 al valore falso. Il circuito logico con due interruttori in serie rappresenta dunque il connettivo logico ∧ e prende il nome di circuito logico AND.


Consideriamo ora il circuito seguente:

stato interrutore Astato interrutore Bstato lampadina
111
101
011
000

Gli interruttori A e B sono in parallelo, anche in questo caso abbiamo due segnali in ingresso e uno in uscita, affinchè il circuito sia chiuso, è sufficiente che uno dei due interruttori sia chiuso. Nella tabella, sono riportati i possibili stati in ingresso e i corrispondenti in uscita.

Anche questa tabella è identica a quella di un connettivo logico: la disgiunzione ∨ e prende il nome di circuito logico OR.



Si osservi il prossimo circuito:



stato interrutore Astato lampadina
10
01

Qui è presente un interuttore particolare, detto invertitore. Quando l'interruttore A è aperto passa corrente (nella figura di sinistra) e la lampadina è accesa. Quando l'interruttore A è chiuso non passa corrente (nella figura a destra)e la lampadina è spenta. In questo circuito si ha un segnale in ingresso ed uno in uscita e il secondo interruttore è dipendente dall'interruttore A poichè è trascinato da quest'ultimo. Questa volta la tavola del circuito è identica alla tavola di verità del connettivo logico NOT.

Il circuito con un interruttore invertitore rappresenta dunque il connettivo logico ¬P e prende il nome di circuito logico NOT



Lo schema sotto riprodotto riassume le relazioni tra operazioni logiche, operazioni insiemistiche e circuiti logici.


operazioni logicheoperazioni insiemistichecircuiti logici
ANDA ∩ B
p ∧ qintersezione
ORA ∪ B
p ∨ qunione
NOTÃ
¬ Pcomplementare

Sono comunque impiegate altre tre porte logiche: il NAND che può essere considerato come AND seguito da NOT, il NOR che può essere considerato come OR seguito da NOT e XOR che è OR "esclusivo" come riportato dallo schema sotto riprodotto.


operazioni logicheoperazioni insiemistichecircuiti logici
NANDcomplementare dell'intersezione
XORdifferenza simmetrica
NORcomplementare dell'unione


Esempi di circuiti logici e tavole di verità


1. Analizziamo il seguente circuito logico:

Corrisponde alla seguente proposizione molecolare: (¬p ∧ q) ∨ p.

A fianco la corrispondente tavola di verità:

pq¬p¬p ∧ q¬p ∧ q ∨ p
VVFFV
VFFFF
FVVVV
FFVFV


2. Analizziamo il seguente circuito logico:

Corrisponde alla seguente proposizione molecolare: (¬p ∨ q) ∧ p.

A fianco la corrispondente tavola di verità:

pq¬p¬p ∨ q(¬p ∨ q) ∧ p
VVFVV
VFFFF
FVVVF
FFVVF


3. Analizziamo il seguente circuito logico:

Corrisponde alla seguente proposizione molecolare: (p ∧ q) ∨ ¬q.

A fianco la corrispondente tavola di verità:

pq¬qp ∧ q(p ∧ q) ∨ ¬q
VVFVV
VFVFV
FVFFF
FFVFV


Attraverso la stesura delle tavole di verità si può verificare che le funzioni proposizionali corrispondenti alle leggi di de Morgan sono equiveridiche, cioè che valgono le seguenti uguaglianze:

1. ¬(p ∨ q) = ¬p ∧ ¬q

2. ¬(p ∧ q) = ¬p ∨ ¬q

Analizziamo la prima:

pqp ∨ q¬(p ∨ q)
VVVF
VFVF
FVVF
FFFV
pq¬p¬q¬p ∧ ¬q
VVFFF
VFFVF
FVVFF
FFVVV

Come si può notare le prime due colomnne e l'ultima colonna delle due tabelle corrispondono.


Analogamente si può verificare che anche le funzioni proposizionali corrispondenti alla proprietà distributiva sono equiveridiche:

(p ∨ q) ∧ r = (p ∧ r) ∨ (q ∧ r)



Reticoli di Boole

In un insieme E si suppongano definite due operazioni che indichiamo con i segni ∧, ∨ soddisfacenti alle seguenti condizioni:


a ∧ a = a

a ∨ a = a

a ∧ b = b ∧ a

a ∧ b = b ∧ a

proprietà commutativa

a ∧ (b ∧ c)=(a ∧ b) ∧ c

a ∨ (b ∨ c) = (a ∨ b) ∨ c

proprietà associativa

a ∨ (a ∧ b) = a

a ∧ (a ∨ b) = a

proprietà assorbimento

Si può introdurre una relazione che indichiamo con "<" col seguente significato: a < b se e solo se a ∧ b = a. Si può provare che si tratta di una relazione d'ordine.

Un reticolo è detto distributivo se in esso ognuna delle due operazioni ∨, ∧ è distributiva rispetto all'altra, ossia se:

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Notiamo che una qualunque delle due proprietà distributive implica l'altra, sicchè per verificare che un reticolo è distributivo basta constatare la validità di una delle due.



Semplificazione di combinazioni di operazioni logiche

Una prima semplificazione sulla notazione è la seguente: ∧ = *, ∨ = +. La motivazione di questa semplificazione deriva dal fatto che Boole fa corrispondere al numero zero il falso e al numero uno il vero.

Una delle caratteristiche delle operazioni booleane e che vi è più di una combinazione di operazioni in grado di produrre lo stesso risultato. In altri termini, la stessa tabella di verità può essere ottenuta con più di un circuito logico. L'obiettivo principale della semplificazione di circuiti logici consiste nel determinare le combinazioni di operazioni logiche che produrranno il risultato desiderato, usando il minimo numero di porte. Ciò ridece i costi e il consumo di energia dei circuiti logici e aumenta la loro velocità operativa. Talvolta un secondo obiettivo è quello di produrre un circuito logico che impiega soltanto un certo tipo di porte. Elenchiamo alcune proprietà algebriche delle operazioni booleane.

¬(¬A) = A

(A + B) + C = A + (B + C)

(A * B) * C = A * (B * C)

A + (B * C) = (A + B) * (A + C)

A * (B + C) = (A * B) + (A * C)

A * A = A

¬(A + B) = ¬A * ¬B

¬(A * B) = ¬A + ¬B

Concludendo la base teorica per il funzionamento degli elaboratori è la logica di Boole che consiste in un certo numero di operazioni che possono essere applicate a variabili logiche o Booleane aventi due soli stati. Le operazioni booleane possono essere rappresentate dai simboli dell'algebra booleana, da circuiti logici in cui essi appaiono come porte o da tabelle di verità. Tutte le operazioni logiche possono essere espresse come combinazioni di operazioni elementari AND, OR, NOT, però sono impiegate altre tre operazioni NAND, NOR, EOR. Le espressioni logiche possono essere semplificate per ridurre il numero di operazioni o per usare soltanto certe operazioni, pur ottenendo gli stessi risultati.



Esempi di semplificazioni di circuiti logici

Il circuito di sinistra può essere tradotto con la seguente proposizione: z = ¬(¬(x * y)). Semplificando: z = ¬(¬(x * y)) = ¬(¬(x + y)) = x + y. Quindi il circuito precedente si può semplificare riducendolo al seguente:



Analogamente questo circuito:

può essere semplificato riducendolo al seguente:



Analogamente questo circuito:

può essere semplificato riducendolo al seguente: