Algebra di Boole

Nel  1854 il matematico irlandese Gorge Boole (1815-1864) pubblicò la sua opera più importante, “An Investigation of the Laws of Thought”, indirizzata alle leggi del pensiero, con la quale propose una nuova impostazione della logica: scopo dell’opera fu quello di studiare le leggi delle operazioni mentali alla base del ragionamento esprimendole nel linguaggio simbolico del calcolo e di istituire, di conseguenza, una disciplina scientifica della logica sorretta da un metodo; dopo aver rilevate le analogie fra oggetti dell’algebra e oggetti della logica, ricondusse le composizioni degli enunciati a semplici operazioni algebriche. Con questo lavoro fondò la teoria di quelle che attualmente vengono dette algebre di Boole (o, semplicemente, “algebra booleana”). Pur mantenendo distinte le operazioni , la scienza della logica nella forma algebrica dall’algebra in quanto settore della matematica, le leggi logiche dai settori delle scienze naturali, il compito di Boole fu quello di travestire la logica con un abito matematico algebrico.

Certo Boole non immaginò che quella che doveva essere prerogativa di un calcolo astratto, sarebbe diventata una delle più grandi conquiste della tecnica moderna. Infatti essa venne ripresa nel 1940 nella costruzione dei calcolatori elettronici: la prima pubblicazione di rilievo fu l’articolo di Claude Shannon  “A symbolic analysis of relay and switching circuits” (Su Transactions of the american institute of electrical engineers, vol 57, dic 1938).

2)  PRINCIPIO DI FUNZIONAMENTO
Essa si basa sul fatto che le variabili logiche possono assumere solo due stati, secondo la tabella seguente.

L’algebra di Boole si applica per quelle situazioni, cioè, in cui si ammettono soltanto due stati,  senza posizioni intermedie.
Analogamente alla matematica, in cui qualunque equazione può essere espressa sia in forma analitica sia mediante una tabella riportante i valori della variabile x e della funzione y, nell’algebra di Boole esiste una tabella che rappresenta la funzione logica. Detta tabella è chiamata tavola della verità.

3) OPERAZIONI LOGICHE FONDAMENTALI
Successivamente prenderemo in esame quelle che sono le operazioni logiche fondamentali dell’algebra di Boole. Di ciascuna si enuncerà:

• il significato
• la sua scrittura
• il simbolo
• la tavola della verità
• il circuito elettrico corrispondente.

SOMMA LOGICA:  OR

• La somma OR (dall’Inglese: o, oppure), si effettua su due o più variabili, e l’uscita assume lo stato 1 se almeno una variabile di ingresso è allo stato 1.

• Scrittura:     Y = A + B   (A OR B, ma anche: A più B)

• Simbolo:

• Tavola della verità:

Þ Quindi l’uscita è “vera “ se è verificata “o” la condizione A, “o” la condizione “B”, o ancora entrambe le condizioni.

• Circuito elettrico:

Si tratta di due interruttori disposti in parallelo: la lampadina verrà accesa se uno qualunque o tutti e due gli interruttori sono chiusi!

PRODOTTO LOGICO:   AND

• Il prodotto logico AND (dall’Inglese: “e”), si effettua su due o più variabili, e l’uscita assume lo stato 1 solo se tutte e due le variabili di ingresso sono allo stato 1.

• Scrittura:     Y = A · B     (A AND B, ma anche: A per B)

• Simbolo:

• Tavola della verità:

Þ Quindi l’uscita è “vera “ se è verificata “sia” la condizione A, “sia” la condizione “B”.

• Circuito elettrico:

Si tratta di due interruttori disposti in serie: la lampadina verrà accesa se entrambi  gli interruttori sono chiusi!

NEGAZIONE:  NOT

• La negazione NOT (dall’Inglese: no, non), si effettua su una sola variabile, e si chiama anche complementazione. L’uscita assume lo stato 1 se la variabile di ingresso è allo stato 0; e assume lo stato 0 se la variabile di ingresso è allo stato 1.

• Scrittura:     Y = Ā  (A negato, ma anche: A complementato)

• Simbolo:

• Tavola della verità:

Þ  Quindi l’uscita è “vera “ se la condizione A non è vera.

• Circuito elettrico:

Si tratta di un interruttore in parallelo con la lampadina: la lampada è accesa solo se l’interruttore è aperto.

SOMMA LOGICA NEGATA:  NOR

• L’operatore NOR (dall’unione di NOT più OR), si effettua su due o più variabili, e l’uscita assume lo stato 1 se tutte  le variabili di ingresso sono allo stato 0.

• Scrittura:         (A NOR B)

• Simbolo:

• Tavola della verità:

Þ Quindi l’uscita è “vera “ solo se “sia” la condizione A, “sia” la condizione “B”, non sono vere.

