En una entrada anterior publicada hace más de 4 años, en primer lugar se explicaba cómo simplificar expresiones booleanas en nuestro código a partir de las propiedades fundamentales o axiomas del álgebra de Boole y de sus propiedades derivadas, así como a partir del complemento de una función booleana. Finalmente, se añadía una nota en la que se comentaba la similitud entre el álgebra de Boole, la lógica de primer orden y la teoría básica de conjuntos (la formulada por Georg Cantor). Con el presente artículo se pretender dar orden y exponer correctamente el porqué de está relación que se dejó caer en forma de una breve nota.

En su breve obra titulada «El análisis matemático de la lógica» publicada en 1847, el matemático británico autodidacta George Boole tuvo la originalidad de utilizar las técnicas algebraicas para tratar expresiones de la lógica. En su sistema se definen unas operaciones sobre unas variables abstractas que tienen que cumplir unas propiedades, de forma similar a como en el álgebra de las fracciones se definen las operaciones de suma, resta, multiplicación y división y deben cumplir unas determinadas propiedades. Con esta obra puso fin a la lógica aristotélica e inició la lógica formal matemática contemporánea.

No obstante, no fue hasta 1860 que en los trabajos del también británico economista y lógico William Jevons y el filósofo, lógico y matemático norteamericano Charles Sanders Peirce apareció el concepto más general de álgebra de Boole. Un álgebra de Boole es una estructura algebraica, es decir, consta de un conjunto no vacío de elementos y un conjunto no vacío de operaciones sobre dicho conjunto. Además, una estructura algebraica es axiomática, es decir, debe cumplir una serie de propiedades.

William Jevons, principalmente conocido por la paradoja de Jevons.

En el caso concreto de la estructura de álgebra de Boole, ésta está formada por un conjunto B con al menos dos elementos diferentes (primero y último), designados con los símbolos 0 y 1. En cada álgebra de Boole estos elementos pueden diferir según los elementos que constituyen el conjunto B. Las operaciones son tres, una unaria denominada complemento que se representa con ¬ o ~ y dos binarias: supremo (representada por v o +) e ínfimo (^ o ·). Para elementos cualesquiera x, y, z ∈ B deben cumplirse estas propiedades o axiomas:

• Conmutativa:
  • x + y = y + x
  • x · y = y · x
• Distributiva:
  • x · (y + z) = (x · y) + (x · z)
  • x + (y · z) = (x + y) · (x + z)
• Identidad. El 0 es el elemento neutro del supremo y el 1 es el elemento neutro del ínfimo:
  • x + 0 = x
  • x · 1 = x
• Complementación. ¬x es el complementario de x:
  • x + (¬x) = 1
  • x · (¬x) = 0
• Asociativa (aunque esta puede deducirse de las propiedades anteriores y de otras obtenidas como consecuencia de ellas):
  • x + (y + z) = y + (x + z)
  • x · (y · z) = (x · y) · z

A partir de estas propiedades fundamentales o axiomas, toda estructura de álgebra de Boole cumple estas otras propiedades o teoremas:

• Idempotencia:
  • x + x = x
  • x · x = x
• Doble negación:
  • ¬¬x = x
• Absorción:
  • x + (x · y) = x
  • x · (x + y) = x
• Dominancia:
  • x + 1 = 1
  • x · 0 = 0
• Leyes de De Morgan:
  • ¬(x + y) = (¬x) · (¬y)
  • ¬(x · y) = (¬x) + (¬y)

Ejemplos de estructuras de álgebras de Boole

A continuación, veremos porqué la teoría básica de conjuntos constituye una álgebra de Boole. Si U es un conjunto no vacío llamado dominio o universo, C es el conjunto de todos los conjuntos que se pueden definir como elementos de U, con las operaciones binarias intersección (ínfimo, representada por ∩) y unión (supremo, representada por υ), la operación unaria «complemento de un conjunto» (representada por ¬), e interpretando 0 como el conjunto vacío ∅ y 1 como el conjunto U, (C ,∩ , ∪, ¬, ∅, U) es el álgebra de Boole de los conjuntos de U. Nótese que no está limitada a 2 elementos sino que tiene tantos como C tenga. Si A, B y C representan conjuntos cualesquiera, se cumplen los axiomas o propiedades fundamentales:

