Algebra di Boole

GeorgeBoole

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.

1

0

Vero

Falso

Tutto

Niente

Contatto chiuso

Contatto aperto

On

Off

High

Low

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)

algebra di boole

  • Simbolo:
  • Tavola della verità:

A

B

Y

0

0

0

0

1

1

1

0

1

1

1

1

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

  • Circuito elettrico:

algebra di boole

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)

algebra di boole

  • Simbolo:
  • Tavola della verità:

A

B

Y

0

0

0

0

1

0

1

0

0

1

1

1

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

  • algebra di booleCircuito 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)

algebra di boole

  • Simbolo:
  • Tavola della verità:

A

Y

0

1

1

0

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

  • algebra di booleCircuito 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:     algebra di boole    (A NOR B)

algebra di boole

  • Simbolo:
  • Tavola della verità:

A

B

Y

0

0

1

0

1

0

1

0

0

1

1

0

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

  • 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:     algebra di boole     (A  NAND   B)

algebra di boole

  • Simbolo:
  • Tavola della verità:

A

B

Y

0

0

1

0

1

1

1

0

1

1

1

0

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

  • algebra di booleCircuito 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 =  algebra di boole  (A  OR esclusivo  B)

algebra di boole

  • Simbolo:
  • Tavola della verità:

A

B

Y

0

0

0

0

1

1

1

0

1

1

1

0

Þ 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.
algebra di boole

  • 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 =  algebra di boole   (A  NOR esclusivo  B)

algebra di boole

  • Simbolo:
  • Tavola della verità:

A

B

Y

0

0

1

0

1

0

1

0

0

1

1

1

Þ 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.

  • algebra di booleCircuito 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 Ā = algebra di boole

  • assioma della doppia negazione

algebra di boole  = 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   algebra di boole

la sua espressione duale diviene :  algebra di boole

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

algebra di boole
Applichiamo dapprima il principio di dualità:                           algebra di boole

Se invece applichiamo alla stessa l’assioma della negazione:     algebra di boole

Confrontando le due ultime equazioni, si ottiene che:

algebra di boole
algebra di boole

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

algebra di boole

    • 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

algebra di boole
Applichiamo dapprima il principio di dualità:                           algebra di boole

Se invece applichiamo alla stessa l’assioma della negazione:     algebra di boole

Confrontando le due ultime equazioni, si ottiene che:

algebra di boole
algebra di boole

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

algebra di boole

    • 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 algebra di boole, allora: Y=A+B

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

Teorema del consenso

Se algebra di boole, allora: algebra di boole

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

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

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:
algebra di boole

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:

algebra di boole

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:J06- Logica e Teorie del ragionamento, L04- Logica - Logic

Tag:,

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

SCIENZA E CULTURA - SCIENCE AND CULTURE

Lo stato dell'arte tra storia e ricerche contemporanee - State of the art: history and contemporary research

ORIENTALIA

Studi orientali - Études Orientales - Oriental Studies

NUOVA STORIA CULTURALE / NETWORK PHILOSOPHY

NUOVA STORIA CULTURALE / NEW CULTURAL HISTORY

TEATRO E RICERCA - THEATRE AND RESEARCH

Sito della Compagnia Lost Orpheus Teatro

LOST ORPHEUS ENSEMBLE

Modern Music Live BaND

Il Nautilus

Viaggio nella blogosfera della V As del Galilei di Potenza

Sonus- Materiali per la musica moderna e contemporanea

Aggiornamenti della Rivista "Sonus"- Updating Sonus Journal

The WordPress.com Blog

The latest news on WordPress.com and the WordPress community.

Antonio De Lisa - Scritture / Writings

Teatro Musica Poesia / Theater Music Poetry

In Poesia - Filosofia delle poetiche e dei linguaggi

Blog Journal and Archive diretto da Antonio De Lisa

%d blogger hanno fatto clic su Mi Piace per questo: