Álxebra de Boole

Na Galipedia, a Wikipedia en galego.
Para unha introducción básica ás operacións Booleanas, diagramas de Venn, táboas da verdade e aplicacións Booleanas, véxase tamén lóxica Booleana.
Para información en canto ó uso dos números binarios nos sistemas informáticos, véxase o artigo aritmética binaria.


En matemáticas, unha Álxebra Booleana é unha estrutura alxébrica que captura a esencia das operacións lóxicas AND, OR e NOT así como o conxunto de operacións unión, intersección e complemento.


A Álxebra de Boole debe o seu nome ó filósofo e matemático George Boole. Boole desenvolveu en 1847, cando tiña 32 anos de idade, unha teoría matemática distinta á que se coñecía ata ese intre coa publicación de “A análise matamática do pensamento”, o cal lle valeu unha cátedra no Queen’s College de Dublín. Boole concibe o espazo como algo biestábel (dous estados), estes estados son opostos e poden representar a realidade. Por exemplo enténdense espazos como día-noite, certo-falso, 0-1 ou corte-saturación (modos de traballo extremo nos que se pode facer traballar a un transistor). O libro máis importante de Boole publicouse en 1854: “As leis do pensamento”

Como anécdota cabe salientar que xa no ano 2000 a.C apareceu na China o “I-Ching” ou “Libro das mutacións” con bases matemáticas moi parecidas ás establecidas por George Boole. Hoxe en día a Álxebra de Boole atópase na maioría das aplicacións de deseño electrónico, trátase dunha boa ferramenta matemática que permite implementar circuitos lóxicos e comprender o seu funcionamento, así fórmanse e compréndense as distintas operacións lóxicas que se poden realizar.

Aplicouse por primeira vez en circuitos de conmutación eléctrica biestables por Claude Shannon. Shannon demostrou en 1938, como as operacións booleanas elementais, podíanse representar mediante circuitos conmutadores eléctricos, e como a combinación de circuitos podía representar operacións aritméticas e lóxicas complexas. Ademais demostrou que a álxebra de Boole podíase empregar para simplificar circuitos conmutadores. A ligazón entre lóxica e electrónica ficou así establecida.


Definición formal[editar | editar a fonte]

Unha Álxebra de Boole é un conxunto “A”, provisto de dúas operacións binarias \land (AND lóxica), \lor (OR lóxica), unha operación

unaria ¬ / ~ (NOT lóxica) e dous elementos “0” (Falso) e “1” (Verdadeiro), de xeito que para todos os elementos “a”, “b” e “c” do conxunto “A”, se cumpren os seguintes axiomas:

 a \lor (b \lor c) = (a \lor b) \lor c  a \land (b \land c) = (a \land b) \land c asociatividade
 a \lor b = b \lor a  a \land  b = b \land a conmutatividade
 a  \lor (a \land b) = a  a  \land (a \lor b) = a absorción
 a \lor  (b \land c) = (a \lor b) \land (a \lor c)  a \land  (b \lor c) = (a \land b) \lor (a \land c) distributividade
 a \lor  \lnot a = 1  a \land \lnot a = 0 complementación

A partir de estes axiomas, pódese demostrar que calquera operación booleana onde interveñan o elemento máis pequeño “0”, o elemento de maior valor “1”, e o complemento ¬a de calquera elemento “a” xenera un resultado único pertencente á mesma gramática de Boole. Para todo “a” e “b” do conxunto “A”, cúmprense as seguintes identidades:

 a \lor a = a  a \land a = a Idempotencia
 a \lor 0 = a  a \land 1 = a Elemento neutro
 a \lor 1 = 1  a \land 0 = 0
 \lnot 0 = 1  \lnot 1 = 0 0 é 1 son complementarios
 \lnot (a \lor b) = \lnot a  \land \lnot b  \lnot (a \land b) = \lnot a  \lor \lnot b Leis de Morgan
 \lnot \lnot a = a Involución

Exemplos[editar | editar a fonte]

  • A álxebra de Boole simplificada ten só dous elementos, 0 e 1, e está definida polas regras:


\lor  0  1    \land  0  1
      ----         ----
  0 | 0  1     0 | 0  0
  1 | 1  1     1 | 0  1


  • Ten aplicacións na lóxica,onde 0 interprétase como “falso”,1 como verdadeiro”, \land como “e”, \lor como "ou", e ¬ é "non". As expesións que involucran variabeis e operadores booleanos representan proposicións, e pódese demostrar que dúas expresión son equivalentes usando os axiomas citados anteriormente se e só se as correspondentes proposicións son loxicamente equivalentes.
  • Os dous elementos da álxebra de Boole son empregados para o deseño de circuitos na enxeñaría eléctrica; 0 e 1 representan os dous diferentes estados dun bit nun circuito dixital, normalmente alta e baixa voltaxe. Os circuitos son descritos por expresións contendo variabeis, e dúas expresión son iguais para todos os valores das variabeis se e só se os correspondentes circuitos teñen o mesmo comportamento da relación entrada-saída. Ademais, cada posíbel combinación de entrada-saída pode ser modelada pola súa conveniente expresión Booleana.
  • A álxebra de Boole binaria tamén é importante na teoía xeral das álxebras de Boole, porque unha ecuación que implica varias variábeis é certa en todas as álxebras booleanas se e só se é certa nunha álxebra booleana de dous elemento (o cal sempre pode ser verificado empregando o algoritmo trivial de forza bruta). Isto pode aplicarse para demostras que as seguintes leis (Teoremas do consenso) son válidos en todas as álxebras booleanas:
    • (ab) ∧ (¬ac) ∧ (bc) ≡ (ab) ∧ (¬ac)
    • (ab) ∨ (¬ac) ∨ (bc) ≡ (ab) ∨ (¬ac)
  • O conxunto formado por todos os subconxuntos de calquera conxunto dado “S” forma unha álxebra de Boole coas dúas operacións ∨ = ∪ (unión) e ∧ = ∩ (intersección). O elemento mínimo “0” é o conxunto baleiro e o elemento máximo “1” é o propio conxunto S.
  • O conxunto formado por todos os subconxuntos de “S” que son finitos ou co infinitos é un álxebra de Boole.
  • Para todo número natural “n”, o conxunto de todos os seus divisores positivos forma unha retícula distributiva se definimos ab como “a” divide a “b”. Esta retícula é unha álxebra de Boole se e só se “n” é ceibo de cadrados. O elemento mínimo “0” desta álxebra é o número natural 1; o elemento máximo “1” desta álxebra booleana é o número natural “n”.
  • Outros exemplos de álxebras de Boole xurden dos espazos topolóxicos: se “X” é un espazo topolóxico, entón a colección de todos os subespazos de “X” que son tanto abertos como pechados forman unha álxebra booleana coas operacións \lor = unión y \land = intersección.
  • Se “R” é un anel e definimos o conxunto de “idempotentes centrais” como:

A = { y en R : y² =y e yx= xy para todo y en R }

entón o conxunto “A” convírtese nunha álxebra booleana coas operacións ( y \lor f = y + fyf) e

(y \land f = yf).

Véxase tamén[editar | editar a fonte]

Ligazóns externas[editar | editar a fonte]