Algebra di Boole

Note

L’algebra di Boole è un sistema algebrico identificato dalla quintupla:

$$(B,+,\ast ,O,I)$$

Dove $B$ è l’insieme di specificazione, $+$ e $\ast$ sono operatori binari, e $O,I\in B$ sono elementi speciali.

Sistemi algebrici

Definiamo un sistema algebrico come una combinazione di un’insieme, e di una o più operazioni.

Operazioni

Definiamo un operazione $\alpha$ sull’insieme $S=\{s_1,s_2,\cdots \}$ come una funzione:

$$\alpha :(S\times S)\to S$$

Le proprietà dei due operatori $+$ e $\ast$ sono dedotte dai seguenti assiomi:

• La somma e il prodotto sono commutativi $\forall x,y\in B$.
• La somma è distributiva rispetto al prodotto, e il prodotto è distributivo rispetto alla somma.
• $O$ è l’elemento neutro della somma, mentre $I$ è l’elemento neutro del prodotto.
• Ogni elemento $x\in B$ ammette un elemento $x^{\prime }\in B$ tale che $(x+x^{\prime })=I$ e $(x\ast x^{\prime })=O$.

Algebra di commutazione

Note

L’algebra Booleana a due valori, anche detta algebra di commutazione è definita da:

$$(\{0,1\},+,\ast ,\sim ,0,1)$$

Cioè un estensione dell’algebra di Boole con $B=\{0,1\}$.

Un’espressione Booleana $E$ è definita in modo induttivo come parola composta da operatori booleani, parentesi, costanti e letterali nel modo seguente:

• Sia gli elementi di $B$, chiamati costanti, che i letterali $x,y,z,\cdots$, sono espressioni booleane.
• Se $E_1$ e $E_2$ sono espressioni booleane, anche $E_1+E_2$, $E_1\ast E_2$ e $\sim E_1$ lo sono.
• Non esistono altre espressioni booleane oltre a quelle che possono essere generate da un numero finito di applicazioni delle due regole precedenti.

Proprietà e principio di dualità

Proprietà	Somma	Prodotto
Associativa	$a+(b+c)=(a+b)+c$	$a\ast (b\ast c)=(a\ast b)\ast c$
Distributiva	$a\ast (b+c)=a\ast b+a\ast c$	$a+(b\ast c)=(a+b)\ast (a+c)$
Idempotenza	$a+a=a$	$a\ast a=a$
Elemento neutro	$a+1=1$ e $a+0=a$	$a\ast 0=0$ e $a\ast 1=a$
Assorbimento	$a+(a\ast b)=a$	$a\ast (a+b)=a$
Leggi di De Morgan	$(a+b{)}^{\prime }=a^{\prime }\ast b^{\prime }$	$(a\ast b{)}^{\prime }=a^{\prime }+b^{\prime }$
Consenso	$a\ast b+a^{\prime }\ast c+b\ast c=a\ast b+a^{\prime }\ast c$	$(a+b)\ast (a^{\prime }+c)\ast (b+c)=(a+b)\ast (a^{\prime }+c)$

Per il principio di dualità ogni identità deducibile dai postulati dell’algebra di Boole è trasformata in un altra identità se:

• Ogni somma è sostituita da un prodotto, e viceversa.
• Ogni elemento identità $0$ è sostituito da un elemento identità $1$, e viceversa.

Funzione di commutazione

Definiamo una funzione di commutazione a $n$ variabili $f(x_0,\cdots ,x_{n-1})$ come una funzione:

$$f:\{0,1{\}}^n\to \{0,1\}$$

Queste funzioni possono essere rappresentate comodamente utilizzando una tabella della funzione o una tabella della verità.

Si ha che una funzione booleana di $n$ variabili può essere espressa da un’espressione booleana di $n$ variabili $E$, e quindi dalle proprietà dell’algebra di commutazione si ha che:

• Possono essere utilizzate per manipolare un’espressione booleana ed ottenerne una equivalente.
• Due espressioni booleane $E_1$ e $E_2$ sono equivalenti se e solo se sono riconducibili alla stessa funzione booleana.

Ad un’espressione $E$ di $n$ variabili corrisponde un’unica funzione $f$ di $n$ variabili, e viceversa.

Si ha che qualunque funzione logica può realizzarsi usando un insieme completo di operatori elementari.

Data un’espressione di una funzione booleana l’algebra di commutazione permette di manipolarla per ottenere un’espressione equivalente, ma di forma diversa, eventualmente con caratteristiche, meglio rispondenti a particolari requisiti.

Si ha che l’applicazione delle trasformazioni algebriche non permette di identificare una procedura sistematica. Di conseguenza non è possibile identificare un algoritmo e non è possibile sapere se un’espressione è quella minima.

Forme canoniche

Prima forma canonica

La prima forma canonica, anche detta SoP, ha come espressione generale:

$$(x_1^{\prime }\cdots x_n^{\prime })\ast f(0,\cdots ,0)+(x_1^{\prime }\cdots x_n)\ast f(0,\cdots ,1)+\cdots +(x_1\cdots x_n)\ast f(1,\cdots ,1)$$

Definiamo i mintermini della funzione $f$ come:

$$(x_1^{\prime }\cdots x_n^{\prime }),(x_1^{\prime }\cdots x_n),\cdots ,(x_1\cdots x_n)$$

Prima forma canonica

La seconda forma canonica, anche detta PoS, ha come espressione generale:

$$((x_1^{\prime }+\cdots +x_n^{\prime })+f(0,\cdots ,0))\ast ((x_1^{\prime }+\cdots +x_n)+f(0,\cdots ,1))\ast \cdots \ast ((x_1+\cdots +x_n)+f(1,\cdots ,1))$$

Definiamo i maxtermini della funzione $f$ come:

$$(x_1^{\prime }+\cdots +x_n^{\prime }),(x_1^{\prime }+\cdots +x_n),\cdots ,(x_1+\cdots +x_n)$$

Teorema di espansione di Shannon

Sia $f:B^n\to B$ una funzione booleana. Per ogni $(x_1,x_2,\cdots ,x_n)$ in $B^n$ si ha:

$$\begin{array}{rl}f(x_1,x_2,\cdots ,x_n)& =x_1^{\prime }\ast f_{x_1^{\prime }}+x_1\ast f_{x_1}\\ & =x_2^{\prime }\ast f_{x_2^{\prime }}+x_2\ast f_{x_2}\\ & =\cdots \\ & =(x_1^{\prime }+f_{x_1})\ast (x_1+f_{x_1^{\prime }})\\ & =(x_2^{\prime }+f_{x_2})\ast (x_2+f_{x_2^{\prime }})\\ & =\cdots \end{array}$$

Questo teorema può essere utilizzato anche su espressioni Booleane.