1.7.3 - Proprietà delle operazioni fondamentali

Operazioni con $n$ predicati

Nella lezione precedente abbiamo introdotto le operazioni fondamentali dell'algebra booleana. In particolare, abbiamo visto come le operazioni di somma e prodotto logici siano di tipo binario, ovvero definite per una coppia di predicati, mentre la negazione sia unaria.

Nonostante questo, è possibile estendere le considerazioni fatte per una logica a due variabili ad una ad $n$ variabili. Prendiamo, ad esempio, il seguente predicato composto:

la palla è tonda AND la palla è verde AND la palla è nella scatola

Questo predicato altro non è se un prodotto logico tra tre predicati semplici e, proprio come nel caso più semplice, sarà vero se e solo se tutti i predicati sono veri.

Si può ragionare allo stesso modo per la somma logica. Immaginiamo di avere il predicato composto:

la palla è tonda OR la palla è verde OR la palla è nella scatola

In questo caso, il predicato composto sarà sempre vero, a meno che tutti i singoli predicati non siano falsi.

A questo punto è possibile generalizzare la somma ed il prodotto logico come segue. Indicando con $+$ l'operazione di somma logica, e con $\times$ quella di prodotto logico, varranno le seguenti regole.

Somma logica di $n$ variabili indipendenti

Date $n$ variabili binarie indipendenti, la loro somma logica è:

