3.1 Álgebra de Boole
Se denomina así en honor a George Boole (1815-1864), matemático inglés autodidacta, que fue el primero en definirla como parte de un sistema lógico, inicialmente en un pequeño folleto: The Mathematical Analysis of Logic, publicado en 1847, en respuesta a una controversia en curso entre Augustus De Morgan y Sir William Hamilton. El álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. Más tarde como un libro más importante: The Laws of Thought, publicado en 1854.
En la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito del diseño electrónico. Claude Shannon fue el primero en aplicarla en el diseño de circuitos de conmutación eléctrica biestables, en 1948. Esta lógica se puede aplicar a dos campos:
Al análisis, porque es una forma concreta de describir como funcionan los circuitos.
Al diseño, ya que teniendo una función lógica aplicamos dicho álgebra para poder desarrollar una implementación de la función.
El uso del álgebra de Boole en la Automática se debe a que buena parte de los automatismos responden a la lógica binaria. Las variables binarias de entrada son leídas y producen variaciones en las señales binarias de salidas.
3.1.1 Definiciones
El álgebra de Boole está formada por un conjunto de variables booleanas, \(x \in \left \{ 0,1 \right \}\). Es decir variables que sólo pueden tomar dos valores: 0 ó 1, verdadero o falso, abierto o cerrado, encendido o apagado, etc.
Un literal l es una variable o su negada. Existen dos tipos: literales con signo positivo cuando representan el valor ‘1’ de la variable (\(l = x\)), y con signo negativo cuando representa el valor ‘0’ (\(l = \overline{x}\)).
Una cláusula (o término C) está formada por un conjunto de literales enlazados mediante conectivas lógicas.
Una fórmula lógica \(\phi\) está formada por conjuntos de cláusulas enlazadas mediante conectivas lógicas. Matemáticamente, toda fórmula lógica \(\phi\) de n variables puede verse también como una función multivariable, esto es \(\phi : \{0,1\}^n \rightarrow \{0,1\}\). En este texto emplearemos indistintamente los términos de función y fórmula.
Una interpretación de una fórmula lógica \(\phi\) es el valor lógico de la fórmula cuando se le asignan valores de verdad (TRUE / FALSE) a sus variables. En consecuencia, existirán tantas interpretaciones como combinaciones de asignaciones posibles.
Se dice que una fórmula lógica es satisfacible cuando existe al menos una interpretación que la hace verdadera.
Una tabla de verdad, o tabla de valores de verdades, es una tabla que muestra el valor de verdad de una cláusula o fórmula lógica, para cada combinación de verdad que se pueda asignar a sus literales23.
3.1.2 Operaciones básicas
El álgebra de Boole está definido por 3 operaciones básicas: complemento, suma (OR) y producto (AND).
El complemento es el negado: \(y = \overline{a}\). Viene dado por la tabla de verdad 3.1.
| a | y |
|---|---|
| 0 | 1 |
| 1 | 0 |
La operación suma u OR se representa \(y = a + b\) y viene dada por la tabla de verdad 3.2.
| a | b | y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
La operación producto u AND se representa \(y = a · b\) y viene dada por la tabla de verdad 3.3.
| a | b | y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
3.1.3 Propiedades
Axiomas básicos
1: La ley asociativa:
\[{\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;(a + b) + c= a+ (b+ c)}\]
\[{\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;(a· b)· c=a · (b· c)}\]
2: Existencia del elemento neutro:
\[{\displaystyle \forall a\in {\mathfrak {B}}:\;a+ 0 =a}\]
\[{\displaystyle \forall a\in {\mathfrak {B}}:\;a· 1=a}\]
3: La ley conmutativa:
\[{\displaystyle \forall a,b\in {\mathfrak {B}}:\;a+ b=b+ a}\]
\[{\displaystyle \forall a,b\in {\mathfrak {B}}:\;a· b=b· a}\]
4: Ley distributiva:
\[\forall a,b,c\in {\mathfrak {B}}:\;a+ (b· c)=(a+ b)· (a+ c)\]
\[\forall a,b,c\in {\mathfrak {B}}:\;a· (b+ c)=(a· b)+ (a· c)\]
5: Existencia del elemento complementario:
\[\forall a \in {\mathfrak {B}};\;\exists \overline{a} \in {\mathfrak {B}}:\;a + \overline{a}=1\]
\[\forall a\in {\mathfrak {B}};\;\exists \overline{a} \in { \mathfrak {B}}:\;a· \overline{a}=0\]
AND
Ley de idempotencia para el producto: \[\forall a\in {\mathfrak {B}}:\;a· a=a\]
Ley de absorción para el producto: \[\forall a\in {\mathfrak {B}}:\;a· 0 =0\]
Ley de identidad para el producto: \[\forall a\in {\mathfrak {B}}:\;a· 1=a\]
OR
Ley de idempotencia para la suma: \[\forall a\in {\mathfrak {B}}:\;a+ a=a\]
Ley de absorción para la suma: \[\forall a\in {\mathfrak {B}}:\;a+ 1=1\]
Ley de identidad para la suma: \[\forall a\in {\mathfrak {B}}:\;a+ 0 =a\]
NOT
Ley de involución: \[\forall a\in {\mathfrak {B}}:\;\overline{\overline{a}}=a\]
Leyes de De Morgan
\[\forall a,b\in {\mathfrak {B}}:\;\overline{a + b}=\overline{a} · \overline{b}\]
\[\forall a,b\in {\mathfrak {B}}:\;\overline{a · b}=\overline{a} + \overline{b}\]
3.1.4 Conectivas derivadas
NOR
Es la negada de la función “OR”:
\[y=\overline{a+b}\]
| a | b | y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
NAND
Es la negada de la función “AND”:
\[y=\overline{a·b}\]
| a | b | y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR
Es la función OR excluyente: o uno u otro, pero no los dos. Se puede utilizar para detectar señales que son distintas.
\[y=a \oplus b = a ·\overline{b} + \overline{a} · b\]
| a | b | y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Ejercicio.- Demostrar la función XOR a partir de la tabla de verdad
XNOR
Es la negada de la función “XOR”. Se puede utilizar para detectar señales que son iguales:
\[y = \overline{a \oplus b} = a · b + \overline{a} · \overline{b}\]
| a | b | y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Ejercicio.- Demostrar la función XNOR a partir de la de XOR
Fue desarrollada por Charles Sanders Peirce por los años 1880, pero el formato más popular es el que introdujo Ludwig Wittgenstein en su Tractatus logico-philosophicus, publicado en 1921 (Wikipedia).↩︎