VISIT

Parte IV Indice
Algebra

booleana

operatori logici espressioni logiche teoremi fondamentali tabelle di verit forme canoniche circuiti logici mappe di Karnaugh

Esercizi

Fondamenti di Informatica

IV.1

Algebra booleana
Lalgebra

booleana adatta per rappresentare eventi binari, cio condizioni che possono assumere solo due valori
Esempio Una lampadina pu essere accesa (a questa condizione si associa il valore 1 o vero) oppure spenta (valore 0 o falso)

Le

funzioni che operano sulle variabili booleane sono dette funzioni booleane e possono produrre anchesse solo i valori 0 e1
IV.3

Fondamenti di Informatica

Algebra booleana
Una

funzione booleana F, funzione di variabili booleane, v1,v2,...,vn si indica:

F(v1,v2,K,vn)
Pu

essere definita in vari modi:

uno di questi consiste nello specificare i valori di F per tutte le possibili combinazioni delle variabili da cui essa dipende. Tale elenco di combinazioni viene detto tabella della verit

Fondamenti di Informatica

IV.4

Algebra booleana
Esempio

F(v1,v2,v3) pu essere definita come: v3 v2 v1 F

0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Ogni variabile booleana pu assumere due valori, quindi, con n variabili si possono avere 2n possibili combinazioni
Fondamenti di Informatica

IV.5

Algebra booleana
Esempio

Descrizione di un evento mediante una funzione booleana

Un allievo passa lesame se si verifica almeno una delle seguenti condizioni:
supera sia il compito di esonero sia la prova orale non supera lesonero, ma sufficiente alla prova scritta di un appello regolare e supera la prova orale

Si pu assegnare ad ogni evento una variabile booleana: a esonero b scritto regolare c prova orale
Fondamenti di Informatica

IV.6

Algebra booleana
Con 3 variabili booleane ci sono 8 (23) possibili combinazioni La tabella della verit della funzione booleana superamento esame S(a,b,c) sar:

a 0 0 0 0 1 1 1 1
Fondamenti di Informatica

b 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1
IV.7

S 0 0 0 1 0 1 0 1

Algebra booleana
Si noti che per superare lesame, cio S = 1, bisogna aver sostenuto e superato lorale e lesonero e/o lo scritto regolare A stretto rigore di logica la condizione a = 0, b = 0, c = 1 non pu verificarsi, in quanto si pu accedere allorale solo dopo aver superato una delle prove precedenti (o entrambe) Il valore di S per quella combinazione si potrebbe pi correttamente non specificare (valore detto dont care e solitamente rappresentato con il simbolo )
Fondamenti di Informatica

IV.8

Operatori logici
Le

variabili booleane possono essere combinate da operatori logici Tali operatori restituiscono anchessi un valore logico Gli operatori sono:
AND OR NOT NAND NOR EXOR EXNOR
IV.9

Fondamenti di Informatica

Operatori logici
Operatore

AND

tale operatore viene denotato dal simbolo (da non confondere con il simbolo di prodotto aritmetico) e spesso sottinteso si applica a due operandi e produce un valore in accordo alle seguenti regole:
00=0 01=0 10=0 11=1

il risultato vero se entrambi gli operandi sono veri

Fondamenti di Informatica

IV.10

Operatori logici
Operatore

OR (inclusivo)

tale operatore viene denotato dal simbolo + (da non confondere con il simbolo di addizione aritmetica) si applica a due operandi e produce un valore in accordo alle seguenti regole:
0+0=0 0+1=1 1+0=1 1+1=1

il risultato vero se almeno uno degli operandi vero

Fondamenti di Informatica

IV.11

Operatori logici
Operatore

NOT

tale operatore viene indicato con il simbolo sopra la variabile da negare (es. a ) si applica ad un solo operando (operatore unario) e produce un valore in accordo alle seguenti regole: 0 =1
1= 0

il risultato il valore opposto (la negazione) di quello delloperando; ovvero, se loperando falso luscita vera e viceversa

Fondamenti di Informatica

IV.12

Operatori logici
Operatore

NAND

tale operatore equivalente ad un operatore AND negato A NAND B = A AND B si applica a due operandi e produce un valore in accordo alle seguenti regole:
0 NAND 0 = 1 0 NAND 1 = 1 1 NAND 0 = 1 1 NAND 1 = 0

il risultato falso se entrambi gli operandi sono veri

Fondamenti di Informatica

IV.13

Operatori logici
Operatore

NOR

tale operatore equivalente ad un operatore OR negato ___________ A NOR B = A OR B si applica a due operandi e produce un valore in accordo alle seguenti regole:
0 NOR 0 = 1 0 NOR 1 = 0 1 NOR 0 = 0 1 NOR 1 = 0

il risultato vero se entrambi gli operandi sono falsi

Fondamenti di Informatica

IV.14

Operatori logici
Operatore

