Algebra di Boole...Elementi di Informatica - Algebra di Boole 3 A. Valenzano 1996-2002 Variabili...

Elementi di Informatica - Algebra di Boole 1 A. Valenzano 1996-2002

Algebra di Boole


Sommario

• Variabili e funzioni booleane• Tabelle di verità• Operatori booleani• Espressioni booleane• Teoremi fondamentali dell’algebra di

Boole• Semplificazione delle espressioni logi-

che


Variabili booleane

• Secondo Boole, il ragionamento è basato sulleasserzioni, le quali assumono il valore Vero o Falso.Esempio: oggi_piove. Introdusse così le variabililogiche, che assumono due valori, T o F.

• Con le variabili logiche si possono modellare tutti ifenomeni che assumono due valori, ad esempio icircuiti di commutazione (ON e OFF), le cifre delsistema binario (1 e 0), ecc.

• Useremo le variabili x1, x2, … , xn, che assumono valoriT o F, chiamandole variabili logiche o booleane.


Funzioni booleane

• Una funzione logica F(x1, x2,…,xn) associa adogni n-pla xi un valore logico T o F.

• Ogni funzione può essere specificata per mez-zo di una tabella di verità, che assegna ad ognicombinazione di valori x1, x2,…,xn il valoreassunto dalla funzione F.


Tabelle di veritàPer ogni combinazione delle variabili indipen-denti si riporta il valore di F.Esempio: F(x,y,z)

x y z F0 0 0 10 0 1 00 1 0 00 1 1 11 0 0 11 0 1 11 1 0 01 1 1 1


Numero di funzioni booleane

• Con n variabili si possono avere 2n combina-zioni. Poiché una funzione può assumere solo2 valori il numero di possibili funzioni diverse èdato da:

m = 22n


Numero di funzioni booleane (2)

• Infatti:x1 x2 … xn F0 F1 F2 Fm-1

0 0 0 0 1 0 11 0 0 0 0 1 10 1 0 0 0 0 1……………………………….1 1 1 0 0 0 1


Tipi di funzioni booleane

• Completamente specificate: viene indicato ilvalore di F per ogni combinazione delle varia-bili indipendenti.

• Non completamente specificate: il valore di Fnon è definito per una o più combinazionidelle variabili indipendenti.

Nota: il valore di F per le combinazioni non spe-cificate è detto "don't care" ed è indicato con "-"sulla tabella di verità.


Funzioni completamente specificate

• Esempio: In una stazione, il treno parte se e solo se ilsemaforo è verde e il capostazione ha dato il via.

Variabili logiche:S: vale 1 (= vero) se il semaforo è verdeC: vale 1 (= vero) se il capostazione ha dato il viaFunzione:T: vale 1 (= vero) se il treno parte


Funzioni completamente specificate (2)

Tavola di verità (completamentespecificata):

S C T0 0 00 1 01 0 01 1 1



• Altro esempio: Un allievo del Politecnico silaurea se ha superato tutti gli esami e se hasvolto una tesi di laurea oppure una prova disintesi.Variabili:E: vale 1 se l’allievo ha superato tutti gliesamiT: vale 1 se ha svolto la tesiS: vale 1 se ha svolto la sintesiFunzione:L: vale 1 se si laurea



Tavola di verità:E T S L0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1


Funzioni non completamente specificate

Si osservi che, nella realtà del Poli,• non si può dare la tesi o la sintesi senza aver

prima superato tutti gli esami (combinazioni 2e 4)

• non viene assegnata la sintesi, se l’allievosvolge la tesi (combinazioni 3 e 8)Per queste combinazioni si può nonassegnare un valore alla funzione (funzionenon completamente specificata). Per lecombinazioni che non accadono mai, si usa ilvalore don’t care.


Funzioni non completamente specificate (2)

Tavola di verità:E T S L0 0 0 00 0 1 -0 1 0 -0 1 1 -1 0 0 01 0 1 11 1 0 11 1 1 -


Operatori booleani

• Rappresentano le operazioni basilari dell'al-gebra di Boole.

• Le loro funzioni possono essere realizzatetramite circuiti elettronici elementari taloradetti porte o porte logiche.

• Possono essere definiti tramite tabelle diverità.

• Tutte le funzioni più complesse sono otte-nute tramite opportune combinazioni di talioperatori.


Operatore ANDE' anche detto "prodotto logico":

x y x AND y0 0 00 1 01 0 01 1 1

Tavola della verità

Simbolo logicoxy

Notazioni

x y

x y

x y

x AND y


Operatore ORE' anche detto "somma logica":

