Introduzione all'algebra di Boole e applicazioni nei circuiti digitali

Algebra di Boole

Table of Contents

Introduzione......1

Variabili e loro valore......4

Operatori booleani......4

Operatori booleani fondamentali......4

L' operatore AND......4

L' operatore OR......6

L' operatore NOT......7

Proprietà fondamentali.......8

Relazioni di De Morgan:......8

Proprietà distributiva dell'AND rispetto all'OR:.....8

Proprietà distributiva dell'OR rispetto all'AND:......8

Assiomi fondamentali.....8

assioma dell'annullamento: ......8

A * 0 = 0......8

assioma del complemento:......8

assioma della negazione:....9

assioma della doppia negazione:.....9

Teoremi dell'assorbimento.......9

I Teorema dell'assorbimento:.......9

II Teorema dell'assorbimento:.........9

Algebra di Boole e circuiti digitali.........9

Pagina 1(fine)

Introduzione

Il matematico Boole ha formalizzato l'algebra che prende il suo nome allo scopo di

associare un'algebra alla logica (~ anni 1850). Per questo si comincia a parlare di logica

matematica. Boole ha voluto tradurre in algebra le proposizioni logiche. Cosa

intendiamo per proposizioni logiche? Si tratta di proposizioni semplici o composte che

ritornano un valore di verità (VERO o FALSO) in base ai valori di verità delle singole

proposizioni ed al significato degli operatori (e, oppure etc..) che le connettono. Il valore

di verità che ogni singola proposizione assume é stabilito dalla realtà che essa

rappresenta.

Quali sono esempi di proposizioni logiche?

Facciamo degli esempi:

Roma é la capitale d'Italia

Questa é una proposizione logica perché risponde al valore di verità: VERO

23 é minore di 9

Questa é una proposizione logica perché risponde al valore di verità: FALSO

In base alla realtà che queste singole proposizioni rappresentano non ho alcun

dubbio su quale sia il valore di verità delle due proposizioni sopra riportate: una é vera e

l'altra é falsa.

Al contrario se ho l'espressione:

Le mele sono più gustose delle pere

non ho a che fare con una proposizione logica perché questa espressione dipende

dai gusti delle persone e quindi non può essere né sicuramente vera né sicuramente

falsa.

Proposizioni logiche composte

Possiamo anche avere proposizioni logiche composte, ad esempio:

Napoli é una città e la Campania é una regione

Si tratta di una proposizione logica perché entrambe le proposizioni sono

proposizioni logiche (tutte e due rispondono ad un valore di verità, in questo caso

pagina 2

VERO). Esse sono tenute insieme da un operatore che le connette di tipo “e”. In base al

significato dell'operatore “e” ed al valore di verità che rappresentano le due singole

proposizioni, questa espressione é VERA nella sua complessità.

Se invece scrivo:

Napoli é una regione oppure la Campania é una città

si tratta ancora di una proposizione logica perché composta da due proposizioni

logiche che rispondono al valore di verità FALSO, ma in questo caso l'intera

espressione é FALSA perché, pur avendo usato l'operatore “oppure”, nessuna delle

due espressioni é vera, per cui l'espressione nel suo insieme é ancora FALSA.

Infine se scrivo:

Napoli é una regione oppure la Campania é una regione

L' intera espressione é VERA perché, essendoci “oppure”, vuol dire che basta che

sia VERA solo una delle due proposizioni per poter rispondere VERO alla domanda

“Napoli é una regione oppure la Campania é una regione? In questo caso una delle

due espressioni é VERA (la Campania é una regione) per cui l'intera proposizione é

vera.

Applicazioni dell'algebra di Boole

Alle proposizioni logiche Boole ha voluto applicare la matematica dando origine e

formalizzando l'algebra di Boole. Cosa significa? Significa che ha pensato di trattare le

proposizioni come delle variabili e le connessioni (“e”, “oppure”) come degli operatori

con i quali effettuare delle operazioni dopo avergli attribuito una definizione e delle

proprietà. Una volta definiti gli operatori si possono svolgere delle operazioni sulle

proposizioni (ora viste come variabili) come fate con la matematica che conoscete.

L' algebra di Boole nel complesso può essere applicata ad espressioni di vario

genere. Ad esempio anche i circuiti possono essere descritti utilizzando l'algebra

booleana.

L'algebra di Boole fornisce gli strumenti per elaborare ed interpretare tutto ciò che

racchiude un'informazione binaria; la cosa importante é che le espressioni che sono

rappresentate da variabili booleane rispondano solo alla domanda VERO o FALSO, 0 o

pagina 3

1, spento o acceso, aperto o chiuso, cioè ammettano solo due valori.

Ad esempio perché i circuiti logici possono essere descritti usando l'algebra

booleana? Perché i circuiti logici sono componenti hardware che manipolano

informazione binaria (basata solo su 0 e 1) in quanto il segnale passa o non passa, il

segnale é alto o basso, é 0 o é 1. Per questo motivo si può descrivere un circuito

digitale usando le variabili e gli operatori dell'algebra booleana che vengono usati per

rappresentare le porte logiche e le connessioni fra di esse. I circuiti di base dove passa

il segnale sono detti porte logiche (logical gates).

Variabili e loro valore

Descrizione delle variabili booleane

Cominciamo a descrivere l'algebra di Boole. La prima cosa importante da dire é che

il matematico ha associato due numeri alle espressioni di base della logica:

FALSO = 0

VERO = 1

Poteva essere fatta la scelta contraria, ma questa é stata la scelta e dobbiamo

accettarla come un dato di fatto.

Tutte le espressioni logiche di cui abbiamo parlato precedentemente possono

assumere solo due valori: 0 e 1. In algebra Booleana le variabili possono assumere solo

due valori: 0 e 1 e su queste variabili si possono fare delle operazioni, ma per fare delle

operazioni servono gli operatori.

Operatori booleani

Operatori booleani fondamentali

Gli operatori dell'algebra booleana sono detti operatori booleani. Ora ne vediamo

alcuni. Ad essi daremo una definizione e ne descriveremo le proprietà specifiche.

Definiamo gli operatori booleani per mezzo delle tabelle della verità. La tabella della

verità riporta tutte le possibili combinazioni dei valori delle variabili ed il risultato che si

ottiene applicando un determinato operatore.

Pagina 4

Gli operatori booleani si dividono in due gruppi: operatori booleani fondamentali ed

operatori derivati. Questi ultimi vengono descritti come combinazione di quelli

fondamentali.

Operatori booleani fondamentali

L' operatore AND

L'operatore AND

L' operatore AND è chiamato anche “prodotto logico”. Vengono usati diversi simboli

per rappresentarlo:

*, ^, &

Come detto sopra lo definiamo usando la tabella della verità:

A B A*B

0 0 0

0 1 0

1 0 0

1 1 1

Possiamo leggere la precedente tabella nel seguente modo: date le variabili A e B,

nelle prime due colonne riportiamo tutte le possibili combinazioni di valori che tali

variabili possono assumere, nella terza colonna, A*B, é invece riportato il loro prodotto

logico. Per definizione l'operatore AND ritorna il valore 1 solo quando tutte le variabili

hanno valore 1, cosa vera anche per più di due variabili.

La tabella della verità riporta tutte le combinazioni possibili dei valori che le variabili

possono assumere: più variabili abbiamo e più aumentano le possibili combinazioni. In

particolare sia ha:

n variabili = 2n combinazioni

pagina 5

Facciamo un esempio: supponiamo di avere 3 variabili: A, B C, quale sarà la tabella

della verità che ci mostra il risultato di A*B*C?

A B C A*B*C

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

3 variabili, 23= 8 combinazioni possibili

Le proprietà dell'operatore AND sono le seguenti:

commutativa: A * B = B * A

associativa: A * (B * C) = (A * B) * C

A * A * A * A * A * A = A questa é una proprietà propria dell'algebra booleana

Per dimostrare quest'ultima proprietà basta fare la tabella della verità:

A A A*A

0 0 0

1 1 1

Il prodotto logico di due variabili uguali non é altro che la variabile stessa. Non serve

nemmeno avere 4 casi nella tabella della verità perché avendo a che fare sempre con

la stessa variabile i casi “0*1” non potranno mai verificarsi.

L' operatore OR

L'operatore OR

L' operatore OR è chiamato anche “somma logica”. Vengono usati diversi simboli per

Pagina 6

rappresentarlo:

+, V, |

Come detto sopra lo definiamo usando la tabella della verità:

A B A+B

0 0 0

0 1 1

1 0 1

1 1 1

La tabella si legge allo stesso modo della tabella per l'AND. Per definizione la somma

logica ritorna il valore 1 se almeno una delle variabile ha valore 1.

Se abbiamo tre variabili:

A B C A+B+C

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 1

3 variabili, 23= 8 combinazioni possibili

Le proprietà dell'operatore OR sono le seguenti:

commutativa: A + B = B + A

associativa: A + (B + C) = (A + B) + C

pagina 7

A + A + A + A + A + A = A questa é una proprietà propria dell'algebra booleana

Per capire il risultato basta fare la tabella della verità:

A A A+A

0 0 0

1 1 1

Come nel caso dell'AND non si possono introdurre 4 casi nella tabella della verità

perché avendo a che fare sempre con la stessa variabile i casi “0*1” non possono mai

verificarsi.

L' operatore NOT

L'operatore NOT

L' operatore NOT é chiamato negazione e per indicarlo si usa generalmente un

trattino sopra la variabile. Ancora una volta per definirlo usiamo la tabella della verità:

A A'

0 1

1 0

L' apice “ ' “ é usato qui per indicare la negazione al posto del trattino.

La negazione é l'operatore che fa cambiare il valore alla variabile, se é vera diventa

falsa, se è falsa diventa vera.

Proprietà fondamentali

Proprietà fondamentali degli operatori

Relazioni di De Morgan:

(A + B)' = A' * B'

(A * B)' = A' + B'

Proprietà distributiva dell'AND rispetto all'OR:

pagina 8

A * (B + C) = (A * B) + (A * C)

Proprietà distributiva dell'OR rispetto all'AND:

A + (B * C) = (A + B) * (A + C)

Assiomi fondamentali
assioma dell'annullamento:

A * 0 = 0

A + 1 = 1

assioma del complemento:

A * A' = 0

A + A' = 1

assioma della negazione:

Se A = B allora A' = B'

assioma della doppia negazione:

(A')' = A

Teoremi dell'assorbimento

Teoremi dell'assorbimento

I Teorema dell'assorbimento:

A * (A + B) = A

Pagina 9

A + (A * B) = A

II Teorema dell'assorbimento:

A * (A' + B) = A * B

A + (A' * B) = A + B

Algebra di Boole e circuiti digitali
L'algebra di Boole può essere usata per interpretare i circuiti elettronici. Questi

sistemi sono caratterizzati da grandezze fisiche (segnali) che possono assumere solo

due valori (acceso/spento come nel caso degli interruttori, alto/basso come nel caso dei

circuiti logici). A questi due stati si può facilmente far corrispondere i valori 0 e 1.

Per quanto riguarda i circuiti logici sono stati proprio costruiti dei circuiti in grado di

effettuare le operazioni di AND, OR e NOT. Questi circuiti prendono il nome di porte

logiche e possono operare su più segnali di ingresso (più variabili booleane) e

producono un segnale in uscita. Essi rispondono a due valori di range di tensioni che

associamo ai valori logico di 0 e 1.

In un disegno di circuito logico questi operatori vengono rappresentati dai seguenti

simboli:

pagina 10

Questi circuiti effettuano le operazioni per i tre operatori che abbiamo sopra descritto

per mezzo delle tabelle della verità. Per capire meglio il loro funzionamento facciamo

una rappresentazione grafica di 2 segnali digitali in funzione del tempo (X(t) e Y(t)) e

delle operazioni AND, OR e NOT su di essi effettuati:

Quindi un'espressione booleana, altrimenti detta funzione booleana, può anche

essere rappresentata per mezzo di un circuito elettronico.

Ad esempio supponiamo di avere la seguente funzione:

F = X + (Y' * Z)