EX-OR (OR esclusivo)

tale operatore viene denotato dal simbolo si applica a due operandi e produce un valore in accordo alle seguenti regole:
00=0 01=1 10=1 11=0

il risultato vero se gli operandi sono diversi tra di loro

Fondamenti di Informatica

IV.15

Operatori logici
Operatore

EX-NOR

tale operatore equivalente ad un operatore EX-OR negato ___________ A B si applica a due operandi e produce un valore in accordo alle seguenti regole:
00 = 1 0 1 = 0 1 0 = 0 11 = 1

il risultato vero se gli operandi sono uguali tra di loro

Fondamenti di Informatica

IV.16

Espressioni logiche
Sono

espressioni contenenti solo:

variabili booleane le costanti 0 e 1 gli operatori logici Esempi

(a + b ) c
a b + c( d + a e) c e
Le

funzioni logiche possono essere definite da espressioni logiche:

F1 = (a + b ) c

F2 = a b + c( d + a e) c e
Fondamenti di Informatica

IV.17

Espressioni logiche
Due

espressioni F1 e F2 si dicono equivalenti quando si verificano entrambe le seguenti condizioni:

tutte le combinazioni di variabili per cui F1 vale 0 sono tali per cui anche F2 vale 0 e viceversa tutte le combinazioni di variabili per cui F1 vale 1 sono tali per cui anche F2 vale 1 e viceversa Ossia ingressi uguali danno uscite uguali in entrambe le funzioni

Esempio

F1 = x F2 = x 1

Fondamenti di Informatica

IV.18

Espressioni logiche
Due

espressioni F1 e F2 si dicono complementari quando si verificano entrambe le seguenti condizioni:

tutte le combinazioni di variabili per cui F1 vale 0 sono tali per cui F2 vale 1 e viceversa tutte le combinazioni di variabili per cui F1 vale 1 sono tali per cui F2 vale 0 e viceversa Ossia ingressi uguali danno uscite opposte nelle due funzioni

Esempio

F1 = a AND b F2 = a NAND b
Fondamenti di Informatica

IV.19

Espressioni logiche
Due

espressioni F1 e F2 si dicono duali quando si verificano entrambe le seguenti condizioni:

tutti gli OR di F1 corrispondono a AND di F2 e viceversa tutti gli 1 di F1 corrispondono a 0 di F2 e viceversa

Esempio

F1 = a + b ( c + 1) F2 = a b + ( c 0)

Fondamenti di Informatica

IV.20

Calcolo di espressioni logiche

Si

devono utilizzare i teoremi propri dellAlgebra di Boole Spesso il calcolo finalizzato a ridurre il numero di termini di una espressione booleana: semplificazione delle espressioni I due metodi per la semplificazione si basano rispettivamente su:
1 i teoremi dellAlgebra di Boole 2 le mappe di Karnaugh

Fondamenti di Informatica

IV.21

Teoremi dellalgebra di Boole

Principali

teoremi

x +1 = 1 1) x 0 = 0 duale 2) x 1 = x duale x+0 = x x+x = x 3) x x = x duale x + x =1 4) x x = 0 duale x+ y = y+x 5) x y = y x duale 6) x y z = ( x y ) z = x ( y z ) duale x + y + z = ( x + y) + z = x + ( y + z) 7)Teorema di De Morgan x y K z = x + y + K + z duale x + y + K + z = x y K z 8) x y + x z = x ( y + z ) duale ( x + y) ( x + z) = x + y z

Fondamenti di Informatica

IV.22

Teoremi dellalgebra di Boole

9) x + x y = x duale x ( x + y ) = x _ _ 10) x y + x y = x duale ( x + y ) ( x + y ) = x _ _ 11) x + x y = x + y duale x ( x + y ) = x y _ 12) z x + z x _y = z x + z y duale
( z + x) ( z + x+ y) = ( z + x) ( z + y)
_ _

13) x y + x z_ + y z = x y + x z duale _ 14) x y + x z_ = ( x + z ) ( x + y ) duale _

( x + y ) ( x + z ) = x z + x y
_ _ _

( x + y) ( x+ z) ( y + z) = ( x + y) ( x+ z)

15) x F ( x, x, y ,K, z ) = x F (1,0, y ,K, z ) _ duale x + F ( x, x, y ,K, z ) = x + F (0,1, y ,K, z ) _ 16) F (_x, x, y ,K, z ) = x F (1,0, y ,K, z ) + + x F (0,1, y ,K, z ) duale
F( x, x, y ,K, z ) = [ x + F (0,1, y ,K, z )] _ [ x + F (1,0, y ,K, z )]
Fondamenti di Informatica
_

IV.23

Teoremi dellalgebra di Boole

Nei

teoremi precedentemente elencati x, y e z possono essere considerate sia come singole variabili sia come espressioni logiche Esempio dalla regola 1 si ricava:
( A + B) 0 = 0