x y x OR y0 0 00 1 11 0 11 1 1

Tavola della verità Simbolo logico

xy

Notazioni:

x y

x y

x OR y


Operatore NOTE' anche detto "negazione":

x NOT x0 11 0

Tavola della veritàSimbolo logico

x

Notazioni:

x

~ x

NOT x


Operatore NAND

x y x NAND y0 0 10 1 11 0 11 1 0

Tavola della verità Simbolo logicoxy

Notazioni

x y

~ (x y)

x y

x NAND y


Operatore NOR

x y x NOR y0 0 10 1 01 0 01 1 0

Tavola della verità

Notazioni:

x y

~ (x y)

x NOR y

Simbolo logico

xy


Operatore EX-ORE' anche detto "or esclusivo":

x y x EX-OR y0 0 00 1 11 0 11 1 0

Tavola della verità Simbolo logico

xy

Notazioni:

x y

x y

x EXOR y


Espressioni logiche

• Sono espressioni che combinano variabilibooleane tramite gli operatori logici

• Espressioni equivalenti: E1 ed E2 sono equi-valenti se

• per tutte le combinazioni delle variabili in-dipendenti per cui E1 = 1 anche E2 = 1 e

• per tutte le combinazioni delle variabili in-dipendenti per cui E1 = 0 anche E2 = 0


Espressioni equivalenti

Esempio di equazioni equivalenti:Impossibile v isualizzare l'immagine.

ba

b

a

TTyzxzTyzxxzT


Espressioni equivalenti (2)

_x y z xz xyz yz Ta Tb0 0 0 0 0 0 0 00 0 1 0 0 0 0 00 1 0 0 0 0 0 00 1 1 0 1 1 1 11 0 0 0 0 0 0 01 0 1 1 0 0 1 11 1 0 0 0 0 0 01 1 1 1 0 1 1 1


Espressioni complementari

E1 ed E2 sono complementari se:• per tutte le combinazioni delle variabili in-

dipendenti per cui E1 = 1 risulta E2 = 0 e• per tutte le combinazioni delle variabili in-

dipendenti 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)

_ _ __x y xy xy xy xy Ta Tb0 0 0 0 1 0 0 10 1 0 1 0 0 1 01 0 1 0 0 0 1 01 1 0 0 0 1 0 1


Espressioni duali

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

AND e viceversa (tenendo conto delle pre-cedenze degli operatori in E1 !!);

• sostituendo il valore 0 con il valore 1 e vi-ceversa.

Regola di complementazione: l'espressione com-plementare di E1 può essere ottenuta dalla sua dua-le E2 complementando tutte le variabili in E2.


Esempi di espressioni booleane

F(a,b,c) = a (b + c) Fd = a + (b c) F = a + (b c)a b c F Fd F0 0 0 0 0 10 0 1 0 0 10 1 0 0 0 10 1 1 0 1 11 0 0 0 1 11 0 1 1 1 01 1 0 1 1 01 1 1 1 1 0


Teoremi dell’algebra booelana

• Possono essere dimostrati per induzio-ne completa (verifica della validità perogni combinazione delle variabili indi-pendenti).

• Dato un teorema esiste il teoremaduale.

• Se è dimostrata la validità di un teore-ma è dimostrata anche la validità delteorema duale.


Principali teoremi

1:

0)

:)

0:1)

11:00)

XXDuale

XXd

XXXDualeXXXc

XXDualeXXb

XDualeXa


Principali teoremi (2)

ZYXZXYXDualevadistributiproprZYXZXYXh

ZYXZYXDuale

DeMorganteoremaZYXZYXg

ZYXZYXZYXDualeassocproprZYXZYXZYXf

XYYXDualeacommutativproprXYYXe

)()(:_._)()

......:

__......)

)()(:._._)()()

:_._)



)()()()(:

)

)(:

)

)()(:

_._)

)(:'__)

YZXZYXZXZDuale

YZXZYXZXZl

YXYXXDuale

YXYXXk

XYXYXDuale

direttafusioneteorXYXYXj

XYXXDualeinclusionedellteoremaXYXXi



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

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

)()(:

)()()

)()()()()(:

)

ZYfXZYXXfXDuale

ZYfXZYXXfXo

YXZXZXYXDuale

YXZXZXYXn

ZXYXZYZXYXDuale

ZXYXZYZXYXm



atogeneralizzdeMorganZYXfZYXfq

ZYfXZYfXZYXXfDuale

ZYfXZYfXZYXXfp

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

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

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


Espressione che rappresenta una funzione

