Introduzione all'Algebra di Boole

(1)

Operazioni Logiche:

Algebra di Boole

Elementi di Informatica e

Programmazione

Ingegneria Gestionale

Università degli Studi di Brescia

Docente: Prof. Ivan Serina Prof. Alfonso Gerevini

Circuiti digitali

• Il calcolatore può essere visto come un insieme di circuiti digitali

• Un circuito digitale è un sistema in cui l’informazione viene rappresentata mediante una grandezza fisica della quale si considerano soltanto valori discreti

• Alla grandezza fisica vengono fatti corrispondere

solamente due valori logici corrispondenti a due livelli di

tensione contrassegnati come alto e basso

• Questi livelli sono identificati da una coppia di simboli:

– 0 1

– Falso Vero – Aperto Chiuso

2

Porte Logiche

• Le porte logiche formano la base hardware su cui i • Le porte logiche formano la base hardware su cui i

circuiti digitali sono costruiti

• Sono particolari dispositivi che possono calcolare varie funzioni dei valori 0 e 1

A B AB A A+B B Ā A B AND B OR NOT A B AB NAND A B A+B NOR

Esempio di circuito

x x₁ x₂ f

(2)

Reti combinatorie

• Una rete combinatoria è costituita da

– un gruppo di elementi (di calcolo) attivi: le

porte logiche

– collegati fra loro da elementi passivi: linee di

ingresso, di uscita e di circuito

• Una rete combinatoria è un circuito

elettronico in grado di calcolare in modo

automatico funzioni binarie di una o più

variabili binarie

5

Algebra di Boole

• E’ lo strumento matematico usato per lo studio

delle reti combinatorie

• E’ un particolare tipo di algebra che include:

– un insieme di supporto A (l’insieme {0,1} nel ns caso) – degli operatori binari: AND (·) e OR (+)

– un operatore complemento: NOT (¯ )

• Gli operatori soddisfano certe proprietà che si

deducono da un insieme di assiomi

6

Variabili Booleane

• Una variabile booleana è una

variabile

• Una variabile booleana è una

variabile

binaria

che può assumere uno dei due

valori logici denotati con 0 e 1

• Usiamo ad esempio i simboli x, y, z, … per

indicare variabili booleane

• Può essere x = 1 oppure x = 0

Operatori Booleani

• Operatori booleani (o logici) fondamentali:

NOT

Negazione Logica

not(x), x, ~x

AND

Prodotto Logico

x and y, x • y, xy

OR

Somma Logica

x or y, x + y

(3)

Le 3 funzioni di base:

Tabelle di verità

x x x ••••x x x x + x x₁ x₀ x₁••••x₀ 0 0 0 0 1 0 1 0 0 1 1 1 x₁ x₀ x₁+ x₀ 0 0 0 0 1 1 1 0 1 1 1 1 x x 0 1 1 0 NOT 1 1 1 1 1 1 AND OR NOT 9

Assiomi dell’Algebra di Boole

Forma AND

Forma OR

Forma AND

Forma OR

Commutatività AB = BA A+B = B+A Distributività A+BC=(A+B)(A+C) A(B+C)=AB+AC

Identità 1A = A 0+A = A

Inverso _{AĀ = 0} _{A+Ā = 1}

10

Proprietà dell’Algebra di Boole

Forma AND Forma OR Forma AND Forma OR

Elemento nullo 0A = 0 1+A = 1

Idempotenza AA = A A+A = A

Assorbimento A(A+B) = A A+AB=A

Associatività (AB)C=A(BC) (A+B)+C=A+(B+C) Associatività (AB)C=A(BC) (A+B)+C=A+(B+C)

De Morgan AB = A+B A+B = A B

Altre proprietà della negazione

• 1 = 1

• 0 = 0

(4)

Altre funzioni di base

x x x ••••x x x x + x x₁ x₀ x₁ ••••x₀ 0 0 1 0 1 1 1 0 1 1 1 0 x₁ x₀ x₁+ x₀ 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 0 NAND NOR 13

Formule (espressioni) booleane

1. Le costanti 0 e 1 e le variabili (simboli a cui

possono essere associati i valori 0 e 1) sono

espressioni booleane

2. Se E, E

₁

ed E

₂

sono espressioni booleane lo sono

anche (E

₁

+E

₂

), (E

₁

·E

₂

) e (E)

3. Non esistono altre espressioni oltre a quelle che

possono essere generate da un numero finito di

applicazioni delle regole 1 e 2

14

Esempi di formule Booleane

((x+y)·z)

((x

₁

·x

₂

)+(x

₃

·(x

₄

+x

₅

)))

Valgono le regole classiche di semplificazione

delle parentesi e di priorità degli operatori:

((x

₅

)

… e il simbolo “·” di solito si omette

x

₃

)

• x

₂

₃

=

x

₁

x

₂

(1 +x

₃

) = x

₁

x

₂

(5)

Equivalenza fra espressioni booleane

Verifica tramite tabella

x + x + x x + x x = x + x + x

?

Tabelle di verità e proprietà

dell’Algebra di Boole: Esempio

Assorbimento: x(x+y) = x

x

y

x+y

x(x+y)

0

1

0

1

0

1

Assorbimento: x(x+y) = x

1

0

1

18

Tabelle di verità e proprietà

dell’Algebra di Boole: Esempio

Proprietà di De Morgan: x y = x + y

x

y

xy

x

y

x + y

0

1

0

1

0

1

0

1

0

1

0

1

Proprietà di De Morgan: x y = x + y

1

0

1

0

1

0

Esercizi

• Costruire le

tabelle di verità

delle seguenti

espressioni logiche:

1. (x + y) + (xy) che è equivalente a scrivere (x OR y) OR NOT(x AND y) 2. ((x + z) + y) + (xz) che è equivalente a scrivere