Fondamenti di Informatica

(1)

Fondamenti di Informatica

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 1

Fondamenti di Informatica - Algebra di Boole

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO

Facoltà di Ingegneria Università degli Studi di Udine

Algebra di Boole

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2 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 slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.

Nota di Copyright

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 ai valori che possono assumere i bit

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

(2)

Fondamenti di Informatica

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2

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

B

U U = AB

U = A•B U = A AND B U = A ^∧ B

0 0

0 1

0

1 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

1 1

0

1 0 1

A B

A B U

0 0 0

0 1 1

1 0 1

1 1 1

A

B

U

(3)

Fondamenti di Informatica

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 3

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

B

U U = AB

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

1 1

1 0

0

1 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

1 0

0

1 0 1

A B

A B U

0 0 0

0 1 1

1 0 1

1 1 0

A

B

U

mappa a scacchiera

(4)

Fondamenti di Informatica

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)

B (dato)

U

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

Fondamenti di Informatica

Fondamenti di Informatica

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 1

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO

Facoltà di Ingegneria Università degli Studi di Udine

Algebra di Boole

Nota di Copyright

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 ai valori che possono assumere i bit

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

Fondamenti di Informatica

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2

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 1

Operatore AND

A

B

U U = AB

U = A•B U = A AND B U = A ∧ B

0 0

0 1

0

1

0 1

A B

A B U

0 0 0

0 1 0

1 0 0

0 ¹

U = A•B U = A AND B U = A ^∧ B

U = A+B U = A OR B U = A ^∨ B