Algebra di Boole
Algebra di Boole
I testi seguenti sono di proprietà dei rispettivi autori che ringraziamo per l'opportunità che ci danno di far conoscere gratuitamente a studenti , docenti e agli utenti del web i loro testi per sole finalità illustrative didattiche e scientifiche.
ALGEBRA DI BOOLE
Indice
- CENNI STORICI
- PRINCIPIO DI FUNZIONAMENTO
- OPERAZIONI LOGICHE FONDAMENTALI
SOMMA LOGICA: OR
PRODOTTO LOGICO: AND
NEGAZIONE: NOT
SOMMA LOGICA NEGATA: NOR
PRODOTTO LOGICO NEGATO: NAND
OR ESCLUSIVO: XOR
NOR ESCLUSIVO: XNOR
- PROPRIETA’ DELL’ALGEBRA DI BOOLE
- proprietà commutativa
- proprietà associativa
- proprietà distributiva
- ASSIOMI DELL’ALGEBRA DI BOOLE
- PRINCIPIO DI DUALITA’
- TEOREMI DI DE MORGAN
- ALTRI TEOREMI
Teorema dell’assorbimento
Teorema del consenso
- CENNI STORICI
L’algebra di Boole deve il suo nome al matematico e filosofo irlandese Gorge Boole (1815-1864), il quale si preoccupò di introdurre un simbolismo nello studio della logica.
Nel 1854 pubblicò “An Investigation of the Laws of Thought” (Un esame sulle leggi del pensiero), in cui sosteneva che il pensiero logico potesse essere facilmente decomposto in insiemi di scelte tra due possibilità.
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)
- 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:
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à:
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”.
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à:
A |
Y |
0 |
1 |
1 |
0 |
Þ 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à:
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.
- 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à:
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.
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à:
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.
- 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à:
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.
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).
Fonte: http://alessioambrogio.altervista.org/Algebra%20di%20Boole.doc
Autore del testo: non indicato nel documento di origine
Algebra di Boole
Algebra di Boole
Disclaimer
Questo sito non rappresenta una testata giornalistica e viene aggiornato senza alcuna periodicità, esclusivamente sulla base della disponibilità del materiale, pertanto non è un prodotto editoriale sottoposto alla disciplina di cui all'art. 1, comma III della Legge n. 62 del 7.03.2001. I riassunti , gli appunti i testi e le citazioni contenuti nel nostro sito sono messi a disposizione gratuitamente a studenti, ricercatori, professori, tecnici con scopi illustrativi didattici e scientifici con il concetto del fair use e con obiettivo del rispetto della direttiva europea 2001/29/CE e della legge n. 633 art. 70 e dlg 68. Il sito è curato e coordinato dall’autore al solo scopo informativo e didattico. Pur ritenendo le fonti utilizzate affidabili, l'autore di questo sito non garantisce l'accuratezza e l'integrità delle informazioni contenute e pertanto declina ogni responsabilità per eventuali problemi o danni causati da errori o omissioni, nel caso tali errori o omissioni risultino da negligenza, caso fortuito o altra causa. Tutti gli appunti, le citazioni i testi e le immagini , sono proprietà dei rispettivi autori o case di produzione che ne detengono i diritti, qualora gli aventi diritto si ritenessero danneggiati dall'inserimento in questo sito dei predetti files o fossero stati inavvertitamente inseriti immagini, informazioni, testi od altro materiale coperto da Copyright saranno immediatamente rimossi e/o ne saranno citate le fonti su semplice segnalazione all' indirizzo e-mail indicato nella pagina contatti .
Gli obiettivi di questo sito sono il progresso delle scienze e delle arti utili in quanto pensiamo che siano molto importanti per il nostro paese i benefici sociali e culturali della libera diffusione di informazioni utili. Tutte le informazioni e le immagini contenute in questo sito vengono qui utilizzate esclusivamente a scopi didattici, conoscitivi e divulgativi. Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione). In questo sito abbiamo fatto ogni sforzo per garantire l'accuratezza dei tools, calcolatori e delle informazioni, non possiamo dare una garanzia o essere ritenuti responsabili per eventuali errori che sono stati fatti, i testi utilizzati sono stati prelevati da siti che li hanno messi a disposizione gratuitamente per farli conoscere nel web con scopi didattici. Se trovate un errore su questo sito o se trovate un testo o tool che possa violare le leggi vigenti in materia di diritti di autore, comunicatecelo via e-mail e noi provvederemo tempestivamente a rimuoverlo.
Algebra di Boole
Designed by Larapedia.com 1998 -2011