Algebra di Boole

Algebra di Boole • I fondamenti dell’algebra Booleana sono stati delineati dal matematico inglese

George Boole in un lavoro pubblicato nel 1847 riguardante l’analisi della logica e in particolare l’algebra della logica.

• Questa algebra include una serie di operazioni che si effettuano su delle variabili logiche, dette appunto variabili Booleane: quantità

che permettono di codificare le informazioni su due soli livelli. • Nell'algebra di Boole essendo, a differenza di quella tradizionale, un'algebra

binaria, le variabili possono assumere soltanto due stati: 0 / 1; v/f ( vero, falso); l/h (low, high); t/f (true, false); on/off;

(acceso/spento) • La definizione di ciascuna operazione booleana si può dare sotto forma di

tabellina (la tabella di verità)• Realizzazione di Reti logiche: circuiti che realizzano una funzione logica

Operazioni logiche/booleane :

perché sono importanti • Sono facili da realizzare utilizzando circuiti elementari • È possibile dimostrare che tutte le funzioni hardware

interessanti (circuiti elettronici, microprocessori, ecc.) possono essere calcolate utilizzando una opportuna combinazione delle funzioni logiche

• Esistono procedimenti automatici per realizzare le funzioni disponibili nell’hardware

• Possiamo scrivere programmi che dialogano direttamente con l’hardware e manipolare sequenze binarie direttamente

• Identità con l’algebra usuale• Tutte e sole le operazioni definite da Boole sono applicabili alla

schematizzazione dei circuiti di commutazione elettronici

•Boole postulo’ una tabella di associazione fra variabili logiche con quattro possibili coppie di valori sono associate fra loro tramite una condizione logica, ad esempio AND oppure OR.

Abbiamo due possibili valori logici (1/0, vero/falso , on/off…) e quindi quattro possibili coppie :

0 1

0

1

Viene definita una operazione logica AND fra queste coppie dia i seguenti risultati:

0 0

0 11

La scelta dei possibili valori di accoppiamento che qui abbiamo operato e’ legata al nostro desiderio di implementare un qualche tipo di meccanismo o dispositivo che sia capace di operare in modo automatico su quantita’booleane. Esempio: un circuito elettronico capace di operare su valori binari (che fornisce proprio i valori sopra indicati) e’ il seguente:

00 00 0000 11 00

0011 00

11 11 11

++

__

Un esempio di implementazione di un circuito logicoUn esempio di implementazione di un circuito logico

Consideriamo un circuito composto da due interruttori e da una lampadina:Consideriamo un circuito composto da due interruttori e da una lampadina:

Creiamo un circuito collegando interruttorie lampadina ai poli di un generatore:Creiamo un circuito collegando interruttorie lampadina ai poli di un generatore:

Se gli interruttori, come in questo caso, sono entrambi OffOff, il circuito non sara’ chiuso e la lampadina restera’ spenta:Se gli interruttori, come in questo caso, sono entrambi OffOff, il circuito non sara’ chiuso e la lampadina restera’ spenta:

++

__

Basta che anche uno solo dei due interruttori sia OffOff, perche’ il circuito rimanga interrotto e la lampadina resti spentaBasta che anche uno solo dei due interruttori sia OffOff, perche’ il circuito rimanga interrotto e la lampadina resti spenta

Un esempio di implementazione di un circuito logicoUn esempio di implementazione di un circuito logico

++

__

Basta che anche uno solo dei due interruttori sia OffOff, perche’ il circuito rimanga interrotto e la lampadina resti spentaBasta che anche uno solo dei due interruttori sia OffOff, perche’ il circuito rimanga interrotto e la lampadina resti spenta

++

__

Se invece mettiamo entrambi gli interruttori sulla posizione OnOn, il circuito verra’ chiuso e la lampadina si accendera’!!Se invece mettiamo entrambi gli interruttori sulla posizione OnOn, il circuito verra’ chiuso e la lampadina si accendera’!!

OffOff OffOff

OffOff

Switch 1Switch 1 Switch 2Switch 2 LampadinaLampadina

On On

OffOff

OffOff

On On OffOff OffOff

On On On On On On

00 00 00

00 11 00

0011 00

11 11 11

Possiamo istituire una corrispondenza fra il comportamento di questo circuito e latabella di verita’ vista prima.

Operatori Logici o porte logiche Circuiti logici ( logic gate) per costruire reti logiche

A B Z

0 0 00 1 01 0 01 1 1

A B Z

0 0 00 1 01 0 01 1 1

A

BZ=AB

AND

A B Z

0 0 00 1 11 0 11 1 1

A B Z

0 0 00 1 11 0 11 1 1

A

BZ=A+B

OR

A Z

0 11 0

A Z

0 11 0

A Z=A

NOT (Inverter)

AND produce 1 in output solo se entrambi gli input sono 1, zero altrimenti.AND produce 1 in output solo se entrambi gli input sono 1, zero altrimenti.

OR produce 1 in output se anche uno solo dei valori in input e’ 1OR produce 1 in output se anche uno solo dei valori in input e’ 1

