© 2010 Marco Mezzalama, Elio Piccolo, Capire linformatica 1 Marco Mezzlama, Elio Piccolo Capire...

© 2010 Marco Mezzalama, Elio Piccolo, Capire l’informatica 1

Marco Mezzlama, Elio Piccolo

Capire l’informatica

Algebra di Boole e Circuiti Logici




Perché è importante la logica• è alla base del ragionamento umano• costituisce il fondamento teorico per

trattare i circuiti digitali che sono alla base dei calcolatori

• è essenziale per la costruzione degli algoritmi e quindi per i linguaggi di programmazione

• è alla base di linguaggi non procedurali come il Prolog




L’Algebra di Boole• fu ideata nella prima metà del XIX secolo dal

matematico inglese George Boole, con l’intento di ricondurre al rigore matematico il ragionamento umano

• fu utilizzata da C. E. Shannon all’inizio del XX secolo per descrivere il comportamento dei circuiti a commutazione (relays), in uso nella telefonia, e da qui ai dispositivi digitali

• È una struttura algebrica, potrebbe essere introdotta in modo formale. Qui verrà proposta in modo intuitivo.




Le basi dell’algebra booleana

Nell’algebra di Boole:• Si mettono in corrispondenza le

proposizioni, o in generale gli eventi binari, con le variabili logiche (o booleane)

• Le variabili logiche sono denotate con le lettere dell’alfabeto (A,B,…a,b,…)

• Le variabili logiche possono assumere solo due valori: Vero (T, o anche 1) o Falso (F, o anche 0)




Le basi dell’algebra booleana (2)

Esempi:macchina_parte P (= T, o 1, se la macchina parte, F, o 0, se non parte)semaforo_verde S (= 1 se è verde, 0 altrimenti)interruttore I (= 1 se è chiuso, 0 se aperto)Nota: l’associazione stato valore di verità è arbitraria.




Le basi dell’algebra booleana (3)

Nell’algebra di Boole:• si possono mettere in relazione n-ple di

variabili indipendenti con una particolare variabile dipendente

• la variabile dipendente è detta funzione booleana

• le funzioni booleane possono assumere solo due valori, T o F, ovvero 1 o 0

• Esempio y = F(x1, x2, … xn).




Tavola di verità

• Una funzione è descritta in modo esaustivo stabilendo, per ogni combinazione delle variabili di ingresso, se vale 1 oppure 0.

• Si crea dunque una tabella, detta tavola di verità della funzione.

• Qui di seguito un esempio di tavola di verità:




Esempio di tavola di verità




Esempio applicativo

“Si può telefonare con il cellulare solo se la batteria è carica, se c’è campo e c’è credito”.

Le variabili logiche sono:• Variabile dipendente:

T: vale 1 (= True) se si può telefonare;• Variabili indipendenti:

B: vale 1 (= True) se la batteria è carica;C: vale 1 (= True) se c’è campo;P: vale 1 (= True) se c’è credito.




Esempio applicativo (2)La tavola di verità della funzione telefonare




Quante funzioni di n variabili?

• Il numero di combinazioni delle variabili di ingresso è 2n. Infatti la prima variabile può assumere 2 valori, per ciascuno di essi la seconda variabile può assumere 2 valori, e così via, per un totale di 2 2 2… 2 = 2n.

• Quante funzioni si possono costruire con n variabili?




Quante funzioni di n variabili? (2)n varabili

k co

mbi

nazi

oni

m funzioni

Numero variabili: n

Numero combinazioni: k = 2n = 2^n

Numero funzioni:

m = 2^k = 2^(2^n)

Esempio: se n = 4,

k = 2^4 = 16 e

m = 2^16 = 65.536




Operatori logici: l’AND• Operatore AND

– esprime il concetto di “e insieme”– indicato nei seguenti modi: A AND B, A B

oppure A B– opera secondo la seguente tavola di verità:




AND (2)

– esempio: mi_compro_il_gelato se fa_caldo AND ho_i_soldi.

– viene anche detto prodotto logico, per analogia con operatore matematico.

– Il simbolo circuitale dell’AND:




AND (3)

• analogo elettrico dell’operatore AND: due interruttori in serie.




OR• L’operatore OR

