Algebra di Boole
L’algebra di Boole è un formalismo che opera su
variabili (dette variabili booleane o
variabili
logiche o asserzioni) che possono assumere due
soli valori:
–Vero
–Falso
L’algebra booleana nasce come tentativo di
definire in forma algebrica processi di tipo
logico-deduttivo
Tuttavia, poiché di fatto l’algebra di Boole
opera su variabili binarie, i suoi operatori
possono essere inclusi fra gli operatori
dell’algebra binaria.
Algebra di Boole
Sulle variabili booleane è possibile definire delle
funzioni (dette funzioni booleane o logiche) e
anch’esse possono assumere i due soli valori
vero e falso.
Le funzioni booleane possono essere definite
tramite le tabelle di verità. Una tabella di verità
di una funzione di N variabili ha 2N righe.
X1
X2
X3
F
0
0
0
1
1
0
0
0
0
1
0
0
0
0
1
0
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
1
Operatori ed Espressioni Booleane
L’algebra di Boole si basa su un insieme di
operatori:
– AND (indicato in genere dal simbolo × )
– OR (indicato in genere dal simbolo + )
– NOT (indicato in genere dal simbolo - )
– XOR (indicato in genere dal simbolo  )
– NAND (indicato in genere dal simbolo  )
– NOR (indicato in genere dal simbolo  )
In realtà, qualunque funzione booleana può
essere realizzata utilizzando 2 soli operatori:
AND e NOT oppure OR e NOT
NOT - AND - OR
X
0
1
NOT
1
0
X1
X2
AND
0
0
0
1
0
0
0
1
0
1
1
1
X1
0
1
0
1
X2
0
0
1
1
OR
0
1
1
1
Il risultato è la negazione
della variabile
Il risultato è 1 (Vero) se
entrambe le variabili hanno
valore 1
Il risultato è 1 (Vero) se almeno
una delle variabili ha valore 1
XOR - NAND - NOR
X1
X2
XOR
0
0
0
1
0
1
0
1
1
1
1
0
X1
X2
NAND
0
0
1
1
0
1
0
1
1
1
1
0
X1
X2
NOR
0
0
1
1
0
0
0
1
0
1
1
0
Il risultato è 1 (Vero) se una
sola delle due variabili ha valore
1
NAND (X1, X2) = NOT (AND (X1,X2))
NOR (X1, X2) = NOT (OR (X1, X2))
Interpretazione logica degli operatori
Gli operatori booleani possono essere utilizzati per
rappresentare regole deduttive di tipo logico.
Le variabili possono rappresentare dei “fatti”
(evidenze) che possono essere dedotte le une dalle
altre.
Es.
A = squame;
C=AxB
B = nuota;
C = pesce;
se ha le squame e nuota, allora è un pesce
( e viceversa ).
In questo caso il segno = significa “ se e solo se ”.
A -> B (se A è vero allora B è vero) vale solo in una
direzione.
Interpretazione logica degli operatori
Se si ha una operazione del tipo:
A*B
(* indica una generica operazione),
il risultato è vero se:
*
condizione
OR
A o B (o entrambe) sono vere
AND
sia A che B sono vere
XOR
A o B (ma non entrambe) sono vere
Funzioni logiche e calcolatori
Il calcolatore, oltre alle funzioni matematiche,
può eseguire anche funzioni logiche che
permettono di fare elaborazioni che operano
anche sui singoli bit. Si esegue l’operazione fra
bit in posizioni corrispondenti.
Es.
A = 11101001
AxB
B = 01001110
11101001
01001110
01001000
Funzioni logiche e calcolatori
Alle funzioni booleane si aggiungono anche altre
funzioni che possono essere utili nella
manipolazione di singoli bit.
Importante è l’operazione di shift (scorrimento)
Shift a destra (right shift)
11100110 ---> 01110011
Shift a sinistra (left shift)
11100110 ---> 111001100
Lo shift può anche fare scorrere il numero di più
di una posizione.
Funzioni logiche e calcolatori
Se ho un byte col seguente contenuto:
11100110
e voglio il valore del bit più significativo
posso fare un AND con 10000000
11100110
10000000
10000000
seguito da uno shift a destra di 7 posizioni
00000001 ---> Il bit più significativo è 1