Problema: una luce L deve essereaccesa / spenta da due interruttoriseparati A e B. Tavola di verità dellafunzione L:

A B L0 0 00 1 11 0 11 1 0


Espressione che rappresenta una funzione (2)

Si consideri l’espressione T data come:_ _

T = AB+ABLa tavola di verità è:

_ _A B AB AB T0 0 0 0 00 1 1 0 11 0 0 1 11 1 0 0 0


Espressione che rappresenta una funzione (3)

L e T si comportano allo stesso modo riga per riga: sidice che T “rappresenta” L.

Regola: si considerano le combinazioni per cui lafunzione vale 1.L’espressione avrà tanti termini in OR quanti sono gli 1della funzione.Ogni termine contiene tutte le variabili in AND. Unavariabile sarà affermata se nella combinazione quellavariabile vale 1, sarà negata se la variabile vale 0.L’espressione ottenuta sarà quindi nella forma sommadi prodotti (min-term).


Semplificazione delle espressioni booleane

• I teoremi fondamentali possono essereimpiegati per semplificare le espres-sioni usate per specificare le funzionibooleane.

• Se una funzione non è completamentespecificata si possono utilizzare le com-binazioni di "don't care" per semplificar-ne l'espressione.


Semplificazione delle espressioni booleane (2)

Regola per la semplificazione:• si confronta ciascun termine con tutti i

successivi;• se i due termini confrontati contengono le

stesse lettere e nei due termini c’è una soladifferenza di una lettera che in un termine èaffermata e nell’altra è negata, si applica ilteorema:

_xY + xY = Y


Semplificazione delle espressioni booleane (3)

• i due termini utilizzati nella fusione simarcano come utilizzati;

• se alla fine ci sono termini non utilizzati innessuna fusione (non marcati), si riportanonell’espressione finale;

• si ripete il tentativo di fusionenell’espressione ottenuta, fino a quando, aduna passata, non si sono effettuate piùfusioni.L’espressione ottenuta è minima (si possonoeventualmente applicare altri teoremi, permigliorare la forma).


Esempi di semplificazione

Tavola di verità di “al Poli ci si laurea”:E T S L0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1


Esempi di semplificazione (2)

)(

)()(

TSEETES

SSETTTES

ETSSETSTEL



x y z F0 0 0 00 0 1 10 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 -



a) don't care = 0

zyxyxz

zyxzyzx

zyxxxzyyyzx

zyxzyxzyxzyxF

)(

)()(



a) don't care = 1

yxzyxzzyxyyzxxz

yxzxzyzyzx

zzyx

yyzxxxzyxxzyyyzx

zyxzyxzyxzyxzyxF

)()(

)(

)()()()(


Realizzazioni circuitali

Infatti

(A·B)·(C·D) = A·B + C·D = A·B + C·D

A

C

B

D

B

A

C

D


Esempio: full adder

La somma S di 2 numeri binari A e B di n bitpuò essere ricondotta a n somme elementaridi 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à disk e rk in funzione di ak , bk e rk-1

ak bk rk-1 sk rk

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


Full adder: espressioni booleane

ak bk rk-1 sk rk

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

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

babarbararb

rbarbarbarbar

barbarbar

babarbabar

rbarbarbarbas

)(

)()(

)()(

1

11

1111

1

11

11

1111

Le espressioni di sk e rk sono date da:


Full adder: struttura a blocchiLe funzioni che forniscono sk ed rk possonoessere realizzate in un unico circuito elettronico(full adder):

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

r0rn-1

rn s0sn-1sn

carry


Esempio (I)Problema (tema di esame del 27/2/96):Si considerino due valori A = a1a0 eB = b1b0 espressi in complemento a 2 su 2 bit.Scrivere l’espressione di una funzionebooleana F che è vera se e solo se A = -BSoluzione:conviene considerare i bit checostituiscono A e B come variabiliindipendenti e scrivere la funzione comeF (a0,a1,b0,b1).


Esempio (II)a1 a0 b1 b0 A B F0 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

F = a1a0b1b0 + a1a0b1b0 + a1a0b1b0


Esempio (III)

Semplificazione di F:

F = a1a0b1b0 + a1a0b1b0 + a1a0b1b0 =

= a1a0b1b0 + a0b0 (a1b1 + a1b1) =

= a1a0b1b0 + a0b0 (a1 + b1)

Algebra di Boole...Elementi di Informatica - Algebra di Boole 3 A. Valenzano 1996-2002 Variabili...

Documents

Transcript of Algebra di Boole...Elementi di Informatica - Algebra di Boole 3 A. Valenzano 1996-2002 Variabili...