– Esprime il concetto di disgiunzione logica (una cosa oppure un’altra oppure entrambe)

– indicato nei seguenti modi: A OR B, A + B oppure A B

– opera secondo la seguente tavola di verità:




OR (2)– esempio: esco_con_l’ombrello se piove OR

nevica.– viene anche detto somma logica (ma qui

l’analogia con l’operatore aritmetico è più lasca)

– Il simbolo circuitale dell’OR:




OR (3)

• analogo elettrico in un circuito dell’OR: due interruttori in parallelo




NOT

• Operatore NOT:– ha il significato di negazione logica– indicato nei seguenti modi: NOT A, oppure

A. – Opera secondo la seguente tavola di verità:




NOT (2)

– Esempio: è_sereno se nuvoloso.– Il simbolo circuitale del NOT:




NOT (3)– analogo elettrico dell’operatore NOT:

Nota: per realizzare la funzione di NOT occorre un dispositivo “attivo”

è realizzato di solito con un semplice transistor.




Altri operatori notevoli

• sono derivabili dagli operatori elementari

• sono di uso frequente o sono concettualmente rilevanti




EX-OR

• L’operatore EX-OR (OR esclusivo):– Indicato nei seguenti modi: A EX-OR B, oppure A B– opera secondo la seguente tavola di verità:




EX-OR (2)– A B è equivalente all’espressione

– Il simbolo circuitale dell’EX-OR:

BABA




EX-OR (3)

• Alcune interpretazioni dell’EX-OR (facendo riferimento alla tavola di verità):– indica diversità (vale 1 se e solo se A e B sono

diversi)– corrisponde alla somma-modulo-2 (in cui si tiene

conto solo del risultato e non del riporto)– condizionamento: sia B è il segnale condizionante.

Quando B=0, l’uscita dell’EX-OR corrisponde al segnale A. Quando B=1, l’uscita corrisponde al segnale A invertito (invertitore pilotato).




Implicazione logica

• L’operatore di implicazione logica– modella il costrutto logico “Se A allora B”– indicato come A B (cioè A implica B) – opera secondo la seguente tavola di verità:




Implicazione logica (2)

– vale la seguente equivalenza:

(la formula equivalente permette le manipolazioni algebriche)

– si noti che se la premessa è Falsa (A = 0), la formula resta Vera indipendentemente da B

– esempio: Se triangolo_rettangolo allora un_angolo_novanta_gradi

– è il fondamento del ragionamento deduttivo

BABA




Espressioni logiche

• Combinazione di variabili e operatori logici• possono essere valutate per ogni combinazione

delle variabili presenti e possono assumere il valore 0 o 1

• anche le espressioni si rappresentano mediante la tavola di verità.

• Nota:– Spesso l’operatore di prodotto logico viene omesso:

T = ab + c– vale la priorità degli operatori (nell’ordine, NOT, poi

AND e infine OR)




Espressioni equivalenti

E1 ed E2 sono equivalenti se

• per tutte le combinazioni delle variabili indipendenti per cui E1 = 1 anche E2 = 1 e

• per tutte le combinazioni delle variabili indipendenti per cui E1 = 0 anche E2 = 0




Espressioni equivalenti (2)

Esempio di equazioni equivalenti:

ba

b

a

TT

yzxzT

yzxxzT




Espressioni equivalenti (3)




Espressioni complementari• E1 ed E2 sono complementari se:

– per tutte le combinazioni delle variabili indipendenti per cui E1 = 1 risulta E2 = 0 e

– per tutte le combinazioni delle variabili indipendenti per cui E1 = 0 risulta E2 = 1

Nota: se due espressioni sono complementari:

E1 = E2




Espressioni complementari (2)

Esempio di funzioni complementari:

ba

b

a

TT

xyyxT

yxyxT




Espressioni complementari (3)




Espressioni dualiE2 è duale di E1 se può essere ottenuta da E1:• sostituendo l'operatore OR con l'operatore

AND e viceversa (tenendo conto delle precedenze degli operatori in E1 !!);

• sostituendo il valore 0 con il valore 1 e viceversa.

Regola di complementazione: l'espressione complementare di E1 può essere ottenuta dalla sua duale E2 complementando tutte le variabili in E2 (teorema di De Morgan) .




