ALGEBRA BOOLEANA
•
•
•
•
•
•
•
•
•
Generalità
Il sistema Binario
Le operazioni con i numeri Binari
Le porte logiche
Proprietà, Assiomi e Teoremi
Mappe di Karnaugh
Problema di logica (1)
Problema di logica (2)
Esercizi
Laboratorio ricerca-azione:
Metodiche formative per adulti
ALGEBRA BOOLEANA
•
La teoria dei circuiti logici considera come modello matematico di
supporto l’Algebra Booleana.
• Un po’ di storia
•
George Boole (Lincoln 1815 - Cork
1864), logico e matematico britannico.
Formatosi principalmente come
autodidatta con l’aiuto del padre, coltivò
dapprima l’interesse per le lingue, e in
particolare del latino, e solo a partire dal
1935 quello per la matematica. Pubblicò
diversi studi sul Cambridge
Mathematical Journal e, in particolare,
uno sulle applicazioni dei metodi
algebrici alla risoluzione delle equazioni
differenziali, che gli valse un
riconoscimento della Royal Society. Nel
1849 venne nominato professore di
matematica al Queen's College (l’attuale
University College) di Cork, in Irlanda,
incarico che conservò per tutta la vita,
guadagnandosi fama di insegnante
appassionato e capace.
Laboratorio ricerca-azione:
Metodiche formative per adulti
ALGEBRA BOOLEANA
L’algebra di Boole è un tipo di algebra completamente diversa da
quella numerica con cui abitualmente si lavora. Essa è definita
come un insieme di definizioni, postulati e teoremi relative a
grandezze che possono assumere soltanto due stati logici distinti.
Questi due stati o valori, si rappresentano con coppie di simboli quali,
per esempio, V (vero) e F (falso); H (high) e L (low) o ancora 0
(zero) e 1 (uno).
Si precisa che 0 e 1 sono considerati solo simboli e non cifre
numeriche.
Nell’ambito elettrico ed elettronico si è solito abbinare lo zero ad un
interruttore aperto e l’ 1 ad un interruttore chiuso.
Laboratorio ricerca-azione:
Metodiche formative per adulti
Proprietà, Assiomi e Teoremi dell’algebra di Boole
N°
Nome
Proprietà
1
Proprietà associativa
a + ( b + c) = ( a + b ) + c; a · ( b · c) = ( a · b ) · c
2
Proprietà commutativa
a + b = b + a; a · b = b · a
3
Proprietà distributiva
a+(b·c)=(a+b)·(a+c)
a·(b+c)=(a·b)+(a·c)
4
Assioma dell’annullamento
a · 0 = 0;
a+1=1
5
Assioma del Complemento
( a + ā ) = 1;
(a·ā)=0
6
Assioma dell’idempotenza
7
Assioma doppia negazione
a · a = a;
== a
a
Teorema di DeMorgan
a + b = ā · b ; a · b= ā + b
9
Teorema dell’assorbimento
Se Y = a + ab
10
Teorema del consenso
Se Y = ab + āc + bc allora Y = ab + āc
a+a=a
8
Laboratorio ricerca-azione:
Metodiche formative per adulti
allora Y = a
Le Porte Logiche
• Not
• Or
• And
• Xor
• Nor
• Nand
• Xnor
Laboratorio ricerca-azione:
Metodiche formative per adulti
Problema di logica
•
•
•
•
Nell’ovile che può essere chiuso con un cancello, c’è una capra; a volte
l’agricoltore apre il cancello dell’ovile per permettere alla capra di pascolare
nel prato. Altre volte apre la porta del granaio, nel quale vi è grano di cui la
capra è ghiotta. Infine può anche accadere che la porta del recinto resti
aperta, al di fuori del quale vi è un lupo che vorrebbe mangiare la capra.
L’agricoltore intende costruire un sistema d’allarme che si attivi solo
allorché la situazione (intesa con porte aperte o chiuse) è di reale pericolo.
Dispone pertanto tre interruttori, uno per ciascuna delle porte.
X1 = Interruttore porta granaio: 0 se aperta; 1 se chiusa;
X2 = Interruttore porta ovile: 0 se aperta; 1 se chiusa;
X3 = Interruttore porta recinto: 0 se aperta; 1 se chiusa.
Si definisce Y il segnale d’allarme:0 se spento 1 se acceso.
Laboratorio ricerca-azione:
Metodiche formative per adulti
Tabella di Verità:
n° riga
X1 granaio
X2 ovile
X3 recinto
Y allarme
1
0
0
0
1
2
0
0
1
1
3
0
1
0
0
4
0
1
1
0
5
1
0
0
1
6
1
0
1
0
7
1
1
0
0
8
1
1
1
0
Laboratorio ricerca-azione:
Metodiche formative per adulti
Spiegazione Tabella di Verità
Riga 1: Allarme: tutte le porte sono aperte:massimo pericolo poichè la capra può
mangiare il grano e il lupo può mangiare la capra;
Riga 2: Allarme:la capra può mangiare il grano;
Riga 3: Nessun allarme: sono aperti il granaio e recinto ma l’ovile è chiuso;
Riga 4 :Nessun allarme: solo il granaio è aperto ma recinto e ovile sono chiusi;
Riga 5: Allarme: il granaio è chiuso ma il recinto e l’ovile sono aperti, il lupo
mangia la capra;
Riga 6 :Nessun allarme: l’ovile è aperto ma granaio e recinto sono chiusi;
Riga 7 :Nessun allarme: il recinto è aperto ma granaio e ovile sono chiusi;
Riga 8 :Nessun allarme: tutte le porte sono chiuse
Laboratorio ricerca-azione:
Metodiche formative per adulti
Problema di logica 2
Progettare ,realizzare collaudare la logica di un antifurto d’appartamento che corrisponda alla
seguente condizione:
 Un sensore di movimento ha un’uscita, normalmente bassa, che va alta quando individua un
