06-Logica Booleana

{gspeech style=2}

Come abbiamo visto, la logica del computer è una logica di tipo intrinsecamente binario, a partire dalla rappresentazione di un qualunque dato (una sequenza di bit). Negli anni ’40, quando i progressi tecnologici imposero in breve il computer sulle più tradizionali macchine elettromeccaniche, ci si ritrovò in un territorio all’epoca tutto da esplorare, se non da inventare e cioè la progettazione di componenti elettronici: era infatti loro il compito di implementare la logica binaria nel modo più naturale possibile (corrente/non corrente). Ci si accorse allora elle già da parecchi decenni i logici e i matematici avevano approfondito un settore di ricerca a cavallo tra le due discipline che sembrava fatto su misura per le nuove esigenze dei progettisti: per quanto potesse sembrare strano, infatti, verso la metà dell’Ottocento il matematico inglese George Boole aveva ideato e sviluppato un tipo di calcolo logico del tutto analogo – di più, formalmente equivalente – alla logica dei circuiti binari, che oggi va sotto il nome di logica (o “aritmetica”, a sottolinearne la valenza matematica) booleana.

O “VERO” O “FALSO”
Chiamiamo booleane tutte quelle variabili che assumono univocamente due valori, che chiameremo “0” e “1”. È il caso, per esempio, di affermazioni che possono essere solo vere o false, come “Questa matita è nera” o “Nella bottiglia c’è dell’acqua”.

OPERATORI BOOLEANI
Su queste variabili si può poi agire con degli “operatori”, cioè dei simboli che a partire da due variabili date ne producono una terza il cui valore dipende in un modo ben preciso – ed e questo a definire l’operatore – dai valori delle due variabili di partenza. Un operatore molto importante è AND (operazione di congiunzione) definito in questo modo:

se x e y sono due variabili booleane,”x AND y” è definita come la variabile booleana che vale 1 se x e y valgono 1 e che vale 0 in tutti gli altri casi. Si è soliti elencare tutti i possibili casi in tabelle dette tavole di verità, tavole che, costituiscono la definizione dell’operatore.

x	y	x AND y
0	0	0
0	1	0
1	0	0
1	1	1

Ad esempio, per indicare che un dato numero è compreso tra 5 e 6 possiamo unire le proposizioni «x maggiore di 5» e «x minore di 6». Se risulta essere vero che x > 5 e temporaneamente che x < 6 la frase composta usando le due proposizioni elementari unite dalla e risulta vera. In logica si usa a volte il simbolo •, oppure ^ per indicare l’operazione di composizione che abbiamo appena visto e che viene meglio definita come congiunzione logica.

Nella parte a sinistra sono elencate le combinazioni possibili delle due proposizioni logiche da combinare, a destra i possibili valori del risultato. I simboli V e F stanno ad indicare se una data proposizione è vera o falsa. Deduciamo dai valori indicati che la congiunzione logica fornisce una proposizione che è vera esclusivamente quando le sue due componenti lo sono.
Vado al cinema e piove è un’affermazione vera solo se sto effettivamente andando al cinema e se contemporaneamente piove.

x	y	x • y
F	F	F
F	V	F
V	F	F
V	V	V

ESEMPIO
Abbiamo costruito un elenco di valori numerici all’interno di Excel. Vogliamo fare in modo che solo alcuni dei valori vengano evidenziati. Si tratta di un’operazione di formattazione condizionali. Selezionando la voce di menu Formato/Formattazione condizionale compare la finestra:

In particolare vogliamo indicare che desideriamo che il valore della cella sia compreso tra due valori. Il calcolo effettuato per stabilire se un numero soddisfa tale requisito proprio un AND logico tra due condizioni.
Otteniamo il risultato illustrato in figura in cui i «voti» insufficienti sono evidenziati dal retino (a video si distinguono per il colore rosso).