Espressioni duale e complementare

F(a,b,c) = a (b + c) Fd = a + (b c) F = a + (b c)

a b c F Fd F 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0




Teoremi dell’algebra di Boole

• si possono dimostrare per induzione completa: è sufficiente fare la tavola di verità.

• vale inoltre una proprietà legata alla dualità: è stato dimostrato che se vale un teorema, vale anche il teorema duale, senza che di debba ripetere la dimostrazione.

• ecco le proprietà e i teoremi più importanti:




Teoremi dell’algebra di Boole (2)

1:

0)

:

)

0:

1)

11:

00)

XXDuale

XXd

XXXDuale

XXXc

XXDuale

XXb

XDuale

Xa





ZYXZXYXDuale

vadistributiproprZYXZXYXh

ZYXZYXDuale

DeMorganteoremaZYXZYXg

ZYXZYXZYXDuale

assocproprZYXZYXZYXf

XYYXDuale

acommutativproprXYYXe

)()(:

_._)()

......:

__......)

)()(:

._._)()()

:

_._)





)()()()(:

)

)(:

)

)()(:

_._)

)(:

'__)

YZXZYXZXZDuale

YZXZYXZXZl

YXYXXDuale

YXYXXk

XYXYXDuale

direttafusioneteorXYXYXj

XYXXDuale

inclusionedellteoremaXYXXi





),...,,1,0(),...,,,(:

),...,,0,1(),...,,,()

)()(:

)()()

)()()()()(:

)

ZYfXZYXXfXDuale

ZYfXZYXXfXo

YXZXZXYXDuale

YXZXZXYXn

ZXYXZYZXYXDuale

ZXYXZYZXYXm





atogeneralizzdeMorganZYXfZYXfq

ZYfXZYfXZYXXfDuale

ZYfXZYfXZYXXfp