considerando (A+B) al posto di x

Fondamenti di Informatica

IV.24

Semplificazioni con i teoremi

Semplificare le seguenti espressioni X + Y + XY + ( X + Y ) XY 1)
X + Y + Y + ( X + Y ) XY X + 1 + ( X + Y ) XY 1 + qualsiasi espressione = 1

2)

( X + Y ) XY + Z

YX X + Z Y 0 + Z = Z

Fondamenti di Informatica

IV.25

Funzioni logiche e tabelle di verit

ricavare la tabella di verit da una funzione logica si applicano tutte le combinazioni di valori agli ingressi e si valutano le uscite Esempio
F ( a , b, c ) = ( ab + b)c a b c ab b c ab + b ( ab + b)c
Per

000 001 010 011 100 101 110 111

Fondamenti di Informatica

0 0 0 0 0 0 1 1

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 0 0 1 1 1 1

1 0 0 0 1 0 1 0

IV.26

Forme canoniche delle espressioni

Forma

canonica SP (Somma di Prodotti)

E una somma logica di termini Ogni termine (detto minterm) contiene il prodotto logico di tutte le variabili dellespressione, ciascuna variabile pu essere affermata o negata

Esempio
F ( a , b, c ) = abc + a bc + abc + abc

lespressione composta da 4 minterm

Fondamenti di Informatica

IV.27

Forme canoniche delle espressioni

Forma

canonica PS (Prodotti di Somme)

E un prodotto logico di termini Ogni termine (detto maxterm) contiene la somma logica di tutte le variabili dellespressione, ciascuna variabile pu essere affermata o negata

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

lespressione composta da 3 maxterm

Fondamenti di Informatica

IV.28

Forme canoniche delle espressioni

Scrittura

della forma canonica SP data la tabella

Per ciascuna delle righe della tabella in cui la funzione ha risultato 1:
scrivere un prodotto di tutte le variabili per ciascuna delle variabili del prodotto: negarla se nella tabella ha valore 0

Sommare i minterm
Scrittura

della forma canonica PS data la tabella

Per ciascuna delle righe della tabella in cui la funzione ha risultato 0:
scrivere una somma di tutte le variabili per ciascuna delle variabili della somma: negarla se nella tabella ha valore 1

Moltiplicare i maxterm
Fondamenti di Informatica

IV.29

Forme canoniche delle espressioni

Esempio

abc 000 001 010 011 100 101 110 111

F 0 1 1 0 1 1 0 0

a bc
(a + b + c)

Risultati SP: F ( a, b, c ) = a bc + abc + a bc + a bc PS: F (a, b, c) = (a + b + c) (a + b + c)

(a + b + c) (a + b + c)
Fondamenti di Informatica

IV.30

Forme canoniche delle espressioni

Conversione in forma canonica di unespressione SP non canonica
F ( x, y , z ) = x y z + yz + x Si esamina ogni termine:
se contiene tutte le variabili (minterm) il termine non necessita di modifiche altrimenti per ciascuna variabile X che manca, si moltiplica il termine per ( X + X ) e si semplifica

Esempio
primo termine: x y z secondo: yz yz ( x + x ) yzx + yz x terzo: x x ( y + y ) ( z + z )
x yz + x y z + x yz + x y z
Fondamenti di Informatica

IV.31

Forme canoniche delle espressioni

Conversione in forma canonica di unespressione PS non canonica
F ( x, y , z ) = ( x + y + z ) ( x + z ) x Si esamina ogni termine:
se contiene tutte le variabili (maxterm) il termine non necessita di modifiche altrimenti per ciascuna variabile X che manca, si aggiunge X X al termine, si usa la propr. distributiva e si semplifica

Esempio
primo termine: ( x + y + z ) secondo: ( x + z ) ( x + z + y y )
( x + z + y) ( x + z + y) terzo: x ( x + y y + z z ) ...
Fondamenti di Informatica

IV.32

Circuiti logici
Una

funzione logica pu essere rappresentata da un circuito logico Le variabili corrispondono ai fili in ingresso Il risultato corrisponde alluscita del circuito Gli operatori logici corrispondono alle porte logiche

Fondamenti di Informatica

IV.33

Porte logiche
AND

OR

NOT

EXOR

NAND

NOR
Fondamenti di Informatica

IV.34

Porte logiche
Equivalenze funzionali di porte
Una porta AND pu essere sostituita da una porta OR (e viceversa) negando sia gli ingressi sia le uscite (N.B. 2 negazioni si annullano)

Esempio =
Esistono porte a ingressi multipli:
a b c a b c

Lo stesso vale per la porta OR

Fondamenti di Informatica

IV.35

Circuiti logici
Circuito logico equivalente ad una funzione
F ( a, b, c ) = a b + c

a b c F

Si noti come viene realizzata la priorit dellAND sullOR

Fondamenti di Informatica

IV.36