Tecnologie informatiche

Tecnologie informatiche

Algebra di Boole
Table of Contents
Introduzione......1
Variabili e loro valore......4
Operatori booleani......4
Operatori booleani fondamentali......4
L' operatore AND......4
L' operatore OR......6
L' operatore NOT......7
Proprietà fondamentali.......8
Relazioni di De Morgan:......8
Proprietà distributiva dell'AND rispetto all'OR:.....8
Proprietà distributiva dell'OR rispetto all'AND:......8
Assiomi fondamentali.....8
assioma dell'annullamento: ......8
A * 0 = 0......8
assioma del complemento:......8
assioma della negazione:....9
assioma della doppia negazione:.....9
Teoremi dell'assorbimento.......9
I Teorema dell'assorbimento:.......9
II Teorema dell'assorbimento:.........9
Algebra di Boole e circuiti digitali.........9
Pagina 1(fine)
Introduzione
Il matematico Boole ha formalizzato l'algebra che prende il suo nome allo scopo di
associare un'algebra alla logica (~ anni 1850). Per questo si comincia a parlare di logica
matematica. Boole ha voluto tradurre in algebra le proposizioni logiche. Cosa
intendiamo per proposizioni logiche? Si tratta di proposizioni semplici o composte che
ritornano un valore di verità (VERO o FALSO) in base ai valori di verità delle singole
proposizioni ed al significato degli operatori (e, oppure etc..) che le connettono. Il valore
di verità che ogni singola proposizione assume é stabilito dalla realtà che essa
rappresenta.
Facciamo degli esempi:
Roma é la capitale d'Italia
Questa é una proposizione logica perché risponde al valore di verità: VERO
23 é minore di 9
Questa é una proposizione logica perché risponde al valore di verità: FALSO
In base alla realtà che queste singole proposizioni rappresentano non ho alcun
dubbio su quale sia il valore di verità delle due proposizioni sopra riportate: una é vera e
l'altra é falsa.
Al contrario se ho l'espressione:
Le mele sono più gustose delle pere
non ho a che fare con una proposizione logica perché questa espressione dipende
dai gusti delle persone e quindi non può essere né sicuramente vera né sicuramente
falsa.
Possiamo anche avere proposizioni logiche composte, ad esempio:
Napoli é una città e la Campania é una regione
Si tratta di una proposizione logica perché entrambe le proposizioni sono
proposizioni logiche (tutte e due rispondono ad un valore di verità, in questo caso
pagina 2
VERO). Esse sono tenute insieme da un operatore che le connette di tipo “e”. In base al
significato dell'operatore “e” ed al valore di verità che rappresentano le due singole
proposizioni, questa espressione é VERA nella sua complessità.
Se invece scrivo:
Napoli é una regione oppure la Campania é una città
si tratta ancora di una proposizione logica perché composta da due proposizioni
logiche che rispondono al valore di verità FALSO, ma in questo caso l'intera
espressione é FALSA perché, pur avendo usato l'operatore “oppure”, nessuna delle
due espressioni é vera, per cui l'espressione nel suo insieme é ancora FALSA.
Infine se scrivo:
Napoli é una regione oppure la Campania é una regione
L' intera espressione é VERA perché, essendoci “oppure”, vuol dire che basta che
sia VERA solo una delle due proposizioni per poter rispondere VERO alla domanda
“Napoli é una regione oppure la Campania é una regione? In questo caso una delle
due espressioni é VERA (la Campania é una regione) per cui l'intera proposizione é
vera.
Alle proposizioni logiche Boole ha voluto applicare la matematica dando origine e
formalizzando l'algebra di Boole. Cosa significa? Significa che ha pensato di trattare le
proposizioni come delle variabili e le connessioni (“e”, “oppure”) come degli operatori
con i quali effettuare delle operazioni dopo avergli attribuito una definizione e delle
proprietà. Una volta definiti gli operatori si possono svolgere delle operazioni sulle
proposizioni (ora viste come variabili) come fate con la matematica che conoscete.
L' algebra di Boole nel complesso può essere applicata ad espressioni di vario
genere. Ad esempio anche i circuiti possono essere descritti utilizzando l'algebra
booleana.
L'algebra di Boole fornisce gli strumenti per elaborare ed interpretare tutto ciò che
racchiude un'informazione binaria; la cosa importante é che le espressioni che sono
rappresentate da variabili booleane rispondano solo alla domanda VERO o FALSO, 0 o
pagina 3
1, spento o acceso, aperto o chiuso, cioè ammettano solo due valori.
Ad esempio perché i circuiti logici possono essere descritti usando l'algebra
booleana? Perché i circuiti logici sono componenti hardware che manipolano
informazione binaria (basata solo su 0 e 1) in quanto il segnale passa o non passa, il
segnale é alto o basso, é 0 o é 1. Per questo motivo si può descrivere un circuito
digitale usando le variabili e gli operatori dell'algebra booleana che vengono usati per
rappresentare le porte logiche e le connessioni fra di esse. I circuiti di base dove passa
il segnale sono detti porte logiche (logical gates).
Variabili e loro valore
Cominciamo a descrivere l'algebra di Boole. La prima cosa importante da dire é che
il matematico ha associato due numeri alle espressioni di base della logica:
FALSO = 0
VERO = 1
Poteva essere fatta la scelta contraria, ma questa é stata la scelta e dobbiamo
accettarla come un dato di fatto.
Tutte le espressioni logiche di cui abbiamo parlato precedentemente possono
assumere solo due valori: 0 e 1. In algebra Booleana le variabili possono assumere solo
due valori: 0 e 1 e su queste variabili si possono fare delle operazioni, ma per fare delle
operazioni servono gli operatori.
Operatori booleani
Gli operatori dell'algebra booleana sono detti operatori booleani. Ora ne vediamo
alcuni. Ad essi daremo una definizione e ne descriveremo le proprietà specifiche.
Definiamo gli operatori booleani per mezzo delle tabelle della verità. La tabella della
verità riporta tutte le possibili combinazioni dei valori delle variabili ed il risultato che si
ottiene applicando un determinato operatore.
Pagina 4
Gli operatori booleani si dividono in due gruppi: operatori booleani fondamentali ed
operatori derivati. Questi ultimi vengono descritti come combinazione di quelli
fondamentali.
Operatori booleani fondamentali
L' operatore AND
L' operatore AND è chiamato anche “prodotto logico”. Vengono usati diversi simboli
per rappresentarlo:
*, ^, &
Come detto sopra lo definiamo usando la tabella della verità:
A B A*B
0 0 0
0 1 0
1 0 0
1 1 1
Possiamo leggere la precedente tabella nel seguente modo: date le variabili A e B,
nelle prime due colonne riportiamo tutte le possibili combinazioni di valori che tali
variabili possono assumere, nella terza colonna, A*B, é invece riportato il loro prodotto
logico. Per definizione l'operatore AND ritorna il valore 1 solo quando tutte le variabili
hanno valore 1, cosa vera anche per più di due variabili.
La tabella della verità riporta tutte le combinazioni possibili dei valori che le variabili
possono assumere: più variabili abbiamo e più aumentano le possibili combinazioni. In
particolare sia ha:
n variabili = 2n combinazioni
pagina 5
Facciamo un esempio: supponiamo di avere 3 variabili: A, B C, quale sarà la tabella
della verità che ci mostra il risultato di A*B*C?
A B C A*B*C
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
3 variabili, 23= 8 combinazioni possibili
Le proprietà dell'operatore AND sono le seguenti:
commutativa: A * B = B * A
associativa: A * (B * C) = (A * B) * C
A * A * A * A * A * A = A questa é una proprietà propria dell'algebra booleana
Per dimostrare quest'ultima proprietà basta fare la tabella della verità:
A A A*A
0 0 0
1 1 1
Il prodotto logico di due variabili uguali non é altro che la variabile stessa. Non serve
nemmeno avere 4 casi nella tabella della verità perché avendo a che fare sempre con
la stessa variabile i casi “0*1” non potranno mai verificarsi.
L' operatore OR
L' operatore OR è chiamato anche “somma logica”. Vengono usati diversi simboli per
Pagina 6
rappresentarlo:
+, V, |
Come detto sopra lo definiamo usando la tabella della verità:
A B A+B
0 0 0
0 1 1
1 0 1
1 1 1
La tabella si legge allo stesso modo della tabella per l'AND. Per definizione la somma
logica ritorna il valore 1 se almeno una delle variabile ha valore 1.
Se abbiamo tre variabili:
A B C A+B+C
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
3 variabili, 23= 8 combinazioni possibili
Le proprietà dell'operatore OR sono le seguenti:
commutativa: A + B = B + A
associativa: A + (B + C) = (A + B) + C
pagina 7
A + A + A + A + A + A = A questa é una proprietà propria dell'algebra booleana
Per capire il risultato basta fare la tabella della verità:
A A A+A
0 0 0
1 1 1
Come nel caso dell'AND non si possono introdurre 4 casi nella tabella della verità
perché avendo a che fare sempre con la stessa variabile i casi “0*1” non possono mai
verificarsi.
L' operatore NOT
L' operatore NOT é chiamato negazione e per indicarlo si usa generalmente un
trattino sopra la variabile. Ancora una volta per definirlo usiamo la tabella della verità:
A A'
0 1
1 0
L' apice “ ' “ é usato qui per indicare la negazione al posto del trattino.
La negazione é l'operatore che fa cambiare il valore alla variabile, se é vera diventa
falsa, se è falsa diventa vera.
Proprietà fondamentali
Relazioni di De Morgan:
(A + B)' = A' * B'
(A * B)' = A' + B'
Proprietà distributiva dell'AND rispetto all'OR:
pagina 8
A * (B + C) = (A * B) + (A * C)
Proprietà distributiva dell'OR rispetto all'AND:
A + (B * C) = (A + B) * (A + C)
Assiomi fondamentali
assioma dell'annullamento:
A * 0 = 0
A + 1 = 1
assioma del complemento:
A * A' = 0
A + A' = 1
assioma della negazione:
Se A = B allora A' = B'
assioma della doppia negazione:
(A')' = A
Teoremi dell'assorbimento
I Teorema dell'assorbimento:
A * (A + B) = A
Pagina 9
A + (A * B) = A
II Teorema dell'assorbimento:
A * (A' + B) = A * B
A + (A' * B) = A + B
Algebra di Boole e circuiti digitali
L'algebra di Boole può essere usata per interpretare i circuiti elettronici. Questi
sistemi sono caratterizzati da grandezze fisiche (segnali) che possono assumere solo
due valori (acceso/spento come nel caso degli interruttori, alto/basso come nel caso dei
circuiti logici). A questi due stati si può facilmente far corrispondere i valori 0 e 1.
Per quanto riguarda i circuiti logici sono stati proprio costruiti dei circuiti in grado di
effettuare le operazioni di AND, OR e NOT. Questi circuiti prendono il nome di porte
logiche e possono operare su più segnali di ingresso (più variabili booleane) e
producono un segnale in uscita. Essi rispondono a due valori di range di tensioni che
associamo ai valori logico di 0 e 1.
In un disegno di circuito logico questi operatori vengono rappresentati dai seguenti
simboli:
pagina 10
Questi circuiti effettuano le operazioni per i tre operatori che abbiamo sopra descritto
per mezzo delle tabelle della verità. Per capire meglio il loro funzionamento facciamo
una rappresentazione grafica di 2 segnali digitali in funzione del tempo (X(t) e Y(t)) e
delle operazioni AND, OR e NOT su di essi effettuati:
Quindi un'espressione booleana, altrimenti detta funzione booleana, può anche
essere rappresentata per mezzo di un circuito elettronico.
Ad esempio supponiamo di avere la seguente funzione:
F = X + (Y' * Z)