Consideriamo ancora un’applicazione in Excel. Abbiamo costruito un elenco di dati composto da alcuni nomi e abbiamo inserito l’operazione di filtraggio. Essa consiste nel selezionare solo dei valori dell’elenco secondo alcuni criteri. Dal menu Dati si accede a Filtro automatico. In un secondo tempo si è inserito un’opzione che permette di selezionare i dati secondo dei criteri personalizzati. La personalizzazione consiste, in questo caso nello specificare un criterio per Cognome, tale per cui vengano visualizzati solo i cognomi che iniziano con la lettera D. Per fare ciò abbiamo dovuto indicare due condizioni unendole con una AND: si vede, infatti, dalla figura che si è unito la condizione «è maggiore o uguale a D’Addazio» con la condizione «è minore di Finaldi».

Ultimo esempio di utilizzo dell’AND logico: capita spesso di effettuare ricerche su Internet. Utilizzando un motore di ricerca, si specificano delle parole chiave che il file o documento dovrà contenere. Per indicare la presenza di più di una parola chiave si usa il segno +.

Operatore OR
Consideriamo adesso un’altra operazione logica fondamentale: la OR.
x OR y (operazione di disgiunzione) è falsa solo se entrambe le proposizioni sono false, mentre è vera se anche solo una tra x e y è vera.
L’operazione è indicata dal +, a volte dal segno Ú.
Tale operatore è la formalizzazione della congiunzione o di uso nel linguaggio comune: l’OR inclusivo.
Ad esempio: «Domani non so cosa fare, andrò al cinema oppure a passeggio». La frase appena vista è vera sia che io vada al cinema sia che vada a passeggio, tenendo conto che sarà vera anche nel caso in cui io faccia entrambe le cose.

x	y	x + y
0	0	0
0	1	1
1	0	1
1	1	1

ESEMPIO
Consideriamo un’operazione di filtro e vediamo di impostare una condizione OR con Excel.

Nel campo Città, impostiamo due condizioni, unite dal connettivo OR.

Il risultato è il seguente:

Operatore NOT
Manca ancora un operatore fondamentale, che assieme ad AND e OR permette di costruire tutte le frasi dell’algebra proposizionale: il NOT. Si tratta della negazione logica, cioè di quella operazione che inverte i valori di verità e viceversa. Una frase da vera passa a falsa e viceversa.
Si noti che la negazione logica si indica con una sopralineatura della proposizione da negare.

A	Ā
F	V
V	F

Operatori NAND e NOR
Esistono altri operatori che si possono comunque ottenere come combinazioni di AND, OR e NOT. Consideriamo dapprima l’operatore NAND e l’operatore NOR. Sono frutto dell’applicazione combinata di AND e NOT il primo, di OR e NOT il secondo.

x	y
F	F	V	V
F	V	V	F
V	F	V	F
V	V	F	F

Operatore EXOR e EXNOR
L’operatore EXOR viene anche chiamato OR esclusivo. È quella congiunzione logica che fornisce come valore di verità vero solo quando esclusivamente una delle due proposizioni componenti assume valore vero. «L’Inter o vince il campionato o non lo vince». È una proposizione in cui le due alternative si escludono a vicenda. In logica tale congiunzione si indica con un operatore che ha la seguente tabella di verità:

x	y	xÅy
F	F	F
F	V	V
V	F	V
V	V	F

È possibile ottenere l’ultima funzione di verità fondamentale invertendo la tabella dell’EXOR ottenendo l’EXNOR:

x	y
F	F	V
F	V	F
V	F	F
V	V	V

Associando logicamente più proposizioni in modo diverso, si ottengono espressioni logiche più complesse. Ad esempio:
A = oggi è giovedì
B = vado al cinema
C = vado al ristorante
A·(B+C) = oggi è giovedì “e” vado al cinema “o” vado al ristorante.

Il valore dell’espressione A·(B+C) si ricava dalla seguente tabella:

A	B	C	B+C	A·(B+C)
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	1	0
1	0	0	0	0
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1

Tutte le considerazioni fatte fin qui nel campo delle posizioni logiche si possono trasferire nel campo dei circuiti che trattano segnali a due valori, come sono quelli usati nei calcolatori e nei sistemi digitali in genere. La cosa è comprensibile se supponiamo di avere a che fare con circuiti composti solo da interruttori, che fanno passare o meno la corrente.