$$x_1+x_2+\dots +x_n=\{\begin{array}{lll}1,& \mathrm{\exists }{x}_i=1,& i\in 1,\dots ,n\\ 0,& \mathrm{\nexists }{x}_i=1,& i\in 1,\dots ,n\end{array}$$

In altre parole, il risultato della somma logica di $n$ variabili è pari ad $1$ se almeno una delle $n$ variabili è anch'essa pari ad $1$.

Prodotto logico di $n$ variabili indipendenti

Date $n$ variabili binarie indipendenti, il loro prodotto logico è:

$$x_1\times x_2\times \dots \times x_n=\{\begin{array}{lll}0,& \mathrm{\exists }{x}_i=0,& i\in 1,\dots ,n\\ 1,& x_1=x_2=\dots =x_n\end{array}$$

Proprietà delle operazioni logiche fondamentali

Alle tre operazioni logiche fondamentali sono associate alcune proprietà fondamentali, che richiamano le equivalenti proprietà aritmetiche. In particolare, alle operazioni di $AND$ ed $OR$ sono associate tre diverse proprietà che, come vedremo, sono concettualmente analoghe a quelle definite nell'aritmetica classica.

Proprietà commutativa

La prima è la proprietà commutativa, per la quale il risultato di somma e prodotto logico rimangono invariati cambiando l'ordine dei singoli predicati. Quindi:

la palla è tonda AND la palla è verde

equivale a:

la palla è verde AND la palla è tonda

così come:

la palla è tonda OR la palla è verde

equivale a:

la palla è verde OR la palla è tonda

Formalmente, dati due predicati $p_1,p_2$:

$$\begin{array}{r}OR\iff p_1+p_2=p_2+p_1\\ AND\iff p_1\times p_2=p_2\times p_1\end{array}$$

Tabelle della verità

Per dimostrare la proprietà commutativa, possiamo usare le tabelle della verità. Per l'operazione di $AND$:

$p_1$	$p_2$	$p_1\times p_2$	$p_2\times p_1$
0	0	0	0
0	1	0	0
1	0	0	0
1	1	1	1

Per l'operazione di $OR$:

$p_1$	$p_2$	$p_1+p_2$	$p_2+p_1$
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	1

Proprietà associativa

La seconda proprietà notevole è quella associativa, per la quale è possibile associare un prodotto o una somma logica mediante relazioni di precedenza senza per questo variare il risultato atteso. In altri termini, immaginiamo di avere i seguenti predicati:

la palla è tonda AND la palla è verde AND la palla è nella scatola

Il valore di verità di questo predicato sarà equivalente a quello dei seguenti:

(la palla è tonda AND la palla è verde) AND la palla è nella scatola

In pratica, nel secondo predicato, verificheremo dapprima che la palla sia tonda e verde, e poi che sia nella scatola, laddove nel primo verificheremo le tre condizioni contemporaneamente. Stesse considerazioni valgono per le operazioni di somma logica.

Causalità delle verifiche

Da notare come questa formulazione abbia come ipotesi "forte" il fatto che non vi sia alcuna relazione di causalità tra le proprietà associate. In pratica, si suppone che il fatto che si verifichi in primis che la palla sia tonda e verde non abbia alcuna influenza o causalità sul fatto che la palla sia nella scatola.

Formalmente, dati $3$ predicati del tipo $p_1,p_2,p_3$:

$$\begin{array}{r}OR\iff p_1+p_2+p_3=p_1+(p_2+p_3)\\ AND\iff p_1\times p_2\times p_3=p_1\times (p_2\times p_3)\end{array}$$

Tabelle della verità

Usiamo le tabelle della verità per verificare la proprietà associativa. Indicando $p_{or}$ il predicato originario avremo per la $AND$:

$p_1$	$p_2$	$p_3$	$p_2\times p_3$	$p_1\times (p_2\times p_3)$	$p_{or}$
0	0	0	0	0	0
1	0	0	0	0	0
0	1	0	0	0	0
1	1	0	0	0	0
0	0	1	0	0	0
1	0	1	0	0	0
0	1	1	0	0	0
1	1	1	1	1	1

Mentre per la $OR$:

$p_1$	$p_2$	$p_3$	$p_2+p_3$	$p_1+(p_2+p_3)$	$p_{or}$
0	0	0	0	0	0
1	0	0	0	1	1
0	1	0	1	1	1
1	1	0	1	1	1
0	0	1	1	1	1
1	0	1	1	1	1
0	1	1	1	1	1
1	1	1	1	1	1

Proprietà distributiva

L'ultima proprietà notevole è quella distributiva del prodotto rispetto alla somma. Anche questa proprietà richiama la corrispondente proprietà aritmetica, e può essere esplicitata come segue.

Vogliamo valutare che:

la palla è tonda AND la palla è verde OR la palla è tonda AND la palla è nella scatola

In pratica, vorremo valutare se la palla sia tonda e verde (primo prodotto logico) oppure se sia tonda e nella scatola (secondo prodotto logico). La proprietà distributiva ci dice che il precedente predicato equivale a scrivere:

la palla è tonda AND (la palla è verde OR la palla è nella scatola)

Staremo quindi valutando se la palla è verde oppure nella scatola e, conseguentemente, se sia tonda. Formalmente, quindi, dati tre predicati $p_1,p_2,p_3$:

$$p_1\times p_2+p_1\times p_3=p_1\times (p_2+p_3)$$

Tabelle della verità

Anche in questo caso, le tabelle della verità ci permettono di confermare l'eguaglianza. Indicando $p_{or}$ il predicato originario, avremo:

$p_1$	$p_2$	$p_3$	$p_1\times p_2$	$p_1\times p_3$	$p_{or}$
0	0	0	0	0	0
1	0	0	0	0	0
0	1	0	0	0	0
1	1	0	1	0	1
0	0	1	0	0	0
1	0	1	0	1	1
0	1	1	0	0	0
1	1	1	1	1	1

Se adesso indichiamo con $p_d$ il predicato associato alla proprietà distributiva, avremo:

$p_1$	$p_2$	$p_3$	$p_2+p_3$	$p_d$
0	0	0	0	0
1	0	0	0	0
0	1	0	1	0
1	1	0	1	1
0	0	1	1	0
1	0	1	1	1
0	1	1	1	0
1	1	1	1	1

Identità dell'operatore $NOT$

Chiudiamo questa carrellata illustrando brevemente tre delle identità che valgono per l'operatore $NOT$.

Partiamo dalla seguente espressione:

la palla è tonda OR la palla non è tonda

In questo caso, vediamo come il precedente predicato composto sia sempre vero. Ciò è legato al fatto che i due predicati semplici si complementano andando, se considerati congiuntamente, a coprire la totalità dei possibili casi esperibili nel mondo reale. Volendo essere meno formali, quindi, potremmo dire che il precedente predicato esprime il concetto al fatto che la palla o è tonda, o non lo è.

Formalmente, quindi, potremo scriivere:

$$p+\bar{p}=1$$

Consideriamo adesso la seguente espressione:

la palla è tonda AND la palla non è tonda

Estendendo il ragionamento precedente, questo predicato non potrà mai essere vero, perché implicherebbe che la palla sia contestualmente tonda e non tonda, il che, ovviamente, non avviene nella realtà. Formalmente:

$$p+\bar{p}=0$$

Infine, consideriamo l'espressione:

NOT (NOT la palla è tonda)

In pratica, l'espressione all'interno delle parentesi nega il predicato, implicando che la palla non sia tonda. Tuttavia, il $NOT$ esterno nega la negazione, il che ovviamente ci riporta al caso iniziale. Formalmente:

$$\overline{\stackrel{―}{x}}=x$$

Queste sono le basi per l'interpretazione dei principi dell'algebra booleana; nella prossima lezione andremo ad approfondire alcune leggi notevoli.