movimento;
 Un sensore collegato ad un monitor, ha un’uscita normalmente bassa, che va alta quando il radar
individua un movimento;
 Un interruttore abilita o interdice il segnale di allarme. Nella posizione ON lo attiva fornendo al
sistema un livello alto, nella posizione OFF lo disattiva fornendo un livello basso;
 Il comando di una sirena di allarme agisce quando almeno un sensore fornisce un’uscita alta.
Tabella della verità
A
P
M
S
0
0
0
0
Schema a blocchi
Sensore
P
Porta
0
0
1
0
M
0
1
0
0
Centralina
Sensore
S
Movimento
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
A
OFF
ON
simulazione
Laboratorio ricerca-azione:
Metodiche formative per adulti
Sirena
Ispeziona l’immagine con il mouse
Laboratorio ricerca-azione:
Metodiche formative per adulti
Problema di logica 2
Laboratorio ricerca-azione:
Metodiche formative per adulti
Problema di logica 2
Laboratorio ricerca-azione:
Metodiche formative per adulti
La funzione logica S è data da: S = A*P*M + A*P*M + A*P*M
mettendo in evidenzia A si ha: S = A (PM + PM +PM)
mettendo in evidenza M: S = A [M (P+P) + (PM)]
ma per la proprietà della negazione: P + P = 1 e quindi S = A [(M * 1 + PM)]
ma per la proprietà del prodotto logico: M * 1 = M e quindi: S = A [(M + PM)]
applicando la proprietà distributiva al termine (M + PM) si ha:
S = A [(M + P) * (M + M)]
ma M + M = 1 , quindi: S = A (M + P) * 1
ponendo A (M + P) = X si ha:
S = X * 1; per il prodotto logico si ha : S = X
sostituendo a X il suo valore si ha
S = A (M + P) essa è la funzione minima.
Laboratorio ricerca-azione:
Metodiche formative per adulti
Problema di logica 2
Il Circuito Logico è il seguente:
M
(M + P)
P
A
Laboratorio ricerca-azione:
Metodiche formative per adulti
S = A (M + P)
Problema di logica 2
Il circuito elettronico che lo realizza è il seguente:
+ Vcc = 5 V
14
2
3
1
2
SN7408
A
1
SN7432
M
P
14
7
3
S
7
massa
Realizzazione Pratica
Laboratorio ricerca-azione:
Metodiche formative per adulti
Problema di logica 2
S
M
P
Laboratorio ricerca-azione:
Metodiche formative per adulti
L’ interruttore
“A” è OFF;
l’allarme,
indipendente
mente dallo
stato di “M”
e “P”, non si
A attiva.
CLICCA SU “A”
Problema di logica 2
S
L’ interruttore
“A” è ON;
“M” è ON,
l’allarme,
si attiva.
M
P
Laboratorio ricerca-azione:
Metodiche formative per adulti
A
CLICCA SU “P”
Problema di logica 2
S
L’ interruttore
“A” è ON;
“P” è ON,
l’allarme,
si attiva.
M
P
Laboratorio ricerca-azione:
Metodiche formative per adulti
A
CLICCA SU “M”
Problema di logica 2
S
M
L’ interruttore
“A” è ON;
“M” e “P”
sono ON,
l’allarme,
si attiva.
P
Laboratorio ricerca-azione:
Metodiche formative per adulti
A
Porta Logica “Not”
La porta logica Not è costituita da un ingresso e da una uscita; effettua operazione di negazione.
Ipotizzando “Y” l’ uscita e “A” l’ ingresso , l’ equazione algebrica è la successiva :
Y=Ā
La tabella della verità e il simbolo grafico sono i seguenti :
A
Y
A
0
1
1
0
Y=A
Si legge: Y uguale A negato
Questa porta può essere simulata mediante interruttori elettrici collegati come in figura:
R
Si deduce che la lampada è
accesa (Y=1) se l’interruttore è
aperto (A=0); viceversa se
l’interruttore è chiuso (A=1) la
lampada è spenta.
A
+
Y
E
Laboratorio ricerca-azione:
Metodiche formative per adulti
Porta Logica “Or”
La porta logica OR effettua la somma logica su due o più variabili di ingresso.
Nel caso di due variabili “A” e “B”, detta “ Y “ l’ uscita, l’ equazione algebrica è la
seguente:
Y=A+B
La tabella della verità e il suo simbolo grafico sono:
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
1
B
Y = A+B
A
Si legge: Y uguale A OR B
Questa porta può essere simulata mediante interruttori elettrici collegati come in figura:
Agli interruttori “A” e ”B”si
assegnano i valori 1 e 0 ossia
chiuso o aperto.
Di conseguenza la lampada
risulta accesa quando almeno
uno dei due interruttori è 1
ossia chiuso.
A
Interruttori
B
Generatore
Laboratorio ricerca-azione:
Metodiche formative per adulti
Lampada
(Y)
Porta Logica “Nand”
L’operatore NAND è derivato da un operatore AND seguito da un NOT. In questo caso l’ uscita Y è
0 quando le variabili d’ ingresso sono tutte a 1, l’ equazione algebrica e la seguente:
Y=A*B
La tabella della verità e il simbolo grafico sono:
Questa porta può essere simulata
mediante interruttori elettrici
collegati come in figura:
A
B
A
B
Y
0
0
1
0
1
1
1
0
1
1
1
0
A
Y=A*B
B
Si legge: Y uguale A AND B negato
Agli interruttori A e B si assegnano i
valori 1 e 0 ossia chiuso e aperto.
Di conseguenza la lampada risulta
spenta quando tutti e due gli
interruttori sono chiusi.
Laboratorio ricerca-azione:
Metodiche formative per adulti
Porta Logica “Xor”
L’operatore XOR è derivato dall’operatore OR. Si tratta di un circuito capace di
riconoscere se due ingressi sono diversi (uscita = 1) o sono uguali (uscita = 0).
Si può verificare che un operazione di OR esclusivo fornisce l’uscita a 1 se è dispari il
numero di 1 degli ingressi, fornisce invece 0 in uscita se i numero di 1 sono pari.
Il simbolo grafico e la tabella della verità sono:
A
B
Y=A + B
Si legge: Y uguale A OR ESCLUSIVO B
Laboratorio ricerca-azione:
Metodiche formative per adulti
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
0
Porta Logica “Nor”
L’operatore NOR è derivato da un operatore OR seguito da un NOT. L’uscita Y di una porta NOR
vale 1 solo se tutte le entrate sono nello stato logico 0. Nel caso di due variabili (A e B) la funzione
digitale si scrive:
Y=A+B
La tabella della verità e il simbolo grafico sono i seguenti:
A
B
Y
0
0
1
0
1
0
1
0
0
1
1
0
A
Y=A+B
B
Si legge: Y uguale A OR B negato
Questa porta può essere simulata mediante interruttori elettrici collegati come in figura:
A
B
Laboratorio ricerca-azione:
Metodiche formative per adulti
Porta Logica “Xnor”
L’operatore NOR esclusivo, indicato con XNOR, è derivato dallo XOR mediante
complementazione della variabile d’uscita. Si noti come il cerchietto nel simbolo
elettrico indica una complementazione.
A
B
Y
0
0
1
0
1
0
1
0
0
1
1
1
A
Y=A + B
B
Si legge: Y uguale A NOR ESCLUSIVO B
oppure A COINCIDENZA B
Il nome di coincidenza logica deriva dal fatto che l’uscita si porta a 1 solo se le entrate
coincidono nello stesso stato logico
Laboratorio ricerca-azione:
Metodiche formative per adulti
Porta Logica “And”
L’operatore AND agisce su due o più variabili di ingresso. L’ uscita Y è 1 quando le variabili
ingresso sono tutte a 1. Nel caso di due variabili di ingresso,
l’ equazione algebrica di uscita è la seguente:
Y=A*B
La tabella della verità e il simbolo grafico sono:
Questa porta può essere simulata
mediante interruttori elettrici
collegati come in figura:
Interruttori
A
B
A
B
Y
0
0
0
0
1
0
1
0
0
1
1
1
A
Y=A*B
B
Si legge: Y uguale A AND B
o anche A per B
Agli interruttori A e B si assegnano i
valori 1 e 0 ossia chiuso e aperto.
Di conseguenza la lampada risulta
accesa solo quando tutti e due gli
interruttori sono chiusi.
Laboratorio ricerca-azione:
Metodiche formative per adulti
d’