Algebra di Boole

L’algebra di Boole viene introdotta da George Boole con il fine di svolgere conti algebrici per risolvere affermazioni logiche.

Definizione

L’algebra di Boole è una struttura algebrica del seguente tipo:

$$\mathcal{B}=⟨A,+,\cdot ,{}^{\prime },0,1⟩$$

Gli elementi che sono dentro la tupla sono i seguenti:

• $A$: L’insieme degli elementi su cui svolgiamo i calcoli algebrici, viene chiamato supporto.
• $+$: operatore booleano di disgiunzione, detto OR.
• $\cdot$: operatore booleano di congiunzione, detto AND.
• ${}^{\prime }$: operatore unario di complementazione, detto NOT.
• $0$: elemento neutro rispetto al $+$
• $1$: elemento neutro rispetto al $\cdot$

Per far valere i calcoli booleani nella seguente tupla, essa deve rispettare i postulati di Huntington.

Postulati di Huntington

1. Disgiunzione e congiunzione sono commutative.
2. Esiste l’elemento neutro rispetto al $+$ e un altro elemento neutro rispetto al $\cdot$
3. Le operazioni binarie sono distributive.
4. Per ogni elemento $a$ esiste, ed è unico, un elemento $a^{\prime }$

Principio di dualità

Ogni proposizione derivata dagli assiomi di Huntington di un’algebra di Boole rimane valida scambiando ovunque tra di loro le operazioni $+$ e $\cdot$ e gli elementi neutri $0$ ed $1$.

Proprietà dell’algebra di Boole

Proprietà	Esempi
Associativa	$x+(y+z)=(x+y)+z$ $x\cdot (y\cdot z)=(x\cdot y)\cdot z$
Idempotenza	$x+x=x$ $x\cdot x=x$
Elemento nullo	$x+1=1$ $x\cdot 0=0$
Unicità del complemento	$x^{\prime }$ è unico
Assorbimento	$x+x\cdot y=x$ $x\cdot (x+y)=x$
Semplificazione	$x+x^{\prime }\cdot y=x+y$ $x\cdot (x^{\prime }+y)=x\cdot y$
Involuzione	$(x^{\prime }{)}^{\prime }=x$
Leggi di De Morgan	$(x+y{)}^{\prime }=x^{\prime }\cdot y^{\prime }$ $(x\cdot y{)}^{\prime }=x^{\prime }+y^{\prime }$
Consenso	$x\cdot y+x^{\prime }\cdot z+y\cdot z=x\cdot y+x^{\prime }\cdot z$ $(x+y)\cdot (x^{\prime }+z)\cdot (y+z)=(x+y)\cdot (x^{\prime }+z)$