[successivo] [precedente] [inizio] [fine] [indice generale]

Capitolo 1. Algebra di Boole

Nell'algebra di Boole le variabili sono dette logiche o binarie.

Il secondo termine è motivato dal fatto che ogni variabile può assumere solo due stati:

F = Falso (False) = 0
V = Vero (True) = 1

Elettricamente 1 corrisponde ad un valore di tensione positivo (interruttore chiuso), 0 corrisponde ad un valore di tensione nullo (interruttore aperto).

1.1 Operatori logici fondamentali

Nell'algebra di Boole esistono tre operatori logici fondamentali:

Elencati in ordine di priorità.

Gli operatori si possono indicare anche nei seguenti modi:

NOT con "-" o con una sbarra sopra la variabile logica
AND con "." o con "^"
OR con "+" o con "v"

Di seguito vengono riportate le porte logiche e le tabelle di verità relative ai tre operatori fondamentali:

Figura 1.1.

boolean-3

A	-A
0	1
1	0

Figura 1.3.

boolean-1

A	B	A^B
0	0	0
0	1	0
1	0	0
1	1	1

Figura 1.5.

boolean-2

A	B	AvB
0	0	0
0	1	1
1	0	1
1	1	1

1.2 Espressioni logiche e equivalenza logica

Un'espressione logica è una espressione costruita con variabili logiche ed operatori logici.

Il valore di verità di un'espressione logica è costituito dai valori associati ad ogni combinazione di valori di verità delle variabili coinvolte (tali combinazioni si chiamano configurazioni in ingresso).

Il metodo più immediato per valutare un'espressione logica è quello di costruirne la tabella di verità.

La tabella di verità si costruisce con tante righe quante sono le configurazioni in ingresso, una colonna per ogni variabile coinvolta, e un numero variabile di ulteriori colonne, in base a quanti sono i "calcoli logici" da effettuare per arrivare al risultato finale.

Esempio: si valuti l'espressione:

-(A^-B)

(il ruolo delle parentesi è quello di alterare l'ordine di valutazione degli operatori logici, come nelle espressioni aritmetiche)

A	B	-B	A^-B	-(A^-B)
0	0	1	0	1
0	1	0	0	1
1	0	1	1	0
1	1	0	0	1

Si dice che due espressione logiche sono logicamente equivalenti se hanno gli stessi valori di verità in corrispondenza delle stesse configurazioni in ingresso.

Per indicare l'equivalenza useremo il simbolo "~" oppure il simbolo "=".

La verifica dell'equivalenza si effettua facilmente costruendo le tabelle di verità delle due espressioni e verificando che forniscono gli stessi valori di verità.

Ad esempio si verifichi:

(P^Q)v-P ~ -PvQ

P	Q	P^Q	-P	(P^Q)v-P
0	0	0	1	1
0	1	0	1	1
1	0	0	0	0
1	1	1	0	1

P	Q	-P	-PvQ
0	0	1	1
0	1	1	1
1	0	0	0
1	1	0	1

1.3 Leggi dell'algebra di Boole

Idempotenza:

PvP ~ P

Associativa:

(PvQ)vR ~ Pv(QvR)

(P^Q)^R ~ P^(Q^R)

Commutativa:

PvQ ~ QvP

P^Q ~ Q^P

Distributiva:

Pv(Q^R) ~ (PvQ)^(PvR)

P^(QvR) ~ (P^Q)v(P^R)

Doppia negazione:

- -P ~ P

Leggi di De Morgan:

-(PvQ) ~ -P^-Q

-(P^Q) ~ -Pv-Q

Dovrebbe essere possibile fare riferimento a questa pagina anche con il nome algebra_di_boole.html

[successivo] [precedente] [inizio] [fine] [indice generale]