Àlgebra de Boole

L'àlgebra de Booletambé anomenadaàlgebra booleana,enmatemàtica,electrònica digitaliinformàticaés unaestructura algebraicaque esquematitza les operacions lògiques. És una branca de les matemàtiques amb propietats i regles similars, tot i que diferents, a les de l'àlgebraordinària.

Història

Fou creada perGeorge Boole(2 de novembre de 1815 a 8 de desembre de 1864) durant el primer quart del seglexix.Matemàtic anglèsautodidacta,va ser el primer a definir-la com a part d'un sistema lògic, inicialment en un petit fullet,The Mathematical Analysis of Logic,publicat el 1847, a resposta a una controvèrsia en curs entreAugustus De Morgani sir William Rowan Hamilton. Va ser un intent de fer servir les tècniques algebraiques per tractar expressions de lalògica proposicional.Més tard va ser estès com un llibre més important:An Investigation of the Laws of Thought on Which founded the Mathematical Theories of Logic and Probabilities(també conegut comAn Investigation of the Laws of Thoughto simplementThe Laws of Thought), publicat el 1854.

L'àlgebra de Boole té una característica especial: les seves variables només poden adoptar dos valors, tradicionalment denominatscertifals(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 conjuntBd'elements sobre els quals s'han definit dues operacions$+$('suma', 'o', 'unió', 'disjunció') i$\cdot$('producte', 'i', 'intersecció', 'conjunció') de manera que compleixen els 5postulatsde Huntington.

«	Les interpretacions respectives dels símbols 0 i 1 al sistema de lògica són Res i Univers.	»
—George Boole

Actualment, l'àlgebra de Boole s'aplica de manera generalitzada a l'àmbit del disseny electrònic.Claude Shannonva ser el primer a aplicar-la en el disseny de circuits de commutació elèctrica biestables, el 1948. Aquesta lògica es pot aplicar a dos camps:

• A l'anàlisi, perquè és una manera concreta de descriure com funcionen els circuits.
• Al disseny, ja que tenint unafunciós'aplica aquesta àlgebra per poder desenvolupar una implementació de la funció.

George Boole

Article principal:George Boole

George Boole (Lincoln,Regne Unit,1815 – Ballintemple, actualIrlanda,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. L'àlgebra de la lògica, com a sistema algebraic explícit que mostra l'estructura matemàtica subjacent de la lògica, va ser introduïda perGeorge Booleal seu llibreThe Mathematical Analysis of Logicde 1847. Amb ell s'inicia el desenvolupament de l'anomenadaàlgebra de la lògica.El 1849 va ser nomenat professor de matemàtiques del Queen's College, aCork,on va romandre la resta de la seva vida.

Definició

Donat un conjunt${\mathfrak {B}}$on s'han definit dues lleis de composició interna$\oplus,\odot$.L'estructura$({\mathfrak {B}},\oplus,\odot )$és un àlgebra de Boole si i només si$({\mathfrak {B}},\oplus,\odot )$és un Reticle distributiu,això és:

• $\odot$és distributiva respecte a$\oplus$:

$a\odot (b\oplus c)=(a\odot b)\oplus (a\odot c)$

• $\oplus$és distributiva respecte a$\odot$

$a\oplus (b\odot c)=(a\oplus b)\odot (a\oplus c)$

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\cdot {\overline {a}}=0\qquad a+{\overline {a}}=1\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 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

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$

Altres formes de notació de l'àlgebra de Boole

A Lògica binària se sol emprar lanotació$(\{0,1\},{\bar {}},+,\cdot )$,comú en la tecnologia digital, sent la forma més usual i la més còmoda de representar. Per exemple leslleis de De Morganes representen així:

${\overline {a+b}}={\bar {a}}\cdot {\bar {b}}\,$

${\overline {a\cdot b}}={\bar {a}}+{\bar {b}}\,$

Quan l'àlgebra de Boole s'empra en electrònica, sol emprar-se la mateixa denominació que per a les porta lògica AND(I), OR(O) i NOT(NO), ampliant-se de vegades amb X-OR (O exclusiva) i les seves negades NAND (NO I), NOR (NO O) i X-NOR (equivalència). Les variables es poden representar amb lletresmajúsculesominúscules,i poden prendre els valors {0, 1}.

Emprant aquesta notació les lleis de De Morgan es representen:

${\mbox{NOT }}(a{\mbox{ OR }}b)={\mbox{NOT }}a{\mbox{ AND }}{\mbox{NOT }}b\,$

${\mbox{NOT }}(a{\mbox{ AND }}b)={\mbox{NOT }}a{\mbox{ OR }}{\mbox{NOT }}b\,$

En la seva aplicació a la lògica es fa servir la notació$\land \lor \lnot$i les variables poden prendre els valors {F, V}, fals o veritable, equivalents a {0, 1 }

Amb la notació lògica les lleis de De Morgan serien així:

$\lnot {(a\lor b)}=\lnot {a}\land \lnot {b}\,$

$\lnot {(a\land b)}=\lnot {a}\lor \lnot {b}\,$

En el format deTeoria de conjuntsel Àlgebra de Boole toma l'aspecte:$({\mathcal {P}}(U),\sim,\cup,\cap )$

En aquesta notació les lleis de De Morgan serien així:

$\sim {(a\cup b)}=\;\sim {a}\;\cap \sim {b}\,$

$\sim {(a\cap b)}=\;\sim {a}\;\cup \sim {b}\,$

Altra forma en l'àlgebra de conjunts del Àlgebra de Boole, les lleis de De Morgan serien així:

${(A\cup B)}^{C}=\;{A}^{C}\cap {B}^{C}$

${(A\cap B)}^{C}=\;{A}^{C}\cup {B}^{C}$

Des del punt de vista pràctic hi ha una forma simplificada de representar expressions booleanes. S'utilitzenapòstrofs(') per indicar la negació, l'operació suma (+) es representa de la forma normal en àlgebra, i per al producte no s'empra cap signe, les variables es representen, normalment amb una lletra majúscula, la successió de dues variables indica el producte entre elles, no una variable nomenada amb dues lletres.