• Circuito elettrico:

Si tratta di due interruttori disposti in parallelo tra loro e con la lampadina: essa  verrà dunque accesa solo se entrambi gli interruttori non sono chiusi.

PRODOTTO LOGICO NEGATO:  NAND

• L’operatore NAND (dall’unione di NOT e AND), si effettua su due o più variabili, e l’uscita assume lo stato 1 se almeno una variabile di ingresso, o entrambe,  è allo stato 0.

• Scrittura:          (A  NAND   B)

• Simbolo:

• Tavola della verità:

Þ Quindi l’uscita è “vera “ se non è verificata “o” la condizione A, “o” la condizione B, o non sono verificate entrambe le condizioni.

• Circuito elettrico:

Si tratta di due interruttori disposti in serie tra loro, e in parallelo con la lampadina: dunque la lampadina verrà accesa se uno qualunque o tutti e due gli interruttori sono aperti: se tutti e due gli interruttori sono chiusi, allora la lampadina non si accende.

OR ESCLUSIVO:  XOR

• L’operatore XOR (eXclusive OR), si effettua su due variabili, e l’uscita assume lo stato 1 se le variabili di ingresso sono ad uno stato logico diverso tra loro.

• Scrittura:     Y =    (A  OR esclusivo  B)

• Simbolo:

• Tavola della verità:

Þ Quindi l’uscita è “vera “ se la condizione A e la condizione B si trovano ad avere due stati diversi tra loro. Per questo il circuito prende il nome di anticoincidenza.

• Circuito elettrico:

Si tratta di due interruttori disposti in serie loro, e in parallelo con la lampadina: la lampadina verrà accesa se gli interruttori sono uno chiuso e uno aperto, altrimenti, se sono entrambi o chiusi, o aperti, essa non si può accendere.

NOR ESCLUSIVO:  XNOR

• L’operatore XNOR (eXclusive NOR), si effettua su due variabili, e l’uscita assume lo stato 1 se le variabili di ingresso sono ad uno stato logico uguale tra loro.

• Scrittura:     Y =     (A  NOR esclusivo  B)

• Simbolo:

• Tavola della verità:

Þ Quindi l’uscita è “vera “ se la condizione A e la condizione B si trovano ad avere due stati uguali tra loro. Per questo il circuito prende il nome di coincidenza.

• Circuito elettrico:

Si tratta di due interruttori disposti in serie loro, e in serie con la lampadina: la lampadina verrà accesa se gli interruttori sono entrambi chiusi , o entrambi aperti, altrimenti, se sono uno chiuso e l’altro aperto, essa non si può accendere.

4) PROPRIETA’ DELL’ALGEBRA DI BOOLE

• proprietà commutativa

Rispetto alla somma logica:   A + B  = B + A
Rispetto al prodotto logico:   A × B  = B × A

• proprietà associativa

Rispetto alla somma logica:   A + ( B + C )  = ( A + B ) + C
Rispetto al prodotto logico:   A × B × C = (A × B) × C

• proprietà distributiva

Rispetto alla somma logica:   A + BC  = ( A + B ) × ( A + C )
Rispetto al prodotto logico:   A × ( B + C )  = AB + AC

Merita prestare attenzione alla proprietà distributiva rispetto alla somma, la quale non ha un corrispettivo rispetto all’algebra unitaria:

se infatti, per es.,  A=2; B=3; C=4, allora:     2 + 3× 4  ¹ ( 2 + 3 ) × ( 2 + 4 )  !

5)  ASSIOMI DELL’ALGEBRA DI BOOLE

• assioma dell’annullamento

A × 0 = 0
A + 1 = 1

• assioma del complemento

A × Ā = 0
A + Ā = 1

• assioma dell’idempotenza

A × A = A
A + A = A

• assioma della negazione

se A = B allora Ā =

• assioma della doppia negazione

  = A

6) PRINCIPIO DI DUALITA’

Data una funzione Y, si chiama espressione duale di Y quella che si ottiene  con le seguenti sostituzioni:

• AND si sostituisce con OR, e viceversa
• 0 si sostituisce con 1, e viceversa
• ogni variabile si sostituisce con il suo complemento, e viceversa

Esempio:

data l’espressione  

la sua espressione duale diviene : 

7)   TEOREMI DI DE MORGAN

Mediante l’utilizzo del principio di dualità si ricavano due fondamentali teoremi, che sono detti Teoremi di De Morgan.

• Primo Teorema di De Morgan.

Consideriamo l’espressione:                                                  Y = A × B

Applichiamo dapprima il principio di dualità:                          

Se invece applichiamo alla stessa l’assioma della negazione:    

Confrontando le due ultime equazioni, si ottiene che:

Ovvero, per il principio della doppia negazione, anche che:

