Algebra di Boole

Sistemi e reti

Algebra di Boole e porte

logiche

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)

Open Ended

Perché studiamo l'algebra di Boole secondo voi?

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.

Open Ended

Cosa sono una funzione booleana e la tabella di verità?

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

Multiple Choice

Un'algebra i cui elementi sono {0,1} e le cui operazioni sono somma logica, prodotto logico e complemento, è detta

• Algebra booleana

• Algebra complessa

• Algebra semplice

• Algebra digitale

Multiple Choice

La seguente figura rappresenta una funzione logica...

• AND

• NOT

• OR

• NAND

Multiple Choice

La tabella mostra l'output di una funzione logica...

• OR

• NAND

• NOT

• AND

Multiple Choice

Indica la corretta priorità degli operatori

• NOT, OR, AND

• OR, NOT, AND

• AND, OR, NOT

• NOT, AND, OR

Multiple Choice

La negazione di <<Non tutte le cornacchie nere volano d'inverno>> è:

• Qualche cornacchia bianca vola d'inverno

• Qualche cornacchia non nera non vola d'inverno

• Nessuna cornacchia di qualunque colore vola d'inverno

• Nessuna cornacchia bianca vola d'inverno

Multiple Choice

1

1

1

0

corrisponde a:

• ~ A + B

• ~ (A * B)

• ~ (A + B)

• Nessuna delle precedenti

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

Multiple Choice

$$\overline{A}\cdot A=$$  

• $$A$$  

• $$\overline{A}$$  

• $$0$$  

• $$1$$  

Multiple Choice

$$\overline{A}+A=$$  

• $$A$$  

• $$\overline{A}$$  

• $$0$$  

• $$1$$  

Multiple Choice

Semplificare $$A\cdot0$$

• $$A\cdot0$$

• $$0$$

• $$A$$

• $$1$$

Multiple Choice

$$A\cdot\overline{A}\ =$$  

• $$A$$  

• $$0$$  

• $$1$$  

• $$\overline{A}$$  

Multiple Choice

$$\overline{\overline{A}}^{ }=$$  

• $$A$$  

• 1

• 0

• $$\overline{A}$$  

Multiple Choice

Quali di queste equivalenze NON E' CORRETTA??

X + 0 = 0

X + 1 = X

X + X = X

X + X= 1

X * 1 = X

X * 0 = 0

X * X = X

X * X= 0

• 1, 2, 4,8

• 2, 5, 6,8

• 1, 5, 6,7

• 2, 4, 6, 7

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)

Multiple Choice

$$A+B\ =B\ +\ A$$  

• VERO

• FALSO

Multiple Choice

$$A\cdot B\ =B\ \cdot\ A$$  

• VERO

• FALSO

Multiple Choice

Quale, tra le seguenti, rappresenta la duale (l'equivalente) dell'espressione: $$A+\overline{A}B\ =\ A\ +\ B$$  

• $$A\left(\overline{A}+B\right)\ =\ AB$$  

• $$A\left(\overline{A}B\right)\ =\ AB$$  

• $$\overline{A}\left(A+\overline{B}\right)=\overline{A}\ \overline{B}$$  

• $$\overline{A}\left(A\overline{B}\right)=\overline{A}\ \overline{B}$$  

Multiple Choice

Questa proprietà: X* (Y* Z) = (X * Y) * Z

• Distributiva

• Associativa

• Esistenza dell'inverso

• Somma o prodotto per una costante

• nessuna delle precedenti

Multiple Choice

A *B + C equivale a:

• (A *B) + C

• A *(B + C)

• A* B + A * C

• A +B * A + C

Multiple Choice

X +Y * Z=

• (X + Y) * (X + Z)

• (X* Z) + (Y * Z)

• (X + Y) + (X + Z)

• Nessuna delle precedenti

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)

Multiple Choice

$$A+\overline{A}B\ =\$$  

• $$A+B$$  

• $$A+\overline{B}$$  

• $$A$$  

• $$B$$  

Multiple Choice

$$A+AB\ =\$$  

• $$A+B$$  

• $$A+\overline{B}$$  

• $$A$$  

• $$B$$  

Multiple Choice

$$(A+B)\cdot(A+\overline{B})$$  

• $$A$$  

• $$B$$  

• $$\overline{A}$$  

• $$\overline{B}$$  

Multiple Choice

$$\overline{A+B}$$  

• $$\overline{A}\cdot\overline{B}$$  

• $$\overline{AB}$$  

• $$AB$$  

• $$\overline{A}+\overline{B}$$  

Multiple Choice

$$\overline{A\cdot B}$$  

• $$\overline{A}+\overline{B}$$  

• $$\overline{A+B}$$  

• $$AB$$  

• $$\overline{A}\cdot\overline{B}$$  

Multiple Choice

Quale proprietà si applica per trasformare porte OR in porte AND

• Distributiva

• Associativa

• De Morgan

• Assorbimento

Multiple Choice

A + B =

• ~ A * ~ B

• ~ (A * B)

• ~ (~ A * ~ B)

• Nessuna delle precedenti