La representació de les lleis de De Morgan amb aquest sistema quedaria així, amb lletra minúscules per a les variables:

$(a+b)'=a'b'\,$

$(ab)'=a'+b'\,$

i així, emprant lletres majúscules per representar les variables:

$(A+B)'=A'B'\,$

$(AB)'=A'+B'\,$

Totes aquestes formes de representació són correctes, s'utilitzen de fet, i es poden veure en consultar bibliografia. La utilització d'una o altra notació no modifica l'àlgebra de Boole, només el seu aspecte, i depèn de la branca de les matemàtiques o la tecnologia en què s'estigui utilitzant per fer servir una o altra notació.

Estructures algebraiques que són àlgebra de Boole

Hi ha nombrosos casos de diferents anàlisis d'estructures algebraiques que corresponen a l'àlgebra de Boole, encara que en aparença són molt diferents, la seva estructura és la mateixa. En veurem alguns, amb el propòsit de fer palpable les similituds en l'estructura i els diferents àmbits d'aplicació i terminologia diferent per referir-se a les operacions o les variables.

Lògica binaria

Article principal:Lògica binaria

Article principal:Sistema digital

Article principal:Sistema binari

Article principal:Taula de veritat

Article principal:Lògica combinacional

Article principal:Formes canònica (àlgebra de Boole)

Article principal:Circuit de commutació

Una sắc rie de temes, aparentment tan diferents, té dues coses en comú, la lògica binària basada en elszerosi elsunsi l'àlgebra de Boole, possiblement la forma més coneguda d'aquesta àlgebra, que de vegades dona lloc a la interpretació que el àlgebra de Boole és la lògica binària exclusivament, així el conjunt${\mathfrak {B}}$en aquest cas està format per dos elements {0,1}, o {F, V}, o {no, sí }, dos valors contraposats, que són les dues possibles alternatives entre dues situacions possibles, aquí, sense pèrdua de la generalitat, prendrem el conjunt: {0,1} com ja hem dit:

${\mathfrak {B}}=\{0,1\}$

On:

$\varnothing =0$

$U=1\;$

• L'operació unària interna, que anomenaremnegació:

${\begin{array}{c|c}a&{\bar {a}}\\\hline 0&1\\1&0\end{array}}$

${\begin{array}{rrcl}{\bar {}}:&{\mathfrak {B}}&\to &{\mathfrak {B}}\\&a&\to &b={\bar {a}}\end{array}}$

L'operació unària interna negació, definim una aplicació que a cada elementade{0,1},li assigna unbde{0, 1}.

$\forall a\in {\mathfrak {B}}\,:\quad \exists!b\in {\mathfrak {B}}\;/\quad b={\bar {a}}$

Per a tot elementaa{0,1},es compleix que existeix un únicba{0,1},tal quebés la negació dea.Com es veu a la taula. Per a tot elementaa{0,1},es compleix que existeix un únicba{0, 1},tal quebés la negació dea.Com es veu a la taula.

• L'operació binària interna, que anomenaremsuma:

${\begin{array}{cc|c}a&b&a+b\\\hline 1&1&1\\1&0&1\\0&1&1\\0&0&0\\\end{array}}\quad \longleftrightarrow \quad {\begin{array}{c|cc}0&1&0\\1&1&1\\\hline +&1&0\\\end{array}}$

${\begin{array}{rrcl}+:&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a+b\end{array}}$

Amb l'operació suma definim una aplicació que, a cada parell ordenat (a,b) deBperB,li assigna uncdeB.

$\forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists!c\in {\mathfrak {B}}\;/\quad c=a+b$

Per a tot parell ordenat (a,b) aBperB,es compleix que existeix un úniccaB,tal quecés el resultat de sumaraambb.

• l'operació binària interna, que anomenaremproducte:

${\begin{array}{cc|c}a&b&a\cdot b\\\hline 1&1&1\\1&0&0\\0&1&0\\0&0&0\\\end{array}}\quad \longleftrightarrow \quad {\begin{array}{c|cc}0&0&0\\1&1&0\\\hline \cdot &1&0\\\end{array}}$

