Algebra di Boole

Algebra di Boole

● L’algebra booleana è un particolare tipo

di algebra in cui le variabili e le funzioni
possono solo avere valori 0 e 1. Deriva il
suo nome dal matematico inglese
George Boole (1815-1864) che la ideò.

● “Il pensiero logico può essere facilmente

decomposto in insiemi di scelte tra due
possibilità” (1854)

Algebra di Boole

● Si studia l’algebra booleana poiché le

funzioni dell’algebra booleana sono
isomorfe ai circuiti digitali. In altre parole,
un circuito digitale può essere
espresso tramite un’espressione
booleana e viceversa.

● Una funzione booleana ha una o più

variabili in input e fornisce risultati che
dipendono solo da queste variabili.

Algebra di Boole

Poiché le variabili
possono assumere solo i
valori 0 o 1 una funzione
booleana con n variabili di
input ha solo 2n
combinazioni possibili e
può essere descritta con
una tabella, detta tabella
di verità, con 2nrighe.

Concetti fondamentali

● Proposizione: una frase di senso compiuto

• “Oggi piove” è una proposizione,
• “Io sono bravo ma cane non beve matite” non è una proposizione

● Enunciato: una proposizione di cui è possibile

stabilire con certezza se è vera o falsa
• “Il Colosseo si Trova a Roma” è un enunciato (proposizione vera)
• “L’Etna si trova nel Veneto” è un enunciato (proposizione falsa)
• “La matematica è una brutta materia” non è un enunciato, perché il

suo valore di verità è soggettivo

Concetti fondamentali

● Termini dell’algebra i

Boole: variabili booleane o
variabili logiche o asserzioni
• Gli enunciati possono essere

rappresentati da 0 o 1

● Operazioni fondamentali

implementate attraverso i
connettivi o operatori logici
• AND congiunzione o prodotto

logico

• OR disgiunzione o somma logica
• NOT negazione logica

Concetti fondamentali

● Tutte le funzioni booleane possono essere

espresse come combinazione dei tre operatori
AND, OR e NOT

● Le espressioni booleane vengono utilizzate nei

linguaggi di programmazione per la definizione dei
criteri decisionali

● Il teorema fondamentale dell’algebra di Boole

afferma che qualunque forma di elaborazione sui dati
codificati in codice binario può ricondursi ad una
opportuna successione delle tre operazioni logiche
fondamentali AND, OR, NOT che sono i passi
elaborativi più elementari a livello macchina

Concetti fondamentali

● Enunciato composto: una combinazione di

enunciati legati da connettivi logici
• “Stasera studierò o andrò al cinema” è un enunciato composto

formato dai sotto enunciati “Stasera studierò” e “andrò al
cinema” legati dal connettivo “o”

● Precedenza degli operatori

• Le operazione unarie (NOT) hanno precedenza su quelle

binarie

• Si usano le parentesi

● Espressioni si possono valutare

• Tabelle di verità o tabelle logiche o tavole di verità

Concetti fondamentali

● Ad ogni funzione di base corrisponde una

porta logica e quindi ogni espressione
booleana può essere tradotta in un circuito.

● Tramite le proprietà dell’algebra booleana è

possibile semplificare espressione booleane
complesse

● Anche i circuiti corrispondenti saranno più

semplici e richiederanno un minor numero di
porte logiche -> Minori costi di realizzazione
dei circuiti e minore occupazione di spazio

Operatori

● Somma logica:

OR
•Y=A+B
•A OR B

● Prodotto logico:

AND
●Y=A*B
●A AND B

● Negazione:

NOT

●Y= A

●NOT A

Operatori

● Somma logica

negata: NOR
•Y=A+B
•A NOR B

● Prodotto

logico negato:
NAND

●Z=A*B
●A NAND B

Operatori

● OR esclusivo:

XOR

•Y= A+B
•A XOR B

● NOR esclusivo:

XNOR

●Y= A+B
●A XNOR B

Assiomi dell’algebra di Boole

● Assioma dell’annullamento e identità

• A*0=0

A+1=1

A*1=A

A+0=A

● Assioma del complemento

• A*A=0

A+A=1

● Assioma dell’idempotenza

• A*A=A

A+A=A

● Assioma della negazione

• Se A=B allora A=B

● Assioma della doppia negazione

• A=A

Proprietà 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à dell’algebra di Boole

● Proprietà distributiva

• Rispetto alla somma logica:

(A+B)*(A+C)=A+BC
(A+B)*(A+C)=AA+AC+AB+BC=
A+AC+AB+BC=
A(1+C+B)+BC=A+BC
• Rispetto al prodotto logico:

A*(B+C)=AB+AC

Principio di dualità

Data una funzione Y si chiama
espressione duale di Y quella che si
ottiene sostituendo:

•AND con OR e viceversa
•0 con 1 e viceversa
•Ogni variabile con il suo complemento e

viceversa

•Es: Y=A+(B*C) il duale è Y=A*(B+C)

Primo teorema di De Morgan

● Consideriamo l’espressione Y=A*B

● Applichiamo il principio di dualità: Y=A+B

● Applichiamo l’assioma della negazione alla

prima Y=A*B, quindi A*B=A+B

● Applichiamo l’assioma della doppia

negazione: A*B=A+B

Si possono trasformare prodotti in somme

Secondo teorema di De Morgan

● Consideriamo l’espressione Y=A+B

● Applichiamo il principio di dualità: Y=A*B

● Applichiamo l’assioma della negazione alla

prima Y=A+B, quindi A+B=A*B

● Applichiamo l’assioma della doppia

negazione: A+B=A*B

Si possono trasformare somme in prodotti

Altri teoremi

● Teorema dell’assorbimento

• Se Y=A+AB allora Y=A, infatti per la proprietà

distributiva Y=A+AB=A(1+B), 1+B=1, quindi
Y=A*1=A
• Se Y=A+AB allora Y=A+B, infatti per la proprietà

distributiva Y=A+AB=(A+A)*(A+B), A+A=1, quindi
Y=1*(A+B)=A+B

● Teorema del consenso

• Se Y= AB+ AC+BC allora Y=AB+AC, infatti Y=

AB+ AC+BC = AB+ AC+(A+A)*BC e dalla proprietà
distributiva: Y=AB+AC+ABC+ABC e anche
Y=AB(1+C) + AC(1+B) e Y=AB+ AC (annullamento)