Transcript
Circuiti digitali Operazioni Logiche: Algebra di Boole
• Il calcolatore può essere visto come un insieme di circuiti digitali • Un circuito digitale è un sistema in cui l’informazione viene rappresentata mediante una grandezza fisica della quale si considerano soltanto valori discreti • Alla grandezza fisica vengono fatti corrispondere solamente due valori logici corrispondenti a due livelli di tensione contrassegnati come alto e basso • Questi livelli sono identificati da una coppia di simboli: – 0 1 – Falso Vero – Aperto Chiuso
Fondamenti di Informatica A Ingegneria Gestionale Università degli Studi di Brescia Docente: Prof. Alfonso Gerevini
Docente: A. Gerevini
Porte Logiche
Esempio di circuito
• Le porte logiche formano la base hardware su cui i circuiti digitali sono costruiti
x1
• Sono particolari dispositivi che possono calcolare varie funzioni dei valori 0 e 1 A
AB
B
A
A+B
A
f
x2
Ā
B AND
NOT
OR
A B
AB
A
A+B
B NAND
Docente: A. Gerevini
2
Fondamenti di Informatica A – Università di Brescia
NOR
Fondamenti di Informatica A – Università di Brescia
3
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
4
Reti combinatorie
Algebra di Boole
• Una rete combinatoria è costituita da
• E’ lo strumento matematico usato per lo studio delle reti combinatorie • E’ un particolare tipo di algebra che include:
– un gruppo di elementi (di calcolo) attivi: le porte logiche – collegati fra loro da elementi passivi: linee di ingresso, di uscita e di circuito
– un insieme di supporto A (l’insieme {0,1} nel ns caso) – degli operatori binari: AND (·) e OR (+) – un operatore complemento: NOT (¯)
• Una rete combinatoria è un circuito elettronico in grado di calcolare in modo automatico funzioni binarie di una o più variabili binarie Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
• Gli operatori soddisfano certe proprietà che si deducono da un insieme di assiomi
5
Docente: A. Gerevini
Variabili booleane
Fondamenti di Informatica A – Università di Brescia
6
Operatori booleani
• Una variabile booleana è una variabile binaria che può assumere uno dei due valori logici denotati con 0 e 1 • Usiamo ad esempio i simboli x, y, z, … per indicare variabili booleane • Può essere x = 1 oppure x = 0
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
• Operatori booleani (o logici) fondamentali: NOT AND OR
7
Docente: A. Gerevini
Negazione Logica Prodotto Logico Somma Logica
not(x), x, ~x x and y, x • y, xy x or y, x + y
Fondamenti di Informatica A – Università di Brescia
8
Le 3 funzioni di base: Tabelle di verità x1
x0
x1 • x0
x1
x0
x1 + x0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
1
AND
Docente: A. Gerevini
Assiomi dell’Algebra di Boole Forma AND
x
0
1
Commutatività AB = BA
1
0
Distributività A+BC=(A+B)(A+C) A(B+C)=AB+AC
NOT
Docente: A. Gerevini
A+B = B+A
Identità
1A = A
0+A = A
Inverso
AĀ = 0
A+Ā = 1
OR
Fondamenti di Informatica A – Università di Brescia
9
Proprietà dell’Algebra di Boole
Elemento nullo Idempotenza Assorbimento Associatività De Morgan
Forma OR
x
Fondamenti di Informatica A – Università di Brescia
10
Altre proprietà della negazione
Forma AND
Forma OR
0A = 0 AA = A A(A+B) = A (AB)C=A(BC) AB = A+B
1+A = 1 A+A = A A+AB=A (A+B)+C=A+(B+C) A+B = A B
Fondamenti di Informatica A – Università di Brescia
Docente: A. Gerevini
11
• 1=1 • 0=0 • 0=1=0=1
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
12
Formule (espressioni) booleane (logiche)
Altre funzioni di base x1
x0
x1 • x0
x1
x0
x1 + x0
0
0
1
0
0
1
0
1
1
0
1
0
1
0
1
1
0
0
1
1
0
1
1
0
NAND
Docente: A. Gerevini
•
• •
NOR
Fondamenti di Informatica A – Università di Brescia
13
•((x+y)· z) •((x1· x2)+(x3· (x4+x5)))
Fondamenti di Informatica A – Università di Brescia
14
• x1x2 + x1x2x3 = x1 (x2+x2x3)
Valgono le regole classiche di semplificazione delle parentesi e di priorità degli operatori: ((x1· x2)+(x3· (x4+x5))) ⇒ x1·x2+x3· (x4+x5) … e il simbolo “· ” di solito si omette Fondamenti di Informatica A – Università di Brescia
Docente: A. Gerevini
Equivalenza fra formule booleane Esempi
Esempi di formule booleane
Docente: A. Gerevini
Le costanti 0 e 1 e le variabili (simboli a cui possono essere associati i valori 0 e 1) sono espressioni booleane Se E, E1 ed E2 sono espressioni booleane lo sono anche (E1+E2), (E1·E2) e (E) Non esistono altre espressioni oltre a quelle che possono essere generate da un numero finito di applicazioni delle regole 1 e 2
15
• x1 + x2 + x2x3 + x2x3 = x1 + x2 + x3(x2+x2) = x1 + x2 + x3 • x1x2 + x1x2x3 + x1x2 = x1x2 + x1x2x3 = x1x2 (1 +x3) = x1x2 Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
16
Tabelle di verità e proprietà dell’Algebra di Boole: Esempio
Equivalenza fra espressioni booleane
Verifica tramite tabella x1 + x2 + x2x3 + x2x3 = x1 + x2 + x3 x3 0 0 0 0 1 1 1 1
x2 0 0 1 1 0 0 1 1
x1 0 1 0 1 0 1 0 1
Docente: A. Gerevini
x2 1 1 0 0 1 1 0 0
Assorbimento:
x2x3 x2x3 x1+x2+x2x3+x2x3 x1+x2+x3 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 17
Fondamenti di Informatica A – Università di Brescia
x 0 0 1 1
Docente: A. Gerevini
y 0 1 0 1
xy 0 0 0 1
xy 1 1 1 0
x 1 1 0 0
xy= x+y
y 1 0 1 0
Costruire le tabelle di verità delle seguenti espressioni logiche: –
x+y 1 1 1 0
–
•
Fondamenti di Informatica A – Università di Brescia
19
(x + y) + (xy)
che è equivalente a scrivere (x OR y) OR NOT(x AND y) ((x + z) + y) + (xz) che è equivalente a scrivere NOT ((x OR z) OR y) OR (x AND z)
Usando le tabelle di verità, o gli assiomi e le proprietà dell’algebra di Boole, dimostrare le seguenti equivalenze espressioni booleane: – –
Docente: A. Gerevini
18
Esercizi •
x 0 0 1 1
x+y x(x+y) 0 0 1 0 1 1 1 1
Fondamenti di Informatica A – Università di Brescia
Tabelle di verità e proprietà dell’Algebra di Boole: Esempio Proprietà di De Morgan:
y 0 1 0 1
x(x+y) = x
Docente: A. Gerevini
xyz + xyz + xyz + x = x xy + xy + x y = x + y Fondamenti di Informatica A – Università di Brescia
20