__),,,...,,(),,,...,,()

),...,,0,1((),...,,1,0((),...,,,(:

),...,,1,0(),...,,0,1(),...,,,()

Da notare che nell’algebra di Boole la proprietà distributiva vale sia per il prodotto (logico) che per la somma (logica).




Dalle funzioni alle espressioni logiche

• Una funzione logica si rappresenta mediante la sua tavola di verità

• Esempio: un comitato di tre persone A, B e C prende le decisioni a maggioranza. Si vuole la funzione che esprima che una mozione è approvata (passa, P).

• Con le stesse lettere A, B e C si indicano le variabili logiche che assumono il valore 1 se la corrispondente persona ha dato voto favorevole, 0 altrimenti.




Dalle funzioni alle espressioni logiche (2)Tavola di verità della funzione “approvazione a maggioranza”:




Dalle funzioni alle espressioni logiche (3)

• È possibile rappresentare questa funzione mediante una espressione?

• Si ricorre al concetto di equivalenza: una funzione può essere rappresentata mediante una espressione che abbia la stessa tavola di verità.

• Una delle possibili espressioni si ricava seguendo il seguente algoritmo:– si individuano le combinazioni per le quali la funzione vale 1;– ogni combinazione fornisce un termine, formato dalla

congiunzione (operatore AND) di tutte le variabili, affermate se le variabili in quella combinazione assumono il valore 1, negate se assumono il valore 0;

– l’espressione è la disgiunzione (operatore OR) di tutti i termini




Dalle funzioni alle espressioni logiche (4)

• Espressione equivalente del tipo somma di prodotti (min term):

ABCCABCBABCAP

ABACBCP

• Applicando i teoremi di base (quello della fusione diretta), si ottiene la forma minima:




Esempio applicativo:l’analisi di un circuito

• Dato il circuito in figura, desumerne il funzionamento.




L’analisi di un circuito (2)

Siano A, B e C le variabili logiche associate agli interruttori (= 1 se chiuso, 0 altrimenti).

Sia L la variabile associata alla lampadina (= 1 se accesa, 0 spenta).

La tavola di verità si realizza controllando se, per ogni combinazione delle variabili indipendenti, la luce è accesa o spenta.





ABCCBABCAL

Considerando le combinazioni per cui L = 1, si ottiene:





• Applicando i teoremi (proprietà distributiva e X+X=X), si minimizza l’espressione:

CBAACBC

ACBBBCAA

ABCCBAABCBCA

ABCCBABCAL

)(

)()(

la luce si accende solo se è chiuso l’interruttore C e insieme uno dei due interruttori A o B.




Sintesi di un circuito

• Problema: in una stanza l’illuminazione è comandata da due deviatori A e B, situati in punti diversi. All’inizio la luce è spenta e i due deviatori si trovano in una posizione che chiamiamo X. Se uno dei due deviatori, diciamo A, viene spostato nella posizione Y, vogliamo che la luce si accenda. Se anche l’altro deviatore viene spostato in posizione Y, vogliamo che la luce si spenga.




Sintesi di un circuito (2)

• Siano A e B le variabili logiche associate ai deviatori. A ciascuna posizione assunta da un deviatore associamo un valore logico: ad esempio associamo 0 alla posizione X, 1 alla posizione Y.

• Sia L la variabile associata alla luce (= 0 se spenta, 1 se accesa).

• La tavola di verità della funzione L è la seguente:





Considerando le combinazioni per cui L = 1, si ha l’espressione:

BABABAL





• Ricordando che l’AND si ottiene con una connessione serie e l’OR con una connessione parallela, si ottiene il circuito:




Esempio: il full-adderLa somma S di 2 numeri binari A e B di n bit può essere ricondotta a n somme elementari di 3 bit tenendo conto che:

• ak, bk sono i bit di peso k di A e B

• sk è il k-esimo bit di S

• rk è il riporto generato dalla somma dei bit

di peso k-1, k-2, ... 0 di A e B.

• r-1 = 0




Full-adder: tabelle di veritàSi possono ricavare le tabelle di verità di sk e rk in funzione di ak , bk e rk-1

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

ak bkrk-1 sk rk




Full-adder: espessioni booleane

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

ak bkrk-1 sk rk

akbkrk-1

akbkrk-1

akbkrk-1

akbkrk-1

akbkrk-1

akbkrk-1

akbkrk-1

akbkrk-1




Full adder: semplificazione delle espressioni

kkkkk

kkkkkk

kkkkkkkkkkkkk

kkk

kkkkkk

kkkkkkkkkk

kkkkkkkkkkkkk

babar

bararb

rbarbarbarbar

bar

barbar

babarbabar

rbarbarbarbas

)(

)()(

)()(

1

11

1111

1

11

11

1111

Le espressioni di sk e rk sono date da:




Full adder: schema circuitale

Le funzioni che forniscono sk ed rk possono essere realizzate in un unico circuito elettronico (full adder):




Sommatore a n bit

Il full-adder può essere usato come circuito base per un sommatore a n bit:

an bn rn-1 a0 b0 0an-1 bn-1rn-2

r0rn-1rn s0sn-1sn

carry




Esercizio

Problema:Si considerino due valori A = a1a0 e B = b1b0 espressi in complemento a 2 su 2 bit.Scrivere l’espressione di una funzione booleana F che è vera se e solo se A = -B

Soluzione:conviene considerare i bit che costituiscono A e B come variabili indipendenti e scrivere la funzione come F (a0,a1,b0,b1).




Esercizio (2)a1 a0 b1 b0 A B F

0 0 0 0 0 0 10 0 0 1 0 1 00 0 1 0 0 -2 00 0 1 1 0 -1 00 1 0 0 1 0 00 1 0 1 1 1 00 1 1 0 1 -2 00 1 1 1 1 -1 11 0 0 0 -2 0 01 0 0 1 -2 1 01 0 1 0 -2 -2 01 0 1 1 -2 -1 01 1 0 0 -1 0 01 1 0 1 -1 1 11 1 1 0 -1 -2 01 1 1 1 -1 -1 0




Esercizio (3)

)(

)(

11000101

1111000101

010101010101

bababbaa

babababbaa

bbaabbaabbaaF

© 2010 Marco Mezzalama, Elio Piccolo, Capire linformatica 1 Marco Mezzlama, Elio Piccolo Capire...

Documents

Transcript of © 2010 Marco Mezzalama, Elio Piccolo, Capire linformatica 1 Marco Mezzlama, Elio Piccolo Capire...