• Il primo teorema di De Morgan afferma dunque che si possono trasformare prodotti in somme

• Secondo Teorema di De Morgan.

Consideriamo l’espressione:                                                  Y = A + B

Applichiamo dapprima il principio di dualità:                          

Se invece applichiamo alla stessa l’assioma della negazione:    

Confrontando le due ultime equazioni, si ottiene che:

Ovvero, per il principio della doppia negazione, anche che:

• Il secondo teorema di De Morgan afferma dunque che si possono trasformare somme in prodotti.

N.B.: si può  osservare che i due teoremi si possono ricondurre in realtà ad uno solo,
         essendo uno il duale dell’altro.

8) ALTRI TEOREMI

Teorema dell’assorbimento

a) Se Y= A  + AB, allora:    Y = A

® Infatti, per la proprietà distributiva :   Y = A + AB = A(1+B)
e per la proprietà dell’annullamento:     Y = A×1 = A

b) Se , allora: Y=A+B

® Infatti, per la proprietà distributiva:    =
e per l’assioma dell’annullamento:        

Teorema del consenso

Se , allora:

Ovvero: si può eliminare il termine BC, quello, cioè in cui  vi sono i fattori contenuti negli altri termini.

® Infatti: dall’assioma del complemento:         
e dalla proprietà distributiva:              
e anche:                                           
e dall’assioma dell’annullamento:         

ESEMPI

ESEMPIO 1

Supponiamo di dover risolvere alcuni problemi inerenti al sistema “ascensore”.

a) AND

L’ascensore può avviarsi se necessariamente sono verificate le seguenti condizioni: pressione del pulsante, porte chiuse.
Quindi:
condizione A = 1    Þ      pressione pulsante
condizione B = 1    Þ      porte chiuse
Risultato      Y = A · B  : l’ascensore si avvia.
La mancanza di una delle due condizioni darà risultato negativo, ovvero Y=0, ossia l’ascensore non parte.

b) NOT

L’ascensore parte se non c’è sovraccarico.
Quindi:
A=1, ovvero sovraccarico di persone, mi dà Y=0, ovvero l’ascensore non parte.
Viceversa A=0, ovvero NON c’è sovraccarico, genera un’uscita Y pari a 1, ossia l’ascensore può avviarsi.

c) OR

L’ascensore si ferma o se arrivato al piano prescelto, o se manca la corrente.

Quindi:

A=1 (cioè aascensore al piano), oppure B=1, (cioè mancanza di corrente), mi danno un esito Y=1 (ovvero ascensore fermo). Ma anche la presenza di entrambe le condizioni (ascensore fermo e al piano), mi danno lo stesso risultato!

ESEMPIO 2

Supponiamo di dover realizzare con le porte logiche il seguente esempio:
se c’è bel tempo, e c’è il sole, allora esco.
Si evince che sono necessarie entrambe le condizioni A (=presenza di bel tempo) e B (=presenza di sole), affinché sia verificato il risultato Y (=uscita).
La mancanza di una sola delle due condizioni non renderà verificata l’uscita.

Quindi si deve applicare una porta AND
Risultato Y = A · B  : esco.

Ma se si vuole complicare introducendo una nuova condizione, ovvero la presenza di un impegno di lavoro, allora è chiaro che questa variabile è indipendente dalle altre due; e se quindi essa risulta verificata, allora io devo uscire anche se non c’è il sole, o se non c’è bel tempo.

Ovvero:
se A = sole
se B= bel tempo
se C=impegno di lavoro

sarà necessario l’impiego di una porta AND per le prime due, ma anche una porta OR per l’ultima condizione, secondo il seguente schema:

Così facendo, io posso uscire, “o” se c’è sia il sole (A) sia bel tempo (B), “o” se ho un impegno di lavoro (C).

ESEMPIO 3

In un consiglio di amministrazione, vi sono tre votanti e il presidente del consiglio. Una proposta è approvata quando essa ha la maggioranza dei voti, tenendo presente però che il Presidente ha il diritto di veto, e che il suo voto vale doppio.

Quindi:

A, B, C = votanti
P = presidente.

La proposta (Y) è approvata se P=1 e se almeno uno dei consiglieri ha votato positivamente, ovvero A+B+C=1
La proposta è invece respinta se P=0 (il presidente ha diritto di veto!)

Quindi, con le porte logiche:

si vede  che i tre votanti sono tra loro interconnessi tramite un porta OR, e il loro risultato è collegato col risultato del presidente tramite una porta AND.
Y varrà 1 se P=1 e (AND) se almeno uno degli altri tre ha votato positivamente (cioè A o B o C =1).

Categorie:K30- [LOGICA], K30.02- Logica e Teorie del ragionamento

Tag:Algebra di Boole, Logica