${\begin{array}{rrcl}\cdot:&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a\cdot b\end{array}}$

Amb l'operació producte definim una aplicació que, a cada parell ordenat (a,b) deBperB,li assigna uncdeB.

$\forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists!c\in {\mathfrak {B}}\;/\quad c=a\cdot b$

Per a tot parell ordenat (a,b) aBperB,es compleix que existeix un úniccaB,tal quecés el resultat del producteaib.Com es pot veure a la taula.

Axiomes

Així$(\{0,1\},{\bar {}},+,\cdot )$és unàlgebra de Booleal complir els següentsaxiomes:

• 1a: La lleiassociativade la suma:

$\forall a,b,c\in \{0,1\}:\;(a+b)+c=a+(b+c)$

• 1b: La llei associativa del producte:

$\forall a,b,c\in \{0,1\}:\;(a\cdot b)\cdot c=a\cdot (b\cdot c)$

• 2a: Existència de l'element neutreper a la suma:

$\forall a\in \{0,1\}:\;a+0=a$

• 2b: Existència de l'element neutre per al producte:

$\forall a\in \{0,1\}:\;a\cdot 1=a$

• 3a: La lleicommutativade la suma:

$\forall a,b\in \{0,1\}:\;a+b=b+a$

• 3b: La llei commutativa del producte:

$\forall a,b\in \{0,1\}:\;a\cdot b=b\cdot a$

• 4a: Lleidistributivade la suma respecte al producte:

$\forall a,b,c\in \{0,1\}:\;a+(b\cdot c)=(a+b)\cdot (a+c)$

• 4b: Llei distributiva del producte respecte a la suma:

$\forall a,b,c\in \{0,1\}:\;a\cdot (b+c)=(a\cdot b)+(a\cdot c)$

• 5a: Existeix element complementari per a la suma:

$\forall a\in \{0,1\};\;\exists {\bar {a}}\in \{0,1\}:\;a+{\bar {a}}=1$

• 5b: Existeix element complementari per al producte:

$\forall a\in \{0,1\};\;\exists {\bar {a}}\in \{0,1\}:\;a\cdot {\bar {a}}=0$

Per tant$(\{0,1\},{\bar {}},+,\cdot )$és àlgebra de Boole.

Teoremes fonamentals

A partir d'aquests axiomes es poden demostrar els següentsteoremes:

• 6a: Llei d'idempotència per a la suma:

$\forall a\in \{0,1\}:\;a+a=a$

• 6b: Llei d'idempotència per al producte:

$\forall a\in \{0,1\}:\;a\cdot a=a$

• 7a: Llei d'absorció per a la suma:

$\forall a\in \{0,1\}:\;a+1=1$

• 7b: Llei d'absorció per al producte:

$\forall a\in \{0,1\}:\;a\cdot 0=0$

• 8a: Llei d'identitat per a la suma:

$\forall a\in \{0,1\}:\;a+0=a$

• 8b: Llei d'identitat per al producte:

$\forall a\in \{0,1\}:\;a\cdot 1=a$

• 9: Llei d'involució:

$\forall a\in \{0,1\}:\;{\bar {\bar {a}}}=a$

• 10: Llei del complement:

${\bar {1}}=0$

${\bar {0}}=1$

• 11: Lleis de De Morgan:

$\forall a,b\in \{0,1\}:\;{\overline {a+b}}={\bar {a}}\cdot {\bar {b}}$

$\forall a,b\in \{0,1\}:\;{\overline {a\cdot b}}={\bar {a}}+{\bar {b}}$

Ordre a l'àlgebra de Boole

Partint de$(\{0,1\},{\bar {}},+,\cdot )$àlgebra de Boole, donades dos variables binaries:a,b,que compleixen alguna d'aquestes condicions:

$\left.{\begin{array}{l}a+b=b\\a\cdot b=a\\{\bar {a}}+b=1\\a\cdot {\bar {b}}=0\end{array}}\right\}\longrightarrow \quad a\leq b$

llavorsaes menor o igual queb.Donats els valors binaris0y1,podem veure:

1. $0+1=1$
2. $0\cdot 1=0$
3. ${\bar {0}}+1=1$
4. $0\cdot {\bar {1}}=0$

Aquestes quatre condicions són equivalents i el compliment d'una suposa el compliment de les altres, en aquest cas és senzill comprovar-les totes. Després podem dir que0antecedeix a1i ho denotem:

$0\leq 1$

Si a més sabem que0y1son valors diferents:

$\left.{\begin{array}{l}0\leq 1\\0\neq 1\end{array}}\right\}\longrightarrow \quad 0<1$

El valor binari0és menor que el valor binari1.

Àlgebra de Boole aplicada a la informàtica

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 delsllenguatges de programació,es tradueix enfalse(fals) otrue(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 comfalse,encara que també permet i equival al valor natural, enter i decimal (exacte) 0, així com la cadenafalse,inclosa la cadena “0”.

L'1 lògic En canvi, la resta de valors apunten al valor booleà d'afirmació, representat normalment com atrue,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 lafalse,en cas de ser la corresposta al 0 lògic).

Vegeu també

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