Possiamo fare il seguente parallelo:

Proposizione vera	Interruttore chiuso	1 – passaggio di corrente
Proposizione falsa	Interruttore aperto	0 – assenza di corrente
“o”	parallelo
“e”	serie

In circuito con due interruttori in serie passa corrente solo se entrambi la fanno passare, cioè sono chiusi; in un circuito con due interruttori in parallelo non passa corrente solo se entrambi sono aperti.

Se chiamiamo A e B i due interruttori e consideriamo il passaggio della corrente come funzione di A e B, il primo circuito esegue la funzione di “prodotto logico” (A·B), il secondo quello di “somma logica” (A+B).

Abbiamo visto le definizioni di somma e prodotto logico di variabili. Illustriamo ora le loro principali proprietà, che non si discostano molto da quelle utilizzate per l’algebra ordinaria. Infatti, sia la somma che il prodotto godono della proprietà associativa. Siano quindi A, B, C variabili binarie. Si ottiene allora:

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

e per il prodotto:

A·B·C=(A·B)·C=A·(B·C)

Quindi, considerata la somma A+B+C, possiamo prima associare A con B =(A+B) e successivamente sommare C; oppure partire associando B e C e sommare poi A. Le stesse condizioni valgono per il prodotto.

Considerando il significato che tale proprietà riveste riguardo ai circuiti logici, utilizziamo una porta AND a tre ingressi.
Ad essa, tramite la proprietà associativa, possiamo sostituire due porte AND a due ingressi ed ottenere lo stesso valore in uscita: le due reti logiche sono equivalenti fra loro.

In una somma logica o in un prodotto logico, scambiando fra loro gli addendi o i fattori, la somma ed il prodotto non cambiano.
È la proprietà commutativa; si ha quindi:

A+B=B+A
A·B=B·A

La proprietà distributiva dice invece che: A·(B+C)=A·B+A·C
Possiamo distribuire A all’interno della parentesi e moltiplicare termine a termine, oppure partendo da una somma di prodotti in cui è presente uno stesso fattore, raccogliere a fattor comune, senza che niente cambi.

Possiamo notare che ogni uguaglianza possiede la sua duale. Consideriamo, per esempio, la proprietà associativa e la proprietà commutativa per la somma. Scambiando il simbolo di addizione con quello di moltiplicazione otteniamo le due uguaglianze per il prodotto. Possiamo quindi passare da una relazione, ad esempio per la funzione OR, a quella duale per la funzione AND ottenendo altre leggi e proprietà. Il concetto di dualità, definito dal cambiamento della funzione AND in OR, e viceversa, e dal cambiamento di “1” in “0” (e viceversa), è un concetto fondamentale dell’algebra di Boole, e può essere definito nel seguente modo: se una equazione è vera, allora anche l’equazione duale è vera. Questa regola si rivela di grande importanza nel progetto logico dei circuiti.

Tornando alla proprietà distributiva che è tipica dell’algebra ordinaria e applicando il principio di dualità valido nell’algebra di Boole, operiamo lo scambio dei simboli:

La seconda uguaglianza è valida solo nell’algebra di Boole; si potrebbe dimostrare la sua validità utilizzando le proprietà che stiamo descrivendo.

Ulteriori proprietà dell’algebra booleana
La stessa cosa avviene per le leggi seguenti.
Leggi di identità. Data la variabile A si ottengono le relazioni:

A + 0 = A
A·1 = A

Il principio di dualità si applica ancora una volta e si esplica scambiando “0” con “ 1” e viceversa, nelle equivalenze considerate. Per spiegare invece come si ottiene il risultato, pensiamo un attimo agli insiemi e consideriamo la relazione contenente il prodotto.

“1” rappresenta l’insieme totale e che A può assumere i valori “0” oppure “1”. Supponiamo che A sia un insieme. Le possibilità sono due, o A è l’insieme totale (“1”) oppure è l’insieme vuoto (“0”), cioè o coincide oppure non ha niente in comune con 1. Nel caso in cui A sia 1, l’intersezione fra i due sarà ancora 1 poiché il risultato è un insieme composto dagli elementi comuni ai due insiemi di partenza.