• Conmutativa:
  • A ∩ B = B ∩ A
  • A ∪ B = B ∪ A
• Distributiva:
  • (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
  • (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
• Identidad:
  • A ∪ ∅ = A
  • A ∩ U = A
• Complementación:
  • A υ ¬A = U
  • A ∩ ¬A = ∅

En consecuencia, se cumplen también la idempotencia, doble negación, absorción, dominancia y las leyes de De Morgan. A modo de ejemplo veamos estas últimas:

• ¬(A ∩ B) = ¬A υ ¬B
• ¬(A υ B) = ¬A ∩ ¬B

Charles Sanders Peirce

Obviamente, la lógica booleana es una álgebra de Boole; más formalmente: ({0, 1}, AND, OR, NOT) es una álgebra de Boole.

La lógica de predicados también es una álgebra de Boole, aunque incluya los cuantificadores ∀ y ∃. Sus conectivas básicas (¬, ^, v) coinciden con las tres operaciones de una álgebra de Boole: La conjunción ^ es el ínfimo, la disyunción v es el supremo y la negación (¬) el complemento. En cuanto a las conectivas condicional (⇒) y bicondicional (⇔), resulta que estas se pueden expresar con las conectivas básicas:

• A ⇒ B puede expresarse como ¬A v B
• A ⇔ B puede expresase como (¬A v B) ^ (¬B v A)

Como la lógica de predicados forma una estructura de álgebra de Boole, también lo es la lógica de enunciados, pues no deja de ser un subconjunto de la de predicados, por ser el predicado una aplicación definida en un dominio que adquiere valores en el conjunto de enunciados, es decir, un predicado es un enunciado parametrizado (con variables). Por ejemplo, si C(x) es una formalización de «x es un cocinero», entonces se crea un enunciado reemplazando la variable x por algún elemento de su dominio. Si el dominio de x es el conjunto de las personas, entonces C(Arguiñano) es un enunciado, concretamente «Arguiñano es un cocinero».

El conjunto de los divisores positivos de 70, D₇₀ = {1, 2, 5, 7, 10, 14, 35, 70}, donde se define las operaciones binarias ínfimo (representada por ^) como el máximo común divisor, el supremo (v) como el mínimo común múltiplo y el complemento (¬) como ¬x = 70/x. En este caso el primer y último elemento son el 1 y el 70, respectivamente. Algunos ejemplos de las operaciones:

• 5 ^ 14 = 1
• 5 v 14 = 70
• ¬5 = 14

No todo los conjuntos de los divisores positivos de n forman una álgebra de Boole. Por ejemplo, no es el caso de D₈ = {1, 2, 4, 8}, pues ni para el elemento 4 ni para el 2 se cumple el axioma de la complementación. En efecto, en el caso concreto del 4 sabemos que su complemento es 2, por lo que:

• 4 v 2 = 4
• 4 ^ 2 = 2

Como el resultado no es 8 y 1, sino 4 y 2, no se cumple el axioma y no forman una álgebra de Boole. En cambio, sí se cumple para D₇₀ :

• 70 v 1 = 70
• 70 ^ 1 = 1

En general, si el cuadrado de alguno de los elementos de D_n es un divisor de n, D_n no tiene estructura de álgebra de Boole.

En definitiva, la lógica booleana que se emplea tanto en el diseño de circuitos como en la programación, pertenece a una estructura algebraica más abstracta: la estructura de álgebra de Boole. Asimismo, a esta estructura pertenecen también la teoría de conjuntos, la lógica de enunciados y la de predicados, por lo que las similitudes entre todas ellas no es mero casual. Además, hay muchos otros ejemplos en ámbito de las matemáticas y de la física. Como todas ellas pertenecen a la misma estructura, tienen los mismos axiomas y una consecuencia importante de esto es que a todas aplicarán también las propiedades derivadas de dichos axiomas.