Lucidi - Dipartimento di Informatica

Informatica Generale
Marzia Buscemi IMT Lucca
email: [email protected]
Ricevimento:
Giovedì ore 16.00-18.00
presso
Dipartimento di Informatica, Largo Pontecorvo 3
stanza 306 PS (lab. Global Computing) Tel. 050.2213102
o per posta elettronica
Pagina web del corso:
http://www.di.unipi.it/~buscemi/IG07.htm
(sommario delle lezioni in fondo alla pagina)
1
La scorsa volta abbiamo
visto...




Cos’è la Logica di Boole
Come rappresentare funzioni logiche
mediante tavole di verità e in termini di
AND-OR-NOT
Come si ridurre funzioni logiche attraverso
l’uso delle Mappe di Karnaugh
Degli esempi di semplici funzioni logiche
(bit di parità, contatore di bit, sommatore,
...)
2
Algebra di Boole


Insieme di regole algebriche della logica binaria
che stanno alla base del funzionamento dei
calcolatori
È costituita da:
 un insieme di variabili booleane A,B,C,... che
possono assumere solo i valori 1 (vero) o 0
(falso).
 un insieme di funzioni (operazioni) che
operano sulle variabili di input e danno delle
variabili di output
 un insieme di leggi (assiomi) che definiscono
le proprietà delle funzioni.
3
Algebra di Boole
Le tre funzioni principali sono:
 AND (*): congiunzione logica
A*B (AB) è vera se sia A sia B sono vere

OR (+): “oppure”
A+B è vera se almeno uno tra A e B è vero

NOT ( ¯ oppure ¬ ): negazione
Ā è vera se A è falsa
4
Tavole di verità

Le tavole di verità servono a visualizzare i
valori assunti dalle funzioni a partire da
tutti i possibili valori delle variabili.
A
0
0
1
B
0
1
0
1 1
A*B
0
0
0
1
A
0
0
1
B A+B
0
0
1
1
0
1
1 1
A
0
1
Ā
1
0
1
A partire da AND OR e NOT si possono ottenere tutte le
funzioni che si scrivono con le tavole di verità.
5
Mappa di Karnaugh
AB 00
CD
01
11
10
1
0
0
1
0
0
1
1
1
1
1
1
00
01
11
10
0
0
0
0
¬B¬C¬D
AD
CD
La funzione risultante è data dall’OR di tutti i gruppi:
6
¬B¬C¬D + AD + CD
Esercizio

Scrivere le mappe di Karnaugh e le
(eventuali) funzioni ridotte per
ciascuna delle variabili di output
della funzione incremento che,
dato un numero x a 3 bit dà in
output il numero x+1 a 4 bit:
incr(x2,x1,x0) = (y3,y2,y1,y0)
7
Funzioni NAND e NOR

NAND: ¬(A*B) vera quando A*B è falsa

NOR: ¬(A+B) vera quando A+B falsa

Universalità di NAND (risp. NOR): AND, OR and
NOT possono essere rappresentate usando
unicamente NAND (risp. NOR).
8
Proprietà delle funzioni logiche

p. commutativa


(A+B)+C = A+(B+C)
A*(B+C) = (A*B)+(A*C)
A+(B*C) = (A+B)*(A+C)
0+A=A 0*A=0 1+A=1
¬(¬A)=A
A + ¬A = 1
1*A=A A+A=A
A* ¬A = 0
leggi di idempotenza e complementazione


(A*B)*C = A*(B*C)
p. distributiva


A+B = B+A
p. associativa


A*B = B*A
A*A=A
leggi di De Morgan

A*B = ¬((¬A)+(¬B)) A+B = ¬((¬A)*(¬B))
9
Uso delle proprietà per ridurre
le funzioni logiche




Un metodo alternativo alle mappe di
Karnaugh consiste nell’applicare le proprietà
viste.
Es.: (A*(B + C)) + (¬A + ¬B) =
A*B + A*C + ¬(A*B) = (A*B) +
¬(A*B) + A*C = A*C + 1 = 1
Esercizio: ridurre la funzione rappresentata
dalla mappa di Karnaugh data in precedenza
È un metodo poco intuitivo. Può essere utile quando
le variabili sono molte (es. più di 6) e le mappe di
Karnaugh diventano difficili da scrivere
10
Circuiti logici



permettono l’elaborazione dei dati in un
calcolatore (esecuzione di operazioni, etc.)
realizzano elettronicamente il
comportamento delle funzioni dell’algebra
booleana
sono di due tipi:


circuiti combinatori (output solo in funzione
dell’input, non hanno memoria del passato)
circuiti sequenziali (output in funzione dell’input
e dello stato precedente, hanno memoria del
passato)
11
Circuiti combinatori

Porte logiche o gate: realizzano elettronicamente
le funzioni logiche elementari
AND
A
B
NOT
OR
A*B
A
B
A+B
NAND
A
B

A
¬A
NOR
¬(A*B)
A
B
¬(A+B)
Circuiti combinatori: si ottengono collegando più
porte logiche e realizzano funzioni complesse.
12
Circuti combinatori (2)

Esercizio 1: far vedere come le porte
logiche AND, OR e NOT si possono
descrivere usando solo porte NAND.

Esercizio 2: far vedere come una funzione
in forma AND-OR (es. AB + CD) può essere
descritta da un circuito che utilizza solo
porte NAND. Provare anche con X-OR.
13