Se invece A è l’insieme vuoto non ci saranno elementi in comune con 1 ed il risultato sarà 0. Nei due casi quindi il risultato è sempre dipendente da A ed è A stesso.
Abbiamo così dimostrato la relazione A·1 = A. Applicando poi il principio di dualità si ottiene la relazione relativa alla somma.
In figura è illustrata la legge di identità per mezzo delle reti logiche, considerando una porta AND e una porta OR a due ingressi e visualizzandone il risultato in uscita.

La legge di annullamento dice che:

A + 1 = 1
A · 0 = 0

Anche in questo caso dobbiamo ricordare per la seconda relazione il significato di prodotto, e applicare poi il principio di dualità che ci permette di ottenere la prima relazione. Consideriamo ora una variabile e la sua complementare. In insiemistica, dato un insieme totale 1, in figura, e preso un suo sottoinsieme A, l’insieme complementare Ā è composto da tutti gli elementi di 1 che non appartengono ad A. Tra A e Ā non abbiamo quindi elementi in comune, ma esiste la proprietà che i due insiemi A ed Ā, se messi assieme, forniscono di nuovo l’insieme totale 1.

Applichiamo ora quanto abbiamo detto ed enunciamo la legge di complementazione (o inversione):

A + Ā = 1
A · Ā = 0

Dalla prima relazione, mettendo assieme intuitivamente A ed Ā otteniamo il tutto, “1”. Dalla seconda, operiamo l’intersezione fra le due variabili. Poiché esse sono l’una l’inverso dell’altra e non hanno niente in comune, il risultato è “0” (vuoto). Le due relazioni sono anch’esse legate fra loro dal principio di dualità.

Leggi di idempotenza:

A + A = A
A · A = A

Non richiede particolari commenti. L’intersezione di un insieme con sé stesso fornisce ancora l’insieme di partenza e dalla legge di dualità si ottiene la prima relazione.

Legge di assorbimento:

A + A·B=A
A ·(A+B)=A

Consideriamo la seconda relazione. Nella somma A+B è contenuta la variabile A. Intersecando tutto questo, cioè cercando fra A ed A + B gli elementi comuni, vediamo che l’unico elemento comune è ancora A. La prima si ottiene dalla seconda nel solito modo.
La legge della doppia negazione dice che:

in altre parole l’inverso dell’inverso di A è ancora A: è chiaro che con due passaggi al complementare si torna al punto di partenza.

Enunciamo infine i due teoremi di De Morgan.
1° Teorema. Date due variabili A e B, il complementare della loro somma logica è equivalente al prodotto logico dei complementari delle singole variabili.

2° Teorema. Date due variabili A e B, il complementare del loro prodotto logico è equivalente alla somma logica dei complementari delle singole variabili.
Questo teorema non è altro che il duale del primo. Scambiando quindi il simbolo di somma con il simbolo di prodotto e viceversa, otteniamo:

Esse possono essere dimostrate nel seguente modo:

1° Teorema

2° Teorema

{/gspeech}

LOGICA BOOLEANA

Esercizi
Date le seguenti tabelle di verità, indicare l’operazione logica cui si riferiscono:
a)
A B Y
0 0 0
0 1 0 operazione logica:
1 0 0
1 1 1

b)
A B Y
0 0 0
0 1 1 operazione logica:
1 0 1
1 1 1

Ricavate la funzione logica che descrive il circuito rappresentato di seguito:

Indicare a quali operazioni logiche si riferiscono le tabelle di verità seguenti e disegnare i simboli elettrici corrispondenti:

06-Logica Booleana

A B Y

0 0 1

0 1 1 operazione logica:

1 0 1

1 1 0

A B Y

0 0 0

0 1 1 operazione logica:

1 0 1

1 1 0

A B Y

0 0 1

0 1 0 operazione logica:

1 0 0

1 1 0

Commento all'articolo Annulla risposta