Àlgebra de Boole

De Viquipèdia

L' àlgebra de Boole és una branca de les matemàtiques amb propietats i regles similars, tot i que diferents, a les de l'àlgebra ordinària.

Fou creada per George Boole durant el primer quart del segle XIX. Pretenia explicar les lleis fonamentals d'aquelles operacions de la ment humana per les que es regeixen els raonaments. Posteriorment, aquesta àlgebra fou utilitzada per al disseny de circuits digitals.

L'àlgebra de Boole té una característica especial: les seves variables només poden adoptar dos valors, tradicionalment denominats cert i fals (normalment representats com a 1 i 0, respectivament). Així doncs, l'àlgebra de Boole manega valors lògics binaris.

Una àlgebra de Boole és un conjunt $B$ finit d'elements sobre els quals s'han definit les operacions $+$ ('suma', 'o', 'unió') i $\cdot$ ('producte', 'i', 'intersecció'), que compleixen els 5 postulats de Huntington.

[edita] Postulats de Hungtington

Primer postulat: les operacions són internes:

$a+b\in B\qquad a\cdot b\in B \qquad \forall a,b\in B$

Segon postulat: existeix un element neutre per a cada operció:

$a+0 = a\qquad a\cdot 1 = a \qquad \forall a\in B$

Tercer postulat: existeix l'element invers:

$a+\overline{a} = 1\qquad a\cdot \overline{a} = 0 \qquad \forall a\in B$

Quart postulat: existeix la propietat commutativa:

$a+b = b+a\qquad a\cdot b = b\cdot a \qquad \forall a,b\in B$

Cinquè postulat: existeix la propietat distibutiva:

$a\cdot (b+c) = (a\cdot b)+(a\cdot c)\qquad a+(b\cdot c) = (a+b)\cdot (a+c) \qquad \forall a,b,c\in B$

[edita] Funcions booleanes

Les funcions booleanes es poden representar explícitament en una taula de veritat com la següent, on observem el valor de la funció $f$ en funció de totes les combinacions de les variables $a$ , $b$ i $c$ :

a	b	c	f
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

A partir de la taula, podem calcular els minterms, que són els productes de $n$ literals que prenen el valor 1 quan la funció val 1. En el nostre cas, el nombre de literals és 3 (tenim tres variables), i els minterms són:

$m_1=\overline{a}\cdot\overline{b}\cdot c$

$m_3=\overline{a}\cdot b\cdot c$

$m_5=a\cdot \overline{b}\cdot c$

Sumant ls minterms obtenim la representació canònica en suma de productes. En el nostre cas:

$f=\overline{a}\cdot\overline{b}\cdot c+\overline{a}\cdot b\cdot c+a\cdot \overline{b}\cdot c$

Aplicant el quart postulat (propietat commutativa):

$f=\overline{a}\cdot c\cdot\overline{b}+\overline{a}\cdot c\cdot b+a\cdot \overline{b}\cdot c$

I el cinquè postulat (propietat distributiva):

$f=\overline{a}\cdot c\cdot (\overline{b}+b)+a\cdot \overline{b}\cdot c$

I el segon postulat (element invers):

$f=\overline{a}\cdot c+a\cdot \overline{b}\cdot c$

I altre cop el cinquè postulat (propietat distributiva):

$f=(\overline{a}+a\cdot \overline{b})\cdot c$

I finalment la llei d'absorció:

$f=(\overline{a}+\overline{b})\cdot c$

De forma que obtenim una expressió molt més senzilla de la funció que la taula de veritat: la funció és certa quan $a$ o $b$ són falsos i $c$ és cert. Alternativament, podem calcular els maxterms (sumes de $n$ literals que prenen el valor 0 quan la funció val 0) i multiplicant-los obtenim la representació canònica en producte de sumes. En el nostre cas i simplificant:

$f=(a+b+c)\cdot(a+\overline{b}+c)\cdot(\overline{a}+b+c)\cdot(\overline{a}+\overline{b}+c)\cdot(\overline{a}+\overline{b}+\overline{c})=$