boole

L'algebra di Boole

L'algebra di Boole tratta di un modello di algebra nel quale esistono solo i numeri 1 e 0 (senza nessun valore intermedio) e le operazioni NOT, AND, OR in ordine di prioritù, da priorità alta a priorità bassa. Talvolta, al posto di 1 e 0 vengono utilizzati T (True, vero in inglese) e F (False, falso in inglese) per significare che 1 e 0 non rappresentano numeri nel senso comune del termine (mi scusino i matematici per questa affermazione semplicistica), ma solamente uno stato, una cosa che esiste oppure non esiste: T e F possono sostituire completamente, senza nessun limite, 1 e 0 (e lo potrebbero fare, per esempio, una patata e una carota...). L'Algebra di Boole richiede e definisce le seguenti proprieta' (solo se sono soddisfatte tutte si puo' parlare di Algebra di Boole):

poniamo
* per rappresentare la funzione AND
+ per rappresentare la funzione OR
! per rappresentare la funzione NOT
PROPRIETÀ DELL'ASSORBIMENTO:
a * ( a + b ) == a
a + ( a * b ) == a

PROPRIETÀ COMMUTATIVA:
a * b == b * a
a + b == b + a
PROPRIETÀ DISTRIBUTIVA:
a * ( b + c ) == ( a * b ) + ( a * c )
a + ( b * c ) == ( a + b ) * ( a + c )

PROPRIETÀ ASSOCIATIVA:
a * ( b * c ) == ( a * b ) * c
a + ( b + c ) == ( a + b ) + c
ALTRE PROPRIETÀ:
a * 0 == 0
a * !a == 0
a + 1 == 1
a + !a == 1

IDEMPOTENZA:
a * a == a
a + a == a

PRINCIPIO DI DUALITÀ:
Se una uguaglianza è corretta, è corretta ed uguale anche l'uguaglianza ottenuta sostituendo da tutte e due le parti 1 con 0 e 0 con 1, AND con OR, OR con AND. La seconda si chiama duale della prima. Da qui deriva il concetto di NOT applicato ad una formula (e non semplicemente ad una variabile o costante).

Cerchiamo di comprendere i concetti che stanno alla base di questi operatori attraverso degli esempi e delle simulazioni:

NB: negli esempi che seguono una lettera sovrastata da un tratto - o da un ~ come ad es: Ã si legge NON A.
nei diagrammi di Carrol (Lewis Carrol autore del famoso libro "Alice nel paese delle meraviglie") la parte in rosso indica la condizione di verità. Nelle porte logiche la casella spuntata indica VERO, quella vuota FALSO.

NOT - NON (NEGAZIONE)
Se l' ingresso è VERO l' uscita è FALSA e viceversa

Porta logica funzionante

A	Ã
V	F
F	V

NOT
Rappresentazione insiemistica

NOT
Diagramma di Carrol

AND - E
Restituisce la condizione di verità solo se tutti i suoi ingerssi sono veri.
Equivale al prodotto logico. Infatti: 1x1=1 1x0=0 0x1=0 0x0=0

Porta logica funzionante

A	B	A and B
V	V	V
V	F	F
F	V	F
F	F	F

AND
Rappresentazione insiemistica

AND
Diagramma di Carrol

OR - VEL - O ( INCLUSIVO)
Restituisce la condizione di verità se almeno uno dei suoi ingerssi è vero
Equivale alla somma logica. Infatti: 1+1=10 1+0=1 0+1=1 0+0=0

Porta logica funzionante

A	B	A or B
V	V	V
V	F	V
F	V	V
F	F	F

Rappresentazione insiemistica

Diagramma di Carrol

XOR - AUT - O (ESCLUSIVO)
Restituisce la condizione di verità se solo uno dei suoi ingerssi è vero.
Equivale alla somma logica senza riporto. Infatti: 1+1=10 1+0=1 0+1=1 0+0=0

Porta logica funzionante

A	B	A xor B
V	V	F
V	F	V
F	V	V
F	F	F

XOR
Rappresentazione insiemistica

XOR
Diagramma di Carrol

poniamo * per rappresentare la funzione AND + per rappresentare la funzione OR ! per rappresentare la funzione NOT	PROPRIETÀ DELL'ASSORBIMENTO: a * ( a + b ) == a a + ( a * b ) == a
PROPRIETÀ COMMUTATIVA: a * b == b * a a + b == b + a	PROPRIETÀ DISTRIBUTIVA: a * ( b + c ) == ( a * b ) + ( a * c ) a + ( b * c ) == ( a + b ) * ( a + c )
PROPRIETÀ ASSOCIATIVA: a * ( b * c ) == ( a * b ) * c a + ( b + c ) == ( a + b ) + c	ALTRE PROPRIETÀ: a * 0 == 0 a * !a == 0 a + 1 == 1 a + !a == 1
IDEMPOTENZA: a * a == a a + a == a
PRINCIPIO DI DUALITÀ: Se una uguaglianza è corretta, è corretta ed uguale anche l'uguaglianza ottenuta sostituendo da tutte e due le parti 1 con 0 e 0 con 1, AND con OR, OR con AND. La seconda si chiama duale della prima. Da qui deriva il concetto di NOT applicato ad una formula (e non semplicemente ad una variabile o costante).