Àlgebra de Boole

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 quals es regeixen els raonaments. Posteriorment, aquesta àlgebra fou utilitzada per al disseny de circuits digitals. L'eina bàsica per a l'anàlisi i el 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), però que tenen l'avantatge de pertànyer al comportament de circuits basats en dispositius de commutació (interruptors, relés, 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[modifica | modifica el codi]

George Boole (Lincoln, el Regne Unit, 1815 - Ballintemple, actual Irlanda, 1864) fou un matemàtic britànic. Procedia d'una família vinguda a menys i va haver de descartar la idea de convertir-se en monjo en veure's obligat a mantenir els seus pares. A setze anys ensenyava matemàtiques en un col·legi privat i més tard en va fundar un de propi. A 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 familiars. 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[modifica | modifica el codi]

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[modifica | modifica el codi]

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 termes mínims, 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 termes mínims 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 termes mínims, 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 altra vegada 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 manera 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 termes màxims (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[modifica | modifica el codi]

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[modifica | modifica el codi]

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 fins i tot des de 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, inclosa la cadena “0”.

Zero

L'1 lògic

En canvi, la resta de valors apunten al valor booleà d’afirmació, representat normalment com a 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).

U

Enllaços relacionats[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Àlgebra de Boole Modifica l'enllaç a Wikidata