Àlgebra de Boole

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'eina bàsica per l'anàlisi i disseny de circuits digitals és l'àlgebra Booleana. Aquesta àlgebra és un conjunt de regles matemàtiques (similars en alguns aspectes a l'àlgebra convencional), pero que tenen l'avantatge de pertànyer al comportament de circuits basats en dispositius de commutació (interruptors, relevadors, transistors, etc).

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 maneja valors lògics binaris.

D'altra banda, una àlgebra de Boole és un conjunt B d'elements sobre els quals s'han definit dues operacions $+$ ('suma', 'o', 'unió', 'disjunció') i $\cdot$ ('producte', 'i', 'intersecció', 'conjunció') de manera que compleixen els 5 postulats de Huntington.

George Boole

Lincoln, el Regne Unit, 1815 - Ballintemple, actual Irlanda, 1864) Matemàtic britànic. Procedia d'una família vinguda a menys i va haver de desestimar la idea de convertir-se en monjo en veure's obligat a mantenir els seus pares. Als setze anys ensenyava matemàtiques en un col·legi privat i més tard en va fundar un de propi. Als vint-i-quatre anys, després de la publicació del seu primer escrit, va poder ingressar a Cambridge, però va desestimar l'oferta, de nou a causa dels seus deures respecte a la seva família. El 1849 va ser nomenat professor de matemàtiques del Queen's College, a Cork, on va romandre la resta de la seva vida.

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 operació:

$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 distributiva:

$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$

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 els 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})=$

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

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

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

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

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

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

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

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

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

Altres propietats

Lleis d'absorció:

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

$a+(\overline{a}\cdot b) = a+b\qquad a\cdot (\overline{a}+b) = a\cdot b\qquad \forall a,b\in B$

Llei d'idempotència:

$a+a=a\quad a\cdot a= a\qquad \forall a\in B$

Llei d'involució:

$\overline{(\overline{a})} = a\qquad \forall a\in B$

Llei de De Morgan:

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

Propietat associativa:

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

Àlgebra de Boole aplicada a la informàtica

Es diu que una variable té un valor booleà quan, en general, la variable conté un 0 lògic i un 1 lògic. Això, en la majoria dels llenguatges de programació, es tradueix en false (fals) o true (verdader), respectivament. Una variable pot no ser del tipus booleà, i guardar valors que, en principi, no són booleans; ja que, globalment, els compiladors treballen amb aquests altres valors, numèrics normalment encara que també alguns permeten canvis des de, inclòs, caràcters, finalitzant en valor booleà.

El 0 lògic

El valor booleà de negació sol ser representada com false, encara que també permet i equival al valor natural, enter i decimal (exacte) 0, així com la cadena false, e inclòs la cadena “0”.

L'1 lògic

En canvi, la resta de valors apunten al valor booleà d’afirmació, representat normalment com true, ja que, per definició, el valor 1 es té quan no és 0. Qualsevol nombre diferent de zero es comporta com un 1 lògic, i el mateix passa amb quasi totes les cadenes (menys la false, en cas de ser la corresposta al 0 lògic).

Enllaços relacionats

• Lògica binària
• Taules de veritat
• Circuits de commutació
• Sistemes digitals
• Operació bit a bit

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Àlgebra de Boole