Università degli Studi di Udine

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria

Università degli Studi di Udine

Algebra di Boole

Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà dell’autore prof. Pier Luca Montessoro, Università degli Studi di Udine.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte dell’autore.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste

Algebra di Boole

costanti

operatori variabili

assiomi

teoremi e

proprietà

Costanti

• Due soli valori, convenzionalmente indicati con 0 e 1

• Talvolta indicati anche con “vero” e

“falso”

• Detti anche “valori logici”, corrispondono

Operatori

• Sono definiti da tabelle che

esaustivamente ne descrivono il comportamento (il numero di

combinazioni di valori di ingresso è finito)

• Le tabelle vengono dette “tabelle della verità”

• Spesso si utilizzano anche descrizioni di

tipo funzionale

Operatori

• Si possono utilizzare diverse notazioni:

– porte logiche (corrispondono ai dispositivi elettronici che svolgono la funzione

dell’operatore)

– notazione algebrica (come nell’algebra tradizionale)

– tabella della verità

– mappa di Karnaugh

Mappe di Karnaugh

00 01 11 10

00

01

11

10

AB CD

00 01 11 10

0

1

AB C

0

1

0 1

A B

!

!

Mappe di Karnaugh

• Topologicamente sono dei TORI:

Mappe di Karnaugh

• Topologicamente sono dei TORI:

0 1 1 1

1 0 1 0

0 1 1 0

0 1 0 0

00 01 11 10

00

01

11

10

AB CD

0 1

1 1

0 ¹

Operatore AND

A

U U = AB

U = A•B

U = A AND B U = A ^∧ B

0 0

0

0 1

A B

A B U

0 0 0

0 1 0

1 0 0

1 1 1

Operatore AND

• Descrizione funzionale (applicabile a porte a N ingressi):

A•B vale 0 se almeno un ingresso vale 0

A•B vale 1 se tutti gli

ingressi valgono 1

Operatore OR

U = A+B

U = A OR B U = A ^∨ B

0 1

0

0 1

A B

A B U

0 0 0

0 1 1

1 0 1

1 1 1

A

U

Operatore OR

• Descrizione funzionale (applicabile a porte a N ingressi):

A+B vale 0 se tutti gli ingressi valgono 0

A+B vale 1 se almeno un

ingresso vale 1

Operatore NOT (“inverter”)

U = A

U = NOT A U = A’

U = A

1 0

0 1

A

A U

0 1

1 0

A U

Altri operatori

• AND seguito da NOT = NAND

• OR seguito da NOT = NOR

• OR esclusivo (EXOR)

Operatore NAND

A

U U = AB

U = A•B

U = A NAND B U = (A•B)

ecc.

1 1

0

0 1

A B

A B U

0 0 1

0 1 1

1 0 1

1 1 0

Operatore NOR

1 0 0 0

0

1

0 1

A B

A B U

0 0 1

0 1 0

1 0 0

1 1 0

A

B

U U = A+B

U = A NOR B

U = (A+B)

ecc.

Operatore EXOR

U = A B

U = A EXOR B

0 1

0

0 1

A B

A B U

0 0 0

0 1 1

1 0 1

1 1 0

A

U

mappa a scacchiera

Operatore EXOR

• A B = AB + AB

• 3 possibili descrizioni funzionali

– complementatore pilotato – comparatore

– generatore di parità

Operatore EXOR

• Descrizione funzionale come complementatore pilotato:

se A = 0 → U = B se A = 1 → U = B

A (controllo)

Operatore EXOR

• Descrizione funzionale come comparatore:

se A = B → U = 0 se A ≠ B → U = 1

A B

U

Operatore EXOR

• Descrizione funzionale come generatore di parità:

A ₁ A ₂ ... A _n = 1

se e solo se il numero di ingressi a 1 è dispari

bit di parità 0 1 0 1 1 0 1 0

00 01 11 10 0

1

AB

C