Àlgebra de Boole

L'àlgebra de Boole també anomenada àlgebra booleana, en matemàtica, electrònica digital i informàtica és una estructura algebraica que 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'àlgebra ordinària.^[1][2]

Fou creada per George Boole (2 de novembre de 1815 a 8 de desembre de 1864) durant el primer quart del segle xix. Matemàtic anglès autodidacta, 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 entre Augustus De Morgan i sir William Rowan Hamilton. Va ser un intent de fer servir les tècniques algebraiques per tractar expressions de la lò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 com An Investigation of the Laws of Thought o simplement The 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 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 ${\displaystyle +}$ ('suma', 'o', 'unió', 'disjunció') i ${\displaystyle \cdot }$ ('producte', 'i', 'intersecció', 'conjunció') de manera que compleixen els 5 postulats de Huntington.

Actualment, l'àlgebra de Boole s'aplica de manera generalitzada a l'àmbit del disseny electrònic. Claude Shannon va 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 una funció s'aplica aquesta àlgebra per poder desenvolupar una implementació de la funció.

George Boole (Lincoln, 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. 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 per George Boole al seu llibre The Mathematical Analysis of Logic de 1847. Amb ell s'inicia el desenvolupament de l'anomenada àlgebra de la lògica.^[4] El 1849 va ser nomenat professor de matemàtiques del Queen's College, a Cork, on va romandre la resta de la seva vida.

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

• ${\displaystyle \odot }$ és distributiva respecte a ${\displaystyle \oplus }$:

${\displaystyle a\odot (b\oplus c)=(a\odot b)\oplus (a\odot c)}$

• ${\displaystyle \oplus }$ és distributiva respecte a ${\displaystyle \odot }$

${\displaystyle a\oplus (b\odot c)=(a\oplus b)\odot (a\oplus c)}$

Primer postulat: les operacions són internes:

${\displaystyle 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ó:

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

Tercer postulat: existeix l'element invers:

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

Quart postulat: existeix la propietat commutativa:

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

Cinquè postulat: existeix la propietat distributiva:

${\displaystyle 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}$

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

A partir de la taula, podem calcular els termes mínims, que són els productes de ${\displaystyle 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:

${\displaystyle m_{1}={\overline {a}}\cdot {\overline {b}}\cdot c}$

${\displaystyle m_{3}={\overline {a}}\cdot b\cdot c}$

${\displaystyle 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:

${\displaystyle 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):

${\displaystyle 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):

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

I el segon postulat (element invers):

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

I altra vegada el cinquè postulat (propietat distributiva):

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

I finalment la llei d'absorció:^[6]

${\displaystyle 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 ${\displaystyle a}$ o ${\displaystyle b}$ són falsos i ${\displaystyle c}$ és cert. Alternativament, podem calcular els termes màxims (sumes de ${\displaystyle 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:

${\displaystyle 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}})=}$

${\displaystyle =(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}})=}$

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

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

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

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

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

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

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

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

Lleis d'absorció:

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

${\displaystyle 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:

${\displaystyle a+a=a\quad a\cdot a=a\qquad \forall a\in B}$

Llei d'involució:

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

Llei de De Morgan:

${\displaystyle {\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:

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

A Lògica binària se sol emprar la notació ${\displaystyle (\{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 les lleis de De Morgan es representen així:

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

${\displaystyle {\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 lletres majúscules o minúscules, i poden prendre els valors {0, 1}.

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

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

${\displaystyle {\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ó ${\displaystyle \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í:

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

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

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

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

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

${\displaystyle \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í:

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

${\displaystyle {(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'utilitzen apò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:

${\displaystyle (a+b)'=a'b'\,}$

${\displaystyle (ab)'=a'+b'\,}$

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

${\displaystyle (A+B)'=A'B'\,}$

${\displaystyle (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ó.

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.

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èrie de temes, aparentment tan diferents, té dues coses en comú, la lògica binària basada en els zeros i els uns i 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 ${\displaystyle {\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:

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

On:

${\displaystyle \varnothing =0}$

${\displaystyle U=1\;}$

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

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

${\displaystyle {\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 element a de {0,1}, li assigna un b de {0, 1}.

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

Per a tot element a a {0,1}, es compleix que existeix un únic b a {0,1}, tal que b és la negació de a. Com es veu a la taula. Per a tot element a a {0,1}, es compleix que existeix un únic b a {0, 1}, tal que b és la negació de a. Com es veu a la taula.

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

${\displaystyle {\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}}}$

${\displaystyle {\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) de B per B, li assigna un c de B.

${\displaystyle \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) a B per B, es compleix que existeix un únic c a B, tal que c és el resultat de sumar a amb b.

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

${\displaystyle {\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}}}$

${\displaystyle {\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) de B per B, li assigna un c de B.

${\displaystyle \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) a B per B, es compleix que existeix un únic c a B, tal que c és el resultat del producte a i b. Com es pot veure a la taula.

Així ${\displaystyle (\{0,1\},{\bar {}},+,\cdot )}$ és un àlgebra de Boole al complir els següents axiomes:

• 1a: La llei associativa de la suma:

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

• 1b: La llei associativa del producte:

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

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

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

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

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

• 3a: La llei commutativa de la suma:

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

• 3b: La llei commutativa del producte:

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

• 4a: Llei distributiva de la suma respecte al producte:

${\displaystyle \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:

${\displaystyle \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:

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

• 5b: Existeix element complementari per al producte:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 9: Llei d'involució:

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

• 10: Llei del complement:

${\displaystyle {\bar {1}}=0}$

${\displaystyle {\bar {0}}=1}$

• 11: Lleis de De Morgan:

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

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

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

${\displaystyle \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}$

llavors a es menor o igual que b. Donats els valors binaris 0 y 1, podem veure:

1. ${\displaystyle 0+1=1}$
2. ${\displaystyle 0\cdot 1=0}$
3. ${\displaystyle {\bar {0}}+1=1}$
4. ${\displaystyle 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 que 0 antecedeix a 1 i ho denotem:

${\displaystyle 0\leq 1}$

Si a més sabem que 0 y 1 son valors diferents:

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

El valor binari 0 és menor que el valor binari 1.

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”.

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).

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