Tanto la teoría de conjuntos como la lógica de enunciados tienen propiedades similares. Tales propiedades se utilizan para definir una estructura matemática denominada álgebra de Boole, en honor al matemático George Boole (1813 1864).
Definición de álgebra de Boole
Sea B un conjunto en el cual se definen dos operaciones binarias, + y *, y una operación unitaria denotada; sean 0 y 1 dos elementos diferentes de B. Entonces la séxtupla: 〈B, +, *, 0, 1〉 se denomina álgebra de Boole si se cumplen los siguientes axiomas para cualesquiera elementos a, b, c del conjunto B:
[B1] Conmutatividad:
(1a) a + b = b + a (1b) a * b = b * a
[B2] Distributividad:
(2a) a + (b * c) = (a + b) * (a + c) (2b) a * (b + c) = (a * b) + (a * c)
[B3] Identidad:
(3a) a + 0 = a (3b) a * 1 = a
[B4] Complemento:
(4a) a + a = 1 (4b) a * a = 0
Terminología y convenciones
Las operaciones + y * se denominan suma y producto, respectivamente.
La operación a se denomina complemento de a.
El elemento 0 se denomina elemento cero (neutro respecto de la suma).
El elemento 1 se denomina elemento unidad (neutro respecto del producto).
Por convención, omitimos el símbolo *, usándose en su lugar la yuxtaposición; de este modo, (2a) y (2b) se escriben:
(2a) a + bc = (a + b) (a + c) (2b) a (b + c) = ab + ac
a + b * c significa a + (b * c) y no (a + b) * c
a * b significa a * ( b ) y no (a *b)
En un álgebra de Boole B, el dual de cualquier enunciado es el enunciado obtenido de intercambiar las operaciones + y *, e intercambiar los elementos neutros 0 y 1 en el enunciado original. Por ejemplo:
El dual de (1 + a) * (b + 0) = b es (0 * a) + (b * 1) = b
Con esta definición de dualidad puede observarse que, en la definición de álgebra de Boole, los axiomas del grupo (1) son duales de los axiomas del grupo (2) y viceversa. En otras palabras, el dual de cualquier axioma de B también es un axioma. En consecuencia, se cumple el siguiente teorema:
Teorema 1.1 (Principio de dualidad): En un álgebra de Boole, el dual de cualquier teorema es también un teorema.
Esto significa que, si cualquier teorema es una consecuencia de los axiomas de un
álgebra de Boole, entonces el dual también es una consecuencia de estos
axiomas ya que se puede probar usando el dual en cada paso de la demostración original.
Teoremas básicos
Utilizando los axiomas de la definición de un álgebra de Boole, pueden demostrarse los siguientes teoremas:
Teorema 1.2: Sean a, b, c elementos cualesquiera de un álgebra de Boole B, se cumple:
(i) Idempotencia:
(5a) a + a = a (5b) a * a = a
(ii) Acotamiento:
(6a) a + 1 = 1 (6b) a * 0 = 0
(iii) Absorción:
(7a) a + (a * b) = a (7b) a * (a + b) = a
(iv) Asociatividad:
(8a) (a + b) + c = a + (b + c) (8b) (a * b) * c = a * (b * c)
Teorema 1.3: Sea a un elemento cualquiera de un álgebra de Boole B, se cumple:
(i) Unicidad del complemento:
Si a + x = 1 y a * x = 0, entonces x = a
(ii) Involución:
a = a
(iii) (9a) 0 = 1 (9b) 1 = 0
Teorema 1.4: Leyes de De Morgan
(10a) a + b = a *b (10b) a *b = a + b
Es importante insistir que el álgebra de Boole es la estructura algebraica de la lógica de enunciados. En efecto, si se reemplazan las variables a, b, c, … por variables proposicionales, la suma y el producto por la disyunción y la conjunción respectivamente, el complemento por la negación, la igualdad por el bicondicional, y 1 y 0 por V y F respectivamente, todos los axiomas y teoremas del álgebra de Boole se transforman en axiomas o teoremas de la lógica de enunciados. Por ejemplo:
(2b) a * (b + c) = (a * b) + (a * c)
(5a) a + a = a
(7a) a + (a * b) = a
(10b) a *b = a + b
Forma de suma de productos
Considérese un conjunto de variables a, b, c, d,….
Una expresión booleana E en estas variables es o una variable o una expresión construida con estas variables y usando las operaciones booleanas +, * o . Por ejemplo, las siguientes son expresiones booleanas:
(a + bc) + (abc + ab) ((abc + b) + ac)
Un literal es una variable o una variable complementada. Por ejemplo, a, a , b, b son literales.
Un producto fundamental es un literal o un producto de dos o más literales en el cual no hay dos literales con la misma variable. Por ejemplo, ac, abc, a, b, bc, abc son productos fundamentales. En cambio, abac y abcb no son productos fundamentales: el primero contiene a y a, mientras que el segundo contiene b dos veces.
ac + abc + abc
Pero la siguiente expresión no está en forma de suma de productos:
ac + aba + abc
ya que el segundo término no es un producto fundamental.
Tablas de verdad
Concretamente, a la izquierda de la tabla hay una lista con todas las combinaciones de valores posibles de las variables de entrada y, a la derecha, el valor de la función para cada una de las combinaciones. Por ejemplo, las tablas que habíamos visto en la figura 3 eran, de hecho, las tablas de verdad de las funciones NOT, AND y OR.
Si una función tiene n variables de entrada, y dado que una variable puede tomar sólo dos valores, 0 ó 1, las entradas pueden adoptar 2n combinaciones de valores diferentes. Por tanto, su tabla de verdad tendrá a la izquierda n columnas (una para cada variable) y 2n filas (una para cada combinación posible). A la derecha habrá una columna con los valores de la función.
Las filas se escriben siempre en orden lexicográfico, es decir, si interpretamos las diferentes combinaciones como números naturales, escribiremos primero la combinación correspondiente al 0 (formada sólo por ceros), después la correspondiente al 1 y así sucesivamente, en orden creciente hasta la correspondiente al 2n – 1 (formada sólo por unos).
La figura 4 muestra la estructura de las tablas de verdad para funciones de una, dos y tres variables de entrada.
Una tabla de verdad expresa una función lógica especificando el valor que tiene la función para cada posible combinación de valores de las variables de entrada.
