Álxebra de Boole

Para unha introdució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. Cando se usa no ámbito dos conxuntos hai que ter en conta as operacións de intersección, unión e complemento.

A partir dos séculos XIX e XX ten un uso masivo na informática e na electrónica dixital que deu lugar a unha representación con diagramas de circuitos.

Representación física AND.
Representación física OR.

A Álxebra de Boole debe o seu nome ó filósofo e matemático George Boole.^[1] 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 matemá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 construír circuítos 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 circuítos de conmutación eléctrica biestables por Claude Shannon. Shannon demostrou en 1938, como as operacións booleanas elementais, podíanse representar mediante circuítos conmutadores eléctricos, e como a combinación de circuítos podía representar operacións aritméticas e lóxicas complexas. Ademais demostrou que a álxebra de Boole podíase empregar para simplificar circuítos 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 destes axiomas, pódese demostrar que calquera operación booleana onde interveñan o elemento máis pequeno “0”, o elemento de maior valor “1”, e o complemento ¬a de calquera elemento “a” xera 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$	Elemento neutro
$\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:

$\land$	$0$	$1$
$0$	$0$	$0$
$1$	$0$	$1$

$\lor$	$0$	$1$
$0$	$0$	$1$
$1$	$1$	$1$

$a$	$0$	$1$
$\neg a$	$1$	$0$

Estas regras poden expresarse cunha táboa de verdade como as seguintes:

$x$	$y$	$x\land y$	$x\lor y$
0	0	0	0
1	0	0	1
0	1	0	1
1	1	1	1

$x$	$\neg x$
0	1
1	0

Un mapa de Karnaugh é un método para simplificar expresións de álxebra booleana.

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 circuítos na enxeñaría eléctrica; 0 e 1 representan os dous diferentes estados dun bit nun circuíto dixital, normalmente alta e baixa voltaxe. Os circuítos 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 circuítos 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.

En informática son a base das instruccións (IF-ELSE) coas súas condicións AND e OR que devolven un resultado true (1) ou false (0).

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 elementos (o cal sempre pode ser verificado empregando o algoritmo trivial de forza bruta). Isto pode aplicarse para demostrar que as seguintes leis (Teoremas do consenso) son válidos en todas as álxebras booleanas:

(a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
(a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)

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 a ≤b 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 xorden 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 + f − yf) e (y

\land

f = yf).

Representación con diagramas[editar | editar a fonte]

Diagramas de Venn[editar | editar a fonte]

Un diagrama de Venn^[2] pódese usar como representación dunha operación booleana usando rexións superpostas sombreadas. Hai unha rexión para cada variable. O interior e o exterior da rexión x corresponden respectivamente aos valores 1 (verdadeiro) e 0 (falso) para a variable x. O sombreado indica o valor da operación para cada combinación de rexións, sendo escuro 1 e claro 0 (algúns autores usan a convención contraria).

Os tres diagramas de Venn da figura seguinte representan respectivamente a conxunción $x \land y$ , a disxunción $x \lor y$ e o complemento ¬x.

Figura 2. Diagramas de Venn para conxunción, disxunción e complemento

No primeiro diagrama, para a conxunción, a rexión dentro de ambos os círculos está sombreada para indicar que $x \land y$ é 1 cando ambas as variables son 1. As outras rexións non sombrean para indicar que $x \land y$ é 0 para as outras tres combinacións.

O segundo diagrama representa a disxunción $x \lor y$ sombreando aquelas rexións que se atopan dentro e ambos os dous círculos.

O terceiro diagrama representa o complemento ¬x sombreando a rexión non dentro do círculo.

Dependendo de como se exprese pode ser verbalmente contraituitivo. Se lemos $x\land y$ como "X e Y" pode parecer que se corresponde cunha unión. Un xeito de expresalo para que se vexa que é a intersección sería "Tense que cumprir X e tense que cumprir Y".

Portas lóxicas dixitais[editar | editar a fonte]

A lóxica dixital é a aplicación da álxebra de Boole de 0 e 1 ao hardware electrónico que consiste en portas lóxicas conectadas para formar un diagrama de circuíto. Cada porta implementa unha operación booleana, e represéntase esquemáticamente cunha forma que indica a operación. As formas asociadas ás portas para a conxunción (portas AND), a disxunción (portas OR) e o complemento (inversores) son as seguintes

De esquerda a dereita: portas AND, OR, e NOT.

^[3]

O complemento realízase cunha porta inversora. O triángulo denota a operación que simplemente copia a entrada na saída; o círculo pequeno da saída indica a inversión real que complementa a entrada. A convención de poñer un círculo deste tipo en calquera porto significa que o sinal que pasa por este porto se complementa ao pasar, xa sexa un porto de entrada ou de saída.

O principio de dualidade, ou as leis de De Morgan, pódense entender como que se se complemetan os tres portos dunha porta AND convérteo nunha porta OU e viceversa, como se mostra en Figura 4 a continuación. Non obstante, o complemento dos dous portos dun inversor deixa o funcionamento sen cambios (non representado na figura).

Outra porta importante é XOR (OR exclusivo) = X ⊕ Y. Indica verdade cando é verdade X ou é verdade Y máis non ambos os dous.


Símbolo ANSI XOR

Pode verse como unha das seguintes expresións alxébricas, $A\cdot {\overline {B}}+{\overline {A}}\cdot B$ ou $(A+B)\cdot ({\overline {A}}+{\overline {B}})$ .