NOT e’ un operatore di inversione, scambia lo zero con 1 e viceversaNOT e’ un operatore di inversione, scambia lo zero con 1 e viceversa

A B Z

0 0 10 1 11 0 11 1 0

A B Z

0 0 10 1 11 0 11 1 0

A

BZ=AB

NAND

A B Z

0 0 10 1 01 0 01 1 0

A B Z

0 0 10 1 01 0 01 1 0

A

BZ=A+B

NOR

A B Z

0 0 00 1 11 0 11 1 0

A B Z

0 0 00 1 11 0 11 1 0

A

BZ=A B

Exclusive-OR (XOR)

A B Z

0 0 10 1 01 0 01 1 1

A B Z

0 0 10 1 01 0 01 1 1

A

BZ=AB

Exclusive-NOR (XNOR)

NAND agisce prima come l’AND e poi necomplementa l’output. NAND agisce prima come l’AND e poi necomplementa l’output.

NOR agisce prima come l’OR e poi ne complementa l’output. NOR agisce prima come l’OR e poi ne complementa l’output.

XOR restituisce un 1 se il numero di 1 in ingresso e’ dispari.XOR restituisce un 1 se il numero di 1 in ingresso e’ dispari.

XNOR agisce prima come l’XOR e poi neinverte l’output.XNOR agisce prima come l’XOR e poi neinverte l’output.

Quelli indicati sono solamente i tipi basilaridi gate logici, sui quali e’ poi possibile costruire logiche piu’ complesse:

ABC

Z = ABC

A B C Z

0 0 0 00 1 0 01 0 0 01 1 0 00 0 1 00 1 1 01 0 1 01 1 1 11

A B C Z

0 0 0 00 1 0 01 0 0 01 1 0 00 0 1 00 1 1 01 0 1 01 1 1 11

Questo gate di tipo AND con tre ingressi sicomportera’ in modo analogo a quello con due ingressi: si avra’ in output un 1 se e solose tutti gli ingressi sono posti ad 1. La tabella di verita’ sara’ composta da otto combinazioni dei tre ingressi A,B,C

Questo gate di tipo AND con tre ingressi sicomportera’ in modo analogo a quello con due ingressi: si avra’ in output un 1 se e solose tutti gli ingressi sono posti ad 1. La tabella di verita’ sara’ composta da otto combinazioni dei tre ingressi A,B,C

Questo esercizio puo’ essere ampliato a piacerecostruendo elementi adatti a risolvere sistemi logici di arbitraria complessita’...

Questo esercizio puo’ essere ampliato a piacerecostruendo elementi adatti a risolvere sistemi logici di arbitraria complessita’...

OR AND NOT

Proprieta’

Proprieta’

Regole di De Morgan

YXYX

YXYX

Funzioni Logiche• Data una espressione booleana si può trovare la tabella della verità che la rappresenta.

• Per determinare il valore dell’espressione si può determinare il valore delle sotto espressioni che compongono l’espressione iniziale:

Esempio: F= ( A AND ( NOT B )) OR C

prima NOT B, poi A AND (NOT B) ed infine tutta l’espressione (A AND (NOT B)) OR C:

Esempio

yzzxyxzyxfu ,,

x y z x y x +y x + z (x + y )(x + z ) yz u

0 0 0 1 1 1 1 1 0 1

0 0 1 1 1 1 1 1 0 1

0 1 0 1 0 0 1 0 0 0

0 1 1 1 0 0 1 0 1 1

1 0 0 0 1 1 0 0 0 0

1 0 1 0 1 1 1 1 0 1

1 1 0 0 0 1 0 0 0 0

1 1 1 0 0 1 1 1 1 1

110110111001110101,1,0 f

U= (X OR (NOT Y)) AND ((NOT X ) OR Z) OR (Y AND Z)

Esempio

Reti Logiche e porte logiche nell’elettronica digitale

• Le reti logiche sono strettamente legate all’algebra di boole, sono reti composte da tre tipi di elementi (AND, OR e NOT) collegati tra loro detti porte logiche.

• Ogni porta logica ha degli ingressi booleani (sulla sinistra) ed una uscita booleana (sulla destra) gli elementi hanno una rappresentazione grafica che è la seguente:

• Le porte logiche possono essere combinate fra loro, si può quindi codificare in linguaggio binario qualsiasi diagramma di flusso (flow chart) e convertirlo poi in circuito logico.

• Per esempio, la frase:

"se è bel tempo ed è caldo esco; tuttavia, se ho un impegno esco in ogni caso" richiede una porta AND ed una porta OR unite tra loro come in figura.

La combinazione di più porte logiche, permette di ottenere risultati più articolati.

• Per esempio, nella figura sotto è mostrata una porta NOR, costituita dalla combinazione di due porte AND, due porte NOT ed una porta OR.

• Questa porta permette di selezionare un valore positivo (1) se e solo se uno dei due dati in ingresso è positivo (a differenza della porta OR che fornisce un valore unitario anche se entrambi i dati in ingresso sono positivi).

Si possono così costruire circuiti in grado di effettuare operazioni matematiche e se combiniamo tra loro più porte logiche si possono ottenere rapidamente, e senza confusione, decisioni immediate per problemi anche complessi.

• I circuiti elettronici digitali sono costituiti da transistor.

•Un transistor permette di far passare o non far passare elettroni.

•Il passaggio di elettroni è un segnale elettronico binario (1 se passano elettroni, 0 se non passano).

•La caratteristica che distingue gli interruttori elettronici dai più comuni interruttori elettrici è che essi sono comandati da un segnale elettronico binario e non dall'intervento umano.

•Questo significa che è possibile usare il segnale elettronico di un transistor per comandare un altro transistor e così ottenere un nuovo segnale elettronico che, a sua volta, può comandare un altro transistor e così via.

•L'insieme di questi interruttori elettronici che si comandano a vicenda viene detto circuito elettronico.

•Vi sono infinite possibilità di costruzione di circuiti elettronici, ma essenzialmente sono tutte riconducibili agli elementi fondamentali qui esaminati.

Circuiti Elettronici Digitali

• Le reti logiche elaborano informazione rappresentata da segnali digitali. Sono gli elementi architettonici dei calcolatori.• L’algebra di Boole costituisce il mezzo matematico fondamentale per descrivere il funzionamento di queste reti, che nella maggior parte dei casi elaborano segnali binari.

Reti Logiche

Reti Logiche

Un uscita di un elemento può essere collegata ad un ingresso di un altro elemento per realizzare una rete logica.

Una rete logica ha un insieme di segnali booleani di ingresso e un insieme di segnali booleani di uscita vediamo un esempio:

Questa rete ha due ingressi X e Y ed una uscita F, a questa rete può essere associata una espressione booleana che determina il valore di F in funzione di X e Y, in questo caso si ha:

F = ( NOT (X AND Y) ) AND ( (NOT X) OR Y )

I calcolatori elettronici sono realizzati utilizzando milioni di componenti elementari AND/OR/NOT.

Funzioni logiche: realizzazione con porte NAND, NOR

Le porte NAND, NOR sono molto piu’ numerose delle AND, OR nei progetti normali in quanto

sono piu’ facili da costruire usando dei transistor

Qualsiasi espressione logica puo’ essere realizzata con porte NAND, NOR, NOT

In realta’, NOT e’ inutile (NOT = NAND o NOR con gli ingressi collegati insieme)

X0

1

Y0

1

X NOR Y1

0

X0

1

Y0

1

X NAND Y1

0

Logica multi-livello: conversione tra formeReti NAND-NAND e NOR-NOR

Leggi di DeMorgan: (A + B)' = A' • B'; (A • B)' = A' + B'

Scritte diversamente: A + B = (A' • B')'; (A • B) = (A' + B')'

In altre parole: OR e’ come NAND con ingressi complementati AND e’ come NOR con ingressi complementati NAND e’ come OR con ingressi complementati NOR e’ come AND con ingressi complementati

EquivalenzaOR/NAND

A A B B

A 0 0 1 1

A 1 1 0 0

B 0 1 0 1

B 1 0 1 0

A + B 0 1 1 1

A • B 0 1 1 1 A A

B B

A + B 1 1 1 0

A • B 1 1 1 0

OR OR

Nand Nand

Logica multi-livello: conversione tra formeEquivalenza

AND/NOR

Si possono convertire reti con AND ed OR in reti con NAND e NOR, introducendo le inversioni opportune (“bolle”) Per mantenere i livelli logici, ogni inversione deve avere un’inversione corrispondente

Si possono convertire reti con AND ed OR in reti con NAND e NOR, introducendo le inversioni opportune (“bolle”) Per mantenere i livelli logici, ogni inversione deve avere un’inversione corrispondente

A A B B

A 0 0 1 1

A 1 1 0 0

B 0 1 0 1

B 1 0 1 0

A • B 0 0 0 1

A + B 0 0 0 1 A A

B B

A • B 1 0 0 0

A + B 1 0 0 0

AND AND

NOR NOR

A A B B

C C D D

A B

C D

A B

C D

Logica multi-livello: conversione tra formeEsempio: trasformare rete AND/OR in rete NAND/NAND

NAND

NAND

NAND

AND

AND

OR

NAND

NAND

NAND

(A)

(C)

(B)

(D)

• reti combinatorie: i segnali di uscita dipendono unicamente dai segnali di ingresso applicati alla rete all’istante considerato.• reti sequenziali: i segnali di uscita dipendono dai segnali di ingresso applicati alla rete nel tempo, fino all’istante considerato.

Reti combinatorie e reti sequenziali

Reti combinatorie• una rete combinatoria realizza una funzione booleana

con n ingressi ed m uscite • Assegnando le variabili binarie x1x2….xm ai segnali di

ingresso e le variabili z1z2….zm ai segnali di uscita, il comportamento della rete si specifica tramite una tabella del tutto analoga a quella che si impiega per assegnare le funzioni booleane

• Ciascuna variabile di uscita è quindi esprimibile in forma algebrica, come espressione booleana delle variabili di ingresso.

• ogni espressione booleana la si può rappresentare usando